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.

Related posts:

1. Challenge – Camel and Bananas
2. Globe Walker
3. 4 Quarts of Water

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.

Related posts:

1. Combinations of a String
2. First Non-Repeated Character
3. Reverse the Order of Words in a String

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.

Related posts:

1. Sub-Array with the Largest Sum
2. Anagrams in an Array of Strings
3. Permutations of a String

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.

Related posts:

1. Challenge – 50 trucks with payload
2. Trailing Zeros in 100 Factorial
3. Chess Squares

Question: How would you find the first common ancestor of two nodes in a binary search tree? First as in the lowest in the tree. Another way to ask is to find the lowest common ancestor of two nodes.

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

Meanwhile, check out the challenges from previous weeks here.

Answer:

TreeNode findFirstCommonAncestor(TreeNode root, TreeNode p,
	TreeNode q) {

    if (root == null) {
        return null;
    }

    if (root == p || root == q) {
	return root;
    }

    TreeNode left = findFirstCommonAncestor(root.left, p, q);
    TreeNode right = findFirstCommonAncestor(root.right, p, q);

    if ((left == p && right == q) ||
        (left == q && right == q)) {
	return root;
    }

    return (left != null) ? left : right;
}

Alternate:

TreeNode findFirstCommonAncestor(TreeNode root, int p, int q) {

    if (root == null) {
        return null;
    }

    if (root.value == p || root.value == q) {
	return root;
    }

    if (root.value > p && root.value > q ) {
        return findFirstCommonAncestor(root.left, p, q);
    }
    else if (root.value < p && root.value < q ) {
        return findFirstCommonAncestor(root.right, p, q);
    }
    else {
        return root;
    }
}

Thanks Dave and Sunil for pointing out the alternate solution.
 

Related posts:

1. Balanced Tree
2. Challenge – Equal Probability between 1 and 7
3. Reverse a Linked-List

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!

Related posts:

1. Challenge – Equal Probability between 1 and 7
2. Challenge – First Common Ancestor

Question: How would you check if a binary tree is balanced?
Answer: A tree is considered balanced when the difference between the min depth and max depth does not exceed 1.

Recursive algorithms always work well on trees, so here’s some code.

int min_depth( Node * root ) {
    if( !root ) {
        return 0;
    }
    return 1 + min( min_depth( root->left ),
                    min_depth( root->right ));
}

int max_depth( Node * root ) {
    if( !root ) {
        return 0;
    }
    return 1 + max( max_depth( root->left ),
                            max_depth( root->right ));
} 

bool is_balanced( Node * root ) {
    return ( max_depth( root ) - min_depth( root ) ) <= 1
}

Simple enough, right? Spread the word on Twitter and Digg!

Related posts:

1. Challenge – First Common Ancestor
2. Singly Linked List – Delete Node
3. Loop in a Singly-Linked List

Question: How would you use stacks to implement a queue?

Answer: So how could we go about doing this? What if we used two stacks and used one as the incoming stack and the other as the outgoing stack? A queue is a FIFO structure, so when we enqueue something, we need to make sure that it does not get popped off before something that was already there. Similarly, when we dequeue something, we have to make sure that elements that were inserted earlier get ejected first.

What’s better than some code!

Stack in;
Stack out;
void enqueue( int value ) {
    while( !out.isEmpty() ) {
        in.push( out.pop() );
    }
    in.push( value );
}

int dequeue() {
    while( !in.isEmpty() ) {
        out.push( in.pop() );
    }
    return out.pop();
}

Isn’t that cool? Help share this on Twitter!

No related posts.

Question: How would you find the number of bit swaps required to convert integer A to integer B?

Answer: Gut instinct might suggest that you go through every bit of A and every bit of B while simultaneously updating a count of the bits that are different. But how about a cooler way to solve this?

A key to solving a lot of bit manipulation questions is the use of the XOR functionality.

int bit_swaps_required( int a, int b ) {
    unsigned int count = 0;
    for( int c = a ^ b; c != 0; c = c >> 1 ) {
        count += c & 1;
    }
    return count;
}

Simple right?

Help share this post through Twitter!

Related posts:

1. Power of 2
2. Number of Ones
3. Trailing Zeros in 100 Factorial

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.

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).

Related posts:

1. Probability of a Car Passing By
2. Red and Blue Marbles
3. 10 Google Interview Puzzles