Constant time max operation on stack

Constant time max operation on stack

We understood stack data structure, operations on it and some examples problems which can be solved using stack. Let’s take problem which is actually based on stack and with the help of other data structures, how can make it more efficient for certain function. Today’s problem is to implement constant time max operation on stack.

To elaborate, you have been given a stack, where elements are pushed and popped randomly. At any given point of time, you have to tell max of all the elements present in stack.
For example : we have stack, we push 5,3,1, current max in stack is 5; we push 6 next, current max is 6 now. How about we pop 6 back. Current max goes back to 5 again.

Constant time max operation: Line of thoughts

Push and pop operation in a stack are already constant time operations. Let’s concentrate on max operation.
If always just pushed on to stack, it would have been easy to just keep track of ma of all the elements we pushed on to stack. However if we are popping out from stack, this may not be as easy. Max will change if the element just popped from stack was current max. What can we do? We keep track of previous max just before the current max. What if next operation is again pop and it pops out the new current max. Again, we have to keep track of previous to previous max.
Are you getting some hint here? We have to keep track of all the max we ever saw while operating on stack in reverse order. That means the max we saw the last, goes out first. LIFO pattern and what better data structure than stack to implement that.

Idea is to have an auxiliary stack which stores all the max seen till a given point of time. Top of this auxiliary stack would be current max. What happens when pop happens on original array? We check if popped element is equal to top element of auxiliary array, that means popped element was current max. So we pop that from auxiliary stack too.

Let’s take an example and see if it works? To start with, both stacks are empty. Now, you add 2 as first element on to stack. Since auxiliary stack is empty, we add 2 on to that stack too.

Push 3 on to stack. Push operation so check if current top of aux stack is less than new element pushed. If yes, push new element to aux stack too.

Push 5 on to stack. Again, push operation and new push element is greater than top of aux stack, we push 5 there too.

Now, push 1. Tricky case. Push 1 on to original stack, but since new element is less than current top of aux stack, nothing gets pushed on aux stack.

Pop from stack now. 1 is popped, it is not equal to current top on aux stack, nothing happens.

Pop from stack again, this time popped element is equal to current max, so we have pop from aux stack too. If we are asked max at this point of time, answer would be 3.

Constant time max operation on stack : Implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> auxStack;

    public MaxStack() {
        stack = new Stack();
        auxStack = new Stack();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek();
        //Push on max stack only if max value is being changed.
        if (max <= x) auxStack.push(x);
        stack.push(x);
    }

    public int pop() {
        int returnValue = stack.pop();
        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return auxStack.peek();
    }

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack();
        while (top() != max) buffer.push(pop());
        pop();
        while (!buffer.isEmpty()) push(buffer.pop());
        return max;
    }
}

Complexity of implementation of constant time max operation stack is O(n) in terms of space, with O(1) time complexity for push, pop and max operation.

Wait, interviewer is not satisfied with this only. What we solve is just reporting the max element in stack at a given point of time. What if we were asked to implement pop max element from stack? Well, first of all finding the max element works as it is. However, popping max element requires popping out all element before max, popping out max and then pushing back all other elements again. Quite a lot of work, even when max operation is O(1).

Which data structure allows us to remove an element in constant time? It’s doubly link list. Once you know which node is to be removed, all we have to do is link previous node to next node. If we implement our original stack as doubly linked list, popping max from stack is O(1) operation without moving any other element on stack.

However finding the node in doubly linked list itself is O(n) operation. Back to square one. What would be helpful is that instead of just storing the max element, we store node address of max in doubly linked list. So in our aux stack, we do not store primitive data type, but a pointer to node which is current max.

Let’s see how it works? We follow the same process of finding the max as explained in earlier solution. It starts with pushing element 2 on to stack. This creates the first node on DLL and stores the pointer on stack.

Now, we push 3 on to stack. Since this is greater than current max being pointed to by top of aux stack, we push that to DLL and store the pointer as max pointer on aux stack.

As for 3, same thing happens when 5 is pushed on to stack.

Since new element pushed is less than current max, it’s pointer is not pushed on to aux stack.
constant time max operation on stack

After pushing 1, we want to pop max. Step 1 would be to fetch the node pointer for current max. Go to that node in doubly linked list. Remove that node from DLL and then remove the pointer from top of stack.

Make a note that whenever, new pushed element is equal to current max, push that on aux stack too. Why?

Let’s see the implementation of this method using doubly linked list.

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackDLL {
    private DoubleLinkedList dll;
    private Stack<ListNode<Integer>> auxStack;

    public MaxStackDLL() {
        auxStack = new Stack();
        dll = new DoubleLinkedList();
    }

    public void push(int x) {
        int max = auxStack.isEmpty() ? x : auxStack.peek().getData();
        //Push on max stack only if max value is being changed.
        ListNode<Integer> newNode = dll.insertAtHead(x);
        if (max <= x) auxStack.push(newNode);
    }

    public int pop() {
        ListNode<Integer> returnValue = dll.deleteAtHead();

        //Pop from aux stack only if ax value is being popped out.
        if(auxStack.peek() == returnValue) {
            auxStack.pop();
        }
        return returnValue.getData();
    }

    public int peekMax() {
        return !auxStack.isEmpty() ? auxStack.peek().getData() : -1;
    }

    public int popMax() {
        return auxStack.isEmpty() ? -1 : dll.deleteNode(auxStack.pop()).getData();
    }
}

Doubly linked list class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class DoubleLinkedList {

    ListNode<Integer> head;

    public DoubleLinkedList(){
        head = null;
    }

    public boolean isEmpty(){
        return this.head == null;
    }

    public ListNode<Integer> insertAtHead(int data){
        if(this.isEmpty()) {
            this.head = new ListNode<Integer>(data);
            return this.head;
        }
        /*
            We are inserting node at head. So following things happen
            1. Create a new node.
            2. Set next of new pointer to current head.
            3. Set prev of head to new node
            4. Make new node as head of linked list
          */
        //First two steps are done here
        ListNode<Integer> newNode = new ListNode<Integer>(data,this.head, null);
        //Step 3.
        this.head.setPrev(newNode);
        //Step 4.
        this.head = newNode;

        return this.head;
    }

    public ListNode<Integer> deleteAtHead(){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node at head. So following things happen
            1. Set temporary node point to head.
            2. Move head to next of node.
            3. Set prev of new head to NULL.
            4. Free the temp node.
          */
        ListNode<Integer> tempNode = this.head;
        this.head = this.head.getNext();
        this.head.setPrev(null);

        return tempNode;
    }

    public ListNode<Integer> deleteNode(ListNode<Integer> node){
        if(this.isEmpty()) {
            return null;
        }
        /*
            We are deleting node in between. So following things happen
            1. If node has prev, set node.prev.next = node.next.
            2. If node has next, set node.next.prev = node.prev
        */
        if(node.getPrev() != null) node.getPrev().setNext(node.getNext());
        if(node.getNext() != null) node.getNext().setPrev(node.getPrev());

        return node;
    }
}

ListNode class is as follows

package com.company;

/**
 * Created by sangar on 22.9.18.
 */
public class ListNode<T> {
    private T data;

    private ListNode<T> next;
    private ListNode<T> prev;

    public ListNode(T data){
        this.data = data;
        next = null;
        prev = null;
    }

    public ListNode(T data, ListNode<T> next, ListNode<T> prev){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    public ListNode<T> getNext(){
        return this.next;
    }

    public ListNode<T> getPrev(){
        return this.prev;
    }

    public void setPrev(ListNode<T> newNode){
        this.prev = newNode;
    }

    public void setNext(ListNode<T> newNode){
        this.next = newNode;
    }

    public T getData(){
        return this.data;
    }
}

Tester class is given below. Can you add more test cases to this?

package test;

import com.company.MaxStackDLL;
import org.junit.jupiter.api.Test;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 22.9.18.
 */
public class MaxStackTest {


    MaxStackDLL tester = new MaxStackDLL();
    @Test
    public void popMaxTest() {

        tester.push(2);
        tester.push(3);
        tester.push(5);
        tester.push(1);

        assertEquals(5, tester.popMax());
        assertEquals(3, tester.popMax());
    }
}

Time complexity of push, pop and popMax is O(1). There is additional space requirement which is O(n).

Please share if there is something wrong or missing. If you are interested in taking personalized coaching by our experienced coaches, please reach out to us at communications@algorithmsandme.com

Implement queue using stack

Implement queue using stack

In last post, we learned about stack data structure, in this post, we will discuss another data structure called queue. However, problem at hand is to implement queue using stack. Implement following functions on queue using stack
1. push() : inserts element at the back of queue.
2. pop() : removes element from front of the queue.
3. peek() : return element at front of the queue.
4. empty() : returns true if there is no element in queue.

Keep in mind that you can only use standard stack operations : push(), pop(), peek() and empty()

Stack is data structure where the element which is entered at top is taken out from top. It’s called LIFO pattern. Oppose to that queue is a FIFO data structure, where elements are entered at the rear and taken out from front. So effectively, we have to implement a FIFO data structure using LIFO data structure.

Implement queue using stack : Line of thoughts

To implement a FIFO using LIFO data structure, we need two stacks.

Push()
When element is inserted i.e push() operation, new element has to be pushed down the stack at bottom, as this should be the last element to be popped. So, to push an element in queue, we will take out all existing elements from stack s1 and put them into stack s2. Now, push the new element on to stack s1. At last, pop all elements from stack s2 back to stack s1. Below picture shows what happens when you we push 3 to queue and what happens behind the scene using stacks.

implement queue using stack

Complexity of push operation with this method is O(n). If there are n elements already inserted into queue, inserting a new element will require n pops from s1, n pushes to s2, then n pops from s2 and then again pushes to s1.

Pop()
If we follow the push operation described above, pop operation would be nothing but to return top of s1, which is constant operation with complexity of O(1).

Peek and empty functions also run always on stack s1. For peek, return s1.peek() and for empty return s1.empty()

Queue with stack : Push O(n), pop O(1) implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 23.9.18.
 */
public class QueueWithStack {
    private Stack<Integer> s1;
    private Stack<Integer> s2;

    public QueueWithStack(){
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x){
        if(s1.empty()) s1.push(x);
        else{
            while(!s1.empty()){
                s2.push(s1.pop());
            }
            s2.push(x);
            while(!s2.empty()){
                s1.push(s2.pop());
            }
        }
    }

    public int pop(){
        if(s1.empty()) return -1;
        return s1.pop();
    }

    public boolean isEmpty(){
        return s1.empty();
    }

    public int peek(){
        return s1.peek();
    }
}

Test class for above implementation would be:

package test;

import com.company.QueueWithStack;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class QueueWithStackTest {

    QueueWithStack tester = new QueueWithStack();
    @Test
    public void queueTest() {

        tester.push(2);
        tester.push(3);
        tester.push(5);
        tester.push(1);

        assertEquals(2, tester.pop());
        assertEquals(3, tester.pop());
        assertEquals(5, tester.peek());
        assertEquals(false, tester.isEmpty());
    }
}

Can we do better than O(n) while pushing element in queue?

Queue with stack : Push O(1), pop amortized complexity O(1) implementation

Push()
What if we push on s1 as it is. What does it change? It make push operation on queue O(1).

Pop()
How does it impacts pop operation? If we pop all element from s1 and push them onto s2, at the top of s2 is actually the element we need. Also, due to this pop and push operation, s2 now contains all the elements in correct pop order for queue.
So idea is to always push in s1 as it is, however when popping out, check if s2 is empty or not? If not, then pop from s2 and return, if it is empty, pop all elements from s1 and push them all on s2 and return the top.

implement queue with stacks

How does it impact the performance? Well, it is true that if there is not element in s2, we have pop and push on s2, which has complexity of O(n). HOwever, all subsequent pop operations are O(1), this is called amortized complexity of O(1).

Empty()
Queue to be empty, there should not any element in either s1 or s2.

Peek()
If s2 is empty, then pop from s1 and push on to s2 and then return peek of s2.

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 23.9.18.
 */
public class QueueWithStackOptimized {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    private int front;

    public QueueWithStackOptimized(){
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x){
        if(s1.empty()) front = x;
        s1.push(x);
    }

    public int pop(){
        if(!s2.empty()) return s2.pop();
        if(!s1.empty()) return -1;

        while(!s1.empty()){
            s2.push(s1.pop());
        }
        return s2.pop();
    }

    public boolean isEmpty(){
        return s1.empty() && s2.empty();
    }

    public int peek(){
        if(!s2.empty()) return s2.peek();

        return front;
    }
}

Complexity of peek function is again amortized to O(1). Can you write test cases for implemented queue?

Reference : Leetcode

Please share if there is something wrong or missing. If you want to have personal coaching from our experienced coaches, please reach out to us at communications@algorithmsandme.com

Stacks : Stock span problem

Stock span problem

Stock span problem is commonly asked in Google and Amazon interviews and taught as the application of stack data structure in universities. Let’s define the problem :

Given a list of prices of a single stock for N number of days, find stock span for each day. Stock span is defined as a number of consecutive days prior to the current day when the price of a stock was less than or equal to the price at current day.

For example, {100,60,70,65,80,85} span will be {1,1,2,1,4,5}.

stock span problem

If you are preparing for an interview, you can signup for a free session to find a coach to help you with your preparation.

For the first day span is always 1. In the example we can see that for day 2 at 60, there is no day before it where the price was less than 60. Hence span is 1 again. For day 3, the price at day 2 (60) is less than 70, hence span is 2. Similarly, for day 4 and day 5. Remember days should be consecutive, that why span for day 4 is 1 even though there was a day 2 where the price was less than 65.

stock span problem example

Stock span problem is slightly complicated to understand but the solution is pretty easy.

Let’s look at the solution. Brute force solution would be: For each day, say current day, scan all days prior to it and increment span till the price of the stock is higher than current day. Simple implementation, however complexity is O(n2) where n is number of days.

Stock span problem : Solution

If we observe the brute force algorithm, it is evident that we are interested in a day which has stock price was greater than the current day’s stock price. So, we need to check the last price which was greater than the current day’s price. Getting some hint? Which is the data structure which allows you to maintain the last price and see it first? What should be the invariant here? We should be using a stack for sure. The invariant is that stack elements should be in increasing order of price. The element at the top should be the maximum price seen till current day. How can we maintain this?

Go through each day stock price, check if the current price on top of the stack is less than the current day’s price. If yes, pop out till price on top of the stack is greater than current day’s price, stock span of the current day is the difference between the day of price on top of the stack and current day.
Storing index of last greatest stock price would make things easier as compared to storing actual stock price on the stack. Hence day is store i on stack, price[i] will give us the price of stock on day i.

Stock span problem : Algorithm

  1. Initialize span of day 1 (i=0) as 1 and put on to stack.
  2. For i=1 to n, do following
  3. While price[stack.top()] < price[i] and !stack.isEmpty(), stack.pop()
  4. If price[stack.top()] > price[i], span = (i - stack.top())
  5. Push current day index i on to stack.

Let's take an example and see if this works? Let's say prices are given on certain days are as following: 100, 60, 70, 65, 80, 85, 200

As per algorithm, we will put span[0] = 1 and stack will be [0].
On day 2, stock price is 60. Stock price on day at the top of stack is 100, which is greater than 60. So span[1] = 1- 0 = 1. Stack = [0,1]
On day 3, stock price is 70. We will pop from the stack till price[stack.top()] < 70, which obviously pops out 1 as price[1] = 60. So span[2] = 2 – 0 = 2. Push new price on stack, stack = [0,2]
On day 4, stock price is 65. price[stack.top()] > price[3], so span[3] = 3-2=1. Stack = [0,2,3]
On day 5, stock price is 80, now we pop out 3 and 2 from stack as price[2] and price[3] are less than 80. span[4] = 4-0 = 4. stack = [0,4].
On day 6, stock price is 85, now we pop out 4 from stack as price[4] is less than 85. span[5] = 5-0 = 5. stack = [0,5].
On day 7, stock price is 200, now we pop out 5 and 0 from stack as price[5] and price[0] are less than 200. Now stack is empty, at this point, span[6] = 6. stack = [6].

Stock span problem : Implementation

package com.company;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created by sangar on 18.9.18.
 */
public class StockSpan {
    public static int[] stockSpan(int[] prices){

        Stack<Integer> s = new Stack();
        int[] span = new int[prices.length];

        //Step 1. Initialization
        span[0] = 1;
        s.push(0);

        for(int i=1; i<prices.length; i++){
            //Find the price on stack which is greater than current day's price
            while(!s.empty() && prices[i] > prices[s.peek()])
                s.pop();

            if(s.empty())
                span[i] = i+1;
            else
                span[i] =  i - s.peek();

            //Push current day onto top of stack
            s.push(i);
        }

        return span;
    }

    public static void main(String args[]){
        int prices[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98, 200};
        int[] span = stockSpan(prices);

        Arrays.stream(span).forEach(System.out::println);

    }
}

If you want to understand the basic implementation of stack data structure, this is the C code for you.

#include<stdio.h>
#include<stdlib.h>

#define STACK_SIZE 100

typedef struct stack{
        int top;
        int items[STACK_SIZE];
}stack;
 
void push(stack *ms, int item){
   if(ms->top < STACK_SIZE-1){
       ms->items[++(ms->top)] = item;
   }
   else {
       printf("Stack is full\n");
   }
}
 
int pop (stack *ms){
   if(ms->top > -1 ){
       return ms->items[(ms->top)--];
   } 
   else{
       printf("Stack is empty\n");
   }
}
int peek(stack ms){
  if(ms.top < 0){
      printf("Stack empty\n");
      return 0;
   }
   return ms.items[ms.top];
}
int isEmpty(stack ms){
   if(ms.top < 0) return 1;
   else return 0;
}

void stockSpan(int prices[], int days){

 stack ms;
 int i;

 int span[days];

 if(days ==0) return;

 span[0] = 1;
 ms.top = -1;
 
 push(&ms, 0);

 for(i=1; i<days; i++){
   while(!isEmpty(ms) && prices[i] > prices[peek(ms)])
      pop(&ms);
      
   if(isEmpty(ms)){
      span[i] = i+1;
   }
   else{
     span[i] =  i - peek(ms);
   }
   push(&ms, i);
 }

 for(i=0; i<days; i++)
   printf("%d  ", span[i]);

 printf("\n");
}
/* Driver program */
int main(){
 
 //int prices[6] ={100,60,70, 65, 85, 80};
 int prices[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98, 200};

 int n  = sizeof(prices)/sizeof(prices[0]);
 
 stockSpan(prices, n);
 return 0;
}

Complexity of stock span algorithm is O(n) along with space complexity of O(n).

Now that you have learned the concept, can you solve similar problem on HackerEarth

Please reach out if there is anything missing or wrong. If you are interested in taking coaching by our experienced software engineers, please contact us, We would be glad to help you.

Infix to postfix conversion using stack

Infix to postfix conversion using stack

Let’s see one more problem which use stack in solution. Problem is to convert infix to postfix expression.
Infix expression is an expression where operator comes in between two operand. For example: A + B is an infix expression as operator + come in between two operands A and B. This is how we human being write and interpret expressions.
Postfix expression is where operator comes after operands like AB+C* is a postfix expression. This is how machines interpret and evaluate expressions.

Infix to postfix conversion : Line of thought

First thing we need to take care of while converting infix expression to postfix is precedence order of operators. Precedence order decides which operation happens in expression before others. For example, if expression is A + B * C, B * C is evaluated first before A+B as * as higher precedence over +.
Another example would be (A + B) * C, in this case A + B is evaluated first, as () has higher precedence over any other operator.

Let’s take an example and see how to convert an infix expression to postfix.

Infix -> A + B

We start with scanning each literal from the expression.As we have to put operator at the end, we will store operator when we see it and put it after operands. In this case, first we see A, we put this literal on output. So, current output would be A.
Next we see +, since it is an operator, we store it on storage. Next literal is B, we append it to output. Current output is AB. We finished scanning string, we will put all the operators on storage. So, the output will be AB+.

Let’s take another example, and see if we can come up with an algorithm.

Infix -> A + B * C

We scan the string, put A on output string. We put + on storage, and then put B on output. Again, we put * on to storage, and then operand C on to output string.
Now, we reached to the end of string, so we put all the operators on storage behind output string. But question is which order operators should be appended to output. If there is no precedence conflict, we should put the last seen operator first. So output will be ABC*+. There is important thing to be noted here : Last in first out pattern and to achieve that, we will use stack to store operators.

Infix to postfix conversion : Algorithm

Now, we know the data structure to use, there is one more thing to understand is how to deal with precedence order.Let’s take an example, and see how it works.

Infix -> A * B + C

Put A on to output, * on to stack, B again on to output. Everything same as above example. Next we see +, that’s where we have to worry. Operator on top of stack is * which has high precedence than +. It means A * B needs to be evaluated before C is added to the result. To achieve this, we will pop all operators from stack which have higher precedence than current operator and append it to output. After that, we will put + on to stack.Current output would be AB*
Append C to output, as we finished scanning string, we will pop all elements on stack and append it to output string. Hence, output would be AB*C+

Let’s apply this algorithm to an expression and see how it works. Expression is 4*5+6/7. Initial state of output and stack would be

Start with first digit 4, it is an operand onto output string.

Next character is *, push it on to stack.

Next is 5, not an operator, put it with 4 in output string, so current state of stack and output string will be as follows

Next we get ‘+’, this is an operator. Here is some work we need to do.
Check if there is an operator already encountered, which has higher precedence than current operator. If not, then we are fine, we will add this operator in the set of operators onto stack but not yet added to postfix expression.

If there is operator which has higher precedence, then take out one by one all such operator (in the order they were encountered), till an operator with lower precedence is seen. Add all these operators to the postfix expressions string. Put the current operator in the set.
In this case + has lower precedence than *, so we will pop * from stack and put it on output string.

Next character is 6. Add it to postfix exp, it becomes 45*6 .

Now we encounter ‘/’. Since it has higher priority than + , it gets pushed to list.

Check 7 and add it to output postfix expression, 45*67.

Now we reached at the end of the expression. Now go to stack and pop operators one by one and add them to postfix expression string.

convert infix to postfix expression

Infix to postfix conversion : implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 23.9.18.
 */
public class InfixToPostfix {
    /* This function return true or false based on whether
        character is operator or not
    */
    public static boolean isOperator(char op){
        if(op == '+' || op == '-' || op == '*' || op == '/' || op =='%')
            return true;
        return false;
    }

    /* This function returns associated precedence to an operator */
    public static int precedence(char op){
        switch (op){
            case '+' :
            case '-' :
                return 1;
            case '/' :
            case '*' :
                return 2;
            case '%' :
                return 3;
            default :
                return 4;
        }
    }

    /* This function tell if the op1 has lower precedence than op2 */
    public static boolean isLowerPrecedence(char op1, char op2){
        if(precedence (op1) < precedence(op2))
            return true;
        return false;
    }
    public static String convertInixToPostfix(String infix){
        Stack<Character> stack = new Stack();
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<infix.length(); i++){
            char currentCharacter = infix.charAt(i);
            //If it's an operand, put it on output string
            if(!isOperator(currentCharacter)){
                sb.append(currentCharacter);
            }
            else{
                if(stack.empty()) stack.push(currentCharacter);
                else{
                    while(!stack.empty()
                    && isLowerPrecedence(currentCharacter, stack.peek())){
                        sb.append(stack.pop());
                    }
                    stack.push(currentCharacter);
                }
            }
        }
        while(!stack.empty()) sb.append(stack.pop());

        return sb.toString();
    }

    public static void main(String[] args){
        System.out.println(convertInixToPostfix("4*5+6/7"));
    }
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LENGTH_EXPRESSION 100

typedef struct stack {
	char items[MAX_LENGTH_EXPRESSION];
	int top;
}stack;

void push(stack *s, char element){
	if(s->top == MAX_LENGTH_EXPRESSION ){
		printf("\n Stack is full");
		return;
	}
	s->items[++s->top] = element;
	return;
}

char pop(stack *s){
	if(s->top == -1){
		printf("\n Stack empty");
	}
	return s->items[s->top--];
}
char peek(stack *s){
	if(s->top == -1){
		printf("\n Stack empty");
	}
	return s->items[s->top];
}

void initialize(stack *s){
	s->top = -1;
}

int empty(stack *s){
	if(s->top == -1) return 1;
	return 0;
}
/* This function return true or false based on whether 
character is operator or not */
int is_operand(char op){ 
  if(op == '+' || op == '-' || op == '*' || op == '/' || op =='%')
    return 1;  
  return 0;
}
 
/* This function returns associated precedence to an operator */
int precedence(char op){ 
  switch (op){   
    case '+' : 
    case '-' :
            return 1; 
    case '/' : 
    case '*' : 
            return 2;     
    case '%' :    
            return 3; 
    default : 
            return 4;  
    }
 }
/* This function tell if the op1 has lower precedence than op2 */
int lower_precedence(char op1, char op2){
  if(precedence (op1) < precedence(op2)) 
       return 1; 
    return 0;
}

void printStack(stack *s){
	printf("\n Stack is:");
	for(int i =0; i<= s->top; i++){
		printf("%c", s->items[i]);
	}
}

void infix_to_postfix(char *s){
    stack ms;

	initialize(&ms);
	
    char *p = (char *) malloc(strlen(s));
    char *post = p;
    char temp;

   /* Wrong input */
    if(s== NULL) return ;

    if(*s == '\0') return ;
   
    
   	while(*s != '\0'){
		/* Case 1. If '(', push on to stack */
        if(*s == '('){
           push(&ms, *s);
        }
 	   /* Case 2. If ')', pop all op from stack till we see '(', Discard ')' */
        else if(*s == ')'){
           while(!empty(&ms) && peek(&ms) != '('){
                *p  = pop(&ms);
                 p++;
           }
           if(!empty(&ms))
               pop(&ms);
       }
	   /* Case 3. If it is operator, pop all op on stack which are of higher 
  		precedence than it. Push this onto stack */
        else if(is_operand(*s)){
            while(!empty(&ms) && (!lower_precedence(peek(&ms), *s))){
               *p  = pop(&ms);
                p++;
            }
            push(&ms, *s);
        }
        /* Case 4. If it neither of above, add it to postfix expression */

        else{
            *p = *s;
             p++;
        }
        s++;
    }
    /*Flush all ops from stack once infix is completely visited */
    while(!empty(&ms)){
        
        *p  = pop(&ms);
        p++;
   }
   printf("\nPostfix expression is : ");
   printf("%s\n" , post);

}
int main(void) {
	infix_to_postfix("4+5*6/7");
	return 0;
}

Complexity of algorithm to convert infix to postfix expression is O(n), along with O(m) space complexity, where m is number of operators in expression.

Please share if there is something wrong or missing. If you are interested in taking personal coaching from our experience coaches, please reach out to us at communications@algorithmsandme.com.

Matching parenthesis problem

Matching parenthesis problem

We understood the concept of stack data structure in last post. Let’s discuss matching parenthesis problemwhich applies those concept. Problem statement is :

Given a string of parenthesis ‘(‘ and ‘)’, write a function which returns true if there are matching pairs and false if there are not. A matching pair means, there should be a closing parenthesis for an opening one, in correct order.

For example : '((()))', function should return TRUE, but ')(())' will return FALSE. Special case would be when there are equal number of parenthesis, closing and opening, but they are not in perfect order, hence function should return false in that case.

Parenthesis matching problem : Line of thoughts

For each closing parenthesis, we need a corresponding opening parenthesis. There are two possibilities : Either we find one or we do not find one. If we do not find one, we can say that string does not contain matching parenthesis.
If there is corresponding opening parenthesis, then that opening parenthesis cannot be matched with any other closing parenthesis.

Also, note that every closing parenthesis will match with the most recent opening parenthesis if there is one. That means we are looking at a order where the parenthesis which came last needs to be fetched first, typical last in first out pattern, which is best implemented by stack.

For asserting that the current closing parenthesis is in sync with what we have already seen, we just need to check if current parenthesis completes a pair with opening parenthesis we last seen. Next closing parenthesis should complete pair with the one prior to last and so on.

Parenthesis matching problem : Algorithm

  1. For each character of input string
  2. If character is opening parenthesis '(', put it on stack.
  3. If character is closing parenthesis ')'
    1. Check top of stack, if it is '(' , pop and move to next character.
    2. If it is not '(', return false
  4. After scanning the entire string, check if stack is empty. If stack is empty, return true else return false.

Matching parenthesis problem : Implementation

package com.company;

import java.util.Stack;

/**
 * Created by sangar on 21.9.18.
 */
public class ParenthesisMatch {

    public static boolean isMatchingParenthesis(String s) {
        Stack<Character> stack = new Stack<>();

        if (s == null) return true;

        int len = s.length();
        for(int i=0; i<len; i++){
            switch(s.charAt(i)){
                case '(' :
                    stack.push(s.charAt(i));
                    break;
                case ')':
                    //If stack is empty, then there is an extra closing parenthesis
                    if(stack.isEmpty()) return false;
                    stack.pop();
                    break;
                default:
                    return false;
            }
        }
        //If stack is empty that means it's a matching parenthesis
        return stack.empty();
    }

    public static void main(String[] args) {
        String s = "()))";
        System.out.println(isMatchingParenthesis(s));
    }
}

Complexity of parenthesis matching algorithm is O(N) time to scan N length string and O(N) extra space for stack.
This problem is quite simple to solve, so if you are asked this question in interview, most probably interviewer wants to understand can you think of good test cases and put your code to test against them. Below are the few test cases you can try your code on.
Test cases

1. ((())) : True
2. ())) : False
3. )((( : False
4. ( : False
5 Empty string : True
6. NULL pointer : False

Can you try solving this problem now on HackerEarth

Please share if there is something wrong or missing. If you are interested to take personal coaching from our experience teachers, please reach out to us at communications@algorithmsandme.com

Stack data structure and applications

Stacks data structure

What is stack data structure? Stack is a dynamic data structure, where information is stack over one another. In common terminology, we use the stack with same meaning like stack of trays or stack of pancakes. Extend the concept of stack in real life, you remove the tray at the top before moving tray below it. So the tray which goes last on to stack, come off the stack first. This pattern is called as Last In First Out or LIFO.

For any data structure, three operations should be considered : How data can be added to it, how data can be removed from it and how data can be read from it? Let’s discuss these operations on stack one by one.

Operations on stack

Write operation on stack is commonly known as push. Push operation writes information on to top of the stack.Complexity of push operation is O(1) as no iteration is required.

Read operation is known as pop, where element at the top of stack is removed. Complexity of pop is also O(1).
stack data structure

Another operation which is commonly used is isEmpty(), this checks if there are any elements in stack at present.

What if you just want to check the top element of stack but do not want to remove it from stack? Then operation called peek() is for you. It reads the top element, however does not remove it from stack.

Since stack can dynamically increase and decrease in size based on push and pop operation, we need to keep track of the top of the stack.

Stack can be represented as recursive structure i.e if we remove the top of the stack, remaining N-1 element is again a stack.

Let’s take an example to see how push and pop operations on stack actually follow Last In First Out pattern.

stack data structure

Implementation of stack data structure

Stacks can be implemented in two ways, first where underlying data storage is an array and second where underlying storage is linked list. Refer difference between array and linkedlist to understand more that impacts stack implementation.

1. In Array based implementation of stack implementation, underlying data structure used is an array. We keep an extra variable (top) to keep track of number of elements present in stack at given time. When we push an element on to stack, increase the top. When we pop an element from stack, we decrease the top.

In this implementation, top being -1 represents empty stack and top equal to N-1, N being the size of array, represents stack full. Push and pop operations are of O(1) complexity.

Drawback of this implementation is that we need to define stack size statically at the compile time and changing it at runtime dynamically would be overhead.

#include<stdio.h>
#include<stdlib.h>

#define STACK_SIZE 100

typedef struct stack{
        int top;
        int items[STACK_SIZE];
}stack;
 
void push(stack *ms, int item){
   if(ms->top < STACK_SIZE-1){
       ms->items[++(ms->top)] = item;
   }
   else {
       printf("Stack is full\n");
   }
}

//Get the element at the top of stack and remove it from stack
int pop (stack *ms){
   if(ms->top > -1 ){
       return ms->items[(ms->top)--];
   } 
   else{
       printf("Stack is empty\n");
   }
}

//Get the element at the top of stack without removing it.
int peek(stack ms){
  if(ms.top < 0){
      printf("Stack empty\n");
      return 0;
   }
   return ms.items[ms.top];
}

//Function to check if stack is empty or not?
int isEmpty(stack ms){
   if(ms.top < 0) return 1;
   else return 0;
}

2. In Linked List based implementation of stack implementation, underlying data structure used is linked list. Every node in the linked list represents an element in stack. Every push operation adds a node at the head of linked list and every pop operation removes a node from head of the linked list.

In this implementation too, push and pop operations are of O(1) complexity. Also stack can grow as much as required. Head being NULL represents empty stack.

Drawback is we need to store 4 bytes extra as next pointer for each element.

#include <stdio.h>

#include<stdlib.h>
#include<stdio.h>

typedef struct node{
    int data;
    struct node *next;
} Node;

/* Create a node of linked list */
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
 
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
    Node *newNode  = createNode(data);
    newNode->next = *headRef;
    *headRef  = newNode;
}

/* This function removes node from the head of linked list */
Node * pop(Node **headRef, int data){
    if(!(*headRef)) return NULL;
	
    Node * poppedNode = *headRef;
    *headRef = (*headRef)->next;
    return poppedNode;
}

/* This function return node at the head of linked list */
Node * peek(Node **headRef, int data){
    if(!(*headRef)) return NULL;
	
    return (*headRef);
} 

int isEmpty(Node **headRef){
    return (*headRef == NULL);
}

Stack Overflow

You must have heard the term stack overflow. Why does it occur and how does it relates to stack data structure?
Stack supports function call paradigm in programming languages. When a function in your program calls another function (which can be the same function in case of recursion), program management module in operating system stores quite a few things to have safe return. This includes : parameters passed to function, return values, return pointers. As you go deep into function calls, one function calling second, then second calling third and so on, each of this successive call takes a frame of system stack as explained above. Depending on the size of information you are putting on stack frame in each call, sooner or later, stack will be full, as it has limited memory allocated in kernel.

Now when you try to add one more frame because you are calling another function, there is no space. That’s when stack overflow happens.

Why do you think function call information is store on stack and not on any other data structure? Let’s say your program calls function A from function B, which in turn was called from function C. When you are returning from function A, you want to return to calling address in function B and not function C. So, you want to return back in reverse order of calling sequence, LIFO, that why stack is best data structure.

It is recommended to implement production code in iterative way rather than recursive using application level stacks. As application stack is allocated from heap, it can grow much bigger than kernel stack. Also, you can select what to put on stack. If you look at iterative preorder traversal, iterative postorder traversal interview problems, they are nothing but to test your knowledge of stack data structure. To read more on stack overflow, please refer : stack overflow

Application of stack : browser back button

Let’s solve a problem and see how stack data structure can be used to solve problems. Problem statement is : Implement back button on browser. When you click on back button, you go to previous site you visited. You press it again, than you go to site prior to it and so on.

Do you see application stack here? When you go back, you want to land on the last site you visited. What pattern is this? Of course, it last in first out which can be implemented using stack.
So idea is to whenever you move to new site or page, current page is added to stack. If you press back button, top of the stack is popped and return to you as current page. If you press again, top of the stack contains now the page you visited before current page, so land there.

browser back button using stack

There can one more complexity added to this problem, which is you want to implement forward button too. In that case, whenever you pop out a page from back stack, put it into a new stack called forward stack. Can you run through some examples and see if that actually works?

Please share if there is something wrong or missing. If you are interested in taking personal coaching by our experienced teachers, please reach out to us at communications@algorithmsandme.com

Merge k sorted arrays

Merge k sorted arrays

Given k sorted arrays each having n elements, merge k sorted arrays into one n*k element array in sorted order. For example, given 3 arrays are as below

merge k sorted arrays
merge k sorted arrays

Result array should be like

Merge k sorted arrays

Merge k sorted arrays

Since all the input arrays are sorted, the first element in result array will be among the first elements of input arrays. How can we find the minimum among all the elements plucked from the first index of each array ? Easy, take those k elements (there are k arrays, so k first elements) and build a min heap. The root of the min heap the least element among the first elements of all arrays, so it will be the first element in the result array.

Once, we add the first element into the result array, we have to find the second element. Second element can be from the set of first elements of all input arrays except one array from which the first element of result array was added. So, we will take second element of that array.

In order to know which array gave the minimum element at a particular time, we will store additional information of about array and index at which minimum element was.

If i represents the array number, and j represents the index of the minimum number in heap in ith array, then we add (j+1)th element to the min heap next and re-heapify. If j goes out of bound for ith array, we take min heap with k-1 size and go on, till we have no elements left in heap.

Follow the procedure for (n-1)*k times. When all array elements are processed, result array will be in the sorted array.

Merge k sorted arrays: algorithm

  • Build min heap with the first element of all k arrays.
  • Pick the root of min element and put it in the result array.
  • If there are remaining elements in the array,  put next element at the root of min heap and heapify again
  • If all elements are already of an array are processed, reduce the size of min heap by 1.
  • Repeat step 2, 3 and 4 till min heap is empty.

Merge k sorted arrays: implementation

package com.company;

import java.util.PriorityQueue;

/**
 * Created by sangar on 2.12.18.
 */
public class MergeKSortedArrays {
    private class HeapNode{
        public int arrayNum;
        public int index;
        public int value;

        public HeapNode(int arrayNum, int index, int value){
            this.arrayNum = arrayNum;
            this.index = index;
            this.value = value;
        }
    }

    public int [] mergeKSortedArrays(int[][] arrays){

        if(arrays == null) return null;

        PriorityQueue<HeapNode> minHeap =
			new PriorityQueue<>(arrays.length,
                (HeapNode a,HeapNode b)-> a.value - b.value);

        int size = 0;
        for(int i =0; i<arrays.length; i++){
            size += arrays[i].length;
        }
        int[] result = new int[size]; // k * n

        //add first elements in the array to this heap
        for(int i=0; i<arrays.length; i++){
            minHeap.add(new HeapNode(i, 0, arrays[i][0]));
        }

        //Complexity O(n * k * log k)
        for(int i=0; i< size; i++){
            //Take the minimum value and put into result
            HeapNode node = minHeap.poll();

            if(node != null){
                result[i] = node.value;
                if(node.index + 1 < arrays[node.arrayNum].length) {
                    //Complexity of O(log k)
                    minHeap.add(new HeapNode(node.arrayNum,
                           node.index + 1,
                           arrays[node.arrayNum][node.index + 1]));
                }
            }
        }
        return result;
    }
}

Test cases

package test;

import com.company.MergeKSortedArrays;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class MergeKSortedArraysTest {

    MergeKSortedArrays tester = new MergeKSortedArrays();

    @Test
    public void mergeKSortedArraysTest() {

        int[][] input  ={
            { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }
        };

        int[] expectedOutput = {1,2,3,4,5,6,7,8,9,10,11,12};

        int [] output = tester.mergeKSortedArrays(input);

        System.out.println(Arrays.toString(output));
        assertEquals(Arrays.toString(expectedOutput), 
					Arrays.toString(output));
    }

    @Test
    public void mergeKSortedArraysWithUnequalSizeTest() {

        int[][] input  ={
                { 1, 2 }, { 5, 6, 7}, { 9, 10, 11, 12 }
        };

        int[] expectedOutput = {1,2,5,6,7,9,10,11,12};

        int [] output = tester.mergeKSortedArrays(input);

        System.out.println(Arrays.toString(output));
        assertEquals(Arrays.toString(expectedOutput),
			Arrays.toString(output));
    }

    @Test
    public void mergeKSortedArraysWithNullTest() {

        int [] output = tester.mergeKSortedArrays(null);

        assertEquals(null, output);
    }
}

Complexity of code to merge k sorted arrays is O(n * k * log k) along with space complexity of O(k).

Please share if there is something wrong or missing. If you are preparing for an interview, please sign up to receive interview preparation kit for free.

Remove particular combination of characters

Remove particular combination of characters from string.

Given a string, we need to remove a particular combination of characters, for example, if s = “aacbbdccaac” and if combination is “ac” then our output will be “abbdcca”. If s = “aacaaccd” and if combination is “ac”, then output should be “acd”. Following will be the execution  aacaaccd ——-> aacd ——>ad 
Note that this has to be done in linear time and without any extra space.

Here there are two subparts of the problem: One, we need to keep track we have already encountered the first character in the combination of characters needed to be removed.
Second we need to keep track of the position where the next character should be placed in the string if it is not to be eliminated. First problem can be easily solved by maintaining a state machine, where we have two states and one moves from one state to another based on the input. In current example, we have states like state “INITIAL” and “MOVED”, Whenever we encountered “a”, we move from INITIAL to MOVED. Then if we get “c” in “MOVED” state we are sure that we have encountered the whole pattern and they need to be removed. If we are in “MOVED” state and if we don’t get “c”, we move back to “INITIAL” state.

For the second part, we can simply follow the approach we have used in this post, that is to maintain two pointers, one to point to the character to be processed, and other to point position where current character to be placed if it is not be eliminated.
The problem can be extended with multiple characters in pattern, with change in state machine accordingly.Same state machine method can be used to count number of words in a given string. Whenever we encounter the separator, we move to OUT state and as soon as we see first character in OUT state we move to IN state till we again see separator.

#define INITIAL 1
#define MOVED 2
char * remove_pattern(char *s, char * pattern){
    int state = INITIAL;
    if(s == NULL) return NULL;
    if(pattern == NULL) return s;

    char * source = s;
    char * destination  = s;
    while(*source != ''){

        /*If character is not equal to the first character of the pattern,
          copy it as such */
          if(state == INITIAL && *source != *pattern){
               *destination = *source;
               destination++;
          }
          else if( *source == *pattern && state == INITIAL){
              /* Move state to MOVED */
              state = MOVED;
          }else if(state == MOVED && *source != *(pattern + 1)){
                /* If next character is not as per pattern, 
                   copy previous character first. */
                *destination =  *pattern;
                destination++;
                /* If next character is first character of the pattern,
                   move state to INITIAL */
                   if(*source != *pattern){
                       *destination  = *source;
                       destination++;
                       state =  INITIAL;
                   }
             }
         /* If we hit the pattern, start again and move state to INITIAL */
          else if(state == MOVED && *source == *(pattern + 1)){
                state = INITIAL;
          }
          /* After moving the characters, check if they 
            don't make pattern again */
          if((int)(destination-s) >= 2
              && *(destination -2) == *pattern
              && *(destination-1) == *(pattern +1)){
              destination -=2;
          }
          source++;
    }
    *destination = '';
    return s;
}

Test cases
1. When pattern is present
s= “aaacacacbbb” pattern = “ac”

2. When pattern is not pattern
s =”aaaabdcaaa” pattern  = “ac”
3. When movement leads to pattern again
s= “abacaccdc” pattern =”ac”

4. When string is NULL or pattern is NULL s= NULL pattern = NULL
5. When return string is empty s = “acacacac” pattern =”ac”

6. Just first character in pattern s= “aaaaaaaaa” pattern =”ac”

The complexity of the above code is O(N) and no extra space used.

Loop in linked list

Loop in linked list

Detect loop in linked list is very common linked list question which is asked in telephonic interview rounds. Problem statement is :

Given singly linked list, check if there is loop in linked list and if yes, find start node or point of the loop.

For example, if for linked list shown below, there is a loop in linked list and it start at node 8.

loop in linked list
Loop in linked list, starting node is 8

Loop in linked list : thoughts

What is difference between a normal singly linked list and a linked list with loop? If we traverse normal linked list, we are destined to encounter a node which is null, which in effect is the last node of normal linked list. However, in a linked list with a loop, we will never reach null and circle around in the loop.

Can we use this property to find if there is a loop or not in a linked list? If we move two pointers with different speeds,, the fast pointer, which moves two nodes at a time will reach to end of linked list before slow pointer, which moves one node at a time, in a normal list (without a loop). However, in list with loop, fast pointer will go around in circles and eventually, slow pointer will catch up with it. So, if ever, before fast pointer reaches null, slow pointer catches up with it, there is definitely a loop in linked list. This method of using fast and slow pointers to traverse linked list at different speeds is commonly known as hare and tortoise method and used in solving many problems on linked list like find middle of linked list, palindrome linked list etc.

Let’s take an example and see what we are thinking is correct. Below is a linked list with a loop, let’s see if slow and faster pointer ever meet.

We initialize slow as head(4) and fast as next of head(3).  fast moves two steps and hence reaches node 8, where as slow reaches at 3.

Since, fast is not null yet, we jump again, this time fast points to 7 and slow points to 5.

Again, fast is still not null, so we move again, fast now is at 8 and so is slow.

This is where we can safely say that there is a loop linked list.

    public boolean isLoop(){
        /* 
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return false;
        }
        
        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here
        
        while(fast != null && fast != slow){
            /*
            Move faster ponter two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return false;
            
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }
        
        return fast == slow;
    }

There is common mistake which happens is to check content of fast and slow pointers to see if there are at the same node. This will fail when there are duplicate values in different nodes. To avoid wrongly predicting nodes being equal when actually content is equal, compare node addresses and not content.

Start of loop in linked list

This problem is interesting and require a bit of thinking. Can we find number of nodes in loop?
Starting from node fast and slow met at, move fast two nodes at a time and slow one node at a time, they will again meet at the same node. Keep count of how many nodes slow pointer moved, it will give length of loop. You can try with different length loops and see that it is actually true.

private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

Now, we have number of nodes in loop, let’s say k. How can we find starting node of loop. We take two pointers again, fast and slow, fast is k nodes ahead of slow which is at head of list. Why? Hypothesis is that if we move them with same speed, when slow reaches start of loop, fast would have finished traversing k loop nodes and will also be at the start of loop. So, with fast ahead of slow by k nodes, when both meet, that node should be start of loop in linked list.

Start of loop in linked list implementation

package com.company;

/**
 * Created by sangar on 14.10.18.
 */
public class LinkedList<T> {
    private Node<T> head;

    public LinkedList(){
        head = null;
    }

    public void insert(T data){
        //If this is the first node to insert
        if(this.head == null){
            this.head = new Node<>(data);
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier,
			it should not be null in this while loop ever though
            * */
            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            //We are at the last node.
            current.setNext(new Node(data));
        }
    }

    public Node getLastNode(){

        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;

            while(current != null && current.getNext() != null){
                current = current.getNext();
            }
            return current;
        }
    }

    public Node<T> get(T data){
        /*
            Base condition if there is no nodes,
            return null
         */
        if(this.head == null){
            return null;
        }
        else{
            Node current = this.head;
            /* Defensive programming, just in case current is null
            * As we check null condition for head earlier, it
			should not be null in this while loop ever though
            * */
            while(current != null && current.getData() != data){
                current = current.getNext();
            }

            return current;
        }
    }

    /* As we need slow pointer to get number
    of nodes again, we will return slow pointer
    rather than boolean
     */
    private Node isLoop(){
        /*
            Base condition if there is no nodes,
            return false
         */
        if(this.head == null){
            return null;
        }

        Node slow = this.head;
        Node fast = slow.getNext(); // slow cannot be null here

        while(fast != null && fast != slow){
            /*
            Move faster pointer two nodes at a time.
             */
            fast = fast.getNext();
            if(fast == null) return null;

            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) { slow = slow.getNext(); }
        }

        return fast == slow ? slow : null;
    }

    private int getNumNodesInLoop(Node slow){

        Node fast = slow;
        int count = 0;

        do{
            /*
            Move faster pointer two nodes at a time.
            As we are sure that there is loop in LL at this
            point, fast cannot be null. That's why it is
            removed from the while loop condition too.
             */
            fast = fast.getNext();
            fast = fast.getNext();
            //Slow pointer moves one node at a time
            if(slow != null) {
                slow = slow.getNext();
                count++;
            }
        }while(fast != slow);

        return count;
    }

    public Node getStartNodeLoop(){

        Node slow = isLoop();

        /* If slow is not null, it means there is a loop */
        if(slow != null){
            int k = getNumNodesInLoop(slow);

            slow = this.head;

            //Give fast head start of k nodes.
            Node fast = slow;
            while(k-- > 0 && fast != null){
                fast = fast.getNext();
            }

            while(fast != slow){
                slow = slow.getNext();
                fast = fast.getNext();
            }
        }
        return slow;
    }
}

Test cases for finding loop in linked list implementation

package test;

import com.company.LinkedList;
import com.company.Node;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class LoopInLinkedListTest {

    LinkedList<Integer> tester = new LinkedList<>();
    @Test
    public void loopPresentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        //Created a loop
        Node loopNode = tester.get(8);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopAbsentTest() {

        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(7);
        tester.insert(10);

        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void EmptyLinkedListTest() {
        assertEquals(null, tester.getStartNodeLoop());
    }

    @Test
    public void OneNodeLoopTest() {
        tester.insert(4);

        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }

    @Test
    public void loopBackToHeadTest() {
        tester.insert(4);
        tester.insert(3);
        tester.insert(5);
        tester.insert(8);
        tester.insert(9);
        tester.insert(5);
        tester.insert(7);


        //Created a loop
        Node loopNode = tester.get(4);
        tester.getLastNode().setNext(loopNode);

        assertEquals(loopNode, tester.getStartNodeLoop());
    }
}

Complexity to find a loop in linked list is O(n) as we have to scan all node of linked list at least once.

Please share if there is something wrong or missing.

Reference : cslibrary.stanford.edu/103/LinkedListBasics.pdf

Merge two sorted linked lists

Merge two sorted linked lists

Problem statement is simple : Merge two sorted linked lists, without using extra space. To refer to the basics of linked list, please follow the post : Linked list data structure. This problem is commonly asked in telephonic round of Amazon and Microsoft. Let’s take an example and understand what is required as solution. Given two linked lists as following,

merge two sorted linked lists
Two sorted linked lists

Result should be like this:

merge two sorted linked list
Resultant linked list.

Merge two sorted linked lists : Thoughts

Consider following two steps to merge sorted linked lists. First, figure out which node should be head of result list. Compare head nodes of two give lists, which ever is smaller, that should be the head of result list.

Second, compare two nodes, one from each list and decide which should go next in result linked list.  Advance the pointer to next node of the node which is added to result list.

As no new node is allocated during this merge, we have to make sure that all the references are maintained when nodes are added to merged linked list.

merge two sorted linked list
Two sorted list to be merged

We can start with one list as merge list and add nodes from second list at appropriate place in that list. Let’s say L1 is our merged list and we always compare node on L2 to see if it should be placed in L1 at current position. L1 grows as more nodes are sorted in merge list.

We compare first two nodes L1 and L2, and decide that node(2) has to go in merged list as head. If it was head of L2, we would have swapped L1 and L2 heads and still L1 will be head of merged list. Why? Because we want that L1 always points to last node in merged list and L1 to represent sorted merged list till this point and L2 switches between two input lists.

As L1 always points to the last node of merged linked list, next node to compare should be L1.next i.e node(4) and L2 i.e node(3).

As L1 follows the merged linked list, we will move L1.next to point node(3), however doing it directly will lead to lose of entire linked list following it. So we do it in four steps : store L1 next as temp; link L2 to L1.next; L2 points to temp and then move L1 to L1.next

Node temp = L1.next;
L1.next = L2;
L2 = temp;
L1 = L1.next
merge two sorted linked lists

Next nodes to be compared are node(5), which is L1.next and node(5) which is L2.

Comparing node 4 and 5 to add in sorted merge list

Of course node(4) has to be added to merged linked list, what should we do? First save L1.next in temp, temp now points to node(5). Second, point L1.next to L2, point L2 to temp, and at last, L1 moves to L1.next. State of two sorted linked lists looks as follows.

merge two sorted linked lists

By this time you must have noticed that L1 and L2 do not point to the one list all the time, L1 always points to the last node of merged list and L2 points to first node of separated list which needs to be merged.

Now, L1.next which is node(7) and L2 which is node(5) will be compared.

node(5) is to be added in merged sorted list. Again same set of steps. L1.next stored as temp, L1.next points to L2 i.e. node(5) and then L2 points to temp i.e. node(7)

merge two sorted linked lists

Again, node(9) which is L1.next will be compared to L2 i.e node(7). L1.next should point to L2. Final state will be as follows

At this point, L1.next i.e node(8) is less than L2, this is simple case, where we just move L1 to L1.next and L2 remains as is.

merge two sorted linked lists

Next two nodes follow the same pattern and added to merged sorted linked list.

At this point, special condition occurs which is L1.next is null. In this case, point L1.next to L2 and two linked lists are merged.

Two sorted linked lists are merged into a sorted list

Merge two sorted linked lists : Implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }

    printf("NULL");
    printf("\n");
}
Node * MergeLists(Node *list1, Node *list2) {
  if (!list1) return list2;
  if (!list2) return list1;

  Node *head;
	//Chosing head of merged list
  if (list1->data < list2->data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
	
  while(list1->next && list2) {
    if (list1->next->data > list2->data) {
	//Step 1. Save the next pointer
      Node *tmp = list1->next;
	//Step 2. Change next pointer to point L2
      list1->next = list2;
	//Step 3. Move L2 to temp
      list2 = tmp;
    }
	//Step 4. Move L1 ahead
    list1 = list1->next;
  } 
  if (!list1->next) list1->next = list2;
  return head;
}
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
	
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
 
        L1 = MergeLists(L1,L2); 
        printList(L1);
 
        return 0;
}

Complexity of this method to merge two sorted lists into one is O(n+m) where n and m are number of nodes in two sorted linked lists.

Recursive implementation to merge two sorted linked lists

#include<stdlib.h>
#include<stdio.h>
 
typedef struct node{
    int data;
    struct node *next;
} Node;
 
Node * mergeSort(Node *a, Node *b){
    Node *result = NULL;
    if(a ==  NULL)
        return b;
    else if(b == NULL)
        return a;

    /* For the first node, we would set the result to either a or b */
      if(a->data <= b->data){
         result = a;
        /* Result's next will point to smaller one in lists 
           starting at a->next  and b */
         result->next = mergeSort(a->next,b);
      }
      else {
        result = b;
       /*Result's next will point to smaller one in lists 
         starting at a and b->next */
        result->next = mergeSort(a,b->next);
      }
      return result;
}

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}

void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }

    printf("NULL");
    printf("\n");
}

/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,7);
        push(&L1,6);
        push(&L1,4);
        push(&L1,3);
        /* creating list 2 */
        push(&L2,10);
        push(&L2,8);
        push(&L2,1);
      
        L1 = mergeSort(L1,L2); 
        printList(L1);
        
        return 0;
}

Please share if there is something wrong or missing. If you want to take personalized coaching from our expert teachers, please signup for free demo class.