# Category: Microsoft Interview

## 2D Matrix with Obstructions in it">Dynamic Programming — Count all paths in 2D Matrix with Obstructions in it

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to count all pos­si­ble paths from top left cor­ner to bottom-right cor­ner. You are allowed to move only in two direc­tions, move right OR move down.…

## Print All Diagonals of a given matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to print all the diag­o­nals of matrix. Exam­ple: Approach: We will solve this prob­lem in two parts. first half of diag­o­nals and sec­ond half of diagonals.…

## Dynamic Programming — Edit Distance Problem

Objec­tive: Given two strings, s1 and s2 and edit oper­a­tions (given below). Write an algo­rithm to find min­i­mum num­ber oper­a­tions required to con­vert string s1 into s2. Allowed Oper­a­tions: Inser­tion — Insert a new character.…

## Dynamic Programming — Box Stacking Problem

Objec­tive: You are given a set of n types of rec­tan­gu­lar 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real num­bers). You want to cre­ate a stack…

## Dynamic Programming — Highway Billboard Problem

Objec­tive:  Sup­pose you’re man­ag­ing con­struc­tion of bill­boards on the Rocky & Bull­win­kle Memo­r­ial High­way, a heav­ily trav­eled stretch of road that runs west-east for M miles. The pos­si­ble sites for bill­boards are given by…

## Double Threaded Binary Tree Complete Implementation

In ear­lier arti­cle “Intro­duc­tion to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advan­tages it has over nor­mal binary tree. In this arti­cle we will see…

## Single Threaded Binary Tree Complete Implementation

In ear­lier arti­cle “Intro­duc­tion to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advan­tages it has over nor­mal binary tree. In this arti­cle we will see…

## Introduction to Threaded Binary Tree

What is Threaded Binary Tree?? A binary tree is threaded by mak­ing all right child point­ers that would nor­mally be null point to the inorder suc­ces­sor of the node (if it exists), and all left child pointers…

## BST to Greater Sum Tree">Convert BST to Greater Sum Tree

Objec­tive: Given a binary search tree (BST), con­vert it into greater sum tree. What is greater sum tree: Greater sum tree is a tree in which every node con­tains the sum of all the nodes…

## Reverse Alternative ‘k’ nodes in a Linked List.

Objec­tive: Given a linked list and a num­ber ‘k’, write an algo­rithm to reverse alter­nate ‘k’ nodes in the linked list. This prob­lem was asked in the Microsoft and Ama­zon inter­views. Exam­ple: Approach: Recursion…

## Reverse a Linked List in groups of given size ‘K’

Objec­tive: Given a linked list and inte­ger ‘k’, write an algo­rithm to reverse the linked list in groups of size ‘k’. Exam­ple: Approach: Ear­lier we have seen how to reverse a linked list, solu­tion for…

## Generate Maximum revenue by selling K tickets from N windows

Objec­tive: Given ‘N’ win­dows where each win­dow con­tains cer­tain num­ber of tick­ets at each win­dow. Price of a ticket is equal to num­ber of tick­ets remain­ing at that win­dow. Write an algo­rithm to sell…

## Get the Sum of all left leaves in a Binary tree

Objec­tive: Given a binary tree, find the sum of all the nodes which are left as well as leaves nodes. Exam­ple:     Approach: Approach is quite sim­ple. Do the inorder tra­ver­sal check if…

## Convert binary tree to its Sum tree

Objec­tive: Given a binary tree, write an algo­rithm to con­vert it into its Sum tree. What is Sum tree: Sum tree of a binary tree, is a tree where each node in the con­verted tree…

## Dynamic Programming — Longest Palindromic Subsequence

Objec­tive: Given a string, find a longest palin­dromic sub­se­quence in it. What is Longest Palin­dromic Sub­se­quence: A longest palin­dromic sub­se­quence is a sequence that appears in the same rel­a­tive order, but not nec­es­sar­ily contiguous(not substring)…

## Dynamic Programming — Maximum Product Cutting Problem.

Objec­tive: Given a rope of length n meters, write an algo­rithm to cut the rope in such a way that prod­uct of dif­fer­ent lengths of rope is max­i­mum. At least one cut has to…

## Dynamic Programming — Longest Common Subsequence

Objec­tive: Given two string sequences, write an algo­rithm to find the length of longest sub­se­quence present in both of them. These kind of dynamic pro­gram­ming ques­tions are very famous in the inter­views like Ama­zon, Microsoft,…

## Dynamic Programming — Coin Change Problem

Objec­tive: Given a set of coins and amount, Write an algo­rithm to find out how many ways we can make the change of the amount using the coins given. This is another prob­lem in which…

## Dynamic Programming — Minimum Cost Path Problem

Objec­tive: Given a 2D-matrix where each cell has a cost to travel. You have to write an algo­rithm to find a path from left-top cor­ner to bottom-right cor­ner with min­i­mum travel cost. You can…

## All N Length Strings from Given String of Length K

Objec­tive: Print All N Length Strings from Given String of Length K where char­ac­ters can appear mul­ti­ple time. Exam­ple: String k = “ALGO” N=2 Result: AA LA GA OA AL LL GL OL AG LG

## Print All N Length Strings from Given Number K

Objec­tive: Given Num­ber K, Print all the strings of N length. Exam­ple: N = 2, K = 3 [1, 1] [2, 1] [3, 1] [1, 2] [2, 2] [3, 2] [1, 3] [2, 3]…

## Dynamic Programming — Subset Sum Problem

Objec­tive: Given a set of pos­i­tive inte­gers, and a value sum S, find out if there exist a sub­set in array whose sum is equal to given sum S. Exam­ple: int[] A = {…

## The Word Break Problem

Objec­tive : Given an string and a dic­tio­nary of words, find out if the input string can be bro­ken into a space-separated sequence of one or more dic­tio­nary words. Exam­ple: dic­tio­nary = [“I” , “have”,…

## Dynamic Programming — Longest Increasing Subsequence

Objec­tive: The longest Increas­ing Sub­se­quence (LIS) prob­lem is to find the length of the longest sub­se­quence in a given array such that all ele­ments of the sub­se­quence are sorted in increas­ing order. OR Given a…

## Backtracking — Knight’s Tour Problem

Objec­tive : A knight’s tour is a sequence of moves of a knight on a chess­board such that the knight vis­its every square only once. If the knight ends on a square that is…

## Backtracking — Search a Word In a Matrix

Objec­tive : Given a 2D matrix of char­ac­ters. Check whether the word exist in the matrix or not. If it exists then print its path. All move­ments are allowed (right, left, up, down and…

## Backtracking — N Queens Problem — Better Solution

Objec­tive : In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen’s prob­lem asks…

## Backtracking — N Queens Problem

Objec­tive : In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen’s prob­lem asks…

## Find the Kth Smallest/Largest Element in an Array

Objec­tive: Given an array of inte­gers. find the Kth Smallest/largest ele­ment in the array. Exam­ple: int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 }; K=4. 4th small­est ele­ment in given…

## Backtracking — Rat In A Maze Puzzle

Given a maze, NxN matrix. A rat has to find a path from source to des­ti­na­tion. maze[0][0] (left top corner)is the source and maze[N-1][N-1](right bot­tom cor­ner) is des­ti­na­tion. There are few cells which are…

## Dynamic Programming — Stairs Climbing Puzzle

Objec­tive: A child is climb­ing up a stair­case with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Imple­ment a method to count how many pos­si­ble ways…

## Dynamic Programming — Minimum Coin Change Problem

Objec­tive: Given a amount ‘A’ and n coins,   v1<v2<v3<.….……<vn . Write a pro­gram to find out min­i­mum num­bers of coins required to make the change for the amount ‘A’. Exam­ple: Amount: 5 Coins []…

## Merge K Sorted Arrays

Objec­tive: Given k sorted array, write an algo­rithm to merge Them into One sorted array. Exam­ple : int[][] A = new int[5][]; A[0] = new int[] { 1, 5, 8, 9 }; A[1] = new…

## Provide the Next Siblings Pointers in a Given Binary Tree

Objec­tive: — Given a binary tree with three point­ers left, right and nextSi­b­ling). Write the pro­gram to pro­vide the nextsi­b­ling point­ers. Exam­ple: Approach:

## Print All Paths From Root In a Binary Tree Whose Sum is Equal to a Given Number

Objec­tive: — Given a binary tree and X, Print all the paths start­ing from root so that sum of all the nodes in path equals to a given num­ber. Example:

## Diameter Of a Binary Tree

Objec­tive: — Given a binary tree, find the diam­e­ter of it. What is Diam­e­ter Of a Tree: Diam­e­ter of tree is defined as A longest path or route between any two nodes in a tree.…

## Find the Deepest Node in a Binary Tree.

Objec­tive: — Given a binary tree, Find the deep­est node in it. Approach: Take two global vari­able as “deep­estlevel” and “value”. start­ing with level=0, Do the inorder tra­ver­sal and when­ever you go down one level…

## Find Increasing Triplet Sub-sequence

Objec­tive: Given an inte­ger array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k]. Exam­ple : int arrA[] = { 10, 9,…

## Print All the Subsets of a Given Set (Power Set)

Objec­tive: Given a set of num­bers, print all the poss­si­ble sub­sets of it includ­ing empty set. Power Set: In math­e­mat­ics, Pow­er­Set of any given set S, PS(S) is set of all sub­sets of S including…

## Print All Possible Valid Combinations Of Parenthesis of Given ‘N’

Objec­tive: — Given “n”, gen­er­ate all valid paren­the­sis strings of length “2n”. Exam­ple: Given n=2 Out­put: (()) ()() Approach:

## Generate All Strings of n bits.

Objec­tive: — Gen­er­ate All Strings of n bits, con­sider A[0..n-1] is an array of size n. Exam­ple : n = 3 Out­put: [0, 0, 0]    [1, 0, 0]    [0, 1, 0]    [1, 1, 0] [0,…

## Implement Queue Using Stacks

Objec­tive: We know that Queue is FIFO (First-in-First-Out) and Stack is LIFO ( Last-in-First-Out). Here our objec­tive is to imple­ment queue using stacks. Approach: Take 2 Stacks, stack1 and stack2. stack1 will be used…

## Reverse The Doubly Linked List

Objec­tive: Reverse The Dou­bly Linked List. Example:

## Merge Sort in a Linked list

Objec­tive: Given a Linked List, Sort it using merge sort. Exam­ple: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Ref­er­ence : Merge Sort in array

## Merge a Linked list into another Linked List at Alternate Positions.

Objec­tive: Given two linked lists, merge one list into another at alter­nate posi­tions, if sec­ond link list has extra nodes, print them as well Exam­ple: 5 -> 10 -> 15 -> 20 ->25 -> null…

## Construct a binary tree from given Inorder and Level Order Traversal

Objec­tive: — Given a inorder and level order tra­ver­sal, con­struct a binary tree from that. Input: Inorder and level order tra­ver­sal Appraoch: int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 }; int[] levelOrder…

## Print The Top View of a Binary Tree

Objec­tive: — Given a binary tree, print it in Top View of it. What is Top View: Top view means when you look the tree from the top the nodes you will see will be…

## Inorder Predecessor and Successor in Binary Search Tree

Objec­tive: — Given a Binary Search Tree, Find pre­de­ces­sor and Suc­ces­sor of a given node. What is Pre­de­ces­sor and Suc­ces­sor : When you do the inorder tra­ver­sal of a binary tree, the neigh­bors of given…

## Rearrange Positive and Negative Elements at Alternate Positions in an Array In O(1) Extra Space

Objec­tive: Given an array arrA[] which has neg­a­tive and pos­i­tive ele­ments, rearrange the array in such a man­ner that pos­i­tive and neg­a­tive ele­ments occupy the alter­nate posi­tions and if there are extra pos­i­tive or…

## Find Kth Smallest or Largest element in an Array.

Objec­tive: Find Kth Small­est or Largest ele­ment in an Array Exam­ple: int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 }; Out­put: The 4th small­est ele­ment is : 8 Approach: Naive…