# Category: Amazon Questions

## Find longest Snake sequence in a given matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to find out the snake sequence which has the max­i­mum length. There could be many snake sequence in the matrix, you need to return the one…

## 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.…

## Dynamic Programming — Count all paths from top left to bottom right of a mXn matrix

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. Example:…

## 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…

## Dynamic Programming — Maximum Subarray Problem

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum. Exam­ple: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5,…

## Kadane’s Algorithm — Maximum Subarray Problem

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum. Exam­ple: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5,…

## Convert Binary Tree into Threaded Binary Tree

Objec­tive: Given a binary tree write an algo­rithm to con­vert it into threaded binary tree. Note: Tree node has extra Boolean field to be used. In ear­lier arti­cle “Intro­duc­tion to Threaded Binary Tree” we have…

## 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…

## Swap Nodes in pairs in a Linked List by changing links

Objec­tive: Given a linked list write an algo­rithm to swap nodes in pairs by chang­ing links . Ear­lier we have seen “Swap Every Kth node in a Linked List”, where we have seen how to…

## 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…

## Binary Tree-Postorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for pos­torder tra­ver­sal. Exam­ple: Ear­lier we have seen “What is pos­torder tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will…

## Binary Tree-Inorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for Inorder tra­ver­sal. Exam­ple: Ear­lier we have seen “What is Inorder tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will…

## 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 — Maximum size square sub-matrix with all 1s

Objec­tive: Given a matrix of 0’s and 1’s (binary matrix). Find out Max­i­mum size square sub-matrix with all 1’s. Exam­ple: Approach: Base Cases: If only one row is given then cells with 1’s will be…

## 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

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…

## Find the Second Largest Element in an Array

Objec­tive: Given an array of inte­gers. find the sec­ond largest ele­ment in the array. Exam­ple: int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 }; Sec­ond largest Ele­ment : 44 Approach:…

## 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…

## Find a Number occurring odd number of times in a Given array

Objec­tive: Given a array of inte­gers, in which every ele­ments occurs even num­ber of times except one num­ber which occurs add num­ber of times. Find out that num­ber. Exam­ple:   int[] A = {…

## 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:

## Check If One Binary is Mirror Tree of another Binary Tree.

Objec­tive: — Given two binary trees check if they are mir­ror image of each other. 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 the Height of a tree without Recursion

Objec­tive: — Find the Height of a tree with­out Recur­sion. In our ear­lier post “Height of tree” we had used recur­sion to find it. In this post we will see how to find it…

## Magic Index — Find Index In Sorted Array Such That A[i] = i.

Objec­tive: Given a sorted array of dis­tinct inte­gers, Find the Magic index or Fixed point in the array. Magic Index or Fixed Point: Magic index or a Fixed point in an array is an index…