Challenge – 50 trucks with payload

Question: Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Assume all the payload will fit in one truck.

Challenge: Do you know the answer to this question? Post in the comments. Answers will be posted on April 22th.

Thanks Ole Sandbu, Czikus and Vanta for the answers.

We want to use as little fuel as possible so we try minimize the number of trucks we use as we go along. Let’s say we start with all 50 trucks with full fuel (5000 miles range). For each mile, we lose 50 miles in range. After two miles, we lose 100 miles leaving us with 4900 miles. This can be supported by 49 trucks so we drop one truck.
As you can see for every 100 miles we lose in range, we drop a truck.

50 trucks: 100/50
49 trucks: 100/49

Total distance = 100/50 + 100/49 + 100/48 + … + 100/2 + 100/1 (harmonic series) = 449.920533833

Meanwhile check out the challenges from previous weeks here.

Implement strstr

Question: Implement strstr in Java. Find the first instance of a string in another string.

Answer:

public int Search(String haystack, String needle){
    for(int i = 0; i < haystack.length(); i++ ) {
        for(int j = 0; j < needle.length() && 
                        i+j < haystack.length(); j++ ) {
            if(needle.charAt(j) != haystack.charAt(i+j)) {
                break;
            } else if (j == needle.length()-1) {
                return i;
            }
        }
    }
    return -1;
}

Like this question? Follow our feed and tweet it.

Search in a sorted rotated array

Question: Implement a search function for a sorted rotated array. Duplicates are allowed. Returning any one of the duplicates is acceptable.

Answer: We can do a binary search with some modified checks.

public int rotatedSearch(int[] values, int start, int end, 
                          int x){
    if(values[start] == x){
        return start;
    } else if(values[end] == x){
        return end;
    } else if(end - start == 1) {
        return -1;
    }
    int middle = (start + end) / 2;

    if(values[start] <= values[middle]){
        if(x <= values[middle] && x >= values[start]){
            return rotatedSearch(values, start, middle, x);
        } else {
            return rotatedSearch(values, middle, end, x);
        }
    } else if(values[middle] <= values[end]){
        if(x >= values[middle] && x <= values[end] ){
            return rotatedSearch(values, middle, end, x);
        } else {
            return rotatedSearch(values, start, middle, x);
        }
    } else {
        return -1;
    }
}

Like this question? Follow our feed and tweet it.

Challenge – Camel and Bananas

Question: The owner of a banana plantation has a camel. He wants to transport his 3000 bananas to the market, which is located after the desert. The distance between his banana plantation and the market is about 1000 kilometer. So he decided to take his camel to carry the bananas. The camel can carry at the maximum of 1000 bananas at a time, and it eats one banana for every kilometer it travels.

What is the largest number of bananas that can be delivered to the market?

Challenge: Do you know the answer to this question? Post in the comments. Answers will be posted April 8th.

Thanks for all the responses. Quite a few of you have the right answer.

At KM#0, we have 3000 bananas. The maximum bananas the camel can carry is 1000 so the camel must at least make 3 trips from the start point. (Leave #0, Return to #0, Leave #0, Return to #0, Leave #0).
If we move just 1km, we need 1 banana for each step mentioned above thus making a total of 5 bananas for each km.

We continue making 3 trips until we reach a banana count of 2000.
3000 – 5*d = 2000 => d = 200
At #200km, we will have 2000 bananas

At this point, we only need to make 2 trips (Leave #200, Return to #200, Leave #200). This will cost 1 banana for each step thus making a total of 3 bananas for each km.

We continue making 2 trips until we reach a banana count of 1000.
2000 – 3*d = 1000 => d = 333km
At#(200+333) = #534km, we will have 998 bananas

At this point, we need to make one trip so the camel just carries everything and marches toward the market.
Remaining km = 1000 – 534 = 466km. Bananas needed = 466.

Therefore, the bananas remaining once the camel reaches the market is 998 – 466 = 532 bananas. :)

Check out the challenges from previous weeks here.

25 Comments

Challenge Series

Hey everyone,

We got great response from the interview challenge posted last week. We’ve decided to make a weekly challenge series (hopefully we have enough questions to keep up :)).

Do you have any interesting questions you would like to share? Or any questions that you’d like answered? Let us know and we can help draw the audience to answer your questions!

Cheers!

0 Comments

Challenge – Equal Probability between 1 and 7

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.

Challenge: Do you know the answer to this question? Post in the comments. Let’s see who is up for the challenge. Answers will be posted February 26th.

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.

Equal Probability 1 to 7

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

That was fun, right? Anyone up for another challenge? Watch out for it next tuesday (March 1st).

84 Comments

10 Google Interview Puzzles

Here is a list of 10 puzzles which have been asked on a Google Interview. They are not in any specific order.

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

How many can you answer in the first attempt? Post in comments.

Feel free to add to this list or leave a comment. Please tweet, Digg or Stumble.

My Tech Interviews

Hello everyone,

Welcome to My Tech Interviews. A blog which helps people prepare for a software technical interview.

My Tech Interviews

This blog is dedicated to helping people prepare for a technical interview, mainly for a software interview. It contains various types of questions like puzzles and programming tasks. These questions are not posted for you to memorize them and regurgitate in the interview. They are meant to make you think and get you used to the type of questions you could expect in an actual interview.

Thanks for all the support you guys have provided us.

Follow us

To keep up to date on what is going on with My Tech Interviews, please subscribe to the RSS Feed. Also feel free to connect with My Tech Interviews on Twitter. Follow us on Facebook.

Contribute

Contribution from the readers is a big factor for our success. If you know any interesting or challenging interview question, feel free to give us a shout at support@mytechinterviews.com.

Advertise with us

For more information, please contact advertising@mytechinterviews.com.

Free Advertising opportunity

If you are interested in a limited-time offer for free advertising, please send us an email to advertising@mytechinterviews.com with the following information.

1. Your URL
2. A short description of the blog/business
3. Why are you interested in running ads on My Tech Interviews
4. Tell me a joke

If we like your submission, you will get free advertising (one ad spot on the side widget) for a month. So keep them coming.

Red, Green and Yellow Balls

Question: You are give two red balls, two green balls and two yellow balls. One ball from each color is heavier than the other one. All the heavier balls weigh the same and all the lighter balls weigh the same. You are only provided with a weighing balance. How many tries would it take to identify which one is heavier and which one is lighter?

Answer: Let’s label the balls R1, R2 (Red ones), G1, G2 (Green ones) and Y1, Y2 (Yellow ones).

First weigh R1, G1 on one side and R2, Y1 on the other.

If they are equal, we know that one of G1 or Y1 is heavy. We can just weigh them both and find out which one is heavier. If G1 is heavy, the heavier set is {G1, R2, Y2} and the others are lighter. If Y1 is heavy, the heavier set is {G2, R1, Y1}.

If R1, G1 is heavy, we know that either G1 is heavy or Y1 is light. We proceed to weigh G1, Y1 with G2, Y2. If they are equal, G1 is the heavy one. The heavier set is {G1, Y2, R1}. If G1, Y1 is heavy, G1 and Y1 are both heavy. The heavier set is {Y1, G1, R1}. If G2, Y2 is heavy, G2 and Y2 are both heavy. The heavier set is {R1, G2, Y2}.

If R2, Y1 is heavy, we know that either Y1 is heavy or G1 is light. This is similar to the case above. Try to work it out yourself before continuing with the solution. Weigh G1, Y1 with G2, Y2. If they are equal, Y1 is heavy. The heavier set is {Y1, R2, G2}. If G1, Y1 is heavy, G1 and Y1 are both heavy. The heavier set is {G1, Y1, R2}. If G2, Y2 is heavier, G2 and Y2 are both heavy. The heavier set is {G2, Y2, R2}.

Therefore, in any of these cases, we only need two tries with the balance.

If you like this puzzles, please Digg it or Tweet it to help spread the word.

8 Comments

Tunnel Trouble

Question: A man needs to go through a train tunnel to reach the other side. He starts running through the tunnel in an effort to reach his destination as soon as possible. When he is 1/4th of the way through the tunnel, he hears the train whistle behind him. Assuming the tunnel is not big enough for him and the train, he has to get out of the tunnel in order to survive. We know that the following conditions are true.

1. If he runs back, he will make it out of the tunnel by a whisker.
2. If he continues running forward, he will still make it out through the other end by a whisker.

What is the speed of the train compared to that of the man?

Answer: This is a simple math and logic question. There is no trickery or hidden assumption here.

We can either do the math and arrive at the solution or just find the solution based on some deductions.

Let T = Speed of train, M = Speed of man, L = Length of the tunnel, D = Distance from train to start of tunnel.

T/M = ?

By observation 1, if he runs back, he will make it out of the tunnel by a whisker. D/T = L/4M – (1)
By observation 2, if he continues running forward, he will still make out through the other end by a whisker. 
(D + L)/T = 3L/4M – (2)

Substituting (1) into (2),

L/4M + L/T = 3L/4M
L/T = L/2M
1/T = 1/2M
T/M = 2

Now let’s analyze this question logically. We know that the man and train will be at the start of the tunnel if he runs back. If he runs forward, by the time the train reaches the start of the tunnel, the man would have traveled another 1/4th of the tunnel. That should put him at 1/2 of the tunnel. For the train to meet the man at the end of the tunnel, the train must be travelling at twice the speed of the man since it has to cover twice the distance. Therefore T = 2M.

If you like this post, Please Digg or Stumble this post! As usual, comments are always welcome.