Interview Questions 7

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.

Advertisements

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

3 Responses to Interview Questions 7

  1. Amar says:

    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

  2. Amar says:

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

    • Avi Dullu says:

      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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: