ravishchawla
BAN USER- 0of 0 votes
AnswersHow would you implement X-ray for Kindle? X-ray is an index of characters in a book that shows how often a character appears in the book, and at which places. I was explained how this index works, and what it will look like on the book. There re more details here: http://www.amazon.com/gp/help/customer/display.html?nodeId=200729910
- ravishchawla in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm
Simple binary search, but we keep track of the last element that was closest to the key we are looking for. It can be recursive or iterative. I'll try recursive.
Public void BinaryCloseSearch(Node, root, Node closest, int data) {
If(root.data == data) { //found the node.
Return root;
}
Else if(root.left == null && root.right == null). //reached the last leaf node.
Return closest;
//if current node is closer the current closest node, reset the closest node
if(Math.abs(root.data - data) < Math.abs(closest.data - data) {
Closest = root;
}
//standard bst search
if(root.data < data) {
Node nodeFound = BinaryClosestSearch(root.right, closest, data);
Else
Node nodeFound = BinaryClosestSearch(root.left, closest, data);
Return nodeFound;
}
Time complexity can be O(1) if it's circular linked list.
- ravishchawla September 21, 2014
So it will still check every possible number, brute forced. I don't see any better way of doing it either tho.
- ravishchawla September 24, 2014