Blog # 27 : Some Important Data Structure Questions : Set 2

1).merge two height balanced binary trees to get another height balanced

 binary tree.

--------------------------------------------------------------
2).given an unsorted array of n integers, find that pair of integers
which gives the maximum sum.
--------------------------------------------------------------------------------------------
3) slight modification.(use heap) find the maximum sum giving combination of k integers.
--------------------------------------------------------------------------------------------
4)sudoku solver
--------------------------------------------------------------------------------------------
5)How do you find  a loop in a linked list?


               1) ptr method
               2) Go on reversing the linked list.
                     If you reach the head again, the list has a loop
--------------------------------------------------------------------------------------------
6) construct a n element binary tree from its inorder and preorder traversals kept in two arrays A[n] and B[n].
{ u can get the roots of each subtree in preorder array. Then we can partition the inorder array into left and right subtrees. Thus this problem can be solved recursively...}


--------------------------------------------------------------------------------------------
7)we are given the answers to a crossword puzzle...we need to generate the blocks...that is the question is to be framed..what data structure do u think should we use for this????(may be trie,linked list.??)
----------------------------------------------------------------------------------------------------
8)how can we reverse a sentence.its not string reversal
example;
given input "this is me"
the output should b "me is this"
{Use a stack !! first "push" every word in correct order.. then "pop" them out... the resulting string will be in reverse order !}
------------------------------ ----------------------------------------------------------------------
9)def. of tree, graph, linked list and many more
----------------------------------------------------------------------------------------------------
10) How do you find a loop in a Binary tree in a most efficient way.
{ by maintaining flag variable in node data.if already traversed ,flag value z true,otherwise  false.
suppose recursive function access the already traversed node,then we can conclude that this tree is having loop.}
----------------------------------------------------------------------------------------------------
11) If 'n' is even donfiltered=n/2
Else if 'n' is odd donfiltered=3*n+1.
If you keep on doing above said operations 'n'will converge to 1 at some point.
You are given a set of numbers (say 65 to 125.Give an efficient solution to find out which number converges to 1 the quickest.
----------------------------------------------------------------------------------------------------
 12) sort an array having elements only 0 and 1 in O(n)time and sorting should terminate immediately after array gets sorted.(1. find the first occurrence of
 1. now find the first occurrence of 0.
2. when u are having two marker one at first 1 and other at first 0. swap  them.}
----------------------------------------------------------------------------------------------------
13)find out the median of two sorted arrays as if this is one sorted array with O(1) space constraint.
----------------------------------------------------------------------------------------------------




14)how will you find out that a given binary tree is binary search tree.
 (inorder traversal and check 4 sorted nos.)


{  

isBST(Node *node){
    if(node == NULL)
          return TRUE;
    if (node->left->data > node->data )
          return FALSE;
    else
          return isBST(node->left);
    if(node->right->data < node->data)
          return FALSE;
    else
          return isBST(node->right);
}
----------------------------------------------------------------------------------------------------
15) given two node pointers in a binary tree . find out the closest common ancestor of the  nodes.


{
     int postOrderToFindLCA(elem *root,elem a,elem b)
{
    if(root==NULL) 

            return 0;
    if(root->left!=NULL)
            left=postOrderToFindLCA(root->left);
    if(root->right!=NULL)
            right=postOrderToFindLCA(root->right);
     if(right+left == 2)
           {
                  printf("I am the LCA%d\n",root->id) ;
                  return 0;

           }
         if(root->id == a->id || root->id == b->id)
           {
                   return 1;
           }
          return (left+right);
}
----------------------------------------------------------------------------------------------------
16. Algorithm to swap two words in a given sentence.
Constraint: You can use only one extra char variable
( reverse the whole sentence. then reverse it with delimiter ' '.)
----------------------------------------------------------------------------------------------------
17). Given the root of a binary tree, write a routine to find the depth of the tree.
 depth ( Tree  T)
{
If isnull(T) then return 0;
else return
max(depth(T->right),depth(T>left))+1
}
----------------------------------------------------------------------------------------------------
18)Given the head pointer of a singly linked list, print the contents of the list in reverse order.
Constraints - O(1) space
 print(node head)
{
if ( head != null)
{
if(head->next == null)
printf("%d",head->element);


print(head->next);


printf("%d",head->element);
}
----------------------------------------------------------------------------------------------------
19) Algorithm to find the number of ones in the binary form of a given number "n". An efficient method.
#include <stdio.h>
main()
{
int x,count=0;
scanf ("%d",&x);
while (x!=0)
{
count++;
x=(x&(x-1));
}
printf (" %d  ",count);
}
----------------------------------------------------------------------------------------------------
20)Given a string of length N, find whether there exits an even length palindrome substring.
----------------------------------------------------------------------------------------------------
21) Given an array arr[a1 a2 ... an b1 b2 ...bn]
Arrange in order arr[a1 b1 a2 b2 .. an bn] in O(n)
----------------------------------------------------------------------------------------------------
22) Given N sets of integers( Assume suitable representation), Device an algorithm to print the cross product of N sets, N known at runtime. complexity?
----------------------------------------------------------------------------------------------------
23)Algo to compute determinant of an array[N][N]
----------------------------------------------------------------------------------------------------
24) Array of size N is given, N is even. In this array one entry is repeated n/2 times and the remaining n/2 entries are unique. Write algo to find the repeated value. Complexity?
----------------------------------------------------------------------------------------------------
25)Given an array which represents a tree. Find out the distance between two elements. Distance between tree-nodes is length of their path from one to other through root. Assume array is represented as heap.
----------------------------------------------------------------------------------------------------
26)Convert a tree into doubly linked list such that the elements in the list are in order same as inorder traversal of tree.
------------------------------------------------------------------------------------------ ----------
27)write a program for Intersection of two sets for general data structures in O(nlogn) complexity or if u can minimise the complexity lower than that it would be great..
----------------------------------------------------------------------------------------------------
28) Can any one come up with generic solution for structurally unique binary search trees if yu are give a set of numbers?
( http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtaln5.html)
----------------------------------------------------------------------------------------------------
29)Compute the minimum (min) or maximum (max) of two integers without branching
int x;  // we want to find the min,max of x and y
int y;
int r;  // the result goes here
r = x - ((x - y) & -(x < y)); // max(x, y)
r = y + ((x - y) & -(x < y)); // min(x, y)
----------------------------------------------------------------------------------------------------
30)int v;      // we  want to find the absolute value of v
int r;      // the result goes here


r = (v ^ (v >> (sizeof(int) * CHAR_BIT - 1))) -
   (v >> (sizeof(int) * CHAR_BIT - 1));
----------------------------------------------------------------------------------------------------
30)Compute the sign of an integer
int v;      // we want to find the sign of v
int sign;   // the result goes here
// CHAR_BIT is the number of bits per byte (normally 8).
sign = v >> (sizeof(int) * CHAR_BIT - 1); // if v < 0 then -1, else 0.
----------------------------------------------------------------------------------------------------
31)Determining if an integer is a power of 2
unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here
f = (v & (v - 1)) == 0;
Note  that 0 is incorrectly considered a power of 2 here. To remedy this, use:
f = !(v & (v - 1)) && v;
----------------------------------------------------------------------------------------------------
32)Reverse bits the obvious way
unsigned int v;           // reverse the bits in this
unsigned int t = v << 1;  // t will have the reversed bits of v
int i;
v >>= 1;
for (i = sizeof(v) * CHAR_BIT - 2; i; i--)
{
 t |= v & 1;
 t <<= 1;
 v >>= 1;
}
t |= v;
( good link-> http://graphics.stanford.edu/~seander/bithacks.html)
----------------------------------------------------------------------------------------------------
33) Reverse an N-bit quantity in parallel in 5 * lg(N) operations:


unsigned int v; // 32  bit word to reverse bit order


int const S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
int const B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};


v = ((v >> S[0]) & B[0]) | ((v << S[0]) & ~B[0]); // swap odd and even bits
v = ((v >> S[1]) & B[1]) | ((v << S[1]) & ~B[1]); // swap consecutive pairs
v = ((v >> S[2]) & B[2]) | ((v << S[2]) & ~B[2]); // swap nibbles ...
v = ((v >> S[3]) & B[3]) | ((v << S[3]) & ~B[3]);
v = ((v >> S[4]) & B[4]) | ((v << S[4]) & ~B[4]);


The following variation is also O(lg(N)), however it requires more operations to reverse v. Its virtue is in taking less memory by computing the table entries on the fly.


unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;
while ((s >>= 1) > 0)
{
 mask ^= (mask << s);
 v = ((v >> s) & mask) | ((v << s) & ~mask);
}


------------------------------------------------------------------------------------------------------
34)Compute modulus division by 1 << s without a division operator


const unsigned int n;          // numerator
const unsigned int s;
confiltered= 1 << s; // So d will be one of: 1, 2, 4, 8, 16, 32, ...
unsigned int m;                // m will be n % d
m = n & (d - 1);
-------------------------------------------------------------------------------------------------------
35)largest sum of contiguous integer
-------------------------------------------------------------------------------------------------------
36)  Given an array of  numbers,How can we find the most frequently occuring element?Without using extra space...
-------------------------------------------------------------------------------------------------------
37)  If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?.learn general approach
-----------------------------------------------------------------------------------------------------
38)absolute value code(2 lines)
-----------------------------------------------------------------------------------------------------
39)Write a routine that prints out a 2-D array in spiral order(o(1)
space)
-----------------------------------------------------------------------------------------------------
40) A version of the "There are three persons X Y Z, one of which always lies".. etc..
-----------------------------------------------------------------------------------------------------
41)An  array of pointers to (very long) strings. Find pointers to the (lexicographically) smallest and largest strings.
-----------------------------------------------------------------------------------------------------
42) Given a list of numbers ( fixed list) Now given any other list, how can you efficiently find out if there is any element in the second list that is an element of the first list (fixed list).
------------------------------------------------------------------------------------------------------
43)http://www.blackboxjobs.com/show/?co=7e4bf9b5-877d-4ad1-9a09-6d973fcff699
http://wiki.mattgoyer.com/Wiki.jsp?page=Interviews