Egg Floor Puzzle

http://classic-puzzles.blogspot.com/2006/12/google-interview-puzzle-2-egg-problem.html

Maximum sum such that no two elements are adjacent

Question: Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Using Dynamic Programming : you have to maintain an array maxsum[] such that maxsum[i] has the maximum sum till the ith element. and

maxsum[i]=max(maxsum[i-2],maxsum[i-3])+arr[i];
and the catch is that we have to include either the 1st element or the 2nd element in the maxsum
so
maxsum[0]=arr[0];
maxsum[1]=arr[1];
maxsum[2]=arr[0]+arr[2];
now apply the recursive structure from the 4th element onwards.

This would take O(n) time and then find the maximum element of maxsum. O(n).

Count number of bits to be flipped to convert A to B

Question: You are given two numbers A and B. Write a program to count number of bits needed to be flipped to convert A to B.

Solution:

  1. Calculate XOR of A and B.
        a_xor_b = A ^ B
  2. Count the set bits in the above calculated XOR result.
        countSetBits(a_xor_b)

XOR of two number will have set bits only at those places where A differs from B.

Example:

   A  = 1001001
   B  = 0010101
   a_xor_b = 1011100
   No of bits need to flipped = set bit count in a_xor_b i.e. 4

Find whether a number is power of two

1. A simple method for this is to simply take the log of the number on base2,if you get an integer then number is power of 2.

2. Another solution is to keep dividing the number by two, i.e, do n = n/2 iteratively. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.

#include
#define bool int
/* Function to check if x is power of 2*/
bool isPowerOfTwo(int n)
{
  if(n == 0)
    return 0;
  while(n != 1)
  {
    n = n/2;
    if(n%2 != 0 && n != 1)
      return 0;
  }
  return 1;
}
/*Driver program to test above function*/
int main()
{
  int test_no = 31;
  if(isPowerOfTwo(test_no))
    printf("%d is a power of 2", test_no);
  else
    printf("%d is not a power of 2", test_no);
  getchar();
}
3. All power of two numbers have only one bit set. So count the no. of set bits and if you get 1 then number is a power of 2.

Find the Number Occurring Odd Number of Times others Even number of times

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

Example: 
I/P = [1, 2, 3, 2, 3, 1, 3]
O/P = 3

Algorithm: 
Do bitwise XOR of all the elements. Finally we get the number which has odd occurrences.


Program:

#include 
int getOddOccurrence(int ar[], int ar_size)
{
     int i;
     int res = 0;
     for(i=0; i < ar_size; i++)
        res = res ^ ar[i];
     return res;
}
/* Diver function to test above function */
int main()
{
     int ar[] = {2, 3, 5, 4, 5, 2, 4, 3, 5, 2, 4, 4, 2};
     printf("%d", getOddOccurrence(ar, 13));
     getchar();
}

Add 1 to a given number without arithmetic operators

Write a program to add one to a given number. You are not allowed to use operators like ‘+’, ‘-’, ‘*’, ‘/’, ‘++’, ‘–’ …etc.

Examples:
Input: 12
Output: 13

Input: 6
Output: 7

We can use bitwise operators to achieve this. Following are different methods to achieve same using bitwise operators.

Method 1
To add 1 to a number x (say 0011000111), we need to flip all the bits after the rightmost 0 bit (we get 0011000000). Finally, flip the rightmost 0 bit also (we get 0011001000) and we are done.


#include
 
int addOne(int x)
{
  int m = 1;
 
  /* Flip all the set bits until we find a 0 */
  while( x & m )
  {
    x = x^m;
    m <<= 1;
  }
 
  /* flip the rightmost 0 bit */
  x = x^m;
  return x;
}  
 
/* Driver program to test above functions*/
int main()
{
  printf("%d", addOne(13));
  getchar();
  return 0;
}

Method 2
We know that the negative number is represented in 2′s complement form on most of the architectures. We have the following lemma hold for 2′s complement representation of signed numbers.

Say, x is numerical value of a number, then

~x = -(x+1) [ ~ is for bitwise complement ]

(x + 1) is due to addition of 1 in 2′s complement conversion

To get (x + 1) apply negation once again. So, the final expression becomes (-(~x)).


int addOne(int x)
{
   return (-(~x));
}
 
/* Driver program to test above functions*/
int main()
{
  printf("%d", addOne(13));
  getchar();
  return 0;
}

Example, assume the machine word length is one *nibble* for simplicity.
And x = 2 (0010),
~x = ~2 = 1101 (13 numerical)
-~x = -1101
Interpreting bits 1101 in 2′s complement form yields numerical value as -(2^4 – 13) = -3. Applying ‘-’ on the result leaves 3. Same analogy holds for decrement. 
Note that this method works only if the numbers are stored in 2′s complement form.

Dijkstra's Algo

Algorithm
Illustration of Dijkstra's algorithm search for finding path from a start node to a goal node in a robot motion planning problem. Open nodes represent the "tentative" set. Filled nodes are visited ones, with color representing the distance: the greener, the further. Nodes in all the different directions are explored uniformly, appearing as a more-or-less circular wavefront as Dijkstra's algorithm uses a heuristic identically equal to 0.
Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.
Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
Mark all nodes except the initial node as unvisited. Set the initial node as current. Create a set of the unvisited nodes called the unvisited set consisting of all the nodes except the initial node.
For the current node, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6+2=8. If this distance is less than the previously recorded distance, then overwrite that distance. Even though a neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
When we are done considering all of the neighbors of the current node, mark it as visited and remove it from the unvisited set. A visited node will never be checked again; its distance recorded now is final and minimal.
The next current node will be the node marked with the lowest (tentative) distance in the unvisited set.
If the unvisited set is empty, then stop. The algorithm has finished. Otherwise, set the unvisited node marked with the smallest tentative distance as the next "current node" and go back to step 3.


 Pseudo Code 
   function Dijkstra(Graph, source):
      for each vertex v in Graph:           // Initializations
          dist[v] := infinity ;              // Unknown distance function from source to v
          previous[v] := undefined ;         // Previous node in optimal path from source
      end for ;
      dist[source] := 0 ;                    // Distance from source to source
      Q := the set of all nodes in Graph ;
      // All nodes in the graph are unoptimized - thus are in Q
      while Q is not empty:                 // The main loop
          u := vertex in Q with smallest dist[] ;
          if dist[u] = infinity:
              break ;                        // all remaining vertices are inaccessible from source
          end if ;
          remove u from Q ;
          for each neighbor v of u:         // where v has not yet been removed from Q.
              alt := dist[u] + dist_between(u, v) ;
              if alt < dist[v]:             // Relax (u,v,a)
                  dist[v] := alt ;
                  previous[v] := u ;
                  decrease-key v in Q;      // Reorder v in the Queue
              end if ;
          end for ;
      end while ;
      return dist[] ;
  end Dijkstra.

Segregate 0s and 1s in an Array

You are given an array of 0s and 1s in random order. Segregate 0s on left side and 1s on right side of the array. Traverse array only once.

Input array   =  [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]
Output array =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

Method 1 (Count 0s or 1s) 

1) Count the number of 0s. Let count be C.
2) Once we have count, we can put C 0s at the beginning and 1s at the remaining n – C positions in array.

Time Complexity: O(n)

The method 1 traverses the array two times. Method 2 does the same in a single pass.



Method 2 (Use two indexes to traverse)
Maintain two indexes. Initialize first index left as 0 and second index right as n-1.

Do following while left < right
a) Keep incrementing index left while there are 0s at it
b) Keep decrementing index right while there are 1s at it
c) If left < right then exchange arr[left] and arr[right]

This method is also called as Dutch National Flag Problem. With this approach , we can segregate 0s 1s 2s also. *** Refer Dutch National Flag ( Segregation of numbers).

Longest consecutive substring of 0 and 1

Given and Array of A[1..n] bits, find the length of longest consecutive substring of 0 and 1 such that number of 0s and 1s are equal 

temp=0;
1. For each index i, Just +1(the value of temp) when '1' is encountered; -1 in the other case and store in B[i];
2. Go through B, get each distinct value's min and max index
3. The biggest max - min is the result.

Sample:
Input: 1 0  0  0  0  1  1  1  0  0  1  0  1
B:     1 0 -1 -2 -3 -2 -1  0 -1 -2 -1 -2 -1

1: Min = Max = 0
0: Min = 1; Max = 7
-1: Min = 2; Max = 12
-2: Min = 3; Max = 11
-3: Min = Max = 4

The result is 10 :  0  0  1  1  1  0  0  1  0  1

Merging two sorted linked lists

Node* MergeLists(Node* list1, Node* list2){
    Node* mergedList;
    if(list1 == null && list2 ==null){//if both are null, return null
        return null;
    }
    if(list1 == null){//if list1 is null, simply return list2
        return list2;
    }
    if(list2 == null){//if list2 is null, simply return list1
        return list1;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
        mergedList = list1;
    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList = list2;
    }
    while(list1!=null && list2!=null){
        if(list1.data < list2.data){
            mergedList->next = list1;
            list1 = list1->next;
        }else{
            mergedList->next = list2;
            list2 = list2->next;
        }
    }
    if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
        mergedList->next = list2;
    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
        mergedList->next = list1;
    }
    return mergedList;
}

 Merging two Sorted Arrays 
public void merge(int[] A, int[] B, int[] C) {
      int i, j, k, m, n;
      i = 0;
      j = 0;
      k = 0;
      m = A.length;
      n = B.length;
      while (i < m && j < n) {
            if (A[i] <= B[j]) {
                  C[k] = A[i];
                  i++;
            } else {
                  C[k] = B[j];
                  j++;
            }
            k++;
      }
      if (i < m) {
            for (int p = i; p < m; p++) {
                  C[k] = A[p];
                  k++;
            }
      } else {
            for (int p = j; p < n; p++) {
                  C[k] = B[p];
                  k++;
            }
      }
}

Reverse a Linked List

/* a function to sort reverse list */
struct node *reverse(struct node *p)
{
        struct node *prev, *curr,*next;
        prev = NULL;
        curr = p;
        while (curr != NULL)
        {
                next = curr-> link;
                curr-> link = prev;
                prev = curr;
                curr = next;
        }
        return(prev);
}

Find nth largest in an Array

You have an array of numbers; you need to find the nth largest in the array in 0(n) Solution

Conventional Algo to find Max and Second Max : 1. First element becomes max and second MAX 2. For all elements in Array you compare each element with MAX if it's greater than MAX=element; and SECONDMAX=MAX; else if element > SECONDMAX then second=element.

Tournament Principle :
From the above picture we can see that we have found the max in the array. Now we know 9 is MAX but we can't say 7 is SECOND MAX since that would be wrong. Number of Comparison's to find MAX = (n/2) + logn(n) = (n-1) in the above case so the above algo is also optimal for finding MAX ; since conventional algo also takes the same. To find SECOND MAX take the players that were directly defeated by MAX. i.e. 9 DIRECTLY DEFEATED BY MAX = 8, 3, 7 If we play the above tournament among 8, 3, 7 we get 8 as second MAX we for this tournament we needed just 2 comparison's Total comparisons to find MAX and second MAX using tournament principle = (n/2) + log(n) + log(n) = (n-1) + log(n) Now to find kth MAX we can play (k/2) such tournaments since in one tournament we get MAX and second MAX..then exclude them and play the tournament again(k/2) times So total comparisons to find kth MAX using above method = (k/2) ((n-1) + log(n)) However in the conventional algo it would be (k/2 passes of array)(2n comparisons to find MAX and second MAX) = k * n So tournament algo is more optimal eg:: if k = 4 and n = 8 Comparison's by conventional algo = 4 * 8 = 32 Comparison's by Tournament algo = (4/2) ((7) + 3) = 2 * 10 = 20

Conventional Solution2: Using MAX HEAP Build a max heap in O(n) ; Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. So total time complexity = O(k logn) To understand building MAX heap in O(n) check http://en.wikipedia.org/wiki/Binary_heap

Code For 3rd largest

int third_biggest(int *arr, int size)
{
	int first = INT_MIN, second = INT_MIN, third = INT_MIN;
	for(int i=0;i first)
		{
			third = second;
			second = first;
			first = arr[i];
		}
		else if(arr[i] > second)
		{
			third = second;
			second = arr[i];
		}
		else if(arr[i] > third)
		{
			third = arr[i];
		}
	}
	return third;
}

Reverse a pair of elements in a linked list.

reverse a pair of elements in a linked list. abcd - badc

// returns head of new list
public Node reverseInPairs(Node head) {

Node first = head;
	Node second = first.next;



if (first == null || second == null) {
		return head; 
// can't reverse a singleton/empty list. head remains the same
	}

while (first != null && second != null) {
		temp = first.next.next;
		second.next = first;
                first.next = temp;
		first = temp;
		second = first.next;
	}

return head.next;
}

Detect Loop in a Linked List (faster)

In the last post we discussed about the regular two pointer approach and a bit about its background. Lets look into how we can make it a bit faster.

What can you do here to make it faster. In the regular approach, the faster pointer goes 2 nodes at a time and the slower pointer goes 1 node per iteration. You cannot really change the speed of the slower pointer, because you definitely need to check every node at least once. But what about the fast pointer? Why just have it go 2 nodes per iteration? Why not 3 or more? And what improvements can you get here? Well. the faster it goes the lesser, the number of assigments and null checks when you traverse the faster pointer. This will be helpful, especially when the cycle (loop) is large. But how can fast do can you go. Since you don’t really know, you could do an exponential advancement. What this means is that, start with 2 nodes per iteration, and see if the slower pointer meets it. If not, traverse 4 nodes in the next iteration, and then 8, 16, 32…

Here’s some sample code that illustrates this.

void LinkedList::IsLooped2() {
    LNode* first=head;
    LNode* second=head;
int i=0;
int k=1;
while(first) {
    first=first->next;
    i++;
    if(second==first) {
            cout < < "Found Loopn";
            return;
    }
    if(i==k) {
        second=first;
        k*=2;
    }
}

}

This is based on Richard Brents Algorithm . Other Operations on this *** Refer for removing the loop and other functionalities on this link .

CODE

/* Function to remove loop. Used by detectAndRemoveLoop() */
void removeLoop(struct node *, struct node *);

/* This function detects and removes loop in the list
  If loop was there in the list then it returns 1,
  otherwise returns 0 */
int detectAndRemoveLoop(struct node *list)
{
    struct node  *slow_p = list, *fast_p = list;

    while (slow_p && fast_p && fast_p->next)
    {
        slow_p = slow_p->next;
        fast_p  = fast_p->next->next;

        /* If slow_p and fast_p meet at some point then there
           is a loop */
        if (slow_p == fast_p)
        {
            removeLoop(slow_p, list);

            /* Return 1 to indicate that loop is found */
            return 1;
        }
    }

    /* Return 0 to indeciate that ther is no loop*/
    return 0;
}

 How to Remove the loop 
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.

 
/* Function to remove loop.
 loop_node --> Pointer to one of the loop nodes
 head -->  Pointer to the start node of the linked list */
void removeLoop(struct node *loop_node, struct node *head)
{
    struct node *ptr1 = loop_node;
    struct node *ptr2 = loop_node;
 
    // Count the number of nodes in loop
    unsigned int k = 1, i;
    while (ptr1->next != ptr2)
    {
        ptr1 = ptr1->next;
        k++;
    }
 
    // Fix one pointer to head
    ptr1 = head;
 
    // And the other pointer to k nodes after head
    ptr2 = head;
    for(i = 0; i < k; i++)
      ptr2 = ptr2->next;
 
    /*  Move both pointers at the same pace,
      they will meet at loop starting node */
    while(ptr2 != ptr1)
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
 
    // Get pointer to the last node
    ptr2 = ptr2->next;
    while(ptr2->next != ptr1)
       ptr2 = ptr2->next;
 
    /* Set the next node of the loop ending node
      to fix the loop */
    ptr2->next = NULL;
}

Detect Loop in a Single Linked List

The Trivial solutions either took too long or eat more memory. Here is a classic well known appraoch the does constant space O(1) and 0(n) space. This is based of Floyd’s cycle-finding algorithm published in the Journal of ACM is his paper Non-Deterministic Algorithms in 1967. There are many variants and improvements to this original solution. These alogrithms can be used for finding cycles in different Data Strucutres. I will explain how it works when applied to Linked Lists

The idea is to use 2 pointers P1 and P2 intialized to the head. Then traverse the two pointers starting from the head, with P1 moving 1 node at a time and P2 moving 2 nodes at a time. If there is indeed a cycle, the nodes will meet inside the loop, otherwise they will reach the tail.

The code below is a simple straightforward illustration of this. There are ways to make this more efficient. I will discuss this in the next post.

bool LinkedList::IsLoopedTwoPointer1() {
 LNode* first=head;
 LNode* second=head;

 while(first && second &&
           first->next && second->next &&
           second->next->next)
{
first=first->next;
second=second->next->next;
if(first==second)
{
    cout < < "Found Loop" << endl;
    return true;
}
 }
 return false;

}

Bread First Search

1. Enqueue the root node.
2. Dequeue a node and examine it.
   • If the element sought is found in this node, quit the search and return a result.
   • Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
3. If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
4. If the queue is not empty, repeat from Step 2.

Depth First Search

1. Push the root node onto a Stack.
2. Pop a node from the stack and examine it.
   • If the element sought is found in this node, quit the search and return a result.
   • Otherwise push all its successors (child nodes) that have not yet been discovered onto the stack. ( *Push Right first then Left )
3. If the stack is empty, every node in the tree has been examined – quit the search and return "not found".
4. If the stack is not empty, repeat from Step 2.

Doubly Linked Lists

To insert a node to the left of node M :

get_node(N)
N.right_link := M
N.left_link := M.left_link
M.left_link.right_link := N
M.left_link := N

To delete a node N :

N.left_link.right_link := N.right_link
N.right_link.left_link := N.left_link

Inverting a Linked List

We can invert a linked list in place using three pointers:

procedure INVERT(X)
p := X, q := 0
while p \= 0 do
r := q;
q:= p;
p := p.link
q.link := r
end X := q
end INVERT