Flipkart Interview 1: Data Structure and Algorithm

It was a telephonic discussion with Flipkart, as per its reputation, its interview throws questions to provide algorithms for them. In the first telecon, I was asked 2 questions (though the interviewer wanted to discuss 3), and those are following 2 questions.

A Binary tree is there, root of the binary tree is provided. It is asked to search a node and find all the nodes that are at a K distance from the tree.

Binary Tree - Not BST

 Consider the tree provided in the figure above.

Root of the tree is A, and it is required to find all the elements at distance 3 from Node D.

Answer should be C, J and K.

Root of the tree is A, and it is required to find all the elements at distance 2 from Node D.

Answer should be A, E, P, Q, R, and S.

Root of the tree is A, and it is required to find all the elements at distance 4 from Node D.

Answer should be T, U, V, F and G.

Solution

It is possible to create the graph where starting node of the graph is D as the starting node of the graph. Search Node along with its path. Create a graph with the help of path that was retained while searching the node, find all the nodes at distance K using BFS.

Algorithm for this as follows:

List 1
Find the element using recursion and store all the elements in a stack.
(Time complexity O(n))
Create the graph such that all the parents, catered in the stacks,
points in the other direction. i.e. D -> B-> A
(Time complexity O log(n) + Space Complexity o(Log n))
Now run the Breadth First Search algorithm to for iterations.
(Time complexity O(n))

Total time complexity for the solution is O(n + log n) = O(k*n) = O(n)

Space Complexity is O(log n). 

Let’s look at the alternative approach, as we have to change the linking, so it might not be feasible to change the DS.

List 2
Find the element using recursion and store all the elements in a stack, 
along with the side of the side of the traversal (Left or Right). 
(Time complexity O(n))
Find all downward elements that are at distance K from the node specified.
For each element pop the stack and maintain a count
From the node popped, find all the elements at (K – count) distance 
at the other side of tree.
End for each 

Let’s write a program for the method mentioned above.

We will need 2 classes for complete DS and solution.

Tree.java
class Tree {  
  char data;
  Tree left;
  Tree right;
  public Tree(char data) {
   this.data = data;
  }
  public char getData() {
   return data;
  }
  public void setData(char data) {
   this.data = data;
  }
  public Tree getLeft() {
   return left;
  }
  public void setLeft(Tree left) {
   this.left = left;
  }
  public Tree getRight() {
   return right;
  }
  public void setRight(Tree right) {
   this.right = right;
  }  
  public String toString(){
   return "" + data;
  }
 }

PathElement.java 
class PathElement {
  int direction;
  Tree node;
  public PathElement(Tree node, int dir) {
   this.node = node;
   direction = dir;
  }
  public int getDirection() {
   return direction;
  }
  public void setDirection(int direction) {
   this.direction = direction;
  }
  public Tree getNode() {
   return node;
  }
  public void setNode(Tree node) {
   this.node = node;
  }
  public String toString(){
   return ("Node:" + node.toString() + " Direction: " + direction  + "\n");
  }
 }

Search the path for element requested, and Keep the PathElement object with the stack.

List 3
 Stack path = new Stack();
 private boolean searchElement(Tree root, char search, int direction) {
  if( root == null ) return false;
  if( root.data == search ){
   path.push(new PathElement(root, direction));
   return true;
  }else{
   path.push(new PathElement(root, direction));
   boolean isInLeftTree = searchElement(root.getLeft(), search, 1);
   boolean isInRightTree = !isInLeftTree? searchElement(root.getRight(), search, 2) : false;
   if(!isInLeftTree && !isInRightTree ){
    path.pop();
    return false;
   }
   return true;
  }
 }

Read the downward element and create for these downward element.

List 4
 private List downwardElements(PathElement elem, int distance) {
  List chars = new LinkedList();
  return readElementAtDistanceK(chars, elem.node, distance);
  //Following method is listed further.
 }

Read the upward elements and add them to the list created above.

List 5
 private List upward(Stack path, PathElement pathElem, int distance) {
  PathElement prevElement = pathElem;
  PathElement element;
  int count = 1;
  List chars = new LinkedList();
  try{
   while( ( element = path.pop() ) != null){
    readElementsInDifferentDirection(chars, element, distance - count, prevElement.direction);
    prevElement = element;
    count++;
   }
  }catch(EmptyStackException ese){
  }
  return chars;
 }

 private List readElementsInDifferentDirection(List chars, PathElement element, int i, int direction) {
  Tree root = element.node;
  if( i == 0 ){
   chars.add(root.data);
  }
  if( direction == 1 ){
   readElementAtDistanceK(chars, root.right, i - 1 );
  }else{
   readElementAtDistanceK(chars, root.left, i - 1 );
  }
  return chars;
 }

Module to Read all the elements at a distance K from a node.

List 6
 private List readElementAtDistanceK(List chars, Tree root, int distance) {
  if( root == null ) return chars;
  if( distance == 0 ){
   chars.add(root.data);
   return chars;
  }
  readElementAtDistanceK(chars, root.left, distance - 1 );
  readElementAtDistanceK(chars, root.right, distance - 1 );
  return chars;
 }

Java representation to call the module is as followed.

List 7
  tp.searchElement(root, search, 0);
  PathElement pathElem = tp.path.pop();
  List<Character> chars = tp.downwardElements(pathElem, distance);
  chars.addAll(tp.upward(tp.path, pathElem, distance));  
  System.out.println("All the Characters:" + chars);

It will contain few generic related warnings and errors, please modify them to compile and run the program.

This approach has space complexity of log(n) and time complexity as defined below.
Search the node and path = O(n) //Worst case scenario.
Search the downward and upward elements = O(n) //Worst case scenario.
Time complexity of algorithm is O(n).