Amazon Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
class MyNode {
constructor( node, prev ) {
this.node = node;
this.prev = prev;
this.next = null;
}
}
class NodeList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
push( node ) {
if( this.tail ) {
this.tail = this.tail.next = new MyNode(node,this.tail);
}
else {
this.tail = this.head = new MyNode(node,null);
}
this.size++;
}
pop() {
if( this.tail ) {
this.tail = this.tail.prev;
if( !this.tail ) {
this.head = null;
}
this.size--;
}
}
clone() {
// TODO
}
count_common_nodes( list ) {
let result = 0;
let list_node = list.head;
for( let mynode=this.head; mynode; mynode=mynode.next ) {
if( mynode.node!=list_node.node )
break;
result++;
list_node = list_node.next;
if( !list_node )
break;
}
return result;
}
}
class Context {
constructor( target ) {
this.target = target;
this.path_to_target = new NodeList();
this.leaves = new NodeList();
}
task( node, path_from_root ) {
if( !node )
return;
path_from_root.push(node);
if( node==target ) {
this.path_to_target = path_from_root.clone();
}
if( !node.left && !node.right ) {
this.leaves.push({'node':node,'path_from_root':path_from_root.clone()});
}
else {
this.task(node.left,path_from_root);
this.task(node.right,path_from_root);
}
path_from_root.pop();
}
}
let context = new Context(target);
context.task(tree,new NodeList()); // This operation is going to take O(n)
if( !context.path_to_target ) {
throw Error("Target is not found in the tree");
}
let min_distance_to_target = Number.POSITIVE_INFINITY;
let closest_leaf = undefined;
for( let mynode=context.leaves.head; mynode; mynode=mynode.next ) {
let leaf = mynode.node;
let size_of_common_prefix = context.path_to_target.count_common_nodes(leaf.path_from_root);
let distance_to_target = leaf.path_from_root.size+context.path_to_target.size-2*size_of_common_prefix;
if( distance_to_target<min_distance_to_target ) {
min_distance_to_target = distance_to_target;
closest_leaf = leaf;
}
}
console.log(closest_leaf.toString());
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other top-tier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
Solution:
- aonecoding August 24, 2018