# Interview Questions 7

April 23, 2010 3 Comments

1. How will you write thread-safe strtok function.

2. Given a polygon and a point, you have to find that whether the point is inside the polygon or outside.

3. How to identify bits that alternate 1 and 0. Ex: 101010, 10101, 01010, 01

4. Given a set of points in a plane. Write a function to check if there exists a vertical line of symmetry in this plane.

5. What has to be done in order to be able to do a O(logn) binary search on a linked list.

6. Given a sorted array (ex. {1,2,3,4,5,6,7,8}). A random number from the array is taken and put the left side array to right side and left side array to right side. In the example; if 6 is randomly taken, the array will become like {7,8,6,1,2,3,4,5}

Question:

Given the above mangled array, write a searching algorithm to find a number present or not. That algo should not be of O(n) solution.

7. Write a function which takes a number as input and returns it next number. Condition: the next and given number should have equal number of 1’s in its binary format.

Example: 5 – 101 its next number 6-110. both have two 1’s.

5. Skip List

6. Array can be divided into 3 parts…. first increasing … second pivot … third increasing…

After finding the pivot in O(log n) , we can do any search in respective parts in O(log n)

7.

unsigned snoob(unsigned x) {

unsigned smallest, ripple, ones;

// x = xxx0 1111 0000

smallest = x & -x; // 0000 0001 0000

ripple = x + smallest; // xxx1 0000 0000

ones = x ^ ripple; // 0001 1111 0000

ones = (ones >> 2)/smallest; // 0000 0000 0111

return ripple | ones; // xxx1 0000 0111

}

courtesy: HAKMEM

Hi Avi,

It would be good if you can start sharing solutions to your earlier problems(Interview problems-1 etc) in new posts.

Hi Amar,

Surely I’ll start posting solutions in the coming posts ( now the questions seem to be difficult to dig up 😛 ). Right now I’m busy with a lot of other stuff. Keep suggesting your approaches, I’ll start posting solutions as soon as I am settled.

Avi