Dutch national flag problem

Problem:
You are given an array of 1's 2's and 3's. Sort this list so the 1's are first, the 2's come second, and the 3's come third.

Ex: Input [1, 3, 3, 2, 1]
Output [1, 1, 2, 3, 3]

But there is a catch!! The algorithm must be one pass, which means no merge/quick sort. Also no extra list allocations are allowed, which means no bucket/radix/counting sorts.

You are only permitted to swap elements.

Solution:
One algorithm is to have the top group grow down from the top of the array, the bottom group grow up from the bottom, and keep the middle group just above the bottom. The algorithm stores the locations just below the top group, just above the bottom, and just above the middle in three indexes. At each step, examine the element just above the middle. If it belongs to the top group, swap it with the element just below the top. If it belongs in the bottom, swap it with the element just above the bottom. If it is in the middle, leave it. Update the appropriate index.

public class DutchNationalFlag {
 
    public static void dutchFlagSort(int[] arr, int p, int k) {
        int p_index = 0;
        int k_index = arr.length - 1;
        for (int i = 0; i <= k_index;) {
                if (arr[i] == p) {
                        swap(arr, i, p_index);
                        p_index++;
                        i++;
                }
                else if (arr[i] >= k) {
                        swap(arr, i, k_index);
                        k_index--;
                }
                else {
                        i++;
                }
        }
    }
 
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
 }

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.careercup.com/question?id=18824667
http://en.wikipedia.org/wiki/Dutch_national_flag_problem

Duplicate a fancy linked list

Problem:
Every node of the linked list has a random pointer (in addition to the next pointer) which could randomly point to another node or be null. How would you duplicate such a linkedlist?

Solution:
* Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N afte the Nth node

* Now copy the arbitrary link in this fashion

original->next->arbitrary = original->arbitrary->next; /*TRAVERSE TWO NODES*/

This works because original->next is nothing but copy of original and
Original->arbitrary->next is nothing but copy of arbitrary.

* Now restore the original and copy linked lists in this fashion in a single loop.
original->next = original->next->next;
copy->next = copy->next->next;

* Make sure that last element of original->next is NULL.

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.linkedin.com/groups/Every-node-linked-list-has-1920463.S.243967327?view=&gid=1920463&type=member&item=243967327&trk=eml-anet_dig-b_nd-pst_ttle-cn

Find two missing numbers

There's an array of 100 numbers. Another array contains only 98 numbers from the first one. Identify two missing numbers.

Constraints:

• Space complexity must be O(1).
  So you can't use any other data structure like a hash-map, etc.
• The arrays are immutable.
  So you can't e.g. sort them.

Math is your friend. For both arrays you need to count a sum of all numbers (sum and sum2), and a sum of squares of the numbers (sq_sum, sq_sum2). Then:

sum - sum2 = a + b
sq_sum - sq_sum2 = a^2 + b^2

(a + b)(a + b) = a^2 + b^2 + 2ab
(a + b)(a + b) - (a^2 + b^2) = 2ab
(sum*sum - sq_sum) = 2ab

(a - b)(a - b) = a^2 + b^2 - 2ab
               = sq_sum - (sum*sum - sq_sum) = 2sq_sum - sum*sum
sqrt(2sq_sum - sum*sum) = sqrt((a - b)(a - b)) = a - b
((a + b) - (a - b)) / 2 = b
(a + b) - b = a

Credit: see link below.

Complexity:

time O(N)

space O(1)

Links:
http://stackoverflow.com/questions/10218791/find-two-missing-numbers

Detect a loop in a linked list

Use two pointers: fast and slow. The slow one goes through all elements one by one. The fast one visits each 2nd element only (i.e. jumps to ->next->next).

If the fast pointer reaches the end of the list, then there's no loops. Otherwise both pointers will meet at some point in the loop, hence detecting the loop itself.

Implementation:

boolean isInInfiniteLoop(Node node) {
  if (node == null) {
    return false;
  }
  Node turtle = node; // slower moving node
  Node rabbit = node.next; // faster moving node
  while (rabbit != null) {
    if (rabbit.equals(turtle)) {
      // the faster moving node has caught up with the slower moving node
      return true;
    } else if (rabbit.next == null) {
      // reached the end of list
      return false;
    } else {
      turtle = turtle.next;
      rabbit = rabbit.next.next;
    }
  }
  // rabbit reached the end
  return false;
}

Source: http://eddii.wordpress.com/2006/11/15/detecting-infinite-loop/

To find the node at which the loop starts, one needs to run the above algorithm first and find the intersection point between the turtle and the rabbit. After that we simply do this:

while (rabbit != node) {
  rabbit = rabbit.next;
  node = node.next;
}

(remember that 'node' points to the head of the list.) I.e. the distance between the head of the list and the loop start is equal to the distance between the rabbit and the same loop start.

Complexity:

time O(n)

space O(1)

Links:

• http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm#Tortoise_and_hare