# Programming Problems 12

March 20, 2010 8 Comments

A few more questions which I dug up from my laptop :). I feel that people are taking interest in problems now so I’ll try to solve more problems and put them here or I’ll re-post the older problems. Enjoy 🙂

1. Given an integer array of length n, find 2 numbers which has maximum XOR.

2. Given a string and a array of smaller strings. Design a method to find out every occurence of smaller implementation in larger string.

3. A semi-connected graph is a graph that for each pair of vertices u,v, there is either a path from u to v or a path from v to u. Give an algorithm to test if a graph is semi-connected.

4. 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; };

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. Print a 2D Youngs Tableau (rows and columns sorted ) in sorted order in less than O(n^3).

6. Input : You have been given a sequence of integers.

Now without actually constructing BST from the given sequence of integers (assuming the sequence is pre-order) determine if each node of BST has single child (either left or right but not both).

Output : YES if given integer sequence corresponds to such a BST. otherwise say NO.

Ex. Say NO for 16,10,8,9,29,27,22.

Say YES for 10,19,17,14,15,16

4: is to save the paths to the nodes A and B from root, then find the highest common ancestor of both ( point of intersection) , if not then they the path passes through the root.

Once you find the intersection, it is easy to print the path from A to B

2. is’t this same as LCS of 2 strings.

3. A semiconnected graph test ( googled it!)

Step1: Reverse all edges in G, we get graph G’.

Step2: For each node v ∈ V (G), do BFS or DFS on both G and G’, we get two sets of points

Reachablev (G) and Reachablev (G’ ).

Step3: Check if Reachablev (G) ∪ Reachablev (G ) = V (G) − v. if false, then G is not a semi-

connected graph, return false.

Step4: Repeat step 2 and 3 until all nodes are tested. Return true.

Reversing takes O(m+n), BFS or DFS takes O(m+n), Checking can be done in O(n), and we

have n nodes, so in total worst case running time is O(n(m+n)).

6. O(n^2) algo for this is intuitive. For every node in array(traverse from left to right),

all the other nodes must be less or all the nodes must be greater than it.

O(n) algo can be achieved if we take a min,max pair and keep updating it (constricting it) as we move on. Not sure about this though. I will have to check it on some cases.

O(n) solution exists for this problem. Just try out on a couple of sequences and you’ll notice the pattern.

Nice approach to target the question though 🙂

3. A sort of addendum to this question. how to reverse a graph which is represented as adjacency list, without using extra space?

2. Rabin-Karp is the method . http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm

You can do much better than this… think some fancy data structure 🙂

Suffix tree is the solution..right?