CareerCup

package javaStuff;

/**
 * Monitor based solution to alternate between 3 threads 
 * to print the sequence :  0 1 2 0 3 4 0 5 6..
 * 
 */
public class AlternateThreadDemo {
	public static void main(String[] args) {
		Monitor monitor = new Monitor(0); //start with thread-0's turn
		
		Thread t1 = new Thread(new MyJob(0, 0, monitor));
		Thread t2 = new Thread(new MyJob(1, 1, monitor));
		Thread t3 = new Thread(new MyJob(2, 2, monitor));
		
		t1.start();
		t2.start();
		t3.start();
	}
}

/**
 * Communicates which thread to run next. 
 * turn/prevTurn together determine this.
 *  
 * @author ayemmanu
 */
class Monitor{
	int turn;
	int prevTurn;
	public Monitor(int id){	this.turn = id;	}
}

class MyJob implements Runnable{
	Monitor monitor;
	int id;
	int val;
	
	public MyJob(int id, int val, Monitor monitor){
		this.id = id;
		this.val = val;
		this.monitor = monitor;
	}
	
	@Override
	public void run() {
		while(true){
			synchronized(monitor){
				
				while(monitor.turn != this.id) //Wait for my thread turn
					try {	monitor.wait();	} 
					catch (InterruptedException e) {}
				
				System.out.print(val + " ");
				
				if(val != 0) val += 2; //Value to be printed in next turn of this thread.
				
				//Logic to switch between threads - 0 1 0 2 0 1 0 2 ..
				//if cur is 0th thread: Next go to 2 if last visited=1. else go to 1 if last visited=2;
				//else: Next switch to 0'th thread if cur thread = 1 or 2
				if (monitor.turn == 0) { 
					if (monitor.prevTurn == 1)	monitor.turn = 2;
					else					monitor.turn = 1;
				} else { 
					monitor.prevTurn = monitor.turn;
					monitor.turn = 0;
				}
				
				try {	Thread.sleep(10);	} catch (InterruptedException e) {}
				
				monitor.notifyAll(); //Awake everyone
			}
		}
	}
}

/* It deals with single digit numbers only. 
           Easily extendible to numbers with Scanner or such Io classes. 
        */
	public int reverseDepthSum (String input)
	{
		// String input = "{{1,1},2,{1,1}}";
		char[] strArray = input.toCharArray();
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();

		int depth = 0, maxDepth = 0;

		for (int i = 0; i < strArray.length; i++) {
			if (strArray[i] == '{') {
				depth++;
				if (depth > maxDepth)
					maxDepth = depth;
			} else if (strArray[i] == '}')
				depth--;
			else {
				if (Character.isDigit(strArray[i])) {
					if (map.containsKey(depth))
						map.put(depth, map.get(depth) + Character.getNumericValue(strArray[i]));
					else
						map.put(depth, Character.getNumericValue(strArray[i]));
				} else {
					// "," => no op
				}
			}
		}

		int result = 0;
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			result += (maxDepth - entry.getKey() + 1) * entry.getValue();
		}

		return result;
	}

while (true){
	if(cur.data < elem){
		if(cur.next.data > elem                //found mid point between the nodes appropriate
			|| cur.next.data < cur.data) //end of sorted numbers, and given elem is the max.
		{
			insert;
			return;
		}
		else{
			cur = cur.next;
		}
	}
	else{
		cur = cur.next;
	}
}

public static void reverseWords(String str){
		StringBuilder string = new StringBuilder(str);
		
		Matcher matcher = Pattern.compile("\\w+").matcher(string);
		while(matcher.find()){
			reverseStr(string, matcher.start(), matcher.end()-1);
		}

                System.out.println(string);
	}
	
	
	private static void reverseStr(StringBuilder str, int i, int j){
		while(i<j){
			char tmp = str.charAt(i);
			str.setCharAt(i, str.charAt(j));
			str.setCharAt(j, tmp);
			i++;
			j--;
		}
	}

/**
	 * 
	 * @param array
	 * @param K -- num of positions shifted
	 * @return - index of the element in original array
	 */
	public static int binarySearchShiftedArray(int array[], int K, int beg, int end, int elem){
		int mid = beg + (end-beg)/2 ;
		int mid1 =  ( mid + K) % (array.length );	//shifted mid
		
		
		if(elem < array[mid1]){
			return binarySearchShiftedArray(array, K, beg, mid-1, elem);
		}		
		else if(elem > array[mid1]){
			return binarySearchShiftedArray(array, K, mid+1, end, elem);
		}
		else return mid1;
		
	}

f(n) = log3(n) + (n is power of 3 ? 1 : 0);
f(3) = f(2) = 1;

f(1) = f(0) = 0; //trivial

Not sure, why dynamic programming needed. Looks to me like, O(1) computation.

ex: f(27) = 1 + f(9); //divide into 9,9,9, compare 2 9's
f(9) = 1 + f(3); //divide into 3,3,3, compare 2 3's
f(3) = 1;
formla gives f(27) = log3(27) + 0


ex: f(12) = f(4) + 1 //4,4,4
f(4) = f(3) + 1; //2,2
f(3) = 1;

formula gives f(12) = log3(12) + 1 = 3;

(Please verify if f(n/3) needs to be considered in forumla instead of log3(n) before accepting)

Dynamic programming :-

O(n), n=num of grids in the game

//+ve=>ladder, -ve=>snake, 0=>neither
LadderSnakeValue[i] = +/-K;

//initialize first roll consequences
MinRolls[100]=0;
MinRolls[99->94]=1;

for(int i=93; i>0; i--){
	int minRolls=INT_MAX;

        //find min of all possible rolls
	for(int roll=1;roll<=6;roll++){
		int reachable;
		if(LadderSnakeValue[i+roll] < 0) //Snake
			continue;
		else{
			reachable = LadderSnakeValue[i+roll]+i; //add ladder value to current position
			if(MinRolls[reachable] + 1< minRolls)	minRolls = 1+MinRolls[reachable]; //1 for current roll + num of min rolls from climbed position
		}
	}
	
	MinRolls[i]=minRolls;
}
return MinRolls[1];

In addition to above:
- Indexes to store the hotels by state, city and/or zipcode will help fast retrieval
- Caching at request nodes will help serve repeated requests from same location
- If load balancing is used, probably distributed caching or global caching helps

My understanding of question :-
Start time can be anything, but endTime - startTime = 1 hr.
Now we need to find the intersecting time period with most number of intervals.

One way could be:
Design each interval as a node, and if interval1 and interval2 intersect, then add edge between node1 to node2.
Now find the node with max degree(max num of edges from the node). This is the interval intersecting with most others.

Now simply find intersection of all intervals of this node with its adjacent ones - to get overlap.

To be exact, below is a better hashcode suggested by Effective java book.

@Override
public int hashCode() {
int result = 17;
result = 31 * result + a[0];
result = 31 * result + a[1];
result = 31 * result + a[2];
return result;
}

But above(approximate one) is good enough, as its close to java.lang.String's hashcode implementation if am not wrong.

These numbers are chosen as they are odd-primes and in depth detail can be found in the book.

One way could be -
1. compte a hashcode out of each row. (17 + 31*a[0] + 31^2*a[1].. <-- approximately)
2. insert into hashMap<hashCode, row>
3. iterate and print hashMap.values()

- First read 1 number from each of K streams, and build a PriorityQueue
- After that keep removing top from PQ, and add next number from the same stream(from which top came)
----- if this stream is over, just move on
- Now repeat this while PQ is not empty

public static void sortKStreams(File f[], int K) 
			throws IOException{
		
		PriorityQueue<NumNode> PQ = new PriorityQueue<NumNode>(3);
		
		Scanner scanners[] = new Scanner[f.length];
		
		//insert 1 number each from one stream
		for(int i=0; i<K; i++){
			scanners[i] = new Scanner(f[i]);
			if(scanners[i].hasNextInt()){
				int inp = scanners[i].nextInt();
				PQ.add(new NumNode(inp, i));
				System.out.println("INITIAL BUILD Adding:" + inp + " from stream=" + i);
			}
		}
		
		//While PQ is not empty
		while(PQ.isEmpty() == false){
			//read next min from PQ
			NumNode nextMin = PQ.remove();
			System.out.println("Final result " + nextMin.getNumber());
			
			//read one element from the stream that provided min last time, and add to PQ
			//Note: as streams get exhausted, PQ size decreases linearly
			int nextReadVal = -1;
			
			Scanner sc = scanners[nextMin.getStreamNumber()];
			if(sc.hasNextInt()){
				nextReadVal = sc.nextInt();
				System.out.println("Adding to PQ: Value:" + nextReadVal + ", From stream=" + nextMin.getStreamNumber());
				PQ.add(new NumNode(nextReadVal, nextMin.getStreamNumber()));
			}
			
			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		
		for(int i=0; i<K; ++i){
			scanners[i].close();
		}
	}

In Java, with TreeMap<String, Integer> this can be solved at O(nLogn).

Or is there a trick to it, rather ?

Answer:- log(n)

System.out.println(Math.log(n));

This can transformed to :-

- Construct each interval as a node.
- Connect two nodes if those intervals overlap, to build an "undirected graph"
(Note: graph could be a forest also(disconnected components))
- Now problem is :- how many of N nodes can be colored with K colors ?

/**
     * Given root, serialize the tree by traversing in pre-order
     * @param root
     * @throws IOException 
     */
    public static void serialize(Node root, PrintWriter pwtr) throws IOException{
        
        if(root == null){
            pwtr.print(Integer.MAX_VALUE + " "); //delimiter
            return;
        }
        else{
            pwtr.print(root.get() + " ");
            serialize(root.left, pwtr);
            serialize(root.right, pwtr);
        }
    }

    /**
     * Read back the pre-order and reconstruct the tree
     * @param fis
     * @return
     * @throws IOException 
     */
    public static Node deserialize(Scanner scanner) throws IOException{
        int value = 0 ;
        
        if(scanner.hasNextInt())        value = scanner.nextInt();
        else            return null;
        
        if(value == Integer.MAX_VALUE)  return null;
        
        Node root = new Node(value);
        root.left = deserialize(scanner);
        root.right = deserialize(scanner);
        
        return root;
    }


    /**
     * Manual serialize/deseialize
     * 
     * @throws IOException
     */
    public static void demo() throws IOException{
        Node root = BinaryTreeUtil.buildTree();
        
        //serialize
        PrintWriter pw = new PrintWriter("binarytree.blob");
        serialize(root, pw);
        pw.close();

        //deserialize
        File file = new File("binarytree.blob");
        Scanner scanner = new Scanner(file);
        root = deserialize(scanner);
        scanner.close();
    }

This solution works.

But, in checking, you dont need to compare all sums. Simply compare if highest segment is longer than sum of smaller ones. Remaining two conditions will hold.

Ex: if A1 > A2 > A3.
Then if A1 > A2 + A3, remaining two will be true automatically. (since A1 > A2 & A1 > A3).

So total complexity = O(nLogn) + O(n) ( Sorting + comparision )

public static int getMaxParanthesisDepth(String str){
        int maxDepth=0;
        int potentialMaxDepth=0;
        int curDepth = 0;
        
        for(int i=0; i<str.length(); ++i ){
            //left brace
            if(str.charAt(i) == '('){
                curDepth++;
                potentialMaxDepth++;
            }
            //right brace
            else if(str.charAt(i) == ')')
            {
                curDepth--;
                
                //unmatched right brace 
                if(curDepth < 0){
                    System.out.println("unmatched brace");
                    maxDepth = -1;
                    break;
                }
                
                //one nest is processed
                if(curDepth == 0){
                    if(potentialMaxDepth > maxDepth){
                        maxDepth = potentialMaxDepth;
                        potentialMaxDepth=0;
                    }
                }
                
            }
        }
        
        ////unmatched left brace 
        if(curDepth != 0){
            System.out.println("Unmatched braces");
            return -1;
        }
        else return maxDepth;
    }

Say length of string=n
rotate by=k

for all indexes i from 0 -> (n-1)
if (i<k) newIndex = n - 1 - i;
else newIndex = i -k;

This will be very simple if saving first substring (k-length) into a temp string.
Also simple, if we can copy to a new string.

If needs to happen in place w/o extra space, do the 3 string reverse operations..
one for String[0..k-1], second String[k..n-1] and third on the resulting string of 1,2 operations.

javarevisited.blogspot.com/2012/02/producer-consumer-design-pattern-with.html

Some possibilities:

1. Threading issues. ("Synchronize" correctly in java to fix the issue)
2. Memory issues: (memory leaks of java objects or connections can be the reason)
3. In test suites lik JUnit, object model remains in memory and order of test cases run is not guaranteed. So make sure no singleton instances are leaking from one test case to another.

/* Function to get no of set bits in binary
   representation of passed binary no. */
int countSetBits(int n)
{
    unsigned int count = 0;
    while (n)
    {
      n &= (n-1) ;
      count++;
    }
    return count;
}

Now, we can simply terminate after 3rd iteration (if n is still != 0) & declare the result.

Maximum complexity = 3 operations.

/* Function to check if it has 3 bits */
boolean has3Bits(int n)
{
    unsigned int count = 0;
    while (n)
    {
      if(count == 3) return false; //more than 3 bits

      n &= (n-1) ;
      count++;      
    }

    if(count == 3)    return true;
    else    return false;  //less than 3 bits.
}

||'ing is correct, except its highly inefficient, if finding one such sequence of words is enough.

Its like exploring all the paths in a tree, even after 1 path lead to the solution.

As soon as one of the recursive calls inside the for loop returns true, we are done! we can return true and set of words visited through that iteration(recursively).

Past 1 hour = Current time to cur_min-60 mins.

We need 2 data structures.
1. For each minute maintain map of - {product_id, current_min_frequency}
2. Heap(priority queue) of all product_ids in the last hour, priority by current_hour_frequency

How to maintain:-

As each new request/product_id is read in,
1. Add to current min - prod_id, freq in current min [if already present, increment current_min_freq]
2. Increment current_hour_frequency in priority queue, and re-heapify

After each min,
1. remove the pair for (curre min - 60 mins)
2. decrement current_hour_freq by cur_min_frequency of that oldest mint in Priority Queue, and re-heapify. If cur_hour_freq reaches 0, delete that product_id's node from min_heap.

When queried, get the top 10 elements from heap.

In below case, inorder doesnt seem to give answer

.
               4
         3
     2	    0
  1   5

The answer is

.
       4
     3
   2
 1

A simple way may be:
1. In the first scan - Find all positions of given key. And number of elements less than key. Now you know
- (a) first position of the key in the result array (with key in the middle and lesser ones on left etc..)
- (b) last position of the key in the result array
2. Move all key elements to middle [from indexes (a) to (b)]
3. Now keep two pointers one always pointing to lesser ones and other to greater ones and swapping at every contradiction.

Each step is O(n).

// Function to find ceil of a given input in BST. If input is more
// than the max key in BST, return -1
int Ceil(node *root, int input)
{
// Base case
if( root == NULL )
return -1;

// We found equal key
if( root->key == input )
return root->key;

// If root's key is smaller, ceil must be in right subtree
if( root->key < input )
return Ceil(root->right, input);

// Else, either left subtree or root has the ceil value
int ceil = Ceil(root->left, input);
return (ceil >= input) ? ceil : root->key;
}

copied from geeksforgeeks, thought will help others..

Inorder & PreOrder take O(n) time.
After that substring search takes O(n) time with KMP algorithm.

So in effect, O(n) time we could verify this.

For each character, that is either the first char or the last char of any string, compute these two details:
1. Length of longest sequence beginning with this char
2. Length of longest sequence ending with this char
If a string has same char as prefix and suffix only count the one which is longer.

Now for each character from above set,
Compute the length by summing (1) + (2) above.

Pick the character with max sum, as answer.

INPUT: ab; ba; aac
Algo:
a - begString: aac, length=2
a - endString: ba, length=1;
b - begString: ba, length =1;
b - endString; ab, length=1;
c - endString: aac, length=1;

for a, sum=2+1=3
for b, 1+1=2;
for c, 1+INF=INF

Output: a [max length=3]

Complexity: O(n). Simply read each character of each string from beginning & ending till it matches with adjacent character and find the above lengths.

Edit: To address the case where max length seq is in the middle of a string, for each char - also keep track of longest length "inside" a string globally(across all strings). This can be easily done by using a map or such data structure.

Solution by Sunny above seems to be more complete & elaborative.

Corrected, according to Sunny's comment. thx..

Ex: String2 = "ABC"; String1="AXBYCZ". Answer = true;

Simple Algo:
First look for 1st char, then 2nd char in remaining string and so on..

boolean f(String str1, String str2)
{
	int begIndex = 0;
	for(int i=0; i<str2.length; ++i){
		int pos = str1.indexOf(str2.charAt(i), begIndex);
		if(pos == -1)	return false;
		begIndex = pos+1;
	}

	return true;
}

Need more details in problem def, for more sophisticated solution.

If its a phone interview, simple recursion with visited mark on all visited cells should do..

Here is pseudo code:
================

int f(srcRow, srcCol, tgtRow, tgtCol, numStepsSoFar){
	
	/* boundary check row/cols */
	if outOfBoundary(sRow, sCol) || outOfBoundary(tRow, tCol) 
		return Integer.MAX_VALUE;

	if(sRow==tgtRow && sCol==tgtCol)	return numStepsSoFar;

	visitedCells.add(sRow, sCol);

	if(!visisted(srcRow+1, sCol+1)		num1=f(sRow+1, sCol+1, numStepsSoFar+1);
	if(!visisted(srcRow-1, sCol+1)		num1=f(sRow-1, sCol+1, numStepsSoFar+1);
	if(!visisted(srcRow+1, sCol-1)		num1=f(sRow+1, sCol-1, numStepsSoFar+1);
	if(!visisted(srcRow-1, sCol-1)		num1=f(sRow-1, sCol-1, numStepsSoFar+1);

	return min(num1, num2, num3, num4);
}

One straight forward way may be:
Maintain a LinkedList of nodes with <timeStamp, request> pairs.
As requests come, keep adding to this linked list (sorted by timestamps).

Maintain 3 pairs of pointers.
1st pair of pointers = lastSecondStart, lastSecondEnd
2nd pair=lastMinuteStart, lastMinuteEnd
3rd pair=lastHourStart, lastHourEnd

After every second do below:
lastSecondStart = lastSecondEnd->next;
lastSecondEnd=move right to node by a 'second' using currentTime & node.timeStamp;

lastMinuteStart=move right to node by a 'second' using currentTime & node.timeStamp;
lastMinuteEnd=lastSecondEnd;

lastHourStart=move right to node by a 'second' using currentTime & node.timeStamp;
lastHourEnd=lastMinuteEnd;

Essentially 3 traversals to right. Num of nodes depends on num of requests in that second.

Caveats: 1.If there are not too many requests this works.
2. Concurrent requests can be handled by making add() method synchronized. But too many of these can tamper performance.

Recursive solution:

public static int nDiceASum(int N, int A, int S){
                if(N<=0) return 0;
                if(N==1){
                        if(S >= 1 && S <= A)
                                return 1;
                        else
                                return 0;
                }

                int result = 0;
                for(int i=1; i<=A; ++i){
                        result += nDiceASum(N-1, A, S-i);
                }

                return result;
        }

Dynamic Program:
Create 2D matrix with numOfDice, sum on 2 dimensions.
So Matrix[s][n] = Sum( Matrix[s-i][n-1]) for i = 1->A

Initialize first row, first column

Matrix[1][1] = 1;
for(int numDice=2; numDice<n; ++numDice)
 	Matrix[1][numDice] = 0;
for(int sum=2; sum<S; sum++){
	if(sum <= A) Matrix[sum][1] = 1;
	else	Matrix[sum][1] = 0;
}

Now compute Matrix[Sum][NumDice] to get the result using below loop

for(int s=2; s<=Sum; s++)
		for(int n=2; n<=NumDice; n++)
			Matrix[s][n] = Sum(Matrix[s-i][n-1]) with i from 1->A;

On similar lines -- instead of trying to store them in bit array (or a binary number), we can simply iterate over [min, max] range and compute the max range that has all numbers present in given array.

This has fewer constraints. Only constraint :- [min, max] range should be reasonable. Numbers can be negative/big/repeated etc.

1. Min time interval between clicks
2. From which ip/area(router) it is coming
3. max num of clicks in a given interval (~ 1 min)
4. If time intervals between clicks is regular(ex: equal could mean a bot)
5.

Correction: "until I get 25 pairs", should be "until I get numOfIncomings=25 & numOfOutgoings=25" as explained in later statements.

Also, it is true that graph has enough info to give required info. But any topological sort may not necessarily give the answer.

"Both lists are of same length." -- So don't need the initial conditions you mentioned.

more over you are maximizing the sum! shouldnt you be maximizing the number of elements considered in contributing to the SUM ? (i.e. Max(1 + Opt(j-1,..), Opt(..)) instead of Max(a[j]+...)) Correct me if am wrong.

This dynamic programming approach may answer the question when it finds the exact match with the expected Sum. can you argue how it would work in case it has to find the closest(but lesser and not equal) one ? (i.e. when exact match doesnt exist).

if we are only given input and output strings, then there is simply no way you can ever figure out the number of rotation if greater than N (i.e. you can only give the answer < N).