Programming Problems 12

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


About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

8 Responses to Programming Problems 12

  1. Neet says:

    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. Neet says:

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

  3. Amar says:

    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.

    • Avi Dullu says:

      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 🙂

  4. Amar says:

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: