Answers

Below are the answers to the post on Google interview questions

Let’s think of this like a decision tree. Each rand5() will be a decision. After 2 tries, we have 25 possible solutions. We try to get maximum bunches of 7 as we can (1 – 21, 3 sets of 7). If we get any of the other values, we just try again. Since the probability of getting each of 21 values are the same every time, trying again won’t affect their probabilities.

Question: Reverse a Linked-list. Write code in C.
Answer: There are multiple ways to go about this. Let’s first look at a recursive solution.

Node * reverse( Node * ptr , Node * previous)
{
    Node * temp;
    if(ptr->next == NULL) {
        ptr->next = previous;
        return ptr;
    } else {
        temp = reverse(ptr->next, ptr);
        ptr->next = previous;
        return temp;
    }
}
reversedHead = reverse(head, NULL);

Now for a non-recursive solution.

Node * reverse( Node * ptr )
{
    Node * temp;
    Node * previous = NULL;
    while(ptr != NULL) {
        temp = ptr->next;
        ptr->next = previous;
        previous = ptr;
        ptr = temp;
    }
    return previous;
}

Question: Write a method to generate a random number
 between 1 and 7, given a method that generates a random number between 1
 and 5. The distribution between each of the numbers must be uniform.

Let’s think of this like a decision tree. Each rand5() will be a decision. After 2 tries, we have 25 possible solutions. We try to get maximum bunches of 7 as we can (1 – 21, 3 sets of 7). If we get any of the other values, we just try again. Since the probability of getting each of 21 values are the same every time, trying again won’t affect their probabilities.

int rand7() {
    while (1) {
        int num = 5*(rand5()-1) + rand5();
        if (num < 22) return ((num % 7) + 1);
    }
}



Question: You are given an array with integers (both positive and negative) 
         in any random order. Find the sub-array with the largest sum.

Answer: This is an all-time favorite software interview question. The best way to solve this puzzle is to use Kadane’s algorithm which runs in O(n) time. The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values. Here’s some code to illustrate.
void maxSumSubArray( int *array, int len, int *start, int *end, int *maxSum ) { int maxSumSoFar = -2147483648; int curSum = 0; int a = b = s = i = 0; for( i = 0; i < len; i++ ) { curSum += array[i]; if ( curSum > maxSumSoFar ) { maxSumSoFar = curSum; a = s; b = i; } if( curSum < 0 ) { curSum = 0; s = i + 1; } } *start = a; *end = b; *maxSum = maxSumSoFar; }

 Question: You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution?
Answer: The easiest way to do this would be to start from the first floor and drop the egg. If it doesn’t break, move on to the next floor. If it does break, then we know the maximum floor the egg will survive is 0. If we continue this process, we will easily find out the maximum floors the egg will survive with just one egg. So the maximum number of tries is 100 that is when the egg survives even at the 100th floor.
Can we do better? Of course we can. Let’s start at the second floor. If the egg breaks, then we can use the second egg to go back to the first floor and try again. If it does not break, then we can go ahead and try on the 4th floor (in multiples of 2). If it ever breaks, say at floor x, then we know it survived floor x-2. That leaves us with just floor x-1 to try with the second egg. So what is the maximum number of tries possible? It occurs when the egg survives 98 or 99 floors. It will take 50 tries to reach floor 100 and one more egg to try on the 99th floor so the total is 51 tries. Wow, that is almost half of what we had last time.
Can we do even better? Yes we can (Bob, the builder). What if we try at intervals of 3? Applying the same logic as the previous case, we need a max of 35 tries to find out the information (33 tries to reach 99th floor and 2 more on 97th and 98th floor).

Interval – Maximum tries
1 – 100
2 – 51
3 – 35
4 – 29
5 – 25
6 – 21
7 – 20
8 – 19
9 – 19
10 – 19
11 – 19
12 – 19
13 – 19
14 –  20
15 –  20
16 –  21

So picking any one of the intervals with 19 maximum tries would be fine.

Question: Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person:  1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge?
Answer: The initial solution most people will think of is to use the fastest person as an usher to guide everyone across. How long would that take? 10 + 1 + 7 + 1 + 2 = 21 mins. Is that it? No. That would make this question too simple even as a warm up question.
Let’s brainstorm a little further. To reduce the amount of time, we should find a way for 10 and 7 to go together. If they cross together, then we need one of them to come back to get the others. That would not be ideal. How do we get around that? Maybe we can have 1 waiting on the other side to bring the torch back. Ahaa, we are getting closer. The fastest way to get 1 across and be back is to use 2 to usher 1 across. So let’s put all this together.
1 and 2 go cross
2 comes back
7 and 10 go across
1 comes back
1 and 2 go across (done)
Total time = 2 + 2 + 10 + 1 + 2 = 17 mins

Question: In a country where everyone wants a boy, each family continues having babies till they have a boy. After some time, what is the proportion of boys to girls in the country? (Assuming probability of having a boy or a girl is the same)
Answer: This is a very simple probability question in a software interview. This question might be a little old to be ever asked again but it is a good warm up.
Assume there are C number of couples so there would be C boys. The number of girls can be calculated by the following method.

Number of girls = 0*(Probability of 0 girls) + 1*(Probability of 1 girl) + 2*(Probability of 2 girls) + …
Number of girls = 0*(C*1/2) + 1*(C*1/2*1/2) + 2*(C*1/2*1/2*1/2) + …
Number of girls = 0 + C/4 + 2*C/8 + 3*C/16 + …
Number of girls = C
(using mathematical formulas; it becomes apparent if you just sum up the first 4-5 terms)

The proportion of boys to girls is 1 : 1.

Question: The probability of a car passing a certain intersection in a 20 minute windows is 0.9. What is the probability of a car passing the intersection in a 5 minute window? (Assuming a constant probability throughout)
Answer: This is one of the basic probability question asked in a software interview. Let’s start by creating an equation. Let x be the probability of a car passing the intersection in a 5 minute window.

Probability of a car passing in a 20 minute window = 1 – (probability of no car passing in a 20 minute window)
Probability of a car passing in a 20 minute window = 1 – (1 – probability of a car passing in a 5 minute window)^4
0.9 = 1 – (1 – x)^4
(1 – x)^4 = 0.1
1 – x = 10^(-0.25)
x = 1 – 10^(-0.25) = 0.4377

Question: You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.

Answer: Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it?
Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time.
When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After picking one, we replace the current stored byte with the one we picked. Now it gets interesting. When we get the third one, it has 1/3 probability of being picked and the one we have stored has a 2/3 probability of being picked. We pick one of the two bytes based on this probability. We can keep doing this forever.
Just generalizing, when we get the nth byte, it has a 1/n probability of being picked and the byte we have stored has (n-1)/n probability of being picked.
Sometimes, this question is a little confusing. The question said you have only space to store one byte but there is an assumption that you have space to store variables to track the number of bytes and so on. Another assumption is that the stream of bytes is not infinite. If not, we won’t be able to calculate (n-1)/n.
Question: How would you cut a rectangular cake into two equal pieces when a rectangular piece has already been cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut.
Answer: Simple question right? There are two possible solutions to this problem. People often overlook the easier solution to this problem. Let’s start with the easiest solution. If you make one straight horizontal cut along the height of the cake, the resulting slices are of equal sizes. But this solution may not work so well on a cake with icing. So let’s rethink.
In general, when a straight cut is made at any angle through the center of a  rectangle, the resulting pieces are always of equal area. So let’s consider our situation. What if we make a straight cut such that it passes through the center of both the rectangles? Since the cut halves both the rectangles, the resulting two pieces are guaranteed to have equal area. Each piece has an area equal to half the original cake minus half the area of the missing rectangular piece. This results in two pieces of equal size, assuming the cake’s height is same at all points

Question: Two old friends, Jack and Bill, meet after a long time.

Three kids

Jack: Hey, how are you man?
Bill: Not bad, got married and I have three kids now.
Jack: That’s awesome. How old are they?
Bill: The product of their ages is 72 and the sum of their ages is the same as your birth date.
Jack: Cool… But I still don’t know.
Bill: My eldest kid just started taking piano lessons.
Jack: Oh now I get it.
How old are Bill’s kids?
Answer: Let’s break it down. The product of their ages is 72. So what are the possible choices?

2, 2, 18 – sum(2, 2, 18) = 22
2, 4, 9 – sum(2, 4, 9) = 15
2, 6, 6 – sum(2, 6, 6) = 14
2, 3, 12 – sum(2, 3, 12) = 17
3, 4, 6 – sum(3, 4, 6) = 13
3, 3, 8 – sum(3, 3, 8 ) = 14
1, 8, 9 – sum(1,8,9) = 18
1, 3, 24 – sum(1, 3, 24) = 28
1, 4, 18 – sum(1, 4, 18) = 23
1, 2, 36 – sum(1, 2, 36) = 39
1, 6, 12 – sum(1, 6, 12) = 19

The sum of their ages is the same as your birth date. That could be anything from 1 to 31 but the fact that Jack was unable to find out the ages, it means there are two or more combinations with the same sum. From the choices above, only two of them are possible now.

2, 6, 6 – sum(2, 6, 6) = 14
3, 3, 8 – sum(3, 3, 8 ) = 14

Since the eldest kid is taking piano lessons, we can eliminate combination 1 since there are two eldest ones. The answer is 3, 3 and 8.

10 Google Interview Puzzle questions

Reverse a Linked-List
Reverse a Linked-list. Write code in C. Answer
Challenge – Equal Probability between 1 and 7
Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. Answer
Sub-Array with the Largest Sum
You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum. Answer
How Strong is an Egg?
You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution? Answer
Four People on a Rickety Bridge
Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person:  1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge? Answer
Boys and Girls
In a country where everyone wants a boy, each family continues having babies till they have a boy. After some time, what is the proportion of boys to girls in the country? (Assuming probability of having a boy or a girl is the same) Answer
Probability of a Car Passing By
The probability of a car passing a certain intersection in a 20 minute windows is 0.9. What is the probability of a car passing the intersection in a 5 minute window? (Assuming a constant probability throughout) Answer
Pick a Random Byte
You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer
Piece of Cake
How would you cut a rectangular cake into two equal pieces when a rectangular piece has already been cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut. Answer
How Old Are My Children?
Two old friends, Jack and Bill, meet after a long time.
Jack: Hey, how are you man?
Bill: Not bad, got married and I have three kids now.
Jack: That’s awesome. How old are they?
Bill: The product of their ages is 72 and the sum of their ages is the same as your birth date.
Jack: Cool… But I still don’t know.
Bill: My eldest kid just started taking piano lessons.
Jack: Oh now I get it.
How old are Bill’s kids? Answer

MICROSOFT WORD,EXCEL,POWERPOINT AND ALSO ONE NOTE FOR IPAD

Microsoft  released native iPad apps for its flagship Office programs—Word, Excel, and PowerPoint. The three new apps join the existing iOS apps from the Office family: OneNote, Lync, OneDrive, OneDrive for Business, and an OWA app for Exchange-based email.
After four years’ worth of speculation and anticipation,  releases are a welcome arrival for longtime Office users who’ve had to deal with incompatibilities and unsatisfying alternatives every time they picked up an iPad.

Make no mistake about it: These three apps are feature-rich, powerful tools for creating and editing Office documents. They look and act like their Office 2013 counterparts on Windows. And although these iPad apps obviously can’t replicate every feature of the full desktop programs, they deliver an impressive subset of those features. Anyone who was expecting Office Lite or a rehash of the underwhelming Office for iPhone will be pleasantly surprised.

big Iphone in 4.7 and 5.5 inch screens

Iphone expected :)

Apple planned to release it's new version of the iphones with a lot of bigger size screens .They may be releasing them in the month of the september.This is a good news for the techgeeks all around the world.The production cycle is already ramping up, with component makers producing elements like fingerprint sensors and LCD driver chips, according to the paper, with LCD mass production kicking off in the April-June quarter.
Apple is also expected to increase the display resolution of these devices compared to current models, which could be designed to keep pixel density high on the larger new screens. Full HD resolution is a likely possibility if these rumors are true.
While it’s risky to go trusting rumors about iPhone launches this early, the Nikkei’s report has a few things that make it ring true. First, the 4.7- and 5.5-inch screen sizes have been reported previously by Bloomberg, and the Wall Street Journal also chiming in early this year to say two larger phones are in development. Also, Nikkei reported last year that the iPhone 5s and 5c would launch September 20 in Japan before either was officially announced, which was exactly when they did end up arriving.
Critics have long called for Apple to release devices with larger screen sizes, and so far, the rumor mill indicates it will finally go beyond the 4-inch display shared by the iPhone 5, iPhone 5c and iPhone 5s. We’ll likely have to wait for fall to find out for sure, but for now, start stretching out those thumbs.