CareerCup

Using O(n) space,
store integers in a hash which has number as the key, and contains no. of consecutive elements smaller than, and no. of consecutive numbers greater than that.
For each number in array, search smaller and larger numbers, then store it updating its own smaller than & greater than values.
keep track of max consecutive sequence, consecutive smaller + larger + number.
That's your answer in O(n) and O(n) space.
Radix sort answer above will also take O(n) space and run slightly slower.

Assuming we are given parent pointer in the tree:
Apply DFS from the leaf node (including the parent), add 1 ms for all nodes in your path until you reach end and recurse back to node where you started. Node keeps max cost after recursive return to itself, and returns that to its calling node. Once reached back to the leaf node, returned cost is the answer.

Apply BFS through a queue, with each Node containing pointer to previous Node and cost so far. Keep track of nodes visited. If a Node is present again in the queue, it can be ignored as we previously traversed it with lower cost.

Solution: O(logn) + O(C)

-> binary search over n to find closest element to K
-> L=closest, R=closest
-> while (R-L+1 < C):
-> if (| array[L-1] - K |<=| array[R+1]) - K |:
-> L=L-1
-> else:
-> R=R+1
->return L

Solution O(N) psuedo code:

Since all start times are sorted, we can iterate through to find subsequent working slots and compare with max found so far. return max

psuedo:

log {
timeStamp start;
timeStamp end;
}

getMaxWorkingSlot(log[] logs) {

	int maxNotIdle=0 //seconds
	log previous;
	for (log l : logs) { 
		if (previous==null)
			previous = l;
			maxNotIdle = l.end-l.start;
			continue;
		if (l.start>previous.end)
			previous = l;
			if (maxNotIdle<l.end-l.start)
				maxNotIdle=l.end-l.start;
		else
			if (l.end>previous.end)
				previus.end=l.end;
				int notIdle = previous.end – previous.start
				if (notIdle>maxNotIdle)
					maxNotIdle=notIdle;
	}

return maxNotIdle;
}