## Monday, 10 January 2011

This is the most common interview question and most commonly required algorithm for writing any code.

Metaphor

Consider you are planning a trip in office and got 2 lists which has names listed on it in alphabetical order. You need to merge these two files to get a master participant list. Now, for this you can do a simple merge of the two lists to generate a single list.

Concept

For merging two lists is a most common algorithm required in many programs. Its similar to the merge algorithm over array where we split the list into 2 and merge. Here, we get 2 lists. We just merge them into a single list and return it.

Code

Using extra memory

`   1:   `
`   2:  List* merge_lists(List *a1, List *a2)`
`   3:  {`
`   4:      List *c = 0;`
`   5:      while(a1 !=0 && a2!=0)`
`   6:      {`
`   7:          if(a1->data > a2->data)`
`   8:          {`
`   9:              if(c == 0)`
`  10:                  c=createNode(a2->data);`
`  11:              else {`
`  12:                  append(c, createNode(a2->data));`
`  13:              }`
`  14:   `
`  15:              a2 = a2->next;`
`  16:          }`
`  17:          else`
`  18:          {`
`  19:              if(c == 0)`
`  20:                  c=createNode(a1->data);`
`  21:              else {`
`  22:                  append(c, createNode(a1->data));`
`  23:              }`
`  24:   `
`  25:              a1 = a1->next;`
`  26:          }`
`  27:      }`
`  28:   `
`  29:      List *iter = c;`
`  30:      while(iter->next !=0) iter = iter->next;`
`  31:      if(a2 != 0)`
`  32:          iter->next = a2;`
`  33:      else`
`  34:          iter->next = a1;`
`  35:      return c;`
`  36:  }`
`  37:   `
`  38:  void main()`
`  39:  {`
`  40:      List *list1 = createNode(2);`
`  41:      append(list1, createNode(3));`
`  42:      append(list1, createNode(5));`
`  43:      append(list1, createNode(10));`
`  44:   `
`  45:      List *list2 = createNode(1);`
`  46:      append(list2, createNode(4));`
`  47:      append(list2, createNode(9));`
`  48:      append(list2, createNode(12));`
`  49:   `
`  50:      List *list3 = merge_lists(list1, list2);`
`  51:  }`

There are interview questions like merge a1 and a2 and place it in a1 without using extra space. We will discuss about this tomorrow.

Important points

• Merge algorithm on-place is very complex and mostly theoretical. We will concentrate on interview questions like How to sort 100GB worth of strings in the coming articles.
• Note that the remaining list at the end is blindly appended to the new list.