Task Scheduler

Problem Statement : 
      Given an input arrays of Tasks
          Input: tasks = [A, A, A, B, B, C,  C,  D]

and a window of size k = 3 (say)

You have schedule tasks in each CPU cycle.(1 task per CPU cycle or CPU cycle can go idle we well). Idle cycle is represented by "X".
You have to make sure no task gets repeated before k intervals, you ma have to have 'idle'  CPU cycle as well in order to achieve this. Find the minimum number of CPU cycles.

for above input

output : A  B  C  D  A  B  C  X  A  X  X  X  A

above output is one possible answer for the given input, if you observe "A" repeats atleast after k=3, for that matter any task repeats at-least after 3 CPU cycles.

Leetcode :
621. Task Scheduler
https://leetcode.com/problems/task-scheduler/

Solution :

This is a very interesting problem, and has been asked in top notch companies.
There are multiple solutions we will be the best approach to solve this. (you can solve this by sorting and using Priority queue as well).

Lets fit the above input into the grid to understand better.

The formula at the end of the above image is crucial, spend time understanding that, thats the crux of the problem.

There is a another interesting case at step 4 in the code below, it occurs when number of idle product of maxCount and k is less compared to total distinct tasks. (i recommend to pay attention to this line carefully). One example of such scenario is  ['A' , 'A' , 'B' , 'C' , 'D' , 'E', 'F' ] and k = 2 , by the above formula, your result would be  (2 - 1 ) * (2 + 1) + 1 = 4 but the correct answer is 7.

Below is the implementation of the above problem.

Please post comments and suggestions.
Happy Coding !! :)

Sliding Window Maxima

Problem Statement : 
        Given an array of size n and window of size k (k < n) , find the maximum element in each contagious array of size k(also can be called as window) .

Leetcode:
239. Sliding Window Maximum
https://leetcode.com/problems/sliding-window-maximum/


Solution : 

There are multiple approaches to solve this problem, we will be solving the problem with the help of deque(double ended queue). The brute force approach would take O(n * k) time complexity as for each n , you will have to traverse next k elements.

Below is the implementation with the help of Deque, important thing to note here is that
i. all elements which are getting out of the window range needs to be removed and
ii. if there is a new larger incoming element coming in as part of new item, remove all smaller elements in the deque.


Below is the code implementation :

Please post comments and suggestions.
Happy Coding !! :)

Infix to Postfix Conversion

Problem Statement : 

Convert Infix expression to Postfix Expression.

Input :  a+b*(c^d-e)^(f+g*h)-i

Output:  abcd^e-fgh*+^*+i

Solution :

Algorithm :

1. If the character is operand, append in the Output Result.
2. If you get openings bracket '(', push into the stack.
3. If you get closing bracket ')', pop all element from the stack until you reach '(' and add in the                Output Result.
4. If the character is operator
  a. if the stack is empty, then push operator to stack.
  b. Else, Pop all the operators from the stack which have greater than or equal
  precedence than that of the current operator.
  After doing that Push the scanned operator to the stack.

Below is the implementation of the above algorithm.

Please post your comments and suggestions.
Happy Coding !! :)

Maximum Frequency Stack

Problem Statement : 

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

1. push(int x), which pushes an integer x onto the stack.
2. pop(), which removes and returns the most frequent element in the stack.

         If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.

Solution : 

The idea here is to maintain frequency Map and bucket of stacks. 
Below is the working code( refer the comments in the code).

Thank you for visting the page, post your comments and suggestions.
Happy Coding !! :)

Validate Stack Sequence

Problem Statement :

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Sample 1 : 

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,

push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Sample 2 : 

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false

Explanation: 1 cannot be popped before 2.

Solution : 

Idea is to keep pushing the elements to a stack from "pushed" array and as you find same value at pushed and poped, pop the stack and move ahead in the poped array comparing stack content. 
In the end stack should be empty.


Below is the code implementation

Thank you for visting the page.

Circular Queue

Problem Statement :
           Implement Circular Queue Using Arrays

Source Code Link
Solution:

Circular Queue is efficient version of Queue, in which elements are stored efficiently without wastage of space.
The concept that circular queue uses is incrementation of the index pointer, which is achieved by
index = (index +1 )%N , this formula brings the index to start position if it crosses the end of the array.

We will be using two pointers namely "rear" and "front".
rear pointer - tracks the latest item inserted.
front pointer - tracks the oldest item in the queue.

Below is the implementation of Circular Queue.

Now given below is implementation of all the operations present in the interface.

Any improvement or suggestions for the above code are most welcome. Source Code is hosted on Ideone , please follow the link given above.
Happy Coding!! :)

Next Greater Element

Problem Statement:
      Print the next greater element to every element in an array , if no greater element exists for a number
 print -1.

Given Array :   7     22    4      12     25      3      9
Output:            22   25    12    25     -1      9      -1

Solution:

The above problem can be solved using stack.

Below is the sub-routine implementation:

Please comment and post suggestions
Happy Coding !! :)

Largest Area in a Histogram

Problem Statement : 
      Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

In the above histogram width of each bar is 1 and heights are H = [2, 1, 5, 6, 2, 3]. 


Solution: 

By brute force algorithm, we can consider each bar every time and consider all other bars adjacent to it which are equal or greater and find the area by Height of the bar multiplied by right and left index difference plus one

Area = Bar Height * (right_index - left_index + 1)

The time complexity for this case would be (n^2) i.e. n-squared. 

We would be discussing another optimised technique which will have a complexity of O(n) using stack. 


We would essentially use same trick as we had done in the Brute force but with storage in a stack we will find a better optimised solution, The trick is to compute left and right index of the of bar such that all bars between these indices are either equal or greater than the bar in consideration. 

Traverse all the bars from left to right and push the bar to the stack if the stack is empty or if the bar is greater than the top of the stack. Once the next incoming bar is smaller than the top of the stack, anchor the index here and this would act as right_index start. Pop the bar and calculate the area as the smallest bar for this left index would be the updated top in the stack. 
i.e. A = bar_height * (right_index - 1 -  new_top_index). 

If this is slightly confusing then lets write the algorithm for it. 

Algorithm :
1. Create a empty stack. 
2. Push i , if stack is empty or H[i] is greater than stack.peek()
3. If the bar is small set anchor to i, continue to pop the indces from the stack until H[stack.peek()] is smaller H[i], for each element poped calculate the area evert time you pop element using 

A = bar_height(of the poped index) * (i - 1 - stack.peek()) 

when stack is empty, 
A = bar_height(of the poped index) * i

update Area A if the newly computed Area is greater than previous. 

4. If all the items are over and stack is still not empty repeat process 3.

Code below :

Let me know if you have any questions in the comments section or any feedback.
Happy Coding !! :)

Post #123 : Eating Fish Problem

Problem Statement :

Below given are two arrays indicating the size of the arrays and the direction in which they are moving. A bigger fish can eat a smaller fish if they are moving in opposite direction.

Two fishes moving in same direction cannot eat each other because all the fishes are moving at a constant speed. Print the output of the fishes which survives

Fishes with distinct sizes and with their direction of movement from their current index

10

11

8

5

3

4

6

9

2

1

7

<--

<--

-->

-->

-->

<--

<--

<--

<--

<--

-->

Output : 

10	11	9	3	1	7
<--	<--	<--	<--	<--	-->

Explanation of output: 

Fishes with size 10 and 11 won't collide hence escapes, 

4 eats 3,  5 eats 4 , 6 eats 5 , 8 eats 6 , 9 eats 8,  then 2 and 1 survives because their behind bigger fish 9. Fish 7 survives because from its current position it will not collide with any other fish , hence the output.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

import java.util.Stack; /** * Bigger fisehes eat smaller ones , in diff direction , * No Fish Eats any other fish of same direction. * Assume all fish sizes are different * @author prateek */ public class EatFishProblem { public static void main(String[] args) { int[] arr1 = {10, 11, 8, 5, 3, 4, 6, 9, 2, 1 , 8} ; int[] dir1 = {-1, -1, 1, 1, 1, -1, -1, -1, -1, -1 , 1} ; solve(arr1,dir1); } static boolean solve(int[] arr,int[] dir){ Stack<Integer> rightDir = new Stack<Integer>(); Stack<Integer> leftDir = new Stack<Integer>(); int i = 0; //Skip all fishes moving to left in the beggining while(dir[i]!=1){ printFish(arr[i],dir[i]); i++; } int len = arr.length ; while(i<len){ if(dir[i] ==1 ) rightDir.push(arr[i]); else leftDir.push(arr[i]); eatFish(leftDir,rightDir); //if Fishes are empty in right stack, print fishes of the left stack //because these fishes moving to the left wont ever collide with subsequent fishes moving the right if(rightDir.isEmpty()) printStackInReverse(leftDir,-1); i++; } //Print Fishes moving the right first printStackInReverse(rightDir,1); printStackInReverse(leftDir,-1); return false; } /** Print stack in reverse order */ static void printStackInReverse(Stack<Integer> stack, Integer direction) { if(stack.isEmpty()) return ; Stack<Integer> temp = new Stack<Integer>(); while (!stack.isEmpty()) temp.push(stack.pop()); while (!temp.isEmpty()) printFish(temp.pop(), direction); } /** Eats fish from the stacks , depending on size */ static void eatFish(Stack<Integer> left, Stack<Integer> right){ while(!(left.isEmpty() || right.isEmpty())){ if(left.isEmpty() || right.isEmpty()) return ; else if(left.peek() > right.peek()) right.pop(); else if(left.peek() < right.peek()) left.pop(); else return ; } } static void printFish(int size, int direction){ System.out.println(direction == 1 ? size + "--> " : "<--"+size + " "); } }

Post your comments and suggestions if any.
Happy Coding :)

Validate Brackets

Problem Statement:
    Given a sequence of brackets, validate if the sequence is valid.

Solution:
Run Source Code

We all must have solved this problem during college as common application of stack for solving mathematical expressions. Below is the implementation to validate given sequence of brackets.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

import java.util.HashMap; import java.util.Map; import java.util.Stack; /** * Given an sequence of brackets , confirm if sequence is valid * @author PRATEEK */ public class ValidateBrackets { private static Map<Character,Character> hash = new HashMap<>(); static { hash.put('{','}'); hash.put('[',']'); hash.put('(',')'); } /** * Sub-routine to validate the sequence of brackets * @param s * @return */ public static boolean validate(String s){ char[] arr = s.toCharArray(); Stack<Character> stack = new Stack<>(); for(Character c:arr) { switch (c) { case '[': case '{': case '(': stack.push(c); break; case ']': case '}': case ')': { if(hash.values().contains(c)) { if(!stack.isEmpty() && hash.get(stack.peek())==c) stack.pop(); else if(stack.isEmpty()) return false; } } break; default: break; } } return stack.isEmpty(); } public static void main(String[] args) { String s= "{()}[]"; boolean isValid = validate(s); System.out.println("input: "+s); System.out.println("output: " +isValid); } }

Download Source Code
Please comment and post your suggestions.
Happy Coding !! :)

Two Stacks

Problem Statement: 
    Implement two stacks in an array.

Fig: Two Stack implementation

Source Code
Solution:

 For implementing two stacks in an array efficiently we will take two TOP pointers which grow from opposite sides of the array.

PUSH , POP , PEEK takes the "StackNumber" argument which decides on which stack operation is to be performed.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

/** * Push Operation * @param stackNum 0: 1st stack , 1: 2nd stack * @param data : data to be pushed * @throws InterruptedException */ public void push(int stackNum, int data) throws InterruptedException{ Thread.sleep(10); if(stackNum==1){ pushToStack1(data); } else if(stackNum==2) pushToStack2(data); else System.out.println("Invalid Stack Number"); } public int pop(int stackNum) throws InterruptedException{ Thread.sleep(10); if(stackNum==1) return popFromStack1(); else if (stackNum==2) return popFromStack2(); else{ System.err.println("Invalid Stack"); return -1; } } public int peek(int stackNum) throws InterruptedException{ Thread.sleep(10); if(stackNum==1) return peekFromStack1(); else if (stackNum==2) return peekFromStack2(); else{ System.err.println("Invalid Stack"); return -1; } }

Please comment and post your suggestions.
Happy Coding!!:)

Three Stacks

Problem Statement:
    Implement three stacks in a single array.

Fig: Implement three stacks in a given array

Source Code
Solution:
The concept is to divide the given array into three parts and using auxiliary space to store status of "Top" pointer of each stack.

Push and Pop operation accepts an extra argument , which specifies on which stack the operation is to be performed.

Below is the implementation  of PUSH, POP and PEEK subroutines.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

private int stackSize=5; private int[] tops={-1,-1,-1}; private int[] arr=new int[stackSize * 3]; /** * Push operation * @param stackNum : specifies the stack number * @return: insertion status * @throws InterruptedException */ public boolean push(int stackNum, int item) throws InterruptedException{ int index= stackNum * stackSize + tops[stackNum] + 1; if(tops[stackNum] < stackSize -1 ){ tops[stackNum]++; arr[index]=item; Thread.sleep(10); System.out.println(Arrays.toString(arr)); return true; } else{ System.err.println("Stack Full"); return false; } } /** * Pop operation * @param stackNum: specifies the stack number * @return the poped item * @throws InterruptedException */ public int pop(int stackNum) throws InterruptedException{ if(tops[stackNum]==-1) { System.err.println("Stack is Empty"); return -1; } int index= stackNum * stackSize + tops[stackNum]; tops[stackNum]--; int item= arr[index]; arr[index]=0; Thread.sleep(10); System.out.println(Arrays.toString(arr)); return item; } /** * Peek operation * @param stackNum: specifies the stack number * @return top element of the specified stack */ public int peek(int stackNum){ if(tops[stackNum]==-1) { System.out.println("Stack is Empty"); return -1; } int index= stackNum * stackSize + tops[stackNum]; return arr[index]; }

Happy Coding !! :)