# Programming Problems 5

October 3, 2009 4 Comments

**1. Distance in a dictionary**

You have a dictionary of N words each of 3 chars. Given 2 words you have to find the optimum path between the 2 words. The optimum path contains the words in the dictionary each word at a distance of 1 from the previous word.

for eg source = cat , target = sun

path is

cat -> bat -> but -> bun -> sun

given all these words are in the dictionary

**2. Nth number with m binary 1s**

There is a series of numbers in ascending order. All these numbers have the same number of binary 1s in them. Given the number of 1 bits set in the numbers, write an algorithm/C program to find the nth number in the series.

**3. kth largest in the array**

You have an array of numbers; you need to find the nth largest in the array in 0(n)

**4.Find the path in two nodes of a binary search tree**

Suppose you have a tree. A binary tree (for something like *simplicity* :p). You are traversing it (using infix, postfix or prefix) to search for a node. You find your required node. You just realized that you need to know the path from this node back to the root node (and/or vice versa). Given the following description of the structure of the tree node that you “**cant**” change:

struct node{Data data; node *right,*left;};

what will you strategy be to tackle this problem.

To make it more intresting (or maybe just the application of the above problem) suppose you find the node A and a node B in consecutive searches. Now what will your strategy be to show a path from A to B. (not neccesarily from the root of the whole tree, but possibly).

**5. Inplace merging in an array**

If i have an array which contains partially sorted lists. Can you suggest and algorithm which can do an in-place merging of the sorted lists.

eg: 40, | 20, 30, | 10, 15, 75, 85

In the above example there are 3 partially sorted lists

2. smallest number with n 1s is the number in which all ones are at the least signicant bits. for eg for n=5 and assuming 32 bit number smallest no is 0x0000001f. now in order to get the next no. traverse the current from right. unset the 1st one. and set the 1st 0 and now move all other 1s ( 1s to the right of the bit which is jst set to the right). repeat this procedure n-1 times to get nth number.

3. using hoare partitioning technique

5. make a min heap from 1st element of each partially sorted array. the element at the top is the minimum. now print it and delete it from heap. and take the next element from that array to which this min element originally belonged. and insert it into the proper place in heap.. repeat this procedure until all elements are printed..

please provide solution for 1 and 4..

please correct me if i am wrong or if there is any better approach

2. ur algo is of exponential order, can be optimized a lot.

3. sure, better ?

5. read up this link.

will update with hints.

5. a second thought

take 1st two sorted list. reverse the second list. now apply bitonic sort on them. now we have merged the first two list and we have got a single sorted list from it. now repeat the procedure for this list( which we have just obtained ) and nest list.. i hope this must be fine.. still thinking for better approach.

4. for 1st part ( path from root to some node)

take a string and store the path in string while searching the node. for eg if the value is < root value we have to go to left so store in string "l"… keep storing the path till u reach the node..

2nd part path between any nodes

just find the lowest common ancestor of the given nodes. now the shortest path is the path from 1 node to other via lca..