vabc3h
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Build a Cartesian Tree in O(N)
Then every query is O(lgN)
[2, 10,5,6,80] can be
80
/
10
/ \
2 6
/
5
This is a heap and when we find one node that is = than VAL and its parent is >= VAL,we return its parent if it's the right child, otherwise return itself.
But if the node is < VAL and parent is >= than VAL, we return its parent.
for 6, we traverse to 6 and return 10. (Right child,return parent)
for 5, we traverse to 5 and return 5. ( Left child)
for 20 we traverse to 10 and return 80. (Not equal, return parent)
Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
@anoy yeah, you're right. The worst case may be O(n)...
- vabc3h October 11, 2012I also agree with @flybug that "the question should be: you can do a pre-process, and after than, every search time is O(log n)." But I think other answer till now either assume the array is sorted or also use a linear time alg.