MaxBrenner
BAN USER
Comments (3)
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
Oh yes. You are right, I missed the part where only the first integer that is greater than input must be returned. I assumed it was the next largest element from the entire array.
- MaxBrenner January 27, 2012Comment hidden because of low score. Click to expand.
0
of 2 vote
Pre-process the array and build a binary search tree. Now for a given number n, find the number in tree O(log n), then call its findSuccessor function (pick the left most node from the right sub tree), this would take O(logn). This would be the next higher value in the array.
Complexity: O(logn + logn)
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
1. Do a shallow copy, and maintain the new node address and data value pair in a hash table.
- MaxBrenner February 12, 20122. Now traverse the new list, using the hash table as reference and update the random pointer.
Complexity O(n+n)