copyconstructor
BAN USERHow about doing an A* search? The nodes (grid points in this case) are expanded based on the function f(x) = g(x) + h(x), where g(x) = path code till now to arrive at node (a,b), where 0<=a<x and 0<=b<y, and h(x) = the heuristic function which describes the estimated cost to get to (i,j) from (a,b). If the heuristic chosen is admissible and monotonic, the A* will give you the optimal path. We can use DP to compute h(a,b) and f(a,b).
- copyconstructor January 11, 2014Isn't this similar to matrix rotation? Gayle covered it in one of her interview videos.
- copyconstructor January 11, 2014Yep, suffix trees are your best bet. Though I wonder if they expect you to actually CODE it during the interview. Name dropping Ukkonen's algorithm is one thing, implementing it is another…
- copyconstructor January 11, 2014What kind of lookups will be required? A directory is usually implemented using something like a B tree, but depending on your application, you may also go for self-balancing trees/treaps etc. If you're simply looking for an alternative to a dictionary, then you can consider using a trie, or hashing.
- copyconstructor January 11, 2014But the rotations would come into play only if the resulting tree will have to be balanced again to retain any properties. If, for instance, there is a constraint that the resulting tree must be a valid binary tree, then rotations will be required in order to ensure than every node has at most 2 children.
The worst that can happen is when an internal node that has two children is chosen, in which case this node will now have 3 children - 2 of its original children and the root (along with the entire left/right subtree attached to the root). So we have some kind of 2-3 tree, of course, satisfying none of the cornerstone conditions which actually makes these kind of trees useful.
Do an inorder traversal of the tree. The values will be in ascending order. Then do a binary search on resulting array to find the index of given number, and then find the next highest number in constant time.
- copyconstructor January 11, 2014
What if the numbers to be added are 851 and 74. As I understand, the linked list would be represented as follows:
- copyconstructor January 12, 20148 -> 5 -> 1 -> 7 -> 4
Is there any additional info provided, like where the second number begins etc? I'm afraid I don't quite understand the Q.