st0le
5/14/2017 - 7:20 PM

# 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

# 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

# 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

# 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

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

# 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

# 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

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

# Get Find and Delete all O(1)

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

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