gumanji
BAN USER
Comments (5)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
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.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
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.endl.start;
continue;
if (l.start>previous.end)
previous = l;
if (maxNotIdle<l.endl.start)
maxNotIdle=l.endl.start;
else
if (l.end>previous.end)
previus.end=l.end;
int notIdle = previous.end – previous.start
if (notIdle>maxNotIdle)
maxNotIdle=notIdle;
}
return maxNotIdle;
}

gumanji
December 07, 2013 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
Using O(n) space,
 gumanji August 24, 2017store 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.