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.
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.
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.
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
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.
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.
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
Partition an integer array in two parts such that sum of each parts are same. The elements need not to be contiguous.
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?
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.
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
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.
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.
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
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"
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.
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.
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.
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 \ |
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
/ \
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.
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
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
You are given a binary tree. Print the level of the binary tree which has the maximum number of nodes. Break tie arbitrarily.
Given a binary tree find the sum of nodes present at odd levels. That means excluding nodes at every alternate levels.
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.
Given a binary tree where each node contains positive numbers, find the maximum sum that is possible along any path of the binary tree.
Constructed binary tree is:
1
/
2 3
/ \
4 5 8
/
6 7
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.
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.
Given two binary trees, find the resultant binary tree if we put one binary tree on top of another. For example,
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.
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.
In a binary tree change each node's value(except leaf node) as the sum of left and right subtree's value.
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.
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.
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.
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
You are given an integer array. Find all the Pythagorean triplets in this array. Pythagorean triplets are 3 numbers a, b, c such that a^2+b^2=c^2.
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.
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.
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.
Given a string find out the longest substring which has all unique letters, i.e. no letter is repeated.
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)
Implement a queue which has an efficient get minimum function along with enqueue and dequeue method.
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.
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),
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.
A stack is given which supports the following methods. Push, pop, peek and isEmpty. Sort this stack irrespective of its inner structure.
Implement a stack which provides an efficient get minimum function along with regular push and pop functionality.
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}
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)
- 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