K reverse a linked list with increasing K

Problem

Reverse k elements in the linked list such that k goes on increasing

Example
Eg.        1 - 2 - 3 - 4 - 5 - 6 - 7
output - 1 - 3 - 2 - 6 - 5- 4 - 7

Solution

You can take this problem here. Here we are just increasing k.

   public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) {
        
        ListNode<Integer> nextNode = headerNode.next;
        ListNode<Integer> startNode = null;
        ListNode<Integer> endNode = null;
        
        int k = 2;
        while (nextNode != null) {
            
            startNode = nextNode;
            endNode = nextNode;
            
            for (int i = 1; i < k; i++) {
                endNode = endNode.next;
                if (endNode == null) {
                    break;
                }
            }



            if (endNode != null) {
                // Save the node next to endNode
                nextNode = endNode.next;
                // Unlink the endNode
                endNode.next = null;
                // Reverse the list starting from startNode

                startNode = reverseListIterative(startNode);
                k++;
            } else {
                nextNode = null;
//              // Save the node next to endNode
//              nextNode = endNode.next;
//              // Unlink the endNode
//              endNode.next = null;
                // Reverse the list starting from startNode

                startNode = reverseListIterative(startNode);
            }

            if (headerNode == null) {
                headerNode = startNode;
            } else {
                headerNode.next = startNode;
                ListNode<Integer> temp = startNode;
                while(temp!=null){
                    if(temp.next==null){
                        break;
                    }
                    temp = temp.next;
                }
                headerNode = temp;
            }
        }

        return headerNode;
    }

    public static ListNode<Integer> reverseListIterative(ListNode<Integer> headerNode) {
        ListNode<Integer> prevNode = null;
        ListNode<Integer> currNode = headerNode;
        ListNode<Integer> nextNode = null;

        while (currNode != null) {
            nextNode = currNode.next;
            currNode.next = prevNode;
            prevNode = currNode;
            currNode = nextNode;
        }

        return prevNode;
    }
    

Time complexity - O(n)

Read More

Convert Binary Tree to Doubly linked list in level order

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below:

The output will be a double linked list like this:

Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list.
For traversing the tree, we'll use level / order traversal a.k.a breadth first search.

To construct the linked list, each node will have its left pointer point to the node in front of it and its right pointer point to the node behind it in the linked list. For instance, if node 1 is in front of node 2 and node 3 is behind node 2 in the linked list, we'll set left pointer of node 2 to node 1 and right pointer of node 2 to node 3 (see picture above)

#include<iostream>
#include<queue>
using namespace std;
struct Node
{
  int data;
  struct Node* left;
  struct Node* right;
};
struct Node* bt2DoubleLinkedList(struct Node* root)
{
  if (root == NULL)
    return NULL;
  queue nodeQueue;
  struct Node* head = root; //reference to head of the linked list
  struct Node* listIT = NULL; //current node being processed
  struct Node* prevNode = NULL; //previous node processed
  //initialize the stack
  nodeQueue.push(root);
  //convert to double linked list
  while (!nodeQueue.empty())
  {
    //process next node in stack
    prevNode = listIT;
    listIT = nodeQueue.front();
   
    nodeQueue.pop();
    //add left child to stack
    if (listIT->left != NULL)
      nodeQueue.push(listIT->left);
    //add right child to stack
    if (listIT->right != NULL)
      nodeQueue.push(listIT->right);
    //add current node to linked list
    if (prevNode != NULL)
      prevNode->right = listIT;
    listIT->left = prevNode;
  }
 
  //connect end node of list to null
  listIT->right = NULL;
  return head;
}

Explanation: the method accepts a pointer to the tree's root as argument and returns the pointer to the head node of the linked list:

1. If the root node is null, we return null because the tree is empty.
2. If the root is not null, we proceed by first creating a queue to store the the nodes. Why do we use queue? That is how we traverse the tree by level. Every time we reach a node, we store its children in the queue for later processing. Thus, the queue will always have something in it as long as there are still unvisited node in the tree.
3. Next, we create three pointers. head points to the head node of the linked list. listIT is our list iterator which used to build the list one node at a time. prevNode is the last node added into the list. We need to keep track of such node because we have to change the right pointer of that node to the node immediate after it, which is the node that listIT will point to.
4. We initialize the queue by adding the root into it. The reason is that we will use the condition of empty queue to end the while loop.
5. The while loop will run until no node left in queue to process. For each node in the queue, we do the following:
   
   prevNode = listIT gets reference to the last processed node because we are about to process a new node
   
   listIT = nodeQueue.front() gets reference to the top in the queue because we're going to add it into the list.
   
   nodeQueue.pop() removes the top node out of the queue.
   
   We then add the left and right child of the top node into the queue, so we can process them later. Notice that we only add the children if they are not null.
   
   Finally, we connect the top node to the linked list. First, we set the right pointer of the previous node (prevNode) to the top node. Then, we set the left pointer of the top node to the previous node. As the result, the top node becomes the end node of the linked list and the previous node completely breaks off the tree.
   
   
6. When the last node is added into the linked list and the while loop exits, we have a double linked list. The only thing left is to set the end node's right pointer (pointed to by listIT) to null because there is no more node to add into the list.

Read More

Number of steps required to convert string 1 to string2 when only bring character to first index operation is giving

Problem
Given 2 strings - s1 and s2, when only 1 operation is allowed - Moving character at a time but only to the first position.

Example
Example 1
Input
s1 = abcd
s2 = bacd

Output
Ans = 1
Reason, just move b forward and we get it.

Example 2
Input
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Output
Ans =7
Explanation
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Characters b,e,g are in the order, rest characters have to brought first.

Solution

This is a DP problem,  LCS of the 2 strings is adf, and rest of the character are moved forward, and rest of the characters will be moved forward.

Read More

Maximize the number of magical gems by passing through array of house

Problem
There was a thief, he has to pass through colored house - which can be red or blue, and contain 0 or more gems. The property of these gems is they multiply the previous gems by the current gems in the house. The houses are in array and thief can only visit once to steal the gems, with the goal of maximizing the gems. Find the range of house where he can maximize the gems in such a way that number of red houses are even.

Example
Gem array = 1 2 0 4 5 6 2 3
color array = 0 0 1 1 1 0 0 1 (r=1,b=0)
o/p = 20 (4*5)

Solution

This is similar to maximum product subarray, but there is another condition of red color.

Here is the code below:

int maximumMoney(int n, int[] colour, int[] gems) {
    int max = 1;
    int red = 0;
    int start = 0, end = 0;
    int actualMax=1;
    for(int i=0;i<gems.length;i++){
        if(gems[i]>0)
        {
            max = max*gems[i];
            end++;
            if(colour[i] == 1)
               red++;
            
               
        }else{
            if(actualMax < max){
                if(red%2==0)
                {
                    actualMax = max;

                }else{
                    int temp = max;
                    int startRed = -1, endRed = -1;
                    for(int i=start;i<end;i++){
                        if(colour[i]==1 && startRed==-1){
                           startRed = i;
                           endRed = i;
                        }else if(colour[i]==1)
                            endRed = i;
                    }
                    int tempProdStart = 1; tempEndProd = 1;
                    for(int i=start;i<=startRed;i++){
                        tempProdStart = a[i]*tempProdStart ;
                        
                    }
                    
                     for(int i=endRed;i<=end;i++){
                        tempEndProd= a[i]*tempEndProd;
                        
                    }
                    int minProd = Math.min(tempProdStart, tempEndProd);
                    
                    max = temp/minProd;
                    if(max > actualMax){
                        actualMax = max;
                    }
                        
                    
                }
                   
            }
              
            start = end+1;
            end = end + 1;
            
        }
    }
}

Time complexity - O(n)

Read More

Find the least wastage in cutting the Trees?

Problem
You are given n Trees with their heights in an array. and you are given a value k units , that much wood you need to collect. You can have an axe of any height you want but you can use only 1 axe when you choose.

Assume height to be integral value.

Solution

So, if height of the tree is H, and you cut it at height X from the ground then H-X will be used will be used. If there is only 1 tree, we will cut it at height X, such that H-X = k.

It is always possible to choose an axe height such that chopping all trees above this height will result in zero waste.
To see this, just sort the trees in descending order of height, and consider moving the axe height gradually down from the top of the tallest tree.

Suppose the tallest tree has height h. Notice that the function:

f(x) = total amount of wood cut by using an axe of height h - x to
       chop all trees of at least this height

• Sort the trees by their height in descending order
•  starts at 0 when x = 0, and is an increasing piecewise linear function of x, with no discontinuities. Every time x increases past the point when one or more trees just start to become choppable, the rate of change of f(x) increases, but this doesn't cause problems. 
• So for any desired level of wood y, just (conceptually) intersect a horizontal line of height y with the graph f(x), and drop a vertical line from this point down to the x axis to find its value. (How to actually do this in a program I leave as an exercise, but here's a hint: consider trees in decreasing height order to find the pair of adjacent x values x1, x2 such that chopping at h - x1 produces too little wood, and h - x2 produces too much.)

Reference

• http://stackoverflow.com/questions/18053325/algorithm-find-the-least-wastage-in-cutting-the-trees

Read More

Implement a function similar to diff command in linux

Problem

Give logic for implementing "diff" command in Linux.
Consider various test cases and explain what will happen in each. The two files are source code and are huge..
For e.g.
File 1: 1-2-3-4
File 2: 1-3-4-2

Solution

The operation of diff is based on solving the longest common sub-sequence problem.
In this problem, you have two sequences of items:
a b c d f g h j q z
a b c d e f g i j k r x y z
and you want to find a longest sequence of items that is present in both original sequences in the same order. That is, you want to find a new sequence which can be obtained from the first sequence by deleting some items, and from the second sequence by deleting other items. You also want this sequence to be as long as possible. In this case it is
a b c d f g j z
From a longest common subsequence it's only a small step to get diff-like output: if an item is absent in the subsequence but present in the original, it must have been deleted. (The '–' marks, below.) If it is absent in the subsequence but present in the second sequence, it must have been added in. (The '+' marks.)
e h i q k r x y
+ - + - + + + +


Resource

• http://www.careercup.com/questionthread?id=98911

Read More