Common Interview Questions - Linked Lists

The following is a list of questions I have compiled based on my interviewing experience and several books:

Linked Lists:

1.  How do you implement  linked-list in an object-oriented language?
2. Write an algorithm to insert at the beginning of the list.
3. Write an algorithm to find a value in a list.
4. Write an algorithm to insert at the end of the list.
5. Write an algorithm to delete an element from a list.
6. Find the mth to the last element.[1]
7. Determine whether a list has a loop(is cyclic).[1]
8. Remove duplicates from a linked list.
9. Add two integers stored in  linked-lists, where each digit is stored in a separate element. Store the result as a linked-list where each digit is stored in a separate node.[2]

In bold : very probable question, that constitutes the required minimum.

You should determine if the linked list is singly-linked, doubly-linked or circularly-linked list. For this post, we will use only singly-linked lists.

1. How do you implement linked-list in an object-oriented language?
class ListElement{
                                 ListElement next;
                                 int data;
                                 ListElement ListElement(int data){ this.data=data; }
}

The implementation above is a singly-linked list and for simplicity it is assumed that the elements contain integer as a data, although data can be an object or a set of objects of any type.

2. Write an algorithm to insert at the beginning of the list.
ListElement LLInsertFront(ListElement head, int data){
ListElement e=new ListElement(data);
e.next=head;
return e;
}

You should not loose the pointer to the head of the list, therefore the method returns the new element.

3. Write an algorithm to find a value in a list.
          bool   LLFind(ListElement head, int data)
{
while (head!=null) if head.data==data return true;
                                else head=head.next;
return false;
}                                                                       

4. Write an algorithm to insert at the end of the list.
void LLInsertTail(ListElement head, int data)
{
while (head.next!=null) head=head.next;
ListElement e=new ListElement(data);
head.next=e;
}

5. Write an algorithm to delete an element from a list.
bool LLDelete(ListElement head, ListElement d)
{
if (head==d) {
                            head=head.next; 
                            delete d; 
                           return true;
                     }
while (head.next!=null)
{
   if (head.next==d) 
       { head.next=d.next;
          delete d;
           return true;
        }

}

6. Find the mth to the last element.
The idea is to use two pointers - A and B, that are m elements apart.
6.1.[Find the mth to the last element] Set the two pointers at the beginning of the list A=B=head;
6.2. Advance pointer B m times.
6.3. Start advancing pointer A and B by 1, checking every time if pointer B has reached the end of the linked list. When pointer B reaches the end, pointer A has the mth to the last element.

7.Determine whether a list has a loop(is cyclic).
The idea is to use two pointers A and B, advancing at a different rates. The fast pointer A moves 2 elements ahead, while the slow pointer B moves 1 element ahead. If the fast pointer reaches the last element, then the list does not contain a loop. Since the fast pointer advances 2 element ahead, you need to check for null the pointer as well as A.next. If the fast pointer reaches the slow pointer, that means the list contains a loop (again you need to check A.next=B as well as A=B).

8. Remove duplicates from a linked list.
Three basic methods exist:
- using two loops - unfavorable time complexity.  The inner loop should check only the element prior to the current element in the outer loop.
- using Hash table - additional memory is needed to store the hash table.
- using a sort algorithm - the original order of the linked list is not preserved.

9. Add two integers stored in  linked-lists, where each digit is stored in a separate element. Store the result as a linked-list where each digit is stored in a separate node. The digits are stored in reversed order.

Example adding (6,0,1) and (5,1,3) will produce (1,2,4). Here is an implementation using recursion:

ListNode AddInt(ListNode a, ListNode b, int carry)
{
int result=carry;
if (a!=null) result+=a.data;
if (b!=null) result+=b.data;
if (a==null) && (b==null) return null;
ListNode n=new ListNode(result%10);
n.next=AddInt(a.next, b.next, result>10?1:0);
return n;
}

Sources:
1. "Programming Interviews Exposed" 2nd Edition, published 2007, John Mongan, Noah Soujanen, Eric Giguere ISBN: 978-0-470-12167-2
2. "Coding Interview" 4th Edition, Gayle Laakmann, 2010, ISBN 978-1451578270,

Common interview questions - Binary trees.

The following is a list of questions I have compiled based on my interviewing experience and several books:

Binary tree:

1.  How do you implement binary tree in a object oriented language?
2. Write algorithms for pre-order, in-order and post-order traversal.
3. Find the lowest common ancestor of two nodes.[1,2]
4. Flip(reverse) a binary tree.
5. Determine if a tree is a sub-tree of another tree.
6. Algorithm to insert a node.
7. Algorithm to delete a node.
8. Find the number of leaves.
9. Find if a tree is a balanced tree.[2]
10. Create a binary search tree with a minimal height from a sorted array.[2]
11. Find the number of nodes in a tree.
12. Find the number of leaves in a tree.
13. Find the height of the tree.
14. Find a value (lookup) in the tree.
15. Implement a breadth-first search algorithm.
16. Implement a depth-first search algorithm.
17. When should you implement  a depth-first search and when a breadth-first search?[1]

In bold : very probable question, that constitutes the required minimum.
In italics: the question does not require Binary Search Tree, just Binary Tree.

Every time you a presented with a binary tree related question, you need to clarify:

• If the tree is a Binary Search Tree or just a Binary Tree. In a Binary Search Tree, the key of the node is greater than the key of left descendant and less than the key of the right descendant.
• If the Binary Search Tree can contain duplicate keys. If duplicate keys are allowed, "greater than" and "less than" should be replaced with "greater than or equal" or "smaller than or equal". You may ask if an equal key should be inserted to the left or to the right of the node. 

Here are the answers that I have prepared.

1. How do you implement binary tree in a object oriented language.
Implementation in C#

Class Node{
                      Node left;
                      Node right;
                      int key;
                      public Node(Node left, Node right, int value)
                     {
                      this.left=left;
                      this.right=right;
                      value=value;
                    }
  }

Please note: According to the best practice, you should implement the members as private and write a methods to access the members. But often in the interest of time, you can ask or explain in advance.

2.Write algorithms for pre-order, in-order and post-order traversal.
The way to remember this is: "order" refers the order of printing(visiting) the parent node in relation to its two descendants.

• "Pre-"order from latin "prae" means " means "before": the parent node should be visited before the child nodes. 
• In-order: parent node visited in between the child nodes. 
• Post-order means parent node is visited after or subsequent to its children.

PreOrder(Node root)
{
if (root==null) return;
    print(root);
    print(root.left);
    print(root.right);
}

for the rest 2 traversals, you have to change the order of the tree operations.
Always check for nulls before you try to access the node!

3.Find the lowest common ancestor of two nodes.
The lowest common ancestor of nodes "2" and "11" from the binary tree http://en.wikipedia.org/wiki/Binary_tree#/media/File:Binary_tree.svg is "7".

The basic algorithm is:

3.1.[Find lowest common ancestor in Binary Tree] Start from the root and find whether the two nodes are located in the left sub-tree or the right sub-tree.
3.1.1 If both nodes are located in the right sub-tree, repeat the algorithm with the right child of the root.
3.1.2 If both nodes are located in the left sub-tree, repeat the algorithm with the left child of the root.
3.2.3.If both nodes are located on different sides of the root, then the root is the most common ancestor.

You will need to write an algorithm that checks whether the node is located in the left sub-tree or the right-sub-tree of the root:

bool ChildExistsInBTree(Node root, int child)
{
if (root==null) return false;
if (root.key==child) return true;
return ChildExistsInBTree(root.left, child) || ChildExistsInBTree(root.right, child);
}


For a Binary Search Tree finding the lowest common ancestor does not need to use the ChildExistsInBTree function:

3.2.[Find lowest common ancestor in Binary Search Tree] Start from the root and find whether the keys of two nodes are lower or higher than the root node..
3.2.1 If both nodes have keys that are higher than the root node, repeat the algorithm with the right child of the root.
3.2.2 If both nodes have keys that are lower than the root node, repeat the algorithm with the left child of the root.
3.2.3.If one node is higher and one node is lower than the  root node, then the root node is the lowest common ancestor..


4.Flip(reverse) a binary tree.
Here is an example of flipping a binary tree:
http://codercareer.blogspot.com/2011/10/no-12-mirror-of-binary-trees.html

void FlipBTree(Node root)
{
  if (root==null) return;
FlipBTree(root.left);
FlipBTree(root.right);
Node temp= root.left;
root.left=root.right;
root.right=temp;
}

5. Determine if a tree is a sub-tree of another tree.

Here is a good example of a sub-tree: http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/
Here are a few points you need to confirm first with the interviewer:

• If the tree is empty, it is a sub-tree of any tree. 
• If a tree is the same as another tree, then it is its subset.

With affirmative answers to the questions above,  the algorithms is as follows:

5.1.[Determine if a tree A is a sub-tree B] Starting the the root of tree B, if tree A is the same as tree B, then tree A is a sub-tree of tree B.
5.2. If tree A and tree B are different, if tree A is the same as left sub- tree or the right-subtree of the root, then tree A is a sub-tree of tree B. Otherwise continue recursively with the left and the right sub-trees until you reach the leaves.

bool IsSameTree(Node A, Node B)
{
 if (A==null) && (B==null) return true;
If (A==null)^(B==null) return false;
return (A.key==B.key) && IsSameTree(A.left, B.left) && IsSameTree(A.right, B.right);
}

bool IsSubTree(Node A, Node B) //return true if A is a sub-tree of B
{
  if (A==null) return true;
if (B==null) return false;
   if IsSameBTree(A,B) return true;
    return IsSameBTree(A,B.left) || IsSameBTree(A, b.right);
}

Another approach is to perform in-order, pre-order or post-order traversal of the trees and build a string concatenations of all keys, then find if the string of tree B contains the string of tree A (requires additional memory and can become an issue if trees are too big).

6. Algorithm to insert a node.
BSTreeInsert(Node root, int newkey)
{
if ((root.left==null) && (root.key>newkey))   {
root.left=new Node(null,null, newkey);
return;
}
if ((root.right==null) && (root.key<=newkey)){
root.right=new Node(null,null, newkey);
return;
}
if (root.key>newkey) BSTreeInsert(root.left, newvalue);
else BSTreeInsert(root.right, newvalue);
}

7. Algorithm to delete a node.

This is the question of the three special cases you need to consider:

• node D to be deleted has no children : simplest case, just set the parent link to the node to null and free the memory;
• node D to be deleted has one child: replace the node with its child and delete the node D;
• node to be deleted has two descendants: find the minimum node M in the left sub-tree and replace the node D with node M, then delete the node D;

BSTreeDelete(Node root, int key)
{

Node D=BSTreeLookup(root, key);
Node parent=BTreeGetParent(D);
if (D.right==null)
{
   if (parent!=null)
   {
      if (parent.right==D) parent.right=D.left;
      if (parent.left==D) parent.left=D.left;
   }
else { root=D.left;} 
delete D;
}
else if (D.left==null)
{
   if (parent!=null)
   {
      if (parent.right==D) parent.right=D.right;
      if (parent.left==D) parent.left=D.right;
   }
   else { root=D.right;} 
delete D;
}
else //neither left or right are null
{
 Node M=BSTreeGetMin(D);
 if (parent!=null)
   {
      if (parent.right==D) parent.right=M;
      if (parent.left==D) parent.left=M;
   }
else { root=M;} 
delete D;
}
}

8. Find the number of leaves.
int BTreeGetLeavesCount(Node root)
{
   if (root==null) return 0;
   if root.left==null && root.right==null return 1;
   return BTreeGetLeavesCount(root.left)+ BTreeGetLeavesCount(root.right);
}

9. Find if a tree is a balanced tree.
The distance of a binary tree node is defined as the minimum number of nodes that need to be visited starting from the root  before the node is reached. The maximum distance of the binary tree is also called a depth. A binary tree is balanced if the maximum difference in the distance of the leaf nodes is 1.

int FindMinDistance(Node root)
{
  if (root==null) return 0;
return 1+ Math.Min(FindMinDistance(root.left), FindMinDistance(root.right));
}
int FindMaxDistance(Node root)
{
  if (root==null) return 0;
return 1+ Math.Max(FindMaxDistance(root.left), FindMaxDistance(root.right));
}
bool BTreeIsBalanced(Node root)
{
   return ((FindMaxDistance(root)-FindMinDistance(root))<=1);
};

10. Create a binary search tree with a minimal height from a sorted array.
It is obvious that you should not start inserting elements in the order they are stored in the array , because you will end up with the worst case of Binary Search Tree, where it resembles a linked list.
10.1.[Create a binary search tree with a minimal height from a sorted array.]  The first element to insert is the middle of the array.
10.2. Split the left sub-array into two parts and insert the middle element, then continue recursively until all elements are inserted.
10.3. Split the right sub-array into two parts and insert the middle element, then continue recursively until all elements are inserted.

11. Find the number of nodes in a tree.
int BTreeGetNodeCount(Node root)
{
 if (root==null) return 0;
if ((root.left==null) && (root.right==null)) return 1;
return (1+BTreeGetNodeCount(root.left) + BTreeGetNodeCount(root.right));
}

12. Find the number of leaves in a tree.
int BTreeGetLeafCount(Node root)
{
 if (root==null) return 0;
if ((root.left==null) && (root.right==null)) return 1;
return (BTreeGetLeafCount(root.left) + BTreeGetLeafCount(root.right));
}
13. Find the height of the tree.
int FindMaxDistance(Node root)
{
  if (root==null) return 0;
return 1+ Math.Max(FindMaxDistance(root.left), FindMaxDistance(root.right));
}

14. Find a value (lookup) in the tree.
Node BSTreeLookup(Node root, int key)
{
if (root==null) return null;
if (root.key=key) return root;
if root.key<=key return BSTreeLookup(root.right);
if root.key>key return BSTreeLookup(root.left);
}

15. Implement a breadth-first search algorithm.

With "Breadth" meaning from side to side, this search first examines all the nodes in one level of the tree before moving to the next level.

The easiest implementation is using a Queue. In C#, Queue class is defined, but you can easily implement it using linked lists or an array.

bool BTreeBreadthFirst(Node root, int key)
{
   Queue q=new Queue();
    if (root==null) return false;
   q. Enqueue(root);
   while (q.Count>0)
      {
         Node t=q.Dequeue();
           if (t.key==key) return true;
           if (t.left!=null) q.Enqueue(t.left);
           if ((t.right!=null)) q.Enqueue(t.right);
      } 
return false;
}

16. Implement a depth-first search algorithm.

The depth-first search examines all sub-trees of a node before returning to its parent. It resembles a pre-order traversal, but it is a search and unlike the pre-order traversal, it does not visit each node of the tree and it stops as soon as it finds the key.

Two ways to implement the depth-first search  are using recursion or using s stack. For consistency with the implementation of the breadth-first search algorithm, I will implement it using a stack:

bool BTreeDepthFirst(Node root, int key)
{
   Stack s=new Stack();
    if (root==null) return false;
   s. Push(root);
   while (s.Count>0)
      {
         Node t=s.Pop();
           if (t.key==key) return true;
           if (t.left!=null) s.Push(t.left);
           if ((t.right!=null)) s.Push(t.right);
      } 
return false;
}

In addition to the C# implementation, a stack can be implemented using a linked list.

17. When should you implement  a depth-first search and when a breadth-first search?

Breadth-first search algorithm should be used if:
- you suspect the key you are looking for is located close to the root;
- you need the nodes of the tree output grouped in levels, for example you need to process only the nodes of a certain level;
- you need to find the node with the matching key that is located closer to the root.

Breadth-first algorithm should be used if:
- you suspect the key you are looking for is not close to the root. In general, this algorithm is faster than Breadth-first search.
- memory is a concert - i.e. the tree is big;


Sources:
1. "Programming Interviewes Exposed" 2nd Edition, pubulished 2007, John Mongan, Noah Soujanen, Eric Giguere ISBN: 978-0-470-12167-2
2. "Coding Interview" 4th Edition, Gayle Laakmann, 2010, ISBN 978-1451578270,
3. "The art of Computer Programming Volume 3", 2nd Edition, Donald E. Knuth, ISBN: 0-201-89685-0