## Nex3

BAN USERI'm Nathan Weizenbaum. I'm going to the University of Washington, in the Computer Science department.

Assuming that 1 <= N <= 100...

Well, you could do it by twos. You start by dropping an egg off the second story. If it breaks, drop it off the first story. If it breaks there, N=1; otherwise, N=2. If it doesn't break on the second story, drop it off the fourth story; it'll work the same way, because you know N!=1 and N!=2. That would take, at worst, 51 drops.

ListNode* nthFromBack(LinkedList* list, int n)

{

int i = 1;

ListNode* node = list->first;

ListNode* to_return = NULL;

while (node)

{

if (i == n)

to_return = node;

node = node->next;

i++;

}

return to_return;

}

I'd test this with a few test cases... the edge cases (list size 0, 1), maybe a five-element list, and a case where n is greater than the list size.

Two.

It's easiest to think about this in terms of cases. In addition, I'll use notation for the balls such that ? represents a ball whose weight you don't have any idea about, H represents a ball that could be heavy, and L represents a ball you know to be light. When you begin, you have eight balls, none of which you know the weight of.

????????

First, you take six of those balls, and weigh them, three on each side. Then either:

1) One of the sides is heavier.

or

2) Neither of the sides are heavier.

In case 2, you know that six of the balls are not the heavy ball. You don't know about the other two.

??LLLLLL

You then take one of the ? balls, and weigh it against one of the L balls. Again there are two possible outcomes:

2.1) The ? ball is heavier.

2.2) The balls are the same.

In case 2.1, we know that the ? ball we just weighed must be the heavy ball, because it's heavier than a ball we know to be normal. In case 2.2, we know that the ? ball we *did not weigh* must be the heavier ball, because we know all other balls to be light.

Now let's jump back to case 1. In this case, three of the balls we weighed could be the heavy ball; the rest must be light.

HHHLLLLL

Our next weighing has one of the H balls against another H ball. This time, there are three ways the weighing could turn out:

1.1) The first H ball is heavier.

1.2) The second H ball is heavier.

1.3) The balls weigh the same.

In cases 1.1 and 1.2, we now know which of the balls is heaver. In case 1.3, the two balls we weighed must be light, because there's only one heavy ball; thus, there is only one possibly heavy ball remaining, so that ball must be the heavy ball.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Seems like the basic classes would be Deck and Card. I think it's a mistake to use inheritance to designate different types of card; the difference between a two of hearts and a queen of spades is nothing more than data.

- Nex3 December 26, 2006For a card, we'd want an int member variable for the value (not zero-based, so it syncs with actual card numbers... one -> ace, five -> five, twelve -> queeen, etc.), and an enum for the suit. It would be trivial to check whether the card was red or black; thus, it's probably not necessary to have a member for that.

The deck class would need some sort of collection of fifty-two cards. Since this is for poker, it's probably safe to assume that we'll only draw from the top of the deck; thus, we can just keep a variable with the number of cards in the deck for use when we shuffle or something so we don't have to worry about the cards we removed, and store it in a simple array. We'd want some sort of "shuffle" method... I'm not familiar with the relative randomness of various algorithms, but what SP suggested sounds fine. We'd of course want a "draw" method that would return the top card of the deck and decrement the card count. The constructor should add all of the possible cards to the deck, but not shuffle, in case the user wants it sorted for some reason.