# Interview Questions 17

September 20, 2010 5 Comments

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?

Q 2.

#define MYSIZEOF(X) ((X*)0 +1)

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!

9. 7 bouquets each containing 3 chocolates and 13 roses

7. two red balls have been removed.

6.

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