# Interview Problems 24

July 2, 2011 Leave a comment

1. Given a linked list structure where every node represents a linked list and contains two pointers of its type:

(i) pointer to next node in the main list.

(ii) pointer to a linked list where this node is head.

Write a C function to flatten the list into a single linked list. (from here)

2. Hundred of millions of irregular shape objects are moving in random direction. Provide data structure and algo to detect collision. (from here)

3. You are given an array of integer A[1..n] and a maximum sliding window of size w. you need to output an array B where B[i] is the maximum in A[i, i+w-1]. (from here)

4. [Design] Find duplicate profiles in Facebook.

5. You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal. (from here)

6. You have a stream of random numbers that are inserted into an expanding array. How can you maintain the current median and what is the complexity.

7. Given n arrays, find n number such that sum of their differences is minimum. For e.g. if there are three arrays

A = {4, 10, 15, 20}

B = {1, 13, 29}

C = {5, 14, 28}

find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here the answer is a = 15, b = 13, and c = 14

8. [Coding] Write a C/C++ program to create a bitmap of any size as determined by user. Say user says 64k bitmap, then create 64k long bitmap. Have set and unset methods.

9. Reorder 1st string based on 2nd string.

eg: (tractor,car)

output: carrtto or carrott or carrtot.

10. There is a straight roads with ‘n’ number of milestones. You are given an array with the distance between all the pairs of milestones in some random order. Find the position of milestones.

Example:

Consider a road with 4 milestones(a,b,c,d) :

a bcd

Distance between a and b = 3

Distance between a and c = 8

Distance between a and d = 10

Distance between b and c = 5

Distance between b and d = 7

Distance between c and d = 2

All the above values are given in a random order say 7, 10, 5, 2, 8, 3.

The output must be 3,5,2 or 2,5,3

## Recent Activity