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

How can SSIS be improved

I am not pretending to be an SSIS guru, especially since I started using SSIS only in the last two months and I am currently finishing my first project. But during my relatively short experience I encountered several problems, that could not be solved in an easy, elegant way with Business Intelligence Developer Studio 2008: 1. I needed to implement a sequence of steps in a data-flow task and have this task execute in parallel on different tables. What I was trying to do was exploiting parallelism through domain-decomposition. that. I needed to parameterize the data source in the data-flow task somehow but I was not able to achieve that. I tried passing parameters from a parent package to a child package or using a stored procedure with input parameter table name, but none of this was easy enough, Finally, I gave up and created copies of the same sql code in several stored procedures and had each stored procedure execute in parallel on its own table. 2. Excel is a nightmare for me. I always get errors about missing 64 bit drivers , so I finally had to create a 32 bit separate project just for the pure purpose of importing from Excel. 3. Fuzzy lookup only works in 64 bit. When I finally decided to work on one 32 bit project for the sake of Excel import, I found out that I actually need another 64bit project for the fuzzy lookup. 4. The regular lookup does not update the table when I specify "Replace column" for the matched records. I need another step to update the IDs with the matched ones from the database. It will be really nice to have this as an option in the lookup component - it's so naturally needed. 5. I cannot easily organize the visual appearance of the steps in my project. I could not find options to align left edges or right edges of the tasks. I had to spend some time positioning elements so that my workspace is not messy. 6. I don't think the XML export is supported. I also want to export my data in Excel and format the column lengths in advance, but this is not a trivial task. Perhaps some of these tasks are actually achievable, but I just don't have the knowledge yet. I am open to any suggestions or comments and will appreciate them!

Origins of code interviews questions

Have you ever wondered where are all those brain teasing ,programming interview questions coming from? You can find them gathered and published in at least a dozen of web sites and books. You read the book before the interview and try to memorize, ideally understand the answers. Then when the interview is over, you forget them.
I was curious where are any of those problems used in practice. I mean, there must be some application. For example, take the short formula (n&(n-1)) ==0, where do you ever need to determine if a number is a power of 2? Of course, since computers are using binary arithmetics, you would think this has many application. I tried googling and I could not find any. I found out about perfect numbers http://mathforum.org/dr.math/faq/faq.perfect.html that are computed based on but I don't think you need to verify if a number is a power of 2 there.
Finding a missing integer in an array of consecutive integers has a simple solution using bit manipulation. I was able to find one application thanks to this site: http://blogs.oracle.com/malkit/entry/finding_missing_value
and after reading it, I got the idea of another application: to find a missing packet in a sequence of received packets, where each one has a sequence number (like in TCP protocol).

After reading http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx
I will rewrite all my methods to use a List instead of an ArrayList.

Difference between List, HashTable and Dictionary

According to http://msdn.microsoft.com/en-us/library/ms379571(v=vs.80).aspx, a Hash table is the fastest data structure in C# when you know the number of records you are going to store because of the collision resulution method.

The better performance of a Hshtable over a Dictionary is doubtful however, due to boxing/unboxing which occurs when using a HashTable (http://msdn.microsoft.com/en-us/library/4yh14awz(v=vs.80).aspx).

Some sources say that HastTable is simply used for backward compability, and the new programs should always use a Dictionary.

My approach will be to use a Dictionary when I have to search for records and a List when I simply add new records or process records one by one. I will be curious to test the performance of a HastTable over a Dictionary though for a fixed-size array.

A good article about how to improve the performance of a DataReader:


http://sqlblog.com/blogs/adam_machanic/archive/2006/07/12/sqldatareader-performance-tips.aspx