CareerCup

Would this be similar to a BigInteger addition in Java.

public class bigInteger {

    public static BigInteger add(BigInteger one, BigInteger two){

        byte big [];
        byte small[];


        if(one.toByteArray().length > two.toByteArray().length){
            big = one.toByteArray();
            small = two.toByteArray();
        }
        else if(one.toByteArray().length < two.toByteArray().length){
            small = one.toByteArray();
            big = two.toByteArray();

        }
        else {
            big = one.toByteArray();
            small = two.toByteArray();
        }
        byte result[] = new byte[small.length+big.length];

        int carry=0;
        for(int i=0;i<big.length;i++){
            int digit2 = i>=small.length?0:small[i];
            int sum = big[i]+digit2+carry;

            carry = (byte)( sum > 9?1:0);

            result[i] = (byte)(sum % 10);

        }
        result[big.length]= (byte)carry;

        return new BigInteger(result);
    }
}

Steps:
1) Create a minute array of 1440
2) When a meeting is requested to be scheduled (1.30pm to 2pm), find the minutes
and update the n-1 minutes of the meeting with 1 in the minute array
3) The end of the meeting's minute needs to be -1 to avoid a clash with any meeting starting
when this ends; 2pm.

Would appreciate feedback on the following design:

public class Calendar {

    static int time [] = new int[1440];

    public static void main(String args[]){

        String s[] =   {"15:30","1:30","1:15","15:00"};
        String e[] = {"18:35","13:28","1:30","15:29"};

        System.out.println(scheduler(s, e));
    }

    public static int calculateMinute(int hour, int minute){
            return hour*60+minute;
    }

    public static boolean timeClashChecker(int start, int end){
            for(int i=start;i<=end;i++){
                if(i==end){
                    time[i] =  -1;
                }
                else if(time[i]==1){
                    return false;
                }
                else if(time[i]==-1){
                    time[i]=1;
                }
                else{
                    time[i]=1;
                }
            }
        return true;
    }
    public static int parser(String time){
        String [] timeParts = time.split(":");
        int hour = Integer.parseInt(timeParts[0].trim());
        int minute = Integer.parseInt(timeParts[1].trim());

        return calculateMinute(hour,minute);
    }
    public static boolean scheduler(String start[], String end[]){

        for(int i=0;i<start.length;i++){
            int startMeeting = parser(start[i]);
            int endMeeting = parser(end[i]);
            boolean result = timeClashChecker(startMeeting,endMeeting);
            if(result == false){ //clash check
                return false;
            }
        }
        return true;

    }

}

1) Since the size of the Window is not relevant nor is the TimeStamp, this would break down to checking for the occurrence of an ip address that is more than an arbitrary k value.
2) For a stream or a static file:
a. HashMap<Ip, Frequency>
b. Increment each ip as they occur
c. Keep a counter with (value = k) and check (while inserting a value) that if it crosses K.
d. Return that IP and break.

Please let me know if my thinking is correct.

solution.Node is my packaged Node class.
Essentially a typical Treenode

public static void zigZagPrint(solution.Node root){
        if(root==null) return;

        boolean fromLeftToRight = false;
        Stack<Node> s1 = new Stack<solution.Node>();
        Stack<solution.Node> s2 = new Stack<solution.Node>();

        s1.push(root);
        while(!s1.isEmpty() || !s2.isEmpty()){
            solution.Node temp = s1.peek();
            s1.pop();
            System.out.print(temp.value+" ");
            if(fromLeftToRight){
                if(temp.right!=null) s2.push(temp.right);
                if(temp.left!=null)s2.push(temp.left);
            }
            else{
                if(temp.left!=null)s2.push(temp.left);
                if(temp.right!=null)s2.push(temp.right);
            }
            if(s1.isEmpty()){
                s1=s2;
                s2= new Stack<solution.Node>();
                fromLeftToRight=!fromLeftToRight;
            }
        }
    }

public class sumOfDigitsArray {
    public static void main(String args[]) {
        int a[] = {1,9,2,8};
        int b [] = {9,6,8,4};

        ArrayList<Integer> result = new ArrayList<Integer>();
        int k=0;
        for(int i=0;i<a.length;i++){
            int sum = a[i]+b[i];
            int digits[] = new int[2];
            if(sum>=10){
                digits=convertNumberToDigits(sum);
                result.add(digits[1]);
                result.add(digits[0]);
            }
            else
                result.add(sum);

        }
        for(int i = 0 ;i<result.size();i++){
            System.out.print(result.get(i)+",");
        }
    }

    public static int[] convertNumberToDigits(int x){
        int result[] = new int[2];
        int temp = x;
        result[0]=x%10;
        x=x/10;
        result[1]=x%10;
        return result;

    }

Implement the square root method. Don't use the methods. I did one variation of the method. I would like to see if there is another better way to do it.

Use a deque (double-ended queue)
First insert the elements of the window size.
Maintain the minimum in the front ( for every window) this allows O(1) retrieval of minimum.
And make sure you only insert if the element in the new window is less than the current queue elements.

public static void maxSlidingwindow(int a[],int n,int w)
    {
        if(w<n)
        {
            int b[]=new int[n];
            Deque<Integer> q=new ArrayDeque<>();

            for(int i=0;i<w;i++)
            {
                while(!q.isEmpty() && a[i]>=a[q.peekLast()])
                    q.removeLast();
                q.addLast(i);
            }
            for(int i=w;i<n;i++)
            {
                b[i-w]=a[q.peekFirst()];
                while(!q.isEmpty() && a[i]>=a[q.peekLast()])
                    q.removeLast();
                while(!q.isEmpty() && q.peekFirst() >= i-w)
                    q.removeFirst();
                q.addLast(i);
            }
            b[n-w]=a[q.peekFirst()];

            for(int i=0;i<n;i++)
                System.out.print(b[i]+"\t");
        }
    }

Please correct me if I am wrong.

public static void maxSlidingwindow(int a[],int n,int w)
    {
        int b[]=new int[n];
        Deque<Integer> q=new ArrayDeque<>();
        for(int i=0;i<w;i++)
        {
            while(!q.isEmpty() && a[i]<=a[q.peekLast()])
                q.removeLast();
            q.addLast(i);
        }
        for(int i=w;i<n;i++)
        {
            b[i-w]=a[q.peekFirst()];
            while(!q.isEmpty() && a[i]<=a[q.peekLast()])
                q.removeLast();
            while(!q.isEmpty() && q.peekFirst() <= i-w)
                q.removeFirst();
            q.addLast(i);
        }
        b[n-w]=a[q.peekFirst()];
        
        for(int i=0;i<n;i++)
            System.out.print(b[i]+"\t");
    }

An inorder traversal starting from the rightmost node.
Right Node- Node- Left Node.

public static int inorderSum(Tree t,int sum)
{
    if(t!=null)
    {
        sum=inorderSum(t.right,sum);
           sum=sum + t.data;
       t.data=sum;
        System.out.print(t.data+" ");
   	sum=inorderSum(t.left,sum);
    }
	return sum;
}

Please correct me if I am wrong.
Steps:

1) You make a file list array with all file names.
2) Process one by one.
3) for each file:
Find a word and store the word and its corresponding line number and file name in a Key Value store.
A Hashmap of type <String, String[]>
String=word in the file.

String[0]= Count of word occurence
String[1]= Line Number
String[2]=Latest File name where the word appears (this is to handle the case where a single word appears in different files)

Each time a word appears increment count and update the line number and file name(if different)

Please correct me if I am wrong.

public static int permute(String prefix,String s)
{
        int n=s.length();
        if(n==0)
        {
             System.out.println(prefix+"\t");
        }
        for(int i=0;i<n;i++)
        {
            permute(prefix+s.charAt(i),s.substring(0,i)+s.substring(i+1,n)); 
        }
        
}

Function 2 merge 2 lists.

public static Node mergenode(Node head1, Node head2)
    {
        if(head1==null && head2==null) return null;
        if(head1==null)return head2;
        if(head2==null) return head1;
     
        if(head1.value<head2.value)
        {
            head1.next=mergenode(head1.next,head2);
            return head1;
        }
        else
        {
            head2.next=mergenode(head2.next,head1);
            return head2;
        }
    }

Please correct me if I am wrong. This is to create a BST.
1) Here we calculate the pivot using the partition function:
This will split the array into 2 sub-arrays

public static int partition(int[] a, int l, int r) 
    {
        
        int m=(l+r)/2;
        swap(a,l,m);
        int pivot=a[l];
        int low=l+1;
        int high=r;
        while(low<=high)
        {
            while(a[high]>pivot)
                high--;
            while(low<=high && a[low]<pivot)
                low++;
            if(low<=high)
            {
                swap(a,low,high);
                low++;high--;
            }
        }swap(a,l,high);
        System.out.println("Here the partition is: "+a[high]);
        return high;
    }

This function should return the root in the 1st case and the node in the later iterations.
2) Now the quicksort on the subarrays leads to further partitions which will be nodes.
The lower subarray will be the left subtree and the higher would be the right subtree.

quickSort(a,p,q);//left subtree
quickSort(a,q+1,r);//right rightsubtree

Please correct me if I am wrong.
This should handle the case of no zeros in the array. In which case, it should return the total number of ones present in the array or even say no zeros found.

public static void flip(int a[])
    {
        int maxdiff=0;
        int fsindex=0;
        int feindex=0;
        int onestoflip=0;
        int totalones=0;
        
        int currentdiff=0;
        int currentstart=0;
        int currentonestoflip=0;
        int zerocount=0;
        for(int i=0;i<a.length;i++)
        {
            if(a[i]==0)
            {
                currentdiff-=1;
                zerocount++;
            }
            else
            {
                currentdiff+=1;
                currentonestoflip++;
                totalones++;
            }
            if(currentdiff<maxdiff)
            {
                maxdiff=currentdiff;
                fsindex=currentstart;
                feindex=i;
                onestoflip=currentonestoflip;
            }
            else if(currentdiff>0)
            {
                currentdiff=0;
                currentstart=i+1;
                currentonestoflip=0;
            }
                
        }
        if(zerocount!=0)
            System.out.println(feindex - fsindex + 1 - onestoflip + totalones - onestoflip);
        else
            System.out.println("No zeros to flip, total number of ones"+totalones);
    }

This lists the files in the current directory.
Try this for a cleaner output

echo list=$(ls)

Basically while raising an integer to the power of the number. You are only multiplying the number by itself at the places where the binary equivalent has a "1".

public static int pow(int x,int y)
    {
        int temp2=x;
        int result=1;
        int temp;
        while((temp=bitcal(y))!=-1)
        {
            if(temp==1)
                result*=temp2;
            temp2*=temp2;y=y/2;
        }
        return result;
    }
    public static int bitcal(int y)
    {
      if(y>=1)
      {     
          y=y%2;     
      }
      else return -1;
      return y;           
    }

static int c=Integer.MIN_VALUE;  //global declaration
public static boolean bst(Tree t)
{
   
   if(t.left!=null)
   {
       if(bst(t.left)==false)
       {
           return false;
       }
   }
   if(t.data<c)
   {
       return false;
       
   }
   
   c=t.data;
   if(t.right!=null)
   {
       if(bst(t.right)==false)
           return false;
   }
     return true;      
}

Please correct me if I am wrong.
1. Provided you know the length of the string, create a circular linked list and place the R at K distance to allow the Rs will be eliminated before the B.
2. Iterate and delete the node at K interval.

Please let me know if this approach is possible:

Let's say the dictionary is a hashmap.
Permute all the combinations of words possible using the characters in the string.
Sort by length and start checking if the word exists in the dictionary.

Algorithm:
1) Convert the number to a string.
2) Take the substring from the start to the middle digit. Reverse that substring and append it to the result = substring(0,n/2) + reverseOf(subString(0,n/2))
3) Convert it back to integer.
4) If this number is less than the number, add 1 to the substring from 0 to n/2 and repeat the reverse and append process. If greater, subtract one and do the reverse and append.
5) Now you have the possible closest 2 palidromes.
Return the one which has a minimum distance from the original number

Please correct me if I am wrong.

public static void findMdiff(int a[])
    {
        if(a.length==0)
        {   System.out.println("Null array"); System.exit(0);}
        if(a.length==1)
            {   System.out.println("The max Diff is 0"); System.exit(0);}
        int min=0;int max=0;
         for(int i=1;i<a.length;i++)
        {
            if(a[i]<a[min])
            {
                min=i;
                
            }
            else if(a[i]>a[max])
            {
                max=i;
                
            }
            else
                continue;
        }
         System.out.println("The difference is great at "+max+" and "+min+" and the diff is : "+ (a[max]-a[min]));
    }

this is a recursive approach.

public static Nodes rev(Nodes head, Nodes previous)
    {
        Nodes temp;
        if(head.next==null)
        {
            head.next=previous;
            return head;
        }
        else
        {
            temp=rev(head.next,head);
            head.next=previous;
            return temp;
        }
      
              
    }

Here is the non-recursive:

public static Nodes brev(Nodes head)
    {
        Nodes temp;
        Nodes previous=null;
        while(head!=null)
        {
            temp=head.next;
            head.next=previous;
            previous=head;
            head=temp;
        }
        return previous;
              
    }

Helps to know both in the interview, depending on what is crucial to the interview.

You will need a Hashtable and a Min-heap for this.
1) Begin with populating the Hashtable with the String (<key>) and their frequency (<value>)
2) Once you completed 1000 strings, iterate through the Hashtable and maintain a min-heap of the size K .
3) Iterate till the end and only add the Keys from the Hashtable that have a value greater than the top of the heap.

Using a min-heap of k elements
First build the heap with the first k elements. As you advance the array, check if the current number is greater than the root of the heap. IFF it is greater, add it to the heap.

largest_elem(int a[], int k)
{
	minheap hp;
	int size=0;
	for(int i=0;i<a.length;i++)
	{
		if(size<k)
		{
			hp.insert(a[i]);
		} size++;
		else
		{
			if(a[i]>hp.peek())
			{
				hp.extract-min();
				hp.insert(a[i]);
			}
		}
	}
}

sieve of eratosthenes. For 1 to 100.

boolean primes[] = new boolean[100];
		int i,j;
		int cnt=0;
		for(i=0;i<10;i++)
		{
			primes[i]=true;
		}
		
		for(i=2;i<Math.sqrt(10);i++)
		{
			if(primes[i]==true)
			{
				j=i*i;
				while(j < 100)
				{
					primes[j]=false;
					cnt++;
					j=j+i;
				}
			}
		}
		
		System.out.println("Primes are");
		for(i=2;i<10;i++)
		{
			if(primes[i]==true)
				System.out.print(i + "  ");
		}

How about this?

public static void revll(Nodes p)
    {
        Nodes temp=p;
        Nodes temp2=p;
      if(temp2==null)
      {     System.out.println("Invalid"); System.exit(0);}
        
        int count=1;
        while(p.next!=null)
        {
            p=p.next;
            count++;
        }
        int a[]=new int[count-1];
        Nodes checkend=new Nodes();
        if(p!=null)
        {
           System.out.print(p.value+"\t");
           checkend=p;
        }
        int i=0;
        while(temp!=checkend)
        {
           a[i]=temp.value;
           i++;
           temp=temp.next;
        }
       //Printing the rest of the elements
        for(int j=a.length-1;j>=0;j--)
        {
            System.out.print(a[j]+"\t");
        }
    }

The catch is to do it in place. No use of temporary array.

void rightShift(int[] array, int n) 
{
    for (int shift = 0; shift < n; shift++) 
    {
        int first = array[array.length - 1];
        System.arraycopy( array, 0, array, 1, array.length - 1 );
        array[0] = first;
    }
}

String s1="pppppppfffffbbbbbuuuuu";
        Map<Character, Integer> cmap=new HashMap<> ();
        for (int i=0; i<s1.length();i++)
        {
            char c=s1.charAt(i);
            if(Character.isAlphabetic(c))
            {
                if(cmap.containsKey(c))
                {
                    cmap.put(c,cmap.get(c)+1);
                }
                else
                    cmap.put(c,1);
                
            }
        }
       
        System.out.println(cmap+"\t");

Could you please elaborate?