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 !! :)

Shell Sort

Problem Statement : 

Write the code for Shell Sort.

Solution : 

Shell sort is an extension of Insertion sort where number of jumps of the corrected element reduces by using simple concept comparisons of elements separated by a gap.

Below is the code for shell sort.

Thanks for visiting the page, post suggestions and comments.
Happing coding !! :)

Distribute Coins in Binary Tree

Problem Statement : 

Distribute Coins in Binary Tree

Given the root of a binary tree with N nodes, each node in the tree has node.val coins, and there are N coins total.
In one move, we may choose two adjacent nodes and move one coin from one node to another.  (The move may be from parent to child, or from child to parent.)
Return the number of moves required to make every node have exactly one coin.

Solution : 

The first time I saw this question it was difficult to guess what is expected and seemed to be tough, but after discussing with my partner we came up with the solution.

The coins needs to be distributed across the tree, we at every node are returning the number coins required from left & right (which can be negative as well) and -1 (for the node itself) and passing up the tree. Whatever the requirement comes from left and right(which can be negative as well, if coins are needed) are the number of moves hence we are taking absolute value to count.
Below is the implementation.

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

class Node { public Node left; public Node right; public int data; public Node(int data) { this.data =data; } } /** * Distribute Coins across the Tree */ public class DistributeCoins { private int result = 0; public int getMoves(Node root) { result = 0; distribute(root); return result; } private int distribute(Node root) { if(root == null) return 0; int left = distribute(root.left); int right = distribute(root.right); result += Math.abs(left) + Math.abs(right); return root.data + left + right - 1 ; } public static void main(String[] args) { DistributeCoins obj = new DistributeCoins(); Node root = new Node(1); root.left = new Node(0); root.right = new Node(2); int moves = obj.getMoves(root); System.out.print("Number of Moves : " + moves); } }

Thanks for visiting us.
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.