Interview Questions 12

1. How many string exists of the following form
a) Only characters from ‘a’ to ‘z’ allowed
b) No character is repeated
c) Length = 10
d) One and only one character in the string is lexicographically greater than the previous character

For example:
zyxwvutsrq = invalid (0)
zyxwvutrqs = valid! since q>r

2. How will you go about implementing google suggest kind of functionality for a cellphone.

3. How will u creat own bool data type which can take only true false or 0,1 in C

4. How to find how much memory your program will need?

5. Design Farmville,
Consider only crops and animals for now.
Whats classes will you have?
How will you handle interactions between various objects?
What design patterns can you use?
How will you handle millions of users?

6. has a link below each product which gives a list of items that “customers who bought this also bought”. How will you design that?

7. You have millions of documents numbered 1,2,3,4,5 ……
You also have a mapping from a word to the list of documents that contains it.
Find all the ‘pair of words’ that occur together in one and only document.

8. How will you find the page with most incoming links from billions of web-pages.

9. Generate a product key for a given product, having this conditions:
1. should be upper roman literals or 0-9 digits;
2. the key should be validated by the installer;
3. how would you check if the key was not registered before?
4. how would you find bad/offensive words in it?(eg. F**K, TIT, T1T…)

10. Given a 4×4 board with pieces in it, find if the board has 4 identical pieces. Each piece has a shape and a color. Two pieces are identical if have the same shape and color. The pieces for this board have 6 colors and 6 shapes.


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

4 Responses to Interview Questions 12

  1. Amar says:

    8. Create a list of websites and keep incrementing the count of incoming links. Isn’t this how pagerank works?

    10. We are looking at a total of 16 elements. Create an array of shapes and another of colors. Fill in the count by iterating through the 16 elements. Then check whether any one of shape equals or exceeds 4. Check the same for colors. If either condition fails, return no as answer. This is O(n). Lets say we do have some arrays of shapes and colors which equals or exceeds 4. Check for those shapes and colors.

  2. Avi Dullu says:

    Glad to see you back Amar 🙂

    8. Its not that simple :). You need to define and refine data structures for the same and should efficiently retrieve a given web page to update its incoming link count. Also notice you have billions of web pages, so simple in memory algorithms would not scale. Its a pure design problem, think distributed.

    10. I din’t get how your algorithm would be O(n). It basically is a -> position map. Should think on lines of determining if a given piece falls in any already existing group or not.

  3. Amar says:

    How about creating and maintaining a hashed list of web pages? … I haven’t studied distributed computing much. Can you please point me to some resources on this?

  4. Avi Dullu says:

    Hash table based solutions are not acceptable in real world because, as I mentioned, everything cannot be stored in memory. (Unless you are at Google using BigTable 🙂 )
    You don’t need any specific distributed computing skills to solve such problems, just think how you can use multiple machines with ~1-2GB RAM and 100-200 GB Hard disk to solve such problems. Also take care of communications issues and scalability.

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: