Month: December 2009

Solution to 2 dice problem

This is the solution to the dice problem in “First technical post!?”

Here you need the sum to be exactly within the range 1-12

So how do we proceed? The total number of possible outcomes with 2 dice is 6*6 = 36. And the total numbers in the range 1-12 is 12, since the probability should be the same, every sum can occur 36/12 = 3 times. is this fine? Now since you need a sum 1, there should be atleast 1 zero and since the sum 1 should appear 3 times there should be 3 zeroes. Now since there should be a sum 12 there should be atleast one 6 on the other die, since the sum 12 should also appear 3 times, there should be 3 sixes too. Now you have 3 zeroes and 3 sixes, so 3+3 = 6, which covers all the sides of the other cube.

If you have any other number other than 0 or 6 on the other cube, the probablity will not be the same!

Survival of the Sheep

Lets solve a logical puzzle.

There is an island filled with grass and trees and plants. The only inhabitants are 100 lions and 1 sheep.
The lions are special:
1) They are infinitely logical, smart, and completely aware of their surroundings.
2) They can survive by just eating grass (and there is an infinite amount of grass on the island).
3) They prefer of course to eat sheep.
4) Their only food options are grass or sheep.

Now, here’s the kicker:

5) If a lion eats a sheep he TURNS into a sheep (and could then be eaten by other lions).
6) A lion would rather eat grass all his life than be eaten by another lion (after he turned into a sheep).

Assumptions:
1) Assume that one lion is closest to the sheep and will get to it before all others. Assume that there is never an issue with who gets to the sheep first. The issue is whether the first lion will get eaten by other lions afterwards or not.
2) The sheep cannot get away from the lion if the lion decides to eat it.
3) Do not assume anything that hasn’t been stated above.

So now the question:
Will that one sheep get eaten or not and why?

Courtesy : http://www.braingle.com/brainteasers/9026/survival-of-the-sheep.html

My understanding of Start-up interviews

Start-ups here I refer to high-end tech start-ups.   There interview process is really fantastic.  If you are a fresher going for an interview for a start-up, you need to have a very good understandings of  computer science fundamentals like Data Structure, Algorithms, Operating Systems, Data bases, and basics of networking.

Start ups really look for smart people, because what I feel is that no one starts a company just to check whether it works or not, they usually start with a vision/mission (what ever you call it) and they want good people to join them in accomplishing it.

Coming to their interview process they ask you real good algorithmic questions, its not just asking you whether you know the Matrix multiplication dynamic programming problem, but ask you a question where in you need to apply the same. I came across two cases one in which they test how (broad) many various technologies you have touch with and in the other case they test what is the technology in which you are exceptional.

Usually in start-ups you have a problem to solve and you also know a perfect solution which is very difficult to explain to others or implement. In this case you need to come up with a way/method to solve the problem irrespective of the order of complexity/ running time. Let’s launch the product, then we can come back and make it more efficient 😛 or spend good amount of time to implement it efficiently and then go out. Your choice 😉 . For example lets consider this, I think you should be aware of balancing a chemical equation, this might be done constructing a matrix and solving it using a Gaussian method or simplex method or some other stuff which are very hard to implement. This might be a efficient solution which is hard to implement. You can probably come up with a trail and error approach to balance the equation, which is a very dumb way of doing it. This is just a random example which struck my mind 😛

Note: This post is not at all a comparison between the start-ups and BIG companies :-). BIG ones might be/are much more harder.

Write a URL shortner.

Write a URL shortner (like tinyurl) . Take a URL as input & return a shortened URL. If you use any kind of storage or persistence, please use the appropriate API’s of the language. Another requirement is that we want to make our URLs as different as possible, so that successive calls return very different URIs
This is to ensure that small typo errors do not lead to users getting to a valid URL, but rather throwing up an error page.

Let start with the design 🙂 and then come up with an implementation probably in Java/C etc.

The interviewer asked me to implement it in Java.

Small Note: Googling for this can give you a code written in PHP right away as your first link :-), please dont start with it. Come up with your own logic.

First technical post!?

1. How will you find n largest pair (a[i], b[j]) from two sorted array A and B

What I mean is .. There are two arrays A and B of length N each and both the arrays are sorted in descending order … Now we need to find the N largest pairs (a[i]+b[j]) from A and B.

Simply putting it is same as finding all the possible n^2 (a[i]+b[j]) combinations of sums from both the arrays and sorting them and them give back the first N numbers. 😉

2. You are given 2 dice. One of the dice is numbered 1 to 6. What should the other die be numbered so that when you roll the two dice the probability of getting a sum in the range 1-12 is same i.e probability of getting sum 1,2,…..12 is equal.

Note: The sum should be only within the range 1 – 12, no other values are permitted.