# Distributed Circular linked list sum

## You are given a circular linked list whose nodes are distributed. Every node has next pointer and a method send(integer). A node can talk to its next node only. Different instances of same �threads are running in the nodes. How would you implement the run method of the thread class so that each node prints the sum of complete linked list.

# Distributed binary tree sum

## You are given a binary tree where each node has an integer value, a left, right and parent pointer. Every node is an independent distributed system where a thread is running in each node. You can talk to other node only by one method called "send(node, data)". And a node can call "send" only to its children or parent. How will you design the system so that all the nodes know the total sum of values of all the nodes in the binary tree and report them asynchronously.

# Distributed doubly linked list sum

## You are given a doubly linked list whose nodes are distributed. Every node has next, previous pointers and a method send(integer). A node can talk to its next and previous nodes only. Different instances of same �threads are running in them. How would you implement the run method of the thread class so that each node prints the sum of complete linked list.

# Jumping frog problem

## There were n stones across a river. Each stone was places 1 meter apart. A frog can jump in steps of 1 meter, 2 meters, 3 meters and so on. The first jump is always 1 meter. The typical behavior of the frog is such that if it goes k meters in one jump then on its next jump it can go either k-1, k or k+1 meters. It won't jump backward. So when there were n stones across the river it could cross the river. Let's take n=10; and initial position of the frog is 0.

Some possible paths could be
1, 2, 3, 4, 6, 9, 10
1, 3, 6, 10
1, 2, 4, 7, 10
Now some of the stones across the river have been removed. Find the algorithm to figure out whether the frog would be able to cross the river after removing those stones. For example, as the frog always takes the first jump for 1 meter. If the first stone is removed then it will never be able to cross the river.Solution

# Increasing array subsequence

## You are given an integer array. Find all the subsequences of the array which has the elements in increasing order. B is a subsequence of array A if B can be formed by removing some elements from the array A without disturbing the order of elements. For example {2,5,6,1,3} is the input array, Then {2,5}, {2,6}, {2,6,1}, {2,1,3} are some of its subsequences. In these {2,5}, {2,6} are increasing subsequences.

# Share price max profit recursive

## You are given the prices of a given stock for some days. You were allowed to own at most one stock at any time and you must not hold any stock at the end of that period. You can do at most k transactions. Find out the maximum profit that you could have.

# Find a subset with given average

## An integer array is given and an average value is given. Find a subset of the array which has the given average. For example input array is 1,3,4,5 and average is 2.5 then the subset {1,4} is the answer as its average is 2.5

# Array equal sum partition

## Partition an integer array in two parts such that sum of each parts are same. The elements need not to be contiguous.

# Gold coins in pots game

## Some pots filled with gold coins and arranged in a line. There are different number of gold coins in different pots. The number is mentioned on each of the pots. Two players will take turn alternatively. In each turn a player can pick any one the two pots at the two ends of the line. Find the winning strategy for a player getting chance to play first, assuming the opponent player is also playing optimally. How many coins will the first player get if he plays optimally?

# Longest common subsequence

## Given two strings find their longest common subsequence. A subsequence is a sequence which can be derived by deleting some of the elements of the original sequence. For example. ale is a subsequence of apple. gre is a subsequence of greed. If a string is subsequence of two strings, i,e it can be obtained by removing some characters from two strings then it is called a common subsequence. The problem is to find a subsequence of highest length of two given strings.

# Longest palindrome dynamic

## Given a string find the longest possible substring which is a palindrome.

# Container loading recursive

## There are some containers with different weights. A ship can hold maximum W weight. The problem is to find out what is the maximum we can load this container using the containers so that it does not exceeds W

# Any numbers sum up to k recursive

## Given an integer array and a number k. Find out whether it is possible to have a sum k by using any number of numbers from the array.

# Any numbers sum up to k iterative

## Given an integer array and a number k. Find out whether it is possible to have a sum k by using any number of numbers from the array.

# Two numbers sum up to k unsorted

## Given an integer array and an integer k, find two numbers which sum upto k.

# Two numbers sum up to k

## Given a sorted integer array and an integer k, find two numbers which sum upto k.

# First increasing second decreasing tuple

## Given N pairs of integers, write an algorithm to sort the pairs so that�the first number in each pair is sorted increasingly while the second�number in each pair is sorted decreasingly. The first and second numbers�in each pair can be swapped. Sometimes there will be no solution, in that�case return an error.

Examples:
� � � � �*
� � � � �* Input: 1 5 7 1 3 8 5 6
� � � � �*
� � � � �* Output: 1 7 <- Swapped 1 5 6 5 <- Swapped 8 3 <- Swapped
� � � � �*
� � � � �* Input: 1 5 6 9
� � � � �*
� � � � �* Output: Not Possible

# Separate words in sentence

## Given a valid sentence without any spaces between the words and a dictionary of valid english words, find the individual words in the sentence. For example, "therearesome" -> "there are so me" "somewordshiden" -> "so me words hi den"

# Find local minima in an array

## Given an array of unique integers whose first two numbers are decreasing and last two numbers are increasing, find a number in the array which is local minima. A number in the array is called local minima if it is smaller than both its left and right numbers. For example in the array 9,7,2,8,5,6,3,4

## 2 is a local minima as it is smaller than its left and right number 7 and 8. Similarly 5 is another local minima as it is between 8 and 6, both larger than 5. You need to find any one of the local minima.

# Find longest interviewer chain

## In an organization employees are interviewed with one or more previous employees. Those previous employees are also interviewed by some other employees during their joining. In this way an interview chain is formed, where every node in the chain has been interviewed by the next node in the chain. You are given such information of interviewers for every employees. Given any employee in the organization find the longest such chain possible.

# Find order of letters

## Find the lexicographic order of letters from given lexicographic order of words.

# Merge N sorted arrays

## Given n sorted arrays. Merge them into a single sorted array.

# Max heap and BST in same structure

## Some number pairs are given. Arrange the number pairs in the form of a binary tree in such a fashion so that the first numbers in each tuple is arranged in a max heap and the second number in each tuple is arranged in a binary search tree.

# Maximum k integers using min heap

## Find k maximum integers from an array of infinite integers.

# Running Median

## Find the running median after entering every number from a sequence of infinite integers.

# Remove duplicate subtree

## Compact a binary tree by removing the duplicate subtrees. For example the binary tree given in figure 1 has two duplicate subtrees. The duplicate parts are circled in figure 2. Wherever such duplication occurs, we should remove that duplicate subtree and point the link to the existing subtree as described in figure 3

```
1
/ \
/ \
2 \
```

/ \

5 6

3
/

/

/ 2
4 /

/ 5 6
/
7
/

8 9

5
Figure 1

```
1
/ \
/ \
2 \
```

/ \

5 6

3
/

/ _____
/ / 2

4 | / \ |
/ |5 6|
/ _____/
7
/

8 9

__
/ \
| 5 |
__/
Figure 2

```
1
/ \
/ ________
2 \ |
```

|\ / \ \ |
| 5 6 \ |
| 3
| /
| /

| /

| 4

| /

| /

| 7
| /

| 8 9
|__/
Figure 3

# Draw a binary tree with ASCII

## Write a program to draw a binary tree with fixed width fonts. Represent left links with a �/� and right link with �\�. For example like this.

```
1
/ \
```

/

2

/ \ 3
4 5 /

9

8
/

6 7

# Make BST from doubly linked list

## You are given a sorted doubly linked list. Nodes of this doubly linked list have a left as previous and right as next pointer and a value. Convert this to a binary search tree using the same nodes.

# Find depth of tree from parent array

## A tree is represented by an array of integer where arr[i] represents the parent of ith node. arr[i]=-1 for root node. Find the depth of that tree

# Find all wrong pairs in a BST

## A binary tree is given. Which is supposed to be a BST, but it has some errors. Find all the pair of numbers which are not following the BST rule

# Binary tree level with maximum number of nodes

## You are given a binary tree. Print the level of the binary tree which has the maximum number of nodes. Break tie arbitrarily.

# Level order traversal without a queue

## Given a binary tree print the node values in level order without using a queue.

# Binary tree sum of nodes at odd levels

## Given a binary tree find the sum of nodes present at odd levels. That means excluding nodes at every alternate levels.

# Binary search tree with insertion order maintained

## Design a binary search tree where the insertion order is maintained.

# Find kth smallest element in a Binary search tree

## Given a binary search tree find the kth smallest element.

# Maximum sum along any tree path with positive and negative values

## You are given a binary tree with positive or negative numbers in its nodes. Find the maximum possible sum along any path of the binary tree.

# Maximum sum along any path of binary tree of positive numbers

## Given a binary tree where each node contains positive numbers, find the maximum sum that is possible along any path of the binary tree.

# Find deepest node(s) of a binary tree

## Given a binary tree find the node(s) at its deepest level. For example,

Constructed binary tree is:
1
/

2 3
/ \

4 5 8
/

6 7

## The output would be 6,7

# Remove duplicates from infinite integers

## You are given an infinite stream of integers. The stream of integers is unsorted and are provided by iterator so that you don't have the access to all the elements at once. You have to return another iterator from the input iterator so that there are no duplicates and the input order is maintained.

# Does any path adds up to a given sum

## Given a binary tree and a number, find out whether any path of the binary tree sums up to k. The binary tree nodes contain numbers. The path can be starting from anywhere, but it should not skip any node in its path. It should be continuous nodes along a path which sums up to k.

# Superimpose binary tree

## Given two binary trees, find the resultant binary tree if we put one binary tree on top of another. For example,

# Find distance between two nodes in a binary tree

## Find the distance between two nodes in a binary tree. Every node of the binary tree has left pointer, right pointer and value. There is no parent pointer given in the nodes. Given two nodes or node values of such a binary tree and root of the tree given, find the distance between the given nodes.

# Find path of a node from root

## Given a binary tree and one of its nodes, find the path from root to the given node

# Create tree from in and pre

## Create a binary tree from given inorder and preorder traversal.

# Is the binary tree BST

## Find whether a given binary tree is a binary search tree or not.

# Binary tree to linked list

## Given a binary tree create individual linked lists from each level of the binary tree.

# Linked list with postorder successor

## Create a linked list with the nodes of a binary tree in a postorder succession.

# Linked list with preorder successor

## Create a linked list with the nodes of a binary tree in an preorder succession.

# Linked list with inorder successor

## Create a linked list with the nodes of a binary tree in an inorder succession.

# Print nodes of a given level

## Given a binary tree and a level, print all the nodes of the corresponding level.

# Print binary tree bottom to top level wise

## Print a binary tree from bottom to top in level order each level in a separate row. For example,

# Print a binary tree from bottom to top

## Print a binary tree from bottom to top in level order. For example,

# Binary tree zigzag print

## Given a binary tree print it in level order zigzag form.

# Lowest common ancestor without root

## There is a binary tree where each node is having a parent pointer. We need to have an algorithm to find out the lowest common ancestor where two nodes are given, but no root node is given.

# Sum of child nodes

## In a binary tree change each node's value(except leaf node) as the sum of left and right subtree's value.

# Lowest common ancestor

## A binary tree is given and two nodes of this tree is given, we have to find out the algorithm for lowest common ancestor of the two given nodes. Common ancestor are the nodes which can be reached from two nodes by following the parent links. Lowest common ancestor is the common ancestor which has the highest depth.

# Balance the balance

## There are some weighing scales which has left and right plates. The weighing scales are very compact and plates are pretty big. As a result of this, one weighing scale can be put into another weighing scale's plate. At the same time some weights can be put onto the plates along with the weighing scale. The empty weighing scale has a fixed predefined weight. Only one weighing scale can be accommodated in one plate. However any number of weights can be put into the plate, even after putting one weighing scale. One such arrangement is given as an input to your program. There are enough supply of weights and they can be of fractional value as well. The program should add weights to the plates to balance the weighing scales. The ultimate result would be that all the weighing scales are balanced.

# Permutation of a string as substring of another

## Given a string A and another string B, Find whether any permutation of B exists as a substring of A.

For example,
if A = "encyclopedia"
if B="dep" then return true as ped is a permutation of dep and ped is a substring of A
if B="ycc" return true as cyc is a substring
if B="yyc" return false.

# Same average subset

## Given an integer array find all subsets having equal average.

# Linked list with random pointer

## A linked list is given where every node of the linked list has one next pointer and one additional pointer called random, which points to any arbitrary node in the linked list. Write a method to deep copy this linked list

# Find the Pythagorean triplets in an array

## You are given an integer array. Find all the Pythagorean triplets in this array. Pythagorean triplets are 3 numbers a, b, c such that a2+b2=c^2.

# Longest subarray with equal number of ones and zeros

## You are given an array of 1's and 0's only. Find the longest subarray which contains equal number of 1's and 0's.

# Find if two words are anagram or not

## Given two words, find whether they are anagram or not. An anagram of a word is another word which can be obtained by rearranging the letters of the first word. Without any addition or deletion of letters.

# Linked list remove duplicates

## You have an infinite linked list which is not sorted and contains duplicate elements. You have to convert it to a linked list which does not contain duplicate elements.

# All unique letter substring

## Given a string find out the longest substring which has all unique letters, i.e. no letter is repeated.

# Find shortest path in a maze

## Given a maze some of whose the cells are blocked. The left top cell is the entry point and right bottom cell is the exit point. Find the shortest path, if possible, from entry to exit through non blocked cells.

For example
Given maze

*|*|*|*|*|#|*|*|*|_|

*|*|#|*|#|*|*|*|#|#|

*|#|*|*|*|#|#|#|_|#|

*|#|*|*|*|#|*|*|#|_|

#|*|#|#|*|*|*|*|*|_|

#|*|*|*|*|*|*|#|*|*|

#|*|*|#|*|*|*|*|*|*|

#|*|*|*|*|*|*|*|#|*|

*|*|*|#|*|#|#|*|*|#|

#|#|#|#|*|#|*|*|*|_|

Shortest path

## (0,1),(0,2),(0,3),(1,3),(2,3),(2,4),(3,4),(4,4),(4,5),(4,6),(5,6),(6,6),(6,7),(7,7),(8,7),(8,8),(9,8),(9,9)

# Queue minimum using stack

## Implement a queue which has an efficient get minimum function along with enqueue and dequeue method.

# Queue using stack

## Implement a queue using stack.

# Snakes and ladders

## Given a snakes and ladder board, find out the minimum move to reach to the top.

# Towers of Hanoi

## There are 3 rods where discs can be stacked. All the discs are having different diameters. The goal of the game is to move all discs from one tower to another using the third tower. The rules are simple. Only smaller disc can go on top of the bigger discs. So the discs will be sorted according to their sizes and bigger one will be at the bottom. Only one disc can be moved at a time. you must put the removed disc in some tower, it cannot be left in any other places. At the beginning there are some discs in tower one. The goal is to move them to tower 2 following the above rules.

# Find longest path in a maze

## Given a maze some of whose cells are blocked. Left top is the entry point and right bottom is the exit point. Find the longest possible path from entry to exit that does not contain any blocked cells.

For example,
Input maze

*|*|*|*|#|#|*|#|*|#|

#|#|#|*|#|#|*|#|#|_|

*|*|*|*|#|#|*|*|*|*|

*|*|*|*|#|*|*|#|*|*|

*|*|*|*|#|*|#|*|#|_|

#|*|*|*|*|*|*|#|#|_|

*|#|#|*|#|*|*|#|_|#|

*|#|*|#|#|*|#|*|*|*|

*|*|*|#|#|*|*|#|*|_|

#|#|*|*|#|#|*|*|*|*|

Output longest path

## (0,0),(0,1),(0,2),(0,3),(1,3),(2,3),(3,3),(4,3),(4,2),(3,2),(2,2),(2,1),(3,1),(3,0),(4,0),(4,1),(5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(6,6),(6,5),(7,5),(8,5),(8,6),(9,6),(9,7),(9,8),(8,8),(7,8),(7,9),(8,9),(9,9),

# Find all possible paths in a maze

## Given a maze where some of the cells are blocked, where left top cell is the entry point and right bottom cell is the exit point, find all possible paths from entry to exit which goes through the non blocked cells.

# Find all permutations

## Find all the permutations of a given string whose letters are unique.

# Sort a stack

## A stack is given which supports the following methods. Push, pop, peek and isEmpty. Sort this stack irrespective of its inner structure.

# Stack with get minimum

## Implement a stack which provides an efficient get minimum function along with regular push and pop functionality.

# Array next element

## Given an integer array replace each number with its next minimum number in the array. For example if input array is {3,4,2,6,5,1,8,4} output would be{2,2,1,5,1,0,4,0}

# Swap without temp

## Swap two integers without using a temp variable.

# Count number of ones till N in binary

## Given a number n find total number of ones in the binary representation of the numbers 1, 2, 3, 4, ..., n

For example, if n=5

1=1 (number of ones=1)
2=10�(number of ones=1)
3=11�(number of ones=2)
4=100�(number of ones=1)
5=101�(number of ones=2)

output
7 (1+1+2+1+2)

# Next power of two

## Given a number find the lowest number which is power of 2 and greater than the given number.

# Calculate power

## Calculate x to the power y.

# Get Find and Delete all O(1)

## You will have to design a telephone directory where the following operations would be supported.

- GET: It will provide a number which is not assigned to anyone
- CHECK: Given a number it will tell whether it is assigned to anyone or not
- RELEASE: It will recycle or release a number

# Find kth node from end in linked list

## Given a linked list find the kth node from end.

# Linked list Y shape

## Given two linked lists find out whether they are converged to a single linked list or not, if yes, find there point of convergence.

# Find loop in linked list

## Given a linked list find whether the list is looped or not. A linked list is looped when one of the nodes point to any one of its previous nodes or itself. Also find the length of the loop and the starting point of the loop.

# Reverse k nodes in linked list

## Reverse every k nodes in a linked list and return the head appropriately.

# Fold a linked list

## Fold a linked list such that the last element becomes second element, last but one element becomes 4 th element and so on. For example input linked list: 1->2->3->4->5->6->7->8->9-> output linked list 1->9->2->8->3->7->4->6->5->

# Reverse linked list recursive

## Reverse a linked list

# Reverse linked list iterative

## Reverse a linked list

# Maximum arithmetic sequence in an array

## You are given an array of integers. Find the length of the longest arithmetic sequence in the array. An arithmetic sequence is contiguous array elements which are in arithmetic progression.

# Sum of array except current element

## Replace an array element a(i) with sum(a)-a(i) without using the '-' operator. Where sum(a)=a(0)+a(1)+...+a(n)

# Maximize stock profit simple

## You are given the prices of a given stock for some days. You were allowed to own at most one stock at any time and you must not hold any stock at the end of that period. Find out the maximum profit that you could have.

# Two missing numbers

## You are given an array of natural numbers from 1 to n in an array where two numbers are missing. So the given array size is n-2. You will have to find the two missing numbers.

# Sort to bring anagrams closer

## Given an array of strings sort it such that the anagrams come side by side. A word is called anagram of another word, if one can be formed by rearranging the letters of the other, without any addition or deletion of letters.

# Expand the array

## You are given a character array like this�a3b1c1d1e4f0g11. You will have to expand the array by repeating the characters denoted by the following numbers. For example the above character array will be expanded to�aaabcdeeeeggggggggggg. The given array will have more than enough trailing spaces such that you can modify the array in place.

# Maximum sum submatrix

## Given a matrix which contains positive and negative integers. Find the submatrix which has the maximum sum.

# Maximum product subarray

## Given an integer array with negative numbers and zero find the subarray with maximum product, i.e. find the contiguous array elements that produce maximum product.

# Rotate a string to make another

## Given two string find whether one string can be formed by rotating another string.

# Merge two sorted arrays in a single array with space

## A sorted array has M elements and N blank spaces. Another array has N sorted elements. merge this two arrays in the first array of size M+N

# Rotate an array k times to left

## Rotate an array k times to its left.

# Reverse the words of a sentence

## Reverse the words in a given sentence. Words are always delimited by spaces. For example if the given word is "reverse words of a sentence". The output will be "sentence a of words reverse"

# Find largest palindrome iterative

## A string is called palindrome when it is same while reading character by character from left side or right side. Given any arbitrary string find out the largest substring in it which is a palindrome.

# Find Kth largest element in sorted matrix

## Given a 2d array or matrix which is sorted by its rows and columns. Find the kth largest element from this matrix.

# Search in sorted matrix

## Given a matrix whose rows and columns are sorted, search for an element in that matrix.

# Largest sum subarray

## Given an integer array find the subarray which has the largest sum.

# Find repetition multiple sorted arrays

## Find repetition in multiple sorted arrays without using extra space. There are k sorted arrays. We have to find whether some numbers are repeating in any one of those arrays. Here k is constant and we are allowed extra space in the order of k as they are constant. The constraint is not to use extra space in order of the length of the arrays.

# Move zeros to the right with minimum swap

## You are given an integer array which contains some zeros. Move the zeros to the right side of the array with minimum number of swaps. The order of the original array can be destroyed.

# Print matrix spiral

## Print a matrix in spiral fashion.

# Least difference in array

## Find the least difference between any two elements of an integer array.

# Next larger palindrome

## Given an integer find the immediate larger integer that that which is a palindrome, example 1234212 -> 1234321, 345676 -> 346643.

# Make larger number

## Given a number whose digits are unique, find the next larger number that can be formed with those digits.

# Find maximum and minimum

## Given an array of integers, find the maximum and minimum of the array.