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.

1 Comment

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.
 

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!

Card Pairology?

Question: John and Matt decide to play a game using a deck of cards. The game involves flipping two cards at a time. If both cards are black, they go into John’s pile and if both cards are red, they go into Matt’s pile. If one card is red and one card is black, they go into a discard pile. The game is played until all 52 cards have been flipped. The person with the most cards in their pile wins. If there is a tie, John wins. If Matt has more cards than John, then John pays Matt a dollar. What is the chance of Matt getting a dollar?

Answer: Any guesses? The chance of Matt getting any money is zero. Do you know why?

Say the deck is arranged in a way such that there are 13 black pairs. In this situation, John gets 13 black pairs. And since there are no other black cards left, Matt gets 13 red pairs too. So there’s a tie and John wins.

Suppose there are 12 black pairs in the deck. In this case, there would be 2 black cards left in the deck that would pair up with 2 other red cards in the deck. These 2 black cards would never be together since we have already claimed that there are only 12 black pairs in the deck. As a result, 2 pairs of cards end up in the discard pile. The remaining cards would all be red and Matt would get 12 red pairs too. So once again, there’s a tie and John wins.

We could continue this process through induction. Assuming there are 11 black pairs, there would be 4 other black cards that pair up with 4 other red cards and go into the discard pile. Once again, both John and Matt end up with 11 pairs of cards each and John wins.

Here’s a table to explain each case.

John Discarded Matt
13 pairs 0 pairs 13 pairs
12 pairs 2 pairs 12 pairs
11 pairs 4 pairs 11 pairs
10 pairs 6 pairs 10 pairs
9 pairs 8 pairs 9 pairs
8 pairs 10 pairs 8 pairs
7 pairs 12 pairs 7 pairs
6 pairs 14 pairs 6 pairs
5 pairs 16 pairs 5 pairs
4 pairs 18 pairs 4 pairs
3 pairs 20 pairs 3 pairs
2 pairs 22 pairs 2 pairs
1 pair 24 pairs 1 pair
0 pairs 26 pairs 0 pairs

So we see that in any case, there is a tie between John and Matt. So Matt never ends up with a dollar.

Liked this post? Spread the word on Twitter and Facebook 🙂

4 Comments

Boxes of Money

Question: You are given b boxes and n dollar bills. The money has to be sealed in the b boxes in a way such that without thereafter opening a box, you can give someone a requested whole amount of dollars from 0 to n. How should b be related to n for this to happen?

Answer: Stumped? Let’s think of an example to approach this problem.

Say we have $100. A good approach to distributing $100 would be the binary number system. So you’d have $1, $2, $4, $8, $16, $32 in the first six boxes. We can’t fill the next box with $64 dollars because we are only left with $37 dollars (from a total of $100). So we’d have to put $37 in the seventh box. To supply any requested amount, we’d have to use a combination of these boxes.

To find out the restrictions on the values of b and n, we have to think of different scenarios. For instance, with a million dollars and just one box, we would never be able to dispense any requested amount less than a million. However, if we are ever in a situation with more boxes than dollars, there is a never a problem.

Using this approach, we can create a table showing the best relationship between b and n

b = 1     n = up to $1
b = 2     n = up to $2 + $1 = $3
b = 3     n = up to $4 + $2 + $1 = $7
b = 4     n = up to $8 + $4 + $2 + $1 = $15

See a pattern yet? So the best way we would be able to dispense any requested amount is to have n <= 2^b – 1.

Liked this post? Let us know through our comments section!

3 Comments

Chasing Dogs

Question: There are four dogs each at the corner of a unit square. Each of the dogs starts chasing the dog in the clockwise direction. They all run at the same speed and continuously change their direction accordingly so that they are always heading straight towards the other dog. How long does it take for the dogs to catch each other and where?

Answer: Let the dogs be A, B, C and D where A is chasing B, B is chasing C, C is chasing D and D is chasing A.

All the dogs will eventually meet in the center of the square. Since all the dogs move in symmetry, the only logical answer to the location of their meeting is the center of the square.

At any point in time, dog A is perpendicular to dog B and B perpendicular to C and so on. Dog A moves towards dog B but dog B does not move towards or away from dog A since it is moving perpendicular to dog A. Therefore, the distance that dog A needs to cover to reach dog B is the same as the original distance between them, one unit.

The speed of each of the dog towards the dog it is chasing is given by (1 + cos(t)) where t is the angle on each corner of the square.

Speed of dog = 1 + cos(90) = 1 + 0 = 1
Time needed = Distance/Speed = 1 / 1 = 1 unit.

Liked this question? Post this on Stumble, Twitter or Digg!

Have a better solution? Let us know through the comments section!

5 Comments

Red and Blue Marbles

Question: You have 50 red marbles, 50 blue marbles and 2 jars. One of the jars is chosen at random and then one marble will be chosen from that jar at random. How would you maximize the chance of drawing a red marble? What is the probability of doing so? All 100 marbles should be placed in the jars.

Answer: Seems tricky at first right? Given that the number of red and blue marbles are the same, you would tend to think that the odds are 50-50. You would try different combinations, such as 25 of each colored marble in a jar or putting all red marbles in one jar and all the blue in the other. You would still end up with a chance of 50%.

So lets think of a better way to distribute the marbles. What if you put a single red marble in one jar and the rest of the marbles in the other jar? This way, you are guaranteed at least a 50% chance of getting a red marble (since one marble picked at random, doesn’t leave any room for choice).  Now that you have 49 red marbles left in the other jar, you have a nearly even chance of picking a red marble (49 out of 99).

So let’s calculate the total probability.

P( red marble ) = P( Jar 1 ) * P( red marble in Jar 1 ) + P( Jar 2 ) * P( red marble in Jar 2 )
P( red marble ) = 0.5 * 1 + 0.5 * 49/99
P( red marble ) = 0.7474

Thus, we end up with ~75% chance of picking a red marble.

Have a better solution? Let us know through the comments section!

The Fox and The Duck

Question: A duck that is being chased by a fox saves itself by sitting at the center of circular pond of radius r. The duck can fly from land but cannot fly from the water. Furthermore, the fox cannot swim. The fox is four times faster than the duck. Assuming that the duck and fox are perfectly smart, is it possible for the duck to ever reach the edge of the pond and fly away to its escape from the ground?

Answer: One would think that the duck could swim directly away from the fox. So the duck would have to swim a distance r. The fox would have to cover half the circumference of the pond (pi * r). Since the fox is four times faster than the duck, we know that

(pi * r) < (4 * r)

This would make it seem like it is impossible for the duck to escape.

So how could the duck make life most difficult for the fox? If the duck just tries to swim along a radius, the fox could just sit along that radius and the duck would continue to be trapped.

The duck could swim in concentric circles, so that the fox has to continuously run along the circumference of the pond to stay on the same radius as the duck. If the duck swims near the edge of the pond, the fox could easily keep up since they would be covering approximately the same distance and the fox is four times faster. But what if the duck swam closer to the center of the pond? The duck would have to cover a smaller circumference, and could use this strategy to put some distance between the fox and itself. At a distance of r/4 from the center of the pond, the circumference of the pond is exactly four times the circumference of the duck’s path. Thus, to stay on the same radius as the duck, the fox would barely keep up.

Say, the duck circles the pond at a distance r/4 – e, where e is an infinitesimal amount. So as the duck continues to swim along this radius, it would slowly gain some distance over the fox. Once the duck is able to gain 180 degrees over the fox, the duck would have to cover a distance of 3r/4 + e to reach the edge of the pond. In the meanwhile, the fox would have to cover half the circumference of the pond (i.e the 180 degrees). At that point,

(pi * r ) > 4 * (3r/4 + e)

The duck would be able to make it to land and fly away.

Liked this question? Post this on Stumble, Twitter or Digg!

2 Comments