Monday, 10 January 2011

Merge algorithm–Using linked list

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.