Blog

Mutex Vs Semaphore

Mutex Vs Semaphore

These are two primitives which everyone confuses almost every time. Let’s clarify on these today and see what are the basic difference between these two. There must be some difference else two of them would not have existed. ūüôā Difference may be subtle but they exist.


First thing we should shed the belief that mutex and semaphore are one and same and can be used interchangeably. No they are not and they cannot be.


Most of use believe that semaphore is just extension of mutex. That is to say mutex is binary version of semaphore, if want to put concurrency control on more than one similar resources, we use semaphores adding count. ¬†It’s wrong.


The toilet analogy has a basic flaw, we have multiple keys to multiple bathrooms in case of semaphore, we have the key, but we still don’t know which bathroom is free. ūüôā So eventually we end up in mechanism where one key is for one bathroom and that is the mutex for us.

Hence adding the count paradigm to mutex does not turn that into semaphore.So hope first misconception is clarified.

Mutex is basically a locking mechanism where a process locks a resource using mutex. Till the time, process has mutex, no other process can have the same resource. (Mutually exclusive for you). Once process is done with resource, it releases the mutex.

Here comes the concept of ownership. Mutex is locked and released by the same process/thread. It cannot happen that mutex is acquired by one process and released by other.

Semaphore is a synchronization mechanism. It is used between two process to synchronize each other. Best example would be producer-consumer problem. Consumer cannot consume till the time producer has produced something. When producer has produced something, it will inform consumer using semaphore primitive.

There is no ownership attached to semaphore. One process can acquire it and other can release it.

In next post we would see some of the APIs used in Linux kernel for mutex and semaphore.

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 [email protected]

Locking : Spinlocks vs Mutex Part -2

Spinlocks Kernel APIs

In last post we learned about the mechanisms for concurrency control.
Concurrency really comes into picture only in case of Symmetric Multiprocessing systems, where two processes can actually execute a piece of code simultaneously. In uni-processing system, no processes can execute at the same time, even though we need some kind of synchronization because relative ordering of execution of instruction can affect the output. 

In this post we would see what are the various APIs which are available in Linux kernel for spinlocks and when should we use them. 

With interrupt enable/disable

spin_lock_irqsave(lock, flags)
spin_unlock_irqrestore(lock, flags)

Usage

spinlock_t my_lock = SPIN_LOCK_UNLOCKED;

unsigned long flags;

spin_lock_irqsave(&my_lock, flags);

/* critical section … */

spin_unlock_irqrestore(&my_lock, flags);

Description
Above API is used to go into busy loop but after disabling interrupts. This may be required because if interrupt itself wants another spinlock, there might be a deadlock.

The corresponding unlocking API, restore the interrupts when spinlock is acquired.

This provides protection against both SMP and interrupt issues.

If one wants to disable all interrupts unconditionally, spin_lock_irq(spinlock_t *lock) and spin_unlock_irq(spinlock_t *lock) are used.

Without interrupt enable/disable

spin_lock(spinlock_t *lock)
spin_unlock(spinlock_t *lock)

Usage
spinlock_t mr_lock = SPIN_LOCK_UNLOCKED;

spin_lock(&mr_lock);

/* critical section … */

spin_unlock(&mr_lock);

Description
Saving and restoring interrupts can take time. If we are quite sure that critical section is not going to receive any interrupts or data is not going to be used in any interrupt, we might avoid saving and restoring interrupts. There we use above APIs.

With soft interrupt enable/disable

spin_lock_bh(spinlock_t *lock)
spin_unlock_bh(spinlock_t *lock)

Description 
Above APIs disable soft IRQ on processor but not hardware interrupts.

This is required in code segment which is written outside soft IRQ but used inside it.

These are three major variants of spinlock usage. There is another variant of all these as 

spin_trylock_irqsave(lock, flags) 
spin_trylock(spinlock_t *lock)
spin_trylock_bh(spinlock_t *lock)

These function try to acquire to lock and return value which tell success or failure to process.

For example spin_trylock() does not spin but returns non-zero if it acquires the spinlock on the first try or 0 if not.

Word of wisdom ūüôā

Use spinlocks in case where you are sure that lock will be acquied in reasonably small amount of time. If it takes time, we would end unnecessary keeping processor busy spinning in loop. trade off is : If making process sleep and wake up again is affordable than spinning, if yes, use semaphore, if not, use spinlock.

Also never use spinlocks for guarding critical section which are accessing memory or IO or scheduling some other process. We may end up in deadlock.


There are other variants like read-write spinlocks. We would discuss them in next post.

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 [email protected]

Recursion: Tower of Hanoi

Tower of Hanoi

Tower of Hanoi is a classic problem to learn recursion. Here we see how recursion base conditions are generated, how parameters to the successive call to the same function are modified to give the desired output. 


Problem at hand is : We have three pegs : A, B, C. Peg A contains N disks which are stack in such a way that any disk below is larger that then disk above as shown in figure. 

We need to move these N disks to Peg B in same condition mentioned above using the peg C.

Initial state

Tower of hanoi


Final State 


Analysis

First thing that comes into mind after reading or looking at the problem is : Move N-1 disks from peg A to peg C and then move the Nth disk to destination peg B. Now we have a problem left with N-1 disks which need to move from peg C to peg B using peg A as spare. 

Easy enough ??

So we get the sight of recursion here? 

First  : We need to do same process to N-1 disk which we did for N disks.  
Second : Base case is when we are left with only one disk at source, we directly move that to destination.

Pseudo-code for Tower of Hanoi
Now we would see how stacks can be used to solve this problem. A rule of thumb is :  If a problem can be solved using recursion, it can also be solve using stack.
We need to map the recursion calls to stack.

Code

Code given here is of recursive implementation.

Test cases

Test case 1 : No of disk  : 3


Enter the number :3
Moving disk from a to b


Moving disk from a to c


Moving disk from b to c

Moving disk from a to b

Moving disk from c to a


Moving disk from c to b

Moving disk from a to b

Complexity of tower of Hanoi problem amounts to number of discs and space complexity is O(n) which is used by internal stack for  recursion

Locking : Mutex vs Spinlocks

Difference between mutex vs spinlocks

I would start with a very basic technical interview question, that is : What is difference between mutex and spin-lock?
First of all, let’s understand what is a mutex?
Mutex is kind of a key to use any resources in the system. If you have mutex, you can use the resource, if you don’t wait till the mutex is released. Process goes to wait queue for that particular resource.¬†

What is spin-lock? Spin lock is a mechanism in which the process needing a resource poll the lock on resource till it gets it. It is also called as busy-waiting. Process will be busy in a loop till it gets the resource.

So we get the first difference there itself, the way both wait for the resource lock. In case of mutex, process goes in wait state and does not use processor while in spin-lock, process keeps on looping and hence uses the processor even while waiting.

Second difference comes from : when should we use spin-lock or mutex?

Spin-locks are best used when a piece of code cannot go to sleep state. Best example of such code would be interrupts request handlers.

Mutexes are best used in user space program where sleeping of process does not affect the system in catastrophic way.

Spin locks make sense when we have multi-processor systems or we have uni-processor system with preemption enabled, spin locks used in uni-processor systems without preemption enabled, may lead to deadlock where process goes on spinning forever.

Following table summarizes the above points.

Mutex Vs Spinlock


Criteria
Mutex
Spinlock
Mechanism
Test for lock.
If available, use the resource
If not, go to wait queue
Test for lock.
If available, use the resource.
If not, loop again and test the lock till you get the lock
When to use
Used when putting process is not harmful like user space programs.
Use when there will be considerable time before process gets the lock.
Used when process should not be put to sleep like Interrupt service routines.
Use when lock will be granted in reasonably short time.
Drawbacks
Incur process context switch and scheduling cost.
Processor is busy doing nothing till lock is granted, wasting CPU cycles.

In next post we would list some the APIs which are used for using mutex and spinlocks in Linux kernel.

Convert a decimal number to binary number.

Convert a decimal number to binary number  

This article explains basic usage of stack with the help of a simple problem that is converting a decimal number to a binary number.

We know how the algorithm for the problem.
1. Divide the given number by 2.
2. Store the remainder.
3. Repeat the step 1 on the quotient.
4. When quotient is zero, print stored remainders in reverse order.

Example: Let’s say we want to convert 27 ¬†to binary number.

Step 1 : 27/2 =13 Remainder 1
Step 2 : 13/2 =6   Remainder 1
Step 3 : 6/2 = 3    Remainder 0
Step 4 : 3/2 = 1    Remainder 1.
Step 5 : 1/2 = 0    Remainder 1.
When we print the remainder in reverse order, we get 11011 which is binary representation of 27.
Since, we want the last remainder first, this is a perfect case for using stack.


Code

Implementation of push and pop functions can be referred here.

Complexity

Complexity of algorithm to convert a decimal number to its binary representation is log(n).

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 [email protected]

Longest Common Subsequence

Longest common subseuence

A subsequence of a string is set of all the characters which are left to right order and not necessarily contiguous. For example, string ABCDEG has ABC, ADG, EG, BCDEG subsequences; whereas BDA is not a subsequence of the given string, even though all the characters are present in the string, they do not appear in the same order.

longest common subsequence lcs

Given two strings X and Y, find longest common subsequence (LCS) Z. For example, X = ABCDSEFGD Y = ACFEFXVGAB; LCS Z would be ACEFG.

Longest common subsequence: line of thoughts

First of all, notice that it is an optimization problem, it is a hint that it may be a dynamic programming problem but we are not sure yet.

Let’s say that the length of the string 1 and the string of 2 are N and M. Can I know the longest common subsequence in length N and M if I already know the LCS in N-1 and M-1? The direct question is can I divide the original problem into subproblems and solve those subproblems to get the answer for original problem? In this case, the answer is yes. (This is the second hint towards dynamic programming application, optimal subproblem substructure).

How can we divide the problem into subproblems? The length of X is N and length of Y as M. Start from the end of both strings. Check if X[N] == Y[M]. If yes, the problem reduces to find the longest common subsequence in X[1..N-1] and Y[1..M-1].

What if they are not equal? Then one by one we have to exclude character from string X and Y. Why?
First, we exclude the character from the X and find LCS in remaining characters of X and all the characters of Y. The problem reduces to X[1..N-1] and Y[1..M]. Next, we exclude a character from Y, the problem reduces to X[1..N] and Y[1..M-1]. Any of the two choices can give us the longest common subsequence, so we would take maximum from both the cases.

LCS(i,j)  =  1 + LCS[i-1, j-1] if X[i] == Y[j]   =   MAX (LCS[i-1,j], LCS[i, j-1]) if X[i] != Y[j] =   0 if i or j is 0

Interesting to see why LCS(i,j) is 0 when either i or j is 0? Because the longest common subsequence in two strings, when one string is empty is 0.

Can we implement the recursive function?

    public int longestCommonSubsequence(String s1, String s2, int i, int j){

        //If any of the string is nul return 0
        if(s1 == null || s2 == null) return 0;

        //We reached at the end of one of the string
        if(i == s1.length() ||  j == s2.length())
            return 0;

        if(s1.charAt(i) ==  s2.charAt(j)){
            return  1 + longestCommonSubsequence(s1, s2, i+1, j+1);
        }

        return Integer.max(longestCommonSubsequence(s1, s2, i+1, j),
                longestCommonSubsequence(s1, s2, i, j+1));

If we follow the execution cycle of the above code, we will see something like below

longest common subsequence lcs

It is evident from the partial tree that there are some problems which are solved again and again. This is the third hint (overlapping subproblems) that we can apply dynamic programming.

It will be more evident if you implement the recursive function with reverse traversal of the strings. In that implementation, the base case will be when one of the string is empty, and at that point, LCS of two strings will be 0. If we take a two dimensional table such that T[i][j] represents longest common subsequence till ith and jth characters of string S1 and S2 then T[0][i] = 0 and T[i][0] = 0.

T[i][j] = T[i-1][j-1] + 1 if X[i] = Y[j] T[i][j] = max(T[i-1][j], T[i][j-1]) if X[i] != Y[j]

Dynamic programming implementation of LCS

package com.company;

/**
 * Created by sangar on 4.2.19.
 */
public class LongestCommonSubsequence {

    public int longestCommonSubsequenceDP(String s1, String s2){

        //If any of the string is nul return 0
        if(s1 == null || s2 == null) return 0;

        int len1 = s1.length();
        int len2 = s2.length();

        int[][] table = new int[len1+1][len2+1];

        for (int i=0; i<=len1; i++){
            for (int j=0; j<=len2; j++) {
                if (j == 0 || i == 0) {
                    table[i][j] =  0;
                }

                else if (s1.charAt(i-1) == s2.charAt(j-1)) {
                    table[i][j] = 1 + table[i - 1][j - 1];
                } else {
                    table[i][j] = Integer.max(table[i - 1][j], table[i][j - 1]);
                }
            }
        }

        return table[len1][len2];
    }
}

Above implementation has time and space complexity of O(n2). Please share if there is anything wrong or missing.

What is dynamic programming?

What is Dynamic Programming or DP

Dynamic programming is an approach to solve a larger problem with the help of the results of smaller subproblems. It is a technique used to avoid computing multiple time the same subproblem in a recursive algorithm. I find a lot of students asking me question around, how do I know this problem is a dynamic programming problem? There is a definite way to arrive at the conclusion if a problem is a dynamic programming problem or not?

The first thing I would recommend you to read before going down is this beautiful explanation of dynamic programming to 4 years old.

The first thing you will notice about dynamic programming problems (not all problems) is they are optimization problem. Either it will be finding minimum or maximum of some entity. For example, find minimum edit between two strings or find longest common subsequence etc. However, problems like Fibonacci series are not exactly like an optimization problem, these are more like Combinatorial problems. Still, this can be a good hint that a problem can be a DP problem.

Second, you will notice that the problem can be divided into a pattern like an fn(n) = C + fn(n-k) where k can be anything between 1 and n.
This property is called optimum subproblem structure, where an optimum solution to the subproblem leads to the optimum solution to the larger problem.
Once you get the equation, it is very easy to come with a recursive solution to the problem. I would advise you to write the recursive solution and try to calculate the complexity of the solution. It will exponential in big-O notation.

Then why did recursion work so well with a divide and conquer approach? The key point is that in divide and conquer, a problem is expressed in terms of subproblems that are substantially smaller, say half the size. For instance, mergesort sorts an array of size n by recursively sorting two subarrays of size n/2. Because of this sharp drop in problem size, the full recursion tree has only logarithmic depth and a polynomial number of nodes. In contrast, in a typical dynamic programming formulation, a problem is reduced to subproblems that are only slightly smaller than the original. For instance, fn(j) relies on fn(j ‚ąí 1). Thus the full recursion tree generally has polynomial depth and an exponential number of nodes.
However, it turns out that most of these nodes are repeats, that there are not too many distinct subproblems among them. Efficiency is therefore obtained by explicitly enumerating the distinct subproblems and solving them in the right order.
Reference

This will lead us to the third property, which is overlapping subproblems. Once, you draw the execution tree of the recursive solution of the problem, it will appear that a lot of problems are being solved again and again at different levels of recursion.

The intuition behind dynamic programming is that we trade space for time, i.e. to say that instead of calculating all the subproblems taking a lot of time but no space, we take up space to store the results of all the subproblems to save time later. The typical characteristics of a dynamic programming problem are optimization problems, optimal substructure property, overlapping subproblems, trade space for time, implementation via bottom-up/memoization.

Dynamic programming in action

Enough of theory, let’s take an example and see how dynamic programming works on real problems. I will take a very commonly used but most effective problem to explain DP in action. Problem is known as the Fibonacci series. Fibonacci series is a series of integers where each integer is the sum of previous two integers. For example, 1,1,2,3,5,8,13,17 is a Fibonacci series of eight integers. Now, the question is given a number n, output the integer which will be at the nth integer in Fibonacci series. For example for n = 4, the output should be 3 and for n=6, it should 8.

First hint: It is a combinatorial problem, so maybe a DP problem. Second, it is already given in the problem that current integer depends on the sum of previous two integers, that means f(n) = f(n-1) + f(n-2). This implies that the solution to subproblems will lead to a solution to the bigger problem which is optimal substructure property.

Next step is to implement the recursive function.

 public int fibonacci (int n) {
    if (n < 2) //base case
        return 1;

    return fibonacci(n-1) + fibonacci(n-2);
 }

Great, next step is to draw the execution tree of this function. It looks like below for n = 6. It is apparent how many times the same problem is solved at different levels.

what is dynamic programming
Recursive tree of Fibonacci series function

So, now we know three things about the Fibonacci problem: It is combinatorial problem, there is optimal substructure and there are overlapping subproblems. As in dynamic programming, we side with more space than time, we will try to use extra space to avoid recalculating subproblems.

The first way is to use a case, which stores the value of fab(n) if it is already calculated. This is called memoization or top-down approach.

Map<Integer, Integer> cache = new HashMap<>();

public int fibonacci(int n){
    if (n == 0)
       return 0;
    if (n == 1)
        return 1;

    if(cache.containsKey(n))
        return cache.get(n);

    cache.put(n, fibonacci(n - 1) + fibonacci(n - 2));

    return cache.get(n);
}

Another approach is bottom up, where the smaller problems are solved in an order which helps us with solving bigger problems. Here also, we use memoization but in a different way. We store the solution of smaller subproblems and directly use this to build the solution.

int[] fib = new int[n];
fib[0] = fib[1] = 1;
public int fibonacci(int n){
   for(int i=2; i<=n; i++){
       fib[n] = fib[n-1] + fib[n-2];
   }
   return fib[n];
}

Above solution requires extra O(n) space, however, the time complexity is also reduced to O(n) with each subproblem solved only once.

Follow longest increasing subsequence problem, how we have applied the same pattern while we solved the problem.

Final thoughts
Where to apply dynamic programming : If you solution is based on optimal substructure and overlapping sub problem then in that case using the earlier calculated value will be useful so you do not have to recompute it. It is bottom up approach. Suppose you need to calculate fib(n) in that case all you need to do is add the previous calculated value of fib(n-1) and fib(n-2)

Recursion : Basically subdividing you problem into smaller part to solve it with ease but keep it in mind it does not avoid re computation if we have same value calculated previously in other recursion call.

Memoization : Basically storing the old calculated recursion value in table is known as memoization which will avoid re-computation if its already been calculated by some previous call so any value will be calculated once. So before calculating we check whether this value has already been calculated or not if already calculated then we return the same from table instead of recomputing. It is also top down approach.
Reference: Answer by Endeavour

Please share if there is something wrong or missing. If you are preparing for an interview and need help with preparation, please book a free session with us to guide you through it.