Bingo Fun!

Question: Given a list of 24 words, how many different BINGO cards can you create. What if there are more words? What if there are duplicates?

Screen Shot 2015-02-01 at 3.25.04 AM

Answer: The first part is a straight forward permutation question.

Number of different cards = 24! = 620 448 401 733 239 439 360 000 (pretty large number)

What if there are more than 24 words (n words). First we will have choose 24 words out of the n options, then do permutation on the selected 24 items. Read more about choosing here

Number of different cards = 24!*nC24 = 24! * n!/(24!(n-24)!) = n!/(n-24)! (simple as that)

What if there are duplicates? (Now it gets a little tricky). Assumption: 24 words. If there are two words which are the same, they can be used interchangeably. In this case, we will need to divide the possible cards by 2 to account for this. What if there are three words which are the same? Going back to the permutation equation (n!), we will have 3! way of arranging the same words. We will need to divide this from the number of total possible cards.

Assume number of duplicates = k

Number of different cards (with duplicates) = 24!/k!

What if there are two different set of duplicates? We will need to divide both set of duplicate possibilities from the number of total possible cards.

Assume number of duplicates = k, j, m

Number of different cards (with multiple duplicates) = 24!/(k!*j!*m*)

Note, thinking back to the first equation, if there are no duplicates, it is as good as having 1 of each word = 24!/(1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!1!)

What happens if there are more than 24 words and there are duplicates? Take a shot at it in the comments section. I will post the answer shortly.

Meanwhile, enjoy the fun game of BINGO by creating customizable BINGO cards at www.custombingocards.net.

0 Comments

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.

20 Comments

Challenge – First Common Ancestor

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.
 

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

Balanced Tree

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!

 

 

5 Comments

Queue Using Stacks

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!

3 Comments

Bit Swaps

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!