-
You are on "Lets make a Deal" and Monty Hall gives you a choice between three doors -- 1, 2, and 3. You pick one. Then he shows you what is behind one of the doors you did not pick and it is a booby prize. You know there is one good prize and two booby prizes. He gives you the chance to switch your choice to the other door you did not choose. Should you change your original selection?
ALWAYS choose to change doors. Many people find this tough to logic out, so think about it for a while.
What is the probability that the first door you picked was the right one? Easy: 1/3. So what is the possibility that it is one of the 2 you didn't pick? Still easy: 2/3. After Monty opens another door, the quirk is that THE ODDS THAT YOU PICKED THE RIGHT DOOR AT THE BEGINNING IS STILL 1/3. As such, the last door must be right 2/3 of the time, so you should switch.
- I have an array of 1..n numbers in no particular order. One number is in the array twice -- How do I find out which one it is?
Are the contents of the array a range? If so, make an array of bools and and bin sort until a collision
If not Hash table. Search for a collision. It's not n time but pretty near, especially with an optimized hash (like 2 hash tables or a tree)
- I have a sorted array of numbers. Write an algorithm to remove the duplicates in place.
- O(n) traverses the array with 2 iterators, one read and one write
- Write a sorted linked list insertion routine.
template
void SortListItr- ::insert(const Item& entry)
// Library facilities used: link2.h
{
start( );
while(is_item( ) && current( ) < entry) // Skip over smaller items
advance( );
while(is_item( ) && current( ) == entry) // Remove any duplicates
remove_current( );
if(is_item( ))
ListItr
- ::insert(entry);
else
ListItr
- ::attach(entry);
// If at end of list must attach
}
- I have one gallon of water and one gallon of wine. Take one cup from the water and put it in the wine, then take one cup from the wine-water mixture and put it in the water. Is there more water in the wine or wine in the water? Explain?
Solution:
- Break up the liquids into 4 groups with five parts to each group (X-water, O-wine)
- Take one group wine and put it into the water
- Evenly distribute/dilute the wine with the water so you have a mixture of with four X parts and one O part per group.
- Now take one group from the water-wine mixture and put it in the wine
- Now evenly mix the two solutions and you will see that there is the same amount of water in the wine as there is wine in the water.
- I have a group of about 800 records and I want to sort them. They are in a linked list totally unsorted. The primary key has only eight possible values -- one through eight. The secondary key can have any integer value. How do I sort them most efficiently?
- Bin sort the first batch, then dump them into arrays and quick sort each bin
- O(800 + 8 * 100 lg 100)
- Write a function that counts the number of binary ones in a four byte number. Your solution should require only one iteration for each one in the number.
int count(int I)
{
int tot = 0;
while (I) {tot++; I ^= (I-1);}
return tot;
}
- I have an array of 3000 numbers between 0 and 32767. There are no duplicates. What is the most efficient way to sort them, and what is the order of your solution?
- Most efficiant method is bin sort. 32767 bools (or bytes to store bools better) Start with all bools off. Traverse array turning them on if necessary. Run through array adding to final array. O(32767 + 3000)
- There was a sheriff in a town who caught three outlaws. He said he was going to give then all a chance to go free. All they had to do is figure out what color hat they were wearing. There sheriff had 5 hats 3 black and 2 white. The first guy guessed and was wrong so he was put in jail. The second guy also guessed and was also put in jail. Finally, a third blind man guessed and he guessed correctly. How did he know?
Solution:
To solve this question all you need to do is figure out all the possible permutations for the hats on the criminals heads. To do this, you must take into acount the two hats tossed out. With that in mind, all the permutaions are:
Now by eliminating each of the first two guy's wrong selections we can find the solution. For instance, if the first man chose a black hat and was wrong, we could eliminate all the selections in which column 1 has a B. Now lets say man #2 chooses a black hat and is wrong. We can eliminate all selections in which column two with B. This leaves only one row left, meaning that convict #3 was wearing a black hat.
Just to prove this deductive process is right, we should try another scenario. Lets say this time, #1 chooses a white hat. Cross out all selection in which column 1 has a W also delete row BWW because you know the other men were not wearing white hats otherwise #1 would have said he was wearing a black hat. Now #2 chooses a black hat. After eliminating all the selections, we are once again left with only one row. Proving #3 is wearing a black hat.
- There were two mathematicians talking when one says to the other, "I want you to guess the ages of my daughters." The conversation went as follows:
M1: Guess my 3 daughters ages.
M2: OK
M1: The product of my daughters aged is 36.
M2: Uh Humm
M1: The sum is equal to the sum of the numbers across the street.
M2: Hmmm... I can't tell from that.
M1: My oldest daughter's name is Susan.
M2: Ok, you daughters ages are...
what are the ages?
Solution:
The solution to this problem is relatively simple. First calculate all the combinations of three numbers whose product is equal to 36:
1,2,18
1,3,12
1,4,9
1,6,6
1,1,36
2,3,6
2,2,9
3,3,4
Now calculate the sums of each row.
You know from clue #2 that the sum is equal to the sum of the number across the street. Only two sets of number have the same sum. That sum being 13. However, you still need some information to make a selection because it can be either of the two sets. The clinch is that you know he has only one older daughter and not twins, therefore the ages have to be 2, 2, and 9.
- Generate a 9 digit number using the number 1-9, without using any number more than once. this number must also be divisible such that if you take the left most digit the number is divisible by 1, if you take the two left most digits the number is divisible by 2, if you take the three left most
digits the number is divisible by 3, etc., etc, What is the number?
- 381,654,729. Good question how to get it without brute force.
There is a company that has ten machines that makes gold coins. One of the machines is producing coins that are one gram too light. How do you tell which machine out of the ten is producing the coins with the wrong amount of gold weight with only one weighing?
Solution:
You could find the solution by checking each machine but that would be inefficient and too slow. The tricky way to check would be to have each machine punch out it's number in coins. I.e. machine 1 makes one coin, machine 2 makes two coins, machine 3 makes three coins, etc., etc. Now, that you have all the coins weigh them together and subtract their weight from the total theoretical weight (1+2+3+4+5+6+7+8+9) = 45. If you are 5 grams off then it means machine 5 is off, if you are 3 grams off then machine 3 is off,etc.
- Why are manhole covers round?
Solution:
So they do not fall in on themselves. So they are easy to roll when you move them.
- How many gas stations are there in the United States?
- How many yards of baseball fieldgrass are there in the United States?
- How do you back up 1 character while making sure you step the right character length (1 or two bytes). If it is a one byte char then it is less than 128, if it is a two byte character then the first byte is greater than 128 and the second byte can be anything. You know where you are pointing is the beginning of a character (1 ot 2 byte).
- Write all the string functions in as few lines as possible
Solution:
/* copy string ct to string s, including '\0', return s */
void *strcpy(char *s, const char *ct)
{
while(*s++ = *c++);
}
/* copy at most n characters of string ct to s; return s. Pad w/ '\0' if ct has fewer than n characters */
void *strncpy(char *s, const char *ct, size_t n)
{
for(;*s++ = (*ct && n) ? *ct++: n ? '\0': NULL; n--);
}
/* concatenate string ct to the end of string s; return s */
void *strcat(char *s, const char *ct)
{
while(*++s);
while(*s++ = *ct++);
}
/* concatenate at most n characters of string ct to string s, terminae s with '\0'; return s *\
void *strncpy(char *s, const char *ct, size_t n)
{
while(*++s);
for(; *s++ = (*ct && n) ? ct++ : '\0'; n--);
}
- Using two cubes (12 sides) make a desk calandar that can cover all of the days of the month (01-31).
Solution:
The trick to this question is to be clever enough to use the 6 and 9 interchangably. That way you can cover all the numbers (01, 02, 03, 04, .... , 28, 29, 30, 31) with only 12 sides.
- Design the idea alarm clock. Explain it's features.
- Write code to reverse a singlely linked list by just stepping through it once.
- Write a function that takes as its arguments 3 integers > 0; if the product of the integers is even, return the one with the lowest value.
Solution:
int lowest(int a, int b, int c)
{
int q;
/* if any of the integers is even, the product will be
even, so there is no need to multiply (which costs
CPU cycles) so just use modulus division to test
odd/even.
*/
if (!(a&1 && b&1 && c&1)) // Is at least 1 item even is small code
{
q= a < b ? a : b; // q = smallest of a vs b
return q < c ? q : c; // return smallest of q vs c
}
else /* product odd, return error code */
return 0;
} /* end lowest */
- You have three lightbulbs in a sealed room. You know that initially, all three lightbulbs are off. Outside the room there are three switches with a one-to-one correspondence to the lightbulbs. You may flip the switches however you like and you may enter the room once. How should you flip the switches to determine which switch controls which lightbulb?
Solution:
Use your other senses. You can't figure out which light bulb is controlled by which switch if you only look at them. What you do is turn two light switches on. Then allow some period of time to pass. After a lengthy period of time, turn one switch off, leaving the other one on.
The on that is on obviously belongs to the switch you left on. Now, feel the other two lightbulbs. The light that is warm belongs to the switch that you turned on and off. The lightbulb that is off and not warm is the switch you didn't touch.
- Consider the earth. You go one mile south, one mile east, and one mile north. How many points are there on the globe such that you start and end at the same point?
Solution:
One: At the north pole.
- Write a function to reverse a singly linked Linked List
- I give you a singly linked Linked List. Write a function to determine if it has a loop.
- I give you a singly linked Linked List. Write a function to swap every second node. [ie - 1->2->3->4->5->| becomes 2->1->4->3->5->|]
- I give you a singly linked Linked List. Write a function to rotate the list by n. [ie - Rotating by 2 changes 1->2->3->4->5->| to 3->4->5->1->2->| ]
- Given the primitive Drawpixel(int x,int y), write the function DrawCircle(int x, int y, int r)
- Write the function FixURLString(char * s). Given a char*, change all of the spaces to &20s.
- Write a function which given the prefix and infix traversals of a tree, will generate the postfix traversal.
- Write a function which takes a modified linked list and allows us to group items [and then group the groups]
- Explain what the "virtual" keyword means in C++
- What are the benefits of Object Oriented programming [abstraction, inheritance, modularity, data hiding]
- Explain how you would implement C++ style classes in C [member functions, inheritance, etc...]
- Write a command to strchr(char * s, char ch), which will find ch in s and return it's position. Optimize this.
- I am a function, a user passes me a string which I must return in the form I found it. Why might it be a bad idea to change it as part of processing?
- Explain how a topological sort works
- Find the largest subset in an array
- I have an array [1..n] which contains numbers in the range [0..n]. Obviously, at least one number needs to be repeated. Find it! [Pick two of the three conditions: 1) In O(n) 2) Without changing the array 3) Without extra space] [bonus: satisfy all three!]
- Write ITOA
- Implement a Hash Table from scratch
- Determine if a 32 bit number is an exact power of 2
- Write a data structure to act as the backbone for a word processor. It should be able to quickly insert and delete text.
- How does 2's Complement Work?
- I have 10 bags of coins and a scale
- I have 9 coins, one is a heavy counterfeit, and a balance scale that I am allowed to use twice. Find the counterfeit