Interview Questions 17

1. Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ? [Hint: This is a nice link to go through]

2. [Old school tricks :D] You are given have a datatype, say X in C. Determine the size of the datatype, without declaring a variable or a pointer variable of that type, and, of course without using the sizeof operator!

3. Reverse a string using only bitwise operators and without temporary storage.

4. Two rectangles are given. As a struct having {bottomleft-x, bottomleft-y, topright-x, topright-y}. You are given two rectangles R1, R2, determine if they intersect.[ Basic Geometry]

5. Write a Generic Swap Macro in C.

6. Given a list of machines where each machine has a hard disk limit and memory capacity and given a list of processes where each process requires certain hard disk space and memory, write an efficient algorithm to match processes to machines. (You may assume process to server mapping is 1:1).

7. A container is filled up with balls. Each ball has a value. Red = 7, Yellow = 5, Green = 2, Blue 2. Some balls are removed from the container and the product of their value is 147,000. How many red balls have been removed?

8. Find out Non-Decreasing subsequence of length k with maximum sum in an array of n integers ? [ Hint: here].

9. You have 21 chocolates and 91 roses, how many bouquets can you make without discarding neither a rose nor a chocolate. All the bouquets must have the same number of chocolates and roses for you.

10. If you want to search for a friend on Facebook, what are the possible strategies that you could use. You are a programmer and can also access Facebook’s Social Graph API. Make your own assumptions. How could you make it a ‘Friend Finder’ app?


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

5 Responses to Interview Questions 17

  1. Anuj Verma says:

    Q 2.
    #define MYSIZEOF(X) ((X*)0 +1)

  2. Bug says:

    how will you determine the size of the datatype, without declaring a variable or a pointer variable of that type, and, of course without using the sizeof operator!

  3. beginner says:

    9. 7 bouquets each containing 3 chocolates and 13 roses

  4. beginner says:

    7. two red balls have been removed.

  5. beginner says:

    machines [300,24] [200, 15] [250, 50] [100, 45]
    processes [50,50] [75, 24] [275, 20] [190, 10]
    sort the machınes and processes according to their disk space need and availability
    machines sorted -> [100, 45] [200, 15] [250, 50] [300,24]
    processe sorted -> [50,40] [75, 24] [190, 10] [275, 20]
    run over the process list and check from the beginning if any machine is suitable for taht process. This is a first match algo I think.
    [50,40] [100,45]
    [75,24] [250,50]
    [190,10] [200,15]
    [275,20] [300,24]
    is hard disk space is enough and memory is not enough check the next and continue like that.
    There must be a field for machine class that is about the availibility of the machine and
    while traversing the machine list we need to check that.
    Complexity is O(mn + mlogm + nlogn) where m is the number ofprocesses and n is the number of machines

Leave a Reply

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

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