Find peak in array (local maxima)

Peak in array

Given an unsorted array, find a peak in array. A peak is defined as an element which is not smaller than its immediate neighbors. In an unsorted array, there can be many such peaks, referred to as local Maxima. Mathematically, ith element is called as peak following property holds true:

A[i-1] <= A[i] >=A[i+1]

For first element and last elements of array, left and right neighbors respectively, are considered as negative infinity.

A[0] = A[n] = -infinity

For example, peak in following array would be 6 or 7

Can you identify the peak in this array?

What would be peak in sorted array? It will be the last element of array and similarly, for reverse sorted array, first element will be peak.

Peak  in array : Thought process

I recommend two things: First, get your pen and paper to practice this problem yourself. Second, try to come up with brute force solution as soon as possible. Why? Because it adds to your confidence, when you have some solution already in hand.

Brute force approach to find peak in an array of integers will be to scan through it and for each element, check if greater than it’s greater than previous and next element.  If it is, return index of that element. In worst case we would end up scanning whole array (in a sorted array), so worst case complexity of brute force solution is O(N)

Obviously, this would not have been an interview question, if expectation was to solve it in O(N) complexity, anyone with basic programming knowledge can solve it. There is no way to differentiate a good candidate from an average based on this question then. However, interviewer expects you to solve it in better than O(N) complexity and that’s where problem becomes interesting.

What if we do not go linear and randomly check index m for local maxima? If it is local maxima, we are good, return the index of that element. If it is not peak and given that array is unsorted, three situations possible at that index :
1. Array is rising toward right, that means, next element is greater than current and it’s previous element.

2.  Array is falling towards right, that means, next element is less than current and it’s previous element.

3.  It’s a valley, where current element is less than both previous and next element.

In first situation, maximum should be on the right side of current index, why? In second situation, peak will be in left side of current index.

If A[m] < A[m+1], A[m] cannot be peak. However, if A[m+2] is less than A[m+1] is less than A[m+1], then A[m+1] can be a peak or some subsequent element can be. In worst case it would be the last element of array if whole A[m..end] is sorted.
If A[m] < A[m-1], in that case, either A[m-1] is peak or some element preceding it can surely be. In worst case, first element will be the peak.

Algorithm to find peak in array

Now question is how to select m? We want to minimize the worst case number of elements to check after splitting, which is possible by splitting the array in middle. Take mid as the starting point, this is classic case of divide and conquer  approach as we will discard half of the array based on certain condition.

  1. Find mid = low + (high-low)/2
  2. If A[mid-1] <= A[mid] =>A[mid+1], then return mid
  3. If A[mid-1] > A[mid], high = mid-1
  4. If A[mid+1] > A[mid], low = mid+1
  5. Repeat step 1 to 4 till there are more than one element in array. Else return that last element.

Let’s take an example and see if this algorithm works. We have given array a as below

peak in array example

Find mid and see if mid is peak we are looking for, in this case it is not as A[mid] is less than A[mid+1].We will discard left subarray and look for peak in right subarray starting from mid+1.

New low and high are shown, we find new mid. Is new mid, local maxima? No, as it is less than previous and next element, it is valley. We will discard right subarray and look for peak in left subarray.

Now, there is only one element, hence it should be peak in array.

peak in array example

Peak in array : Implementation

package com.company;

/**
 * Created by sangar on 25.3.18.
 */
public class BinarySearcchAlgorithm {

    public  static int findPeak(int[] a){
        int low = 0;
        int high = a.length-1;

        while (low<high){
            int mid = low + (high-low)/2;
            if(mid == low ) return a[low] > a[high] ? low:high;

            //If mid is local maxima, return it.
            if(a[mid-1] <= a[mid]
                    && a[mid] >= a[mid+1]) return mid;
            //Discard right subarray
            else if(a[mid-1] > a[mid]) high = mid-1;
            //Discard left subarray
            else low = mid+1;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] input = {1,2,6,5,3,7,4};

        int index = findPeak(input);
        System.out.print("Peak found at : " + index);
    }
}

Always remember to check for array with two elements, that will catch almost all bugs regarding boundary overflow. Also, notice that since we are accessing mid+1 and mid-1 indices of array, make sure that these indices are within bounds of array. These two things are very important for a solution to be correct and acceptable in interview. Also, to understand more about binary search algorithm and how it works, please refer to Binary search algorithm

Complexity of divide and conquer algorithm to find peak in unsorted array is O(log n). Recurrence relation for this would be T(n) = T(n/2) + c

Please share if there is something wrong or missing. If you want to contribute to website and help others to learn, please reach out to us on communications@algorithmsandme.com

Move all zeros at the end of the array

Move all zeros at the end of the array

Given an array, which contains random numbers, including zero. We have to move all zeros at the end of the array. For example input array is

Output array is

Basic idea is to scan through array, whenever we find a zero, move all successive elements accordingly. We wont be moving all elements every time we hit zero. Trick is similar to problem where we delete specific characters from a string. For complete explanation refer to this post. For above example, at some point, below will be state of array and other variables

By the time we reach at the end of the array, we may have a difference between the last element of the array and size of the given input array. That will be the number of zeros in the input array. Fill all those spots with zero.

#define MAX_ELEM 10
void move_zeroes(int a[], int size){
    int i, dest = 0;

    for(i =0; i<size; i++){
        if(a[i] != 0){
            a[dest++] = a[i];
        }
    }
    for(i= dest; i<size; i++){
        a[i] = 0;
    }
    printf("\n");
    for(i= 0; i<size; i++){
        printf("%d ", a[i]);
    }
}

int main(){
    int a[] = {0,1,3,4,0,0,0,5,6,7};
    int size = sizeof(a)/sizeof(a[0]);
    move_zeroes(a, size);
    return 0;
}

Simple it is O(N). There is another problem which can be solved with the same approach. Problem is to delete consecutive duplicate elements except the first in an array. For example, input array is { 0,1,1,3,3,5,0,0,6,6}  {0,1,3,5,0,6}

Find k number in sliding window problem

Sliding window problem

Given a large integer array of size x, window size of n and a random number k, find smallest k numbers in every window of n elements in array. This is commonly know as sliding window problem. For example: for an array [2,3,1,5,6,4,2,5,4,3,8] k = 2 and n = 6, output should be [1,2],[1,2],[1,3][1,4][1,3][1,3]. How? see below figure.

This problem regularly features in Amazon interviews.

Find k numbers in sliding window : thoughts

If we spit down the problem, it reduces to find k smallest elements in an array, which can easily be solve in multiple ways. All we have to take care of is moving the window and storing results for each window.

Quick sort method
First way is to use quick sort, we randomly pick a pivot and put it in right place. When pivot is at right place, all elements on the right side of pivot are greater than pivot and all elements on the left side are less than pivot. If pivot is a kth position in array, all elements on left side of pivot automatically become K smallest elements of given array. In worst case this method take O(n log n) for each window.

Using heaps
What are we interested in is k elements, what if from current window, we take out first k numbers and consider them as k smallest elements? This set of k numbers may change based value of following numbers in the window. Which way? If new number is smaller than any of the number chosen randomly, new number has to be added into the k smallest element set. However, we have only k spaces there, so someone has to move out.

If new number is less than any number in set, it must be less than maximum number in set

Given above fact, we can always swap new number with maximum of set. Now problem is how to find max in a set? This set will modified repeatedly, so we cannot just sort it once and find the max. For use cases when data is changing and we have to find max of that set, heaps are the best data structures to use. In this case we will use max heap. Max heap is kind of heap where children of root node are smaller than root node. Max heap will give us O(1) complexity to find max and O(log n) complexity to heapify on removal old max and insertion of new number.

Algorithm

  1. Create a max heap with first k elements of window.
  2. Scan through remaining elements in window
    1. If root of max heap is less than new number, remove the root and add new element to heap
    2. All elements in heap at the end of processing are k smallest numbers in window.

    Sliding window algorithm to find k smallest elements : Implementation

    #include<stdio.h>
    #include<stdlib.h>
    #include <math.h>
    
    typedef struct node {
    	struct node * left;
    	struct node * right;
    	int data;
    } heapNode;
    
    int leftChild(int i){
    	return 2*i + 1;
    }
    
    int rightChild(int i){
    	return 2*i + 2;
    }
    
    void swapPtr(heapNode *a[], int i, int largest){
    	heapNode *temp = a[i];
    	a[i] = a[largest];
    	a[largest] = temp;
    }
    /* This function heapifies heap after removal of root  
    or at time of building heap from an array */
    void max_heapify_ptr(heapNode *a[], int i, int len){
            int largest = i;
            int left, right;
    
            left = leftChild(i);
            right = rightChild(i);
           
            if(left <= len && a[i]->data <a[left]->data){
                    largest = left;
            }
            if(right <= len && a[largest]->data < a[right]->data){
                    largest = right;
            }
            if(largest != i){
                    swapPtr(a, i, largest);
                    max_heapify_ptr(a, largest, len);
            }
    }
    
    /* Building heap from given elements */
    void build_max_heap_ptr(heapNode *a[], int len){
            int i = len/2 +1;
            for(; i>=0; i--){
                    max_heapify_ptr(a,i, len);
            }
    }
    
    /* This function allocates node of heap */
    heapNode * create_node(int data){
            heapNode *node = (heapNode *)(malloc)(sizeof(heapNode));
            if(node){
                    node->data = data;
            }
            return node;
    
    }
    
    /* This function is real implementation of 
    the sliding window algorithm */
    void slide_window(int buffer[], int N, int K, int buffer_len){
    
        int i =0, j =0,s;
        heapNode *max_heap[K+1];
        int num = K;
    
        for(j=0 ; j + N < buffer_len; j++){
          /* Window starts at index 0 and is of size N */
           printf("\nCurrent window :");
           for(s =j; s<j+N; s++){
               printf("%d ", buffer[s]);
           }
           printf("\n");
           /* Put K element from N element window */
           for(i=0;i<K; i++){
           /* Since we wold be doing for every window, 
              avoiding reallocation of node */
               if(max_heap[i]){
                    max_heap[i]->data = buffer[i+j];
                }
                else{
                    max_heap[i] = create_node(buffer[i+j]);
                }
            }
            /* Build min heap with those entered elements */
             build_max_heap_ptr(max_heap,K-1);
    
            /*Now for all remaining N-K-1 elements in window, 
             check if they fit in max heap */ 
             for(i=K+j; i< N+j; i++){
                 heapNode * root = max_heap[0];
                 if(buffer[i] < root->data){
                       root->data = buffer[i];
                       max_heapify_ptr(max_heap, 0, K-1);
                  }
              }
              
              /*Print the current max heap, it will contain K smallest 
                element in current window */
               printf("K minimum elements in this window :");
               for(int x=0; x< K; x++){
               	printf("%d ", max_heap[x]->data);
               }
               
               
            }
    }
    /* Driver Program to execute above code */
    int main(){
       int buffer[10] = {1,4,5,6,3,2,4,8,9,6};
    
       int K= 4;
       int N =5;
       
       int size = sizeof(buffer)/ sizeof(buffer[0]);
       
       slide_window(buffer,N, K,size);
       return 0;
    }
    

    Following figures explain how window slides and how heap is updated.
    1. Window starts at index 0 and ends at N. We take K minimum elements among N elements and store in max heap. Array is given in below picture with window size of 9 and k = 4.
    First step is to create a max heap with first 4 elements of window.

    sliding window problem

    Next we are looking at 4, which is less than max in max heap. So we remove the max from heap and add the new element(4) to heap.

    k smallest element in sliding window

    Next is 2, which is less than max in max heap. So we remove the max from heap and add the new element(2) to heap.

    Next is 3, which is less than max in max heap. So we remove the max from heap and add the new element(3) to heap.

    Next we have 10 and 11 which are greater than root of max heap, so nothing happens.

    We come to end of window. Therefore, 4 smallest element in window are [ 1,2,3,4 ]

    Next window moves one step ahead, that’s where you discard the max heap and create the new empty one and repeat the process.

    We can actually avoid discarding the entire heap when window moves, however complexity of overall algorithm will remain the same. This problem is asked in a different way, which is to find maximum in sliding window.

    #include <iostream>
    #include<deque>
    using namespace std;
    
    void slidingWindow(int buffer[], int n, int w, int output[])
    {
       deque<int> Q;
       int i;
       /*Initilize deque Q for first window, put all W elements, however also
       removing elements which cannot be maximum in this window */
       for (i = 0; i < w; i++)
       {
       	   //This is where we are removing all less than elements
           while (!Q.empty() && buffer[i] >= buffer[Q.back()])
               Q.pop_back();
           // Pushing the index
           Q.push_back(i);
       }
      
       for (i = w; i < n; i++)
       {
           output[i-w] = buffer[Q.front()];
    
           //update Q for new window
           while (!Q.empty() && buffer[i] >= buffer[Q.back()])
               Q.pop_back();
    
           //Pop older element outside window from Q    
           while (!Q.empty() && Q.front() <= i-w)
               Q.pop_front();
          
           //Insert current element in Q
           Q.push_back(i);
       }
       output[n-w] = buffer[Q.front()];
    }
    
    int main(){
    	int a[]={3,5,4,2,-1,4,0,-3};
    	int n = sizeof(a)/sizeof(a[0]);
    	int output[n];
    
    	slidingWindow(a,n,4,output);
    	return 0;
    }
    

    Worst case complexity of sliding window algorithm would be O(n2k). K is included as it takes O(k) complexity to build heap of k elements.

    Please share if there is something wrong or missing.

Find words in maze

Find words in a maze

We learned basics of tries in last post. Let’s see if we could apply some of those properties in solving some real problems. Today’ problem at hand is to find all the words which are present in a maze of characters of size NxN. The condition is that characters of words should be adjacent to each other either horizontally or vertically.
For example, below maze contains cat, dog and word words in it.

What is the brute force solution? Simple, find all the words which can be formed using these characters in maze starting of length 1 to N*N. For each word check if the given dictionary contains the word, if yes, store that word in the result.
What is the search space here? There will be (n2!) words to be looked into the dictionary. Not a practical solution. Optimizing search in the dictionary using sorting and binary search will not be of much help. (Good point to mention at interview though).
So how can we reduce the search space? Let’s first take an example and see what is happening in the brute force approach.
If we look closely, we are checking string length N, even though we already know that N-1 character string leading to it is not a valid string. Can we avoid it? Yes, using tries. This is how we can do it.

Store all words in the given dictionary in a trie. If there is no prefix in trie with length = i; there cannot be the word with i+1 length having this prefix of length i. So just abort the lookup of words with this prefix. Else increase the string length by 1 and repeat the above step. Trie fits perfectly in this algorithm as we are dealing with prefixes. We need to keep track that what we have already visited and if there can be more words with the visited prefix. If we take the example of the above maze, we start from ‘a’, as we see that there is no word starting with ‘a’ in trie by looking at children array of the root, we can safely avoid calculating words starting with ‘a’ of any length from there.

Find words in a maze : Implemenetation

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

#define N 4

int search_key(Node *current, char key){
   int index  =  GET_CHAR_INDEX(key);

   if(current->children[index] == NULL) return false;

   return true;
}

enum direction {
        NORTH =1,
        SOUTH,
        LEFT,
        RIGHT
};

void update_params(int row, int col, int *new_row, int *new_col, int dir){
   switch(dir){
      case NORTH:
           *new_row = --row;
           *new_col = col;
      break;
      case SOUTH:
           *new_row = ++row;
           *new_col = col;
      break;
      case LEFT:
           *new_col =  ++col;
           *new_row = row;
      break;
      case RIGHT:
           *new_col =  --col;
           *new_row = row;
      break;
     }
}


void find_words_wrapper(trie *t, char maze[][N]){

  int i,j,len, prefix_found = false;
  for(i=0; i<N; i++){
     for(j=0; j<N; j++){

    /*Consider all length words which can be formed stating with maze[i][j] char */

      for(len =1; len <N*N; len++){
        /* To check if we need to check for further length 
           1. if prefix_found = false, don't check, 
           no words possible for larger length 
           2. if prefix_found = true, continue looking*/

           prefix_found = false;

           /* If finally reached at the leaf of trie starting 
              with maze[i][j] and length = len */

              if(find_words(t->root, maze, len,i,j, &prefix_found)){
                 printf(" Word found at (%d %d)\n", i,j);
              }
              else if(prefix_found == false)
                 break;
       }
     }
   }
}

int valid_position(int row, int col){
        if(row<0 || row>N-1 || col <0 || col>N-1) return false;

        return true;
}

int find_words(Node *t, char maze[][N], int curr_len, 
               int curr_row, int curr_col, int *prefix){
       
       int new_row, new_col;
       int  dir,i;
       char key = maze[curr_row][curr_col];

       Node * current = t->children[GET_CHAR_INDEX(key)];

    /* Before finish the prefix we hit the null, prefix is not present */
       if(current == NULL) return false;

       /* If reach the prefix of len = curr_len but its not a word, 
        we can look forward with len = curr_len +1 */
       if(curr_len == 1 && current->value != LEAF_NODE){
                *prefix = true;
                return false;
       }
     /* If we reach at the leaf node, for this length, 
      we found a word with length = curr_len */
       if(curr_len == 1 && current->value == LEAF_NODE)
                return true;

       /* For every character look in all direction */
       for(dir = NORTH; dir<= RIGHT; dir++){

         /* if the key is present */
         if(search_key(t, key)){
         /* Move to next character based on direction of movement */
            update_params(curr_row, curr_col, &new_row, &new_col, dir);

            /*Validate that we are good in maze */
             if(valid_position(new_row, new_col)){

             /*Find word with len -1 in remaining trie */
              if(find_words(current, maze, curr_len-1, new_row, new_col, prefix)) {
                   return true;
               }
             }
          }
          else{
              return false;
          }
       }
}
void main(){

        trie t;
        initialize(&t);
        int i;

        char *dict []  = {"cat", "dog", "word"};

        char maze[N][N]  = { 'a' , 'c', 'a', 't',
                             'd' , 'w', 'o', 'r',
                             'o',  'g', 'd', 'd',
                             'p', 'p',  'p', 'p'
                           } ;
        for(i =0; i <3; i++){
                insert(&t, dict[i]);
        }

         find_words_wrapper(&t, maze);
}

Even though we have reduced the search space, we may end up looking at all the words i.e (n2!). There is a way to reduce it by using dynamic method approach, we look at that in the future.

Tries as data structure

Tries as data structure

Tries is a data structure which is usually neglected by programmers while designing solutions. Tries are very useful in cases where strings are involved with a good amount of duplication of their prefixes. What are tries? Trie is a data structure which stores information, referred to as key, in such a manner that the common information is stored only once. Usually keys are strings. No node in trie stores the whole key, but the position of the node gives us information that which key it is part of. All the descendant node in trie have the same prefix, hence trie is also know as prefix trees.Word trie is taken from retrieval word.

Another property of trie is that every node of trie has multiple children. In case of string (assuming lower case), there will be 26 children of each node. Take an example: We have the following strings: “House”, “Home”, “Tree” I need to store this information, Trie for the above words would look like:

Trie data structure example

Insertion in trie

Before insertion, we need to understand that how can we represent a node of a trie. Since intermediate nodes of a key do not store any information at them, we need to distinguish between the leaf node and the intermediate node. For that we can store a field called as the value inside each node, If the value is zero, it’s an intermediate node, if non-zero, it’s a leaf node.
In our case, we are assuming MAX_SIZE of 26.
Basic initialization

#define MAX_SIZE 26

#define GET_CHAR_INDEX(ch)\
        ((int) ch - (int)'a' )

#define LEAF_NODE  1
#define true 1
#define false 0

typedef struct trie_node_t {
        int value;
        struct trie_node_t * children[MAX_SIZE];
}Node;

typedef struct trie{
        int count ;
        Node *root;
}trie;

void initialize(trie *t){
        t->root = (Node *)malloc(sizeof(Node));
        t->count =0;
}

Now we can go and see insertion part.
Scan through the string character one by one. For each character, check if it has child nodes. The character acts as an index in children array. If the node at the char index has a child node, move to the child node and take the next character of the string. Repeat step 2 and 3 If the node at the char index doesn’t have a child node, create a child node and add it to trie. Move the character in the string and move down to a newly created child. Go to step 2.

void insert(trie *t, char key[]){

        int len = strlen(key);
        int i;

        if(t->root == NULL){
                printf("\n Trie is not initialized\n");
        }

        Node * current = t->root;
        for(i=0; i<len; i++){

             /* Get the index of char in children array */
             int index  =  GET_CHAR_INDEX(key[i]);

             /* If the children array does not contain the pointer
                at index pointed by char, allocate new node */

             if(current->children[index] == NULL){
                current->children[index] = (Node *)malloc(sizeof(Node));
             }
             /* Else traverse down the trie. */
             current = current->children[GET_CHAR_INDEX(key[i])];
        }

        /* To mark it as leaf */
        current->value = LEAF_NODE;
}

Search in trie
The best part of the trie is its search. It is done in O(M) where M is the length of the input string.
Start from the root. and take the first character of the string. If the array index pointed by the character is NULL, return false. Else move to the child node and next character. Repeat step 2 and 3 till the end to the input string. If we reach till the end of the string and the current node is a leaf node (identified using value), then return true.

int search(trie *t, char key[]){
        int len = strlen(key);
        int i;
        if(t->root == NULL){
                printf("\n Trie is not initialized\n");
        }

        Node * current = t->root;
        for(i=0; i<len; i++){
                int index  =  GET_CHAR_INDEX(key[i]);

                /* If characters are left in key and we have 
                reached at NULL, there is no key present */
                if(current->children[index] == NULL) return false;
                 
                /* Else traverse down the trie */
                current = current->children[index];
        }

        /* If we have reached the lead=f node, key is present */
        if(current && current->value == LEAF_NODE )
                return true;

        return false;
}

The only drawback with tries is that it takes a lot more space (K *  MAX_SIZE * N) as compared to the binary search tree. It is evident from the fact that every node in trie has to have a place for all the possible characters. In time complexity terms, insertion and search both are O(M) where M is length of string being entered. In this post we saw insertion and search operation in tries. We will use these operations in the future post and solve some real problems.

LRU cache (Least Recently Used cache)

LRU cache implementation in Java

This is commonly asked question in interview, especially Microsoft and Amazon interviews. Problem statement is very simple

Implement LRU cache or Least Recently Used cache

Before going further into solution, first let’s understand what is cache?  In computer architectural terms, a cache is small buffer of pages OS maintains in-order to avoid more expensive main memory accesses.

Usually cache accesses are faster than main memory access, improving overall performance. Whenever process needs to access content from a specific memory location, it tries to search that page in cache first. If it finds page in cache, it uses it and does not access memory. It’s called cache hit.

However, caches are very small in size as compared to main memory, there is probability that page requested by process is not present in cache. In that case, new page is moved into cache and one of existing page is swapped out. When this happens, it is called cache miss.

Caching also happens at application layer too, for example, caching visited pages on browser, caching frequently accessed data from DB to in memory caches like Redis.

Based on how cache miss is handled in cache, there different type of caches like first in first out cache, least recently use cache, least frequently use cached.

In first in first out cache, in the event of cache miss, entity which came first into cache is evicted first; where as in least recently used cache, page which was used least recently gets evicted. In the same vain, least frequently used cache is where page which is least frequently used among all the pages in cache.

LRU cache implementation

Consider that you have a cache with space for additional page. If cache miss happens, we bring page from memory and put it in cache for future access.

Now, if cache is full, and cache miss happens, we have to bring in a new page and evict a page from cache. In LRU cache, this page will  be the page which accessed longest time ago.

What if a page was accessed at the start, and then accessed just before the cache miss? Is it the least recently used page? On the contrary, it is the most recently used page and hence should be last to evict. Question now is which page should we evict? In this case, page which came after the first page goes out.

If page is brought into cache first, it is first candidate for eviction, if it is not accessed again before cache miss happens.

Why queue?

In principle, LRU cache is first in first out cache with special case, that if a page is accessed again, it goes to end of eviction order. Which data structure is best to implement FIFO pattern? Of course it’s queue. So our LRU cache will be a queue where each node will store a page. This queue will have specific size as cache as limited size. Whenever a new page is brought in, it is added at the rear of queue. When eviction happens, it happens from the front of cache.

Why hash?

There is one requirement of LRU cache which does not map directly to queue data structure, which is to move a node corresponding recently accessed page to end of the queue. This poses two problems : First, how to find the node in the queue corresponding to page id being accessed? Second, how to move it to end as efficiently possible? Both problems are very similar to what we solved in first non repeated character in stream.

We will use hash which will store the node address in queue corresponding to page id. This will give us immediate access to the node to be reshuffled.

Why doubly linked list based queue?

Still problem remains to move nodes around with moving all elements of the queue. Which data structure removes an element in O(1), given the element? Doubly linked list it is. If we implement queue as doubly linked list, removing and adding pages from queue will be O(1) operation.

LRU cache algorithm

  • Cache miss happens :
    • If cache has free entry, enqueue page to queue.
    • If cache is full,  remove the page from from of queue and add new page at the end of queue.
  • Cache hit happens :
    • delete node from current location in queue.
    • Enqueue page at the end of queue.
  • If page is present in hash, it’s a cache hit, if page is not present in hash map, it’s a cache miss.

LRU cache implementation

Queue interface

package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public interface Queue<E> {
    public ListNode<E> peek();
    public ListNode<E> remove();
    public ListNode<E> enqueue(E data);
    public ListNode<E> deleteNode(ListNode<E> node);
    public boolean isEmpty();
    public int size();
}

Queue implementation

package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public class QueueImplementation<E> implements Queue<E>{
    ListNode<E> head;
    ListNode<E> tail;
    int size;

    public QueueImplementation(){
        head = null;
        tail = null;
        this.size = 0;
    }

    @Override
    public ListNode<E> deleteNode(ListNode<E> node){
        if(this.isEmpty()) {
            return null;
        }

        if(this.head == node){
            if(this.head.getNext() != null) this.head.getNext().setPrev(null);
            this.head = this.head.getNext();
            this.size--;
            return node;
        }

        if(this.tail == node){
            if(this.tail.getPrev() != null) this.tail.getPrev().setNext(null);
            this.tail = this.tail.getPrev();
            this.size--;
            return node;
        }
        /*
            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());

        this.size--;
        return node;
    }


    @Override
    public ListNode peek() {
        if(this.isEmpty()) {
            return null;
        }
        return this.head;
    }

    @Override
    public ListNode remove() {
        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<E> tempNode = this.head;
        this.head.setPrev(null);
        this.head = this.head.getNext();

        this.size--;
        return tempNode;
    }

    @Override
    public ListNode enqueue(E data) {
        if(this.isEmpty()) {
            this.head = new ListNode<E>(data);
            this.tail = this.head;
            this.size++;
            return this.head;
        }
        ListNode<E> newNode = new ListNode<E>(data,null, this.tail);
        this.tail.setNext(newNode);
        this.tail = newNode;

        this.size++;
        return newNode;
    }

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

    @Override
    public int size() {
        return this.size;
    }
}

LRU cache implementation in java

package com.company;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Created by sangar on 9.10.18.
 */
public class LRUCache {
    private Queue<Integer> queue;
    private HashMap<Integer, ListNode> pages;
    private int cacheSize;

    public LRUCache(int cacheSize){
        this.cacheSize = cacheSize;
        queue = new QueueImplementation<>();
        pages = new HashMap<>();
    }

    /* This function implements the LRU cache */
    public void readPage(int pageId) {

        /*Cache Miss and we can add the page in the cache */
        if (!pages.containsKey(pageId) && queue.size() < cacheSize) {
            pages.put(pageId, queue.enqueue(pageId));
            return;
        }

        /* Cache Miss and we cannot add new page to cache,
        remove the LRU page */
        if (!pages.containsKey(pageId) && queue.size() >= cacheSize) {
            //First remove it from the queue.
            ListNode evictedPage = queue.remove();
            //Remove node from hash table
            pages.remove(evictedPage.getData());
            //Enqueue new node and add it at tail
            queue.enqueue(pageId);
            return;
        }

        /* Cache is Hit */
        if (pages.containsKey(pageId)) {
            updateCache(pageId);
        }

        return;
    }

    /* This function modifies queue when there is cache hit */
    public void updateCache(int pageId){

        /* Case where queue may be empty - defensive programing*/
        if(queue.isEmpty() && queue.size() < cacheSize){
            pages.put(pageId,queue.enqueue(pageId));
        }
        /* Update the pointers of neighbor nodes and tail in dummy node */
        else{
            ListNode node = queue.deleteNode(pages.get(pageId));
            if(node != null){
                queue.enqueue((Integer)node.getData());
            }
        }
    }

    public ArrayList<Integer> cacheState(){
        ListNode current = queue.peek();
        ArrayList<Integer> cacheState = new ArrayList<>();
        while(current != null){
            cacheState.add((Integer)current.getData());
            current = current.getNext();
        }
        return cacheState;
    }
}

Test case for LRU cache implementation

package test;

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

import java.util.ArrayList;
import java.util.Arrays;

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

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

    LRUCache tester = new LRUCache(5);

    @Test
    public void testCacheInsertion() {

        ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(1,2,3,4,5));

        tester.readPage(1);
        tester.readPage(2);
        tester.readPage(3);
        tester.readPage(4);
        tester.readPage(5);

        assertEquals(cacheState, tester.cacheState());
    }

    @Test
    public void testCacheHit() {

        ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(1,4,5,2,3));

        tester.readPage(1);
        tester.readPage(2);
        tester.readPage(3);
        tester.readPage(4);
        tester.readPage(5);
        tester.readPage(2);
        tester.readPage(3);

        assertEquals(cacheState, tester.cacheState());
    }

    @Test
    public void testCacheMiss() {

        ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(2,3,4,5,6));

        tester.readPage(1);
        tester.readPage(2);
        tester.readPage(3);
        tester.readPage(4);
        tester.readPage(5);
        tester.readPage(6);

        assertEquals(cacheState, tester.cacheState());
    }

    @Test
    public void testEvictionAndInsertion() {

        ArrayList<Integer> cacheState = new ArrayList<>(Arrays.asList(3,4,5,6,1));

        tester.readPage(1);
        tester.readPage(2);
        tester.readPage(3);
        tester.readPage(4);
        tester.readPage(5);
        tester.readPage(6);
        tester.readPage(1);

        assertEquals(cacheState, tester.cacheState());
    }


    @Test
    public void testEmptyCache() {
        ArrayList<Integer> cacheState = new ArrayList<>();

        assertEquals(cacheState, tester.cacheState());
    }
}

Let’s take an example and see how whole thing works. Let’s say we have cache of size 5, which is empty to start with. Application accesses page id 1,2,3,4 and 5. As they are all cache miss to start with and there is space in cache, all these pages are brought into cache.

implement lru cache in java
Cache state after reading first 5 pages

Now, application accesses page 6. We have a cache miss. What happens? As cache is full, we evict the page which is at the front and add page 6 to it.

Page 1 is evicted, and page 6 added to queue

Application accesses page 2 again, which is already present in cache, it’s a cache hit. As page 2 is most recently used page, it has to go to end of the queue.

implement lru cache
Page 2 moves at the end

Let’s say next page accessed is page 7, it is cache miss. Evict a page from cache, which is the first node in queue (3).

lru cache implementation
New page 7 added to end after evicting page 3 from front

Insertion and removal from queue is O(1) complexity.

Please share if there is something wrong or missing. If you are interested in taking personal coaching from our expert teachers, please contact us at communications@algorithmsandme.com

Linked list based implementation of queue in Java

Linked list-based implementation of queue

A Queue is an abstract data structure which follows the First In First Out FIFO principle. It means the element which came into the queue first will leave the queue first. This ordering is very helpful in a lot of solutions. Two things are important for a queue: front and rear or tail.

linked list based implementation of queue

A new element is added into the queue at the rear or at the tail, which is called enqueue operation.

queue implemented using linked list
enqueue operation on linked list based queue

The front is the point from where an element of a queue is taken out. This operation is called dequeue operation.

Dequeue operation on queue implemented using linked list

Interface for a queue would be as shown below. This interface can be implemented in multiple ways. There are different ways in which an abstract data structure can be implemented using concrete data structures, for example, a queue can be implemented using arrays or linked lists. Limitation in array-based implementation is that we have to allocate array size beforehand which restricts the number of elements that can be accommodated. Another issue is to correctly tell if the queue is empty or full. We have to maintain an extra counter for that purpose.

package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public interface Queue<E> {
    public ListNode<E> peek();
    public ListNode<E> remove();
    public ListNode<E> enqueue(E data);
    public boolean isEmpty();
    public int size();
}

Let’s discuss how to implement a queue using linked lists.

Single linked list based implementation of queue

A linked list a collection of nodes where each node has two components, first component store the data for the node and second component points to the next node in the linked list. In the last node, the second component points to NULL, which signifies the end of the linked list.

singly linked list based implementation of queue
singly linked list based implementation of queue

If we use a linked list, we solve the first problem of statically allocating memory beforehand for the queue. The linked list is a dynamic data structure, we can allocate memory at the runtime based on our requirements. Also, to find if a queue is empty, check if linked list empty, which is a simple operation to check if the head of linked list NULL.

The time complexity to remove an element out to the singly linked list based queue is O(1), remove the head and make the next node of the head new head. However, to add an element into the singly linked list, we have to go the end of the lists which has a time complexity of O(n).

This problem can be easily be solved by keeping a tail pointer, which points to the last node of the linked list. When we have to enqueue an element in the queue, we update the next of tail to point to the new node and make new node has the tail of the queue. The complexity of enqueue operation is also O(1).

The singly linked list seems to be working for the queue implementation, with dynamic size, dequeue and enqueue operation with O(1) complexity.

One more operation performed on queues to solve certain problems like LRU Cache, non repeated characters in a stream etc. This operation is to delete a random node in queue. Given a random node in the queue, remove that node from the queue.

This problem is tricky in a singly linked list. Brute force solution is to traverse the linked list, go till the previous node and the do the pointer rearrangement and then free the memory of the given node. This operation in the worst case requires O(n) operations. There is a trick method, which is to copy the data of the next node of the given node to the given node and then delete the next node. Caveat to this trick, which I have discussed in delete a node from linked list.

To delete a node from a linked list, two pointers are required: the previous node of the node and the next node of the node. All we do is to make the next pointer of the previous node point to the next node of the given node and free the given node.

Doubly linked list based implementation of queues

From the above discussion, it is easy to guess which type of linked list implementation will give us previous and next node of a given node without traversing the list. It is doubly linked list.

doubly linked list based implementation of queues
doubly linked list based implementation of queues

All the operations remain the same, with same time complexity. With the doubly linked list, delete operation also becomes O(1). So, whenever you have a use case where you may have to delete a random node from the queue, always go for the doubly linked list based implementation. The only overhead is that we have to store double the number of pointers than a singly linked list.

package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public interface Queue<E> {
    public ListNode<E> peek();
    public ListNode<E> remove();
    public ListNode<E> enqueue(E data);
    public ListNode<E> deleteNode(ListNode<E> node);
    public boolean isEmpty();
    public int size();
}
package com.company;

/**
 * Created by sangar on 8.10.18.
 */
public class QueueImplementation<E> implements Queue<E>{
    ListNode<E> head;
    ListNode<E> tail;
    int size;

    public QueueImplementation(){
        head = null;
        tail = null;
        this.size = 0;
    }

    @Override
    public ListNode<E> deleteNode(ListNode<E> node){
        if(this.isEmpty()) {
            return null;
        }

        if(this.head == node){
            if(this.head.getNext() != null) 
                this.head.getNext().setPrev(null);
            this.head = this.head.getNext();
            this.size--;
            return node;
        }

        if(this.tail == node){
            if(this.tail.getPrev() != null)
                this.tail.getPrev().setNext(null);
            this.tail = this.tail.getPrev();
            this.size--;
            return node;
        }
        /*
            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());

        this.size--;
        return node;
    }


    @Override
    public ListNode peek() {
        if(this.isEmpty()) {
            return null;
        }
        return this.head;
    }

    @Override
    public ListNode remove() {
        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<E> tempNode = this.head;
        this.head.setPrev(null);
        this.head = this.head.getNext();

        this.size--;
        return tempNode;
    }

    @Override
    public ListNode enqueue(E data) {
        if(this.isEmpty()) {
            this.head = new ListNode<E>(data);
            this.tail = this.head;
            this.size++;
            return this.head;
        }
        ListNode<E> newNode = new ListNode<E>(data,null, this.tail);
        this.tail.setNext(newNode);
        this.tail = newNode;

        this.size++;
        return newNode;
    }

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

    @Override
    public int size() {
        return this.size;
    }
}

Circular linked list base implementation of queue

Sometimes, the interviewer asks to you solve a trick question like this: Implement queue using only one pointer, either front or rear

The correct answer to it is to use a circular linked list, where the last pointer points back to the head or front pointer. In that case, we will use only the rear pointer.

Enqueue operation:
We create a new node, point the next of new node to the next of tail node, make it next of the tail node and new node becomes the tail node. This whole operation is in constant time, hence the complexity of this operation is O(1).

implementation of queue using only one pointer
implementation of queue using only one pointer

   newNode.next=tail.next; 
   tail.next=newNode;
   tail=newNode; 

Dequeue operation:

   node = tail.next //node to be removed
   tail.next =  node.next // point to the next of front node.

We learned different ways to implement a queue using linked lists. Based on the requirements and constraints of the problem we choose one of the give implementations. To understand more how queues are implemented in Java, please read Queue Implementations

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

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.