## Monday, July 21, 2008

### Microsoft Questions at IIT Delhi

1) Two linked lists intersect at one node (imagine Y shape)...after intersecting, remaining nodes are common to both the link lists. how do u find the point of intersection

2) Given a BST, how do u check whether it is a valid BST

3) You have n machines, each having n integers. Now u have to find median of these n^2 numbers, but u can load only 2n integers at a time in memory

4) Given an array having 16000 unique integers, each lying within the range 1
5) Remove alternate nodes from a link list

6) Write code for removing loop from a link list

7) You have a BST containing integers. now Given any two numbers x and y, how do u find the common ancestor of nodes which have these values in them. You are given pointet to root of the BST.

8) Code for printing all permutations of a string.

9) Code for reversing words of the string

Solution for Qn 4   4) Given an array having 16000 unique integers, each lying within the range 1   Solution: Have an array of 2500 bytes (memory equaivalent of 625 ints) - Each bit in the array will show the presence/absence of a num betw 1-20,000. Lets call this the "presence-bit-map".

Since you can store the presence of 8 nos in a byte, you need (20,000/8) = 2500 bytes.

Initialize all bytes in the presence-bit-map to 0, meaning 'absent'.

Iterate the large integer list(be it in file / mem) once. For every number encountered, set the corresponding bit to 1(indicating present) in the presence-bit-map.

Now, by scanning the presence-bit-map once, you can write the present numbers in sorted order.

` `
` `
` `
` `
` `
` `
` `
` `
` `
` `
` `
` `
` `
` `
` `
` `
`#include `
`#include <string.h>`
`#include `
`void swap(char* src, char* dst)`
`{`
`        char ch = *dst;`
`        *dst = *src;`
`        *src = ch;`
`}`
`/* permute [set[begin], set[end]) */`
`int permute(char* set, int begin, int end)`
`{`
`        int i;`
`        int range = end - begin;`
`        if (range == 1) {`
`                printf("set: %s\n", set);`
`        } else {`
`                for(i=0; i`
`                        swap(&set[begin], &set[begin+i]);`
`                        permute(set, begin+1, end);`
`                        swap(&set[begin], &set[begin+i]);       /* set back */`
`                }`
`        }`
`        return 0;`
`}`
`int main()`
`{`
`        char str[] = "abcd";`
`        permute(str, 0, strlen(str));`
`        return 0;`
`}`