Linkedin Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
Java Version:
public class KClosestNodes {
public static void kClosestNodes(BinaryTreeNode root, int target, int k, Deque<Integer> q){
if(root == null)
return;
kClosestNodes(root.getLeft(), target, k, q);
if(q.size() < k){
q.addLast(root.getData());
}else if(Math.abs(target - root.getData()) < Math.abs(target - q.peekFirst())){
q.removeFirst();
q.addLast(root.getData());
}else{
return;
}
kClosestNodes(root.getRight(), target, k, q);
}
public static List<Integer> kClosestNodes(BinaryTreeNode root, int target, int k){
Deque<Integer> q = new LinkedList<Integer>();
List<Integer> result = new ArrayList<>();
kClosestNodes(root, target, k, q);
while(!q.isEmpty()){
result.add(q.removeFirst());
}
return result;
}
public static void main(String[] args) {
BinaryTreeNode root = buildBST();
int target = 21, k = 3;
System.out.println(kClosestNodes(root, target, k));
}
public static BinaryTreeNode buildBST(){
BinaryTreeNode node3 = new BinaryTreeNode(3);
BinaryTreeNode node5 = new BinaryTreeNode(5);
BinaryTreeNode node7 = new BinaryTreeNode(7);
BinaryTreeNode node20 = new BinaryTreeNode(20);
BinaryTreeNode node6 = new BinaryTreeNode(6);
node6.setLeft(node5);
node6.setRight(node7);
BinaryTreeNode node22 = new BinaryTreeNode(22);
node22.setRight(node20);
BinaryTreeNode node4 = new BinaryTreeNode(4);
node4.setLeft(node3);
node4.setRight(node6);
BinaryTreeNode node17 = new BinaryTreeNode(17);
node17.setRight(node22);
BinaryTreeNode root = new BinaryTreeNode(9);
root.setLeft(node4);
root.setRight(node17);
return root;
}
}
public class BinaryTreeNode {
private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;
public BinaryTreeNode(int data){
this.data = data;
this.left = null;
this.right = null;
}
public int getData(){
return this.data;
}
public void setData(int data){
this.data = data;
}
public BinaryTreeNode getLeft(){
return this.left;
}
public void setLeft(BinaryTreeNode left){
this.left = left;
}
public BinaryTreeNode getRight(){
return this.right;
}
public void setRight(BinaryTreeNode right){
this.right = right;
}
}
Solution to Closest K Nodes
Looking for interview experience sharing and coaching?
- aonecoding August 30, 2017Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!