Reverse alternate K nodes in a Singly Linked List

Example:

Inputs:   1->2->3->4->5->6->7->8->9->NULL and k = 3
Output:   3->2->1->4->5->6->9->8->7->NULL.

Algo

kAltReverse(struct node *head, int k)
  1)  Reverse first k nodes.
  2)  In the modified list head points to the kth node.  So change next 
       of head to (k+1)th node
  3)  Move the current pointer to skip next k nodes.
  4)  Call the kAltReverse() recursively for rest of the n - 2k nodes.
  5)  Return new head of the list.

Code

struct node *kAltReverse(struct node *head, int k)
{
    struct node* current = head;
    struct node* next;
    struct node* prev = NULL;
    int count = 0;   
 
    while (current != NULL && count < k)
    {
       next = current->next;
       current->next = prev;
       prev = current;
       current = next;
       count++;
    }

    if(head != NULL)
       head->next = current; 

    count = 0;
    while(count < k-1 && current != NULL )
    {
      current = current->next;
      count++;
    }
 
    if(current !=  NULL)
       current->next = kAltReverse(current->next, k);

Reverse a Linked List in groups of given size

Given a linked list, write a function to reverse every k nodes (where k is an input to the function). 
Example:
Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3 
Output:  3->2->1->6->5->4->8->7->NULL. 

Inputs:   1->2->3->4->5->6->7->80->NULL and k = 5
Output:  5->4->3->2->1->8->7->6->NULL. 


struct node *reverse (struct node *head, int k)
{
    struct node* current = head;
    struct node* next = NULL;
    struct node* prev = NULL;
    int count = 0;   
     
    /*reverse first k nodes of the linked list */
    while (current != NULL && count < k)
    {
       next  = current->next;
       current->next = prev;
       prev = current;
       current = next;
       count++;
    }
     
    /* next is now a pointer to (k+1)th node 
       Recursively call for the list starting from current.
       And make rest of the list as next of first node */
    if(next !=  NULL)
    {  head->next = reverse(next, k); }
 
    /* prev is new head of the input list */
    return prev;
}

Reverse a linked list

Iterative Method

static void reverse(struct node** head_ref)
{
    struct node* prev   = NULL;
    struct node* current = *head_ref;
    struct node* next;
    while (current != NULL)
    {
        next  = current->next; 
        current->next = prev;  
        prev = current;
        current = next;
    }
    *head_ref = prev;
}

Recursive Method

let’s say we are dealing with node 99 in the linked list image above – the Node coming after node 99 (node 37) is represented by Node 99 -> next. If we want node 37 to point back to node 99 (which is what we would want if we are reversing the nodes), then we would set the next pointer of node 37 to point back to Node 99, which in pseudocode would look like Node99 -> next -> next = Node 99.

We would also need to get rid of the pointer from node 99 to node 37 so we would have to set Node 99 -> next to NULL.

CODE

public void recursiveReverse(Node currentNode )
{  
 if(currentNode == NULL)
    return;

if(currentNode.next == NULL) 
{ 
head = currentNode; 
return;
}

recursiveReverse(currentNode.next);
currentNode.next.next = currentNode;
currentNode.next = null; //set "old" next pointer to NULL
}

Find the largest multiple of 3

1.Sort the array in increasing order.
2.Queue q0 stores the elements which on dividing by 3 gives remainder 0.
3.Queue q1 stores the elements which on dividing by 3 gives remainder 1.
4.Queue q2 stores the elements which on dividing by 3 gives remainder 2.
5.Find the sum of all the given digits.Let it be ‘s’.
6.If s is divisible by 3,goto step 9.
7.If s when divided by 3 gives remainder 1:
Remove one item from q1.
If q1 is empty,remove two items from q2.
If q2 contains less than two elements,number is not possible.
8.If s when divided by 3 gives remainder 2:
Remove one item from q2.
If q2 is empty,remove two items from q1.
If q1 contains less than two elements,number is not possible.
9.Empty all queues into an temporary array and sort it in decreasing order.

CODE

int findMaxMultupleOf3( int* arr, int size )
{
    // Step 1: sort the array in non-decreasing order
    qsort( arr, size, sizeof( int ), compareAsc );
 
    // Create 3 queues to store numbers with remainder 0, 1 and 2 respectively
    Queue* queue0 = createQueue( size );
    Queue* queue1 = createQueue( size );
    Queue* queue2 = createQueue( size );
 
    // Step 2 and 3 get the sum of numbers and place them in corresponding queues
    int i, sum;
    for ( i = 0, sum = 0; i < size; ++i )
    {
        sum += arr[i];
        if ( (arr[i] % 3) == 0 )
            Enqueue( queue0, arr[i] );
        else if ( (arr[i] % 3) == 1 )
            Enqueue( queue1, arr[i] );
        else
            Enqueue( queue2, arr[i] );
    }
 
    // Step 4.2: The sum produces remainder 1
    if ( (sum % 3) == 1 )
    {
        // either remove one item from queue1
        if ( !isEmpty( queue1 ) )
            Dequeue( queue1 );
 
        // or remove two items from queue2
        else
        {
            if ( !isEmpty( queue2 ) )
                Dequeue( queue2 );
            else
                return 0;
 
            if ( !isEmpty( queue2 ) )
                Dequeue( queue2 );
            else
                return 0;
        }
    }
 
    // Step 4.3: The sum produces remainder 2
    else if ((sum % 3) == 2)
    {
        // either remove one item from queue2
        if ( !isEmpty( queue2 ) )
            Dequeue( queue2 );
 
        // or remove two items from queue1
        else
        {
            if ( !isEmpty( queue1 ) )
                Dequeue( queue1 );
            else
                return 0;
 
            if ( !isEmpty( queue1 ) )
                Dequeue( queue1 );
            else
                return 0;
        }
    }
 
    int aux[size], top = 0;
 
    // Empty all the queues into an auxiliary array.
    populateAux (aux, queue0, queue1, queue2, &top);
 
    // sort the array in non-increasing order
    qsort (aux, top, sizeof( int ), compareDesc);
 
    // print the result
    printArr (aux, top);
 
    return 1;
}

Clone a linked list with next and random pointer

ALGO

The idea is to use Hashing. Below is algorithm.
1. Traverse the original linked list and make a copy in terms of data.
2. Make a hash map of key value pair with original linked list node and copied linked list node.
3. Traverse the original linked list again and using the hash map adjust the next and random reference of cloned linked list nodes.

CODE

public class Node {
    private Node next;
    private Node random;
    private String data;
    // getters and setters omitted for the sake of brevity
}

private Node deepCopy(Node original) {

    Map<Node, Node> map = new HashMap<Node, Node>();
    // We scan the original list and for each Node x we create a new 
    // Node y whose data is a copy of x's data, then we store the 
    // couple (x,y) in map using x as a key.

    Node x = original;
    while (x != null) {
        Node y = new Node();
        y.setData(new String(x.getData()));
        y.setNext(null);
        y.setRandom(null);
        map.put(x, y);
        x = x.getNext();
    }

    // We scan again the original list and 
    // we set the pointers buildings the new list

    x = original;
    while (x != null) {
            // we get the node y corresponding to x from the map
        Node y = map.get(x);
            // let x' = x.next; y' = map.get(x') is the new node 
            // corresponding to x'; so we can set y.next = y'
        y.setNext(map.get(x.getNext()));
            // let x'' = x.random; y'' = map.get(x'') is the new 
            // node corresponding to x''; so we can set y.random = y''
        y.setRandom(map.get(x.getRandom()));
        x = x.getNext();
    }

    return map.get(original);
}

No. of paths in integer array

An integer array {3,1,2,7,5,6}. One can move forward through the array either each element at a time or can jump a few elements based on the value at that index.

count the number of possible paths to reach the end of the array from start index.

Ex – input {3,1,2,7,5,6}

sol[6] = 1;
for (i = 4; i>=0;i--) {
     sol[i] = sol[i+1];
     if (i+input[i] < 6 && input[i] != 1)
         sol[i] += sol[i+input[i]];             
}

return sol[0];

DFA based division

Example

Suppose we want to check whether a given number ‘num’ is divisible by 3 or not

1. When we are at state 0 and read 0, we remain at state 0.
2. When we are at state 0 and read 1, we move to state 1, The number so formed(1) in decimal gives remainder 1.
3. When we are at state 1 and read 0, we move to state 2, The number so formed(10) in decimal gives remainder 2.
4. When we are at state 1 and read 1, we move to state 0, The number so formed(11) in decimal gives remainder 0.
5. When we are at state 2 and read 0, we move to state 1, The number so formed(100) in decimal gives remainder 1.
6. When we are at state 2 and read 1, we remain at state 2, The number so formed(101) in decimal gives remainder 2.

The transition table looks like following:

state   0   1
_____________
0      0   1
1      2   0
2      1   2

Let us check whether 6 is divisible by 3?
Binary representation of 6 is 110
state = 0
1. state=0, we read 1, new state=1
2. state=1, we read 1, new state=0
3. state=0, we read 0, new state=0
Since the final state is 0, the number is divisible by 3.

Let us take another example number as 4
state=0
1. state=0, we read 1, new state=1
2. state=1, we read 0, new state=2
3. state=2, we read 0, new state=1
Since, the final state is not 0, the number is not divisible by 3. The remainder is 1.

Note that the final state gives the remainder.

Make a fair coin from a biased coin

Question

You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with 40% probability. Write a new function that returns 0 and 1 with 50% probability each. Your function should use only foo()

Answer
We call foo() two times. Both calls will return 0 with 60% probability. So the two pairs (0, 1) and (1, 0) will be generated with equal probability from two calls of foo().
(0, 1): The probability to get 0 followed by 1 from two calls of foo() = 0.6 * 0.4 = 0.24
(1, 0): The probability to get 1 followed by 0 from two calls of foo() = 0.4 * 0.6 = 0.24
So the two cases appear with equal probability. The idea is to return consider only the above two cases, return 0 in one case, return 1 in other case. For other cases [(0, 0) and (1, 1)], recur until you end up in any of the above two cases.

int my_fun() 
{
    int val1 = foo();
    int val2 = foo();
    if (val1 == 0 && val2 == 1)
        return 0;   // Will reach here with 0.24 probability
    if (val1 == 1 && val2 == 0)
        return 1;   // // Will reach here with 0.24 probability
    return my_fun();  // will reach here with (1 - 0.24 - 0.24) probability
}

Check divisibility by 7

A number of the form 10a + b is divisible by 7 if and only if a – 2b is divisible by 7
Example:

the number 371: 37 – (2×1) = 37 – 2 = 35; 3 – (2 × 5) = 3 – 10 = -7; thus, since -7 is divisible by 7, 371 is divisible by 7.

Solution
return isDivisibleBy7( num / 10 – 2 * ( num – num / 10 * 10 ) );

LOGIC

   10.a + b 
after multiplying by 2, this becomes
   20.a + 2.b 
and then
   21.a - a + 2.b 
Eliminating the multiple of 21 gives
   - a + 2b
and multiplying by -1 gives
    a - 2b

Equal Probability

Question

Given a function foo() that returns integers from 1 to 5 with equal probability, write a function that returns integers from 1 to 7 with equal probability using foo() only.

Solution

If we somehow generate integers from 1 to a-multiple-of-7 (like 7, 14, 21, …) with equal probability, we can use modulo division by 7 followed by adding 1 to get the numbers from 1 to 7 with equal probability.
We can generate from 1 to 21 with equal probability using the following expression.

 5*foo() + foo() -5

Let us see how above expression can be used.
1. For each value of first foo(), there can be 5 possible combinations for values of second foo(). So, there are total 25 combinations possible.
2. The range of values returned by the above equation is 1 to 25, each integer occurring exactly once.
3. If the value of the equation comes out to be less than 22, return modulo division by 7 followed by adding 1. Else, again call the method recursively. The probability of returning each integer thus becomes 1/7.

CODE

int my_rand() // returns 1 to 7 with equal probability
{
    int i;
    i = 5*foo() + foo() - 5;
    if (i < 22)
        return i%7 + 1;
    return my_rand();
}