With finals going on and the horrible weather, I thought maybe we could all throw out a few riddles, brain teasers, kewl interview questions or whatever out there to give us a break. I have one, I am sure a lot of you have heard it, so if you have give it some time before you post it so other people can try to figure it out. If you have any of your own, feel free.
Riddle: You are walking down a road in the middle of the desert (I don't know why), and come to a fork in the road. There is a sign there that says "One road leads to your certain death (no way around this if you take this road), and the other leads you to salvation. There are two men here, one always lies, and the other always tells the truth. They both know the correct road to take, but you can only ask one question to one of the men of your choosing." If you ask one person you cannot ask the other person just to be clear. Only one question. What would be the question in which the answer would tell you the path that will leave you to safety?
Hmm, I know the answer, but I then realized I should give it more time before posting. Oops!
I figured you would probably either get this one, or know it already lol.
I think this is like an exam question in the logic portion of MATH 224; a lot more people may know it than you think. ^_^;
Please no more 224. I have the final tomorrow and my head hurts. :\
BTW, you ask one "If you were the other guy, would you tell me the left path leads to salvation?"
Arbitrarily picking left, both will say NO if the left path is the correct path, or YES if right is the correct path! :)
I'll go ahead and ask the next puzzle..if I may do so
There are 5 houses in 5 different colors. In each house lives a person with a different nationality. The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet. No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.
Somebody owns a fish. The question is: who?
Hints
* The Brit lives in the red house.
* The Swede keeps dogs as pets.
* The Dane drinks tea.
* The green house is on the left and next to the white house.
* The green homeowner drinks coffee.
* The person who smokes Pall Mall rears birds.
* The owner of the yellow house smokes Dunhill.
* The man living in the center house drinks milk.
* The Norwegian lives in the first house.
* The man who smokes Blends lives next to the one who keeps cats.
* The man who keeps the horse lives next to the man who smokes Dunhill.
* The owner who smokes Bluemaster drinks beer.
* The German smokes Prince.
* The Norwegian lives next to the blue house.
* The man who smokes Blends has a neighbor who drinks water.
Quote from: Mark Sands on 2008-12-18T00:31:04-06:00 (Thursday)
Please no more 224. I have the final tomorrow and my head hurts. :\
BTW, you ask one "If you were the other guy, would you tell me the left path leads to salvation?"
Arbitrarily picking left, both will say NO if the left path is the correct path, or YES if right is the correct path! :)
In that case, if you had chosen the correct path, the liar will tell you it's the wrong path, but the honest one will tell you it's correct.
You need to ask one of them, "Which path would the other person tell me to take?" in order to XNOR them. Then take the opposite path.
Quote from: Tangent Orchard on 2008-12-17T23:41:19-06:00 (Wednesday)
I think this is like an exam question in the logic portion of MATH 224; a lot more people may know it than you think. ^_^;
I know, that is why I said many of you might already know this. I just wanted to get something started lol.
Quote from: William Grim on 2008-12-18T01:30:02-06:00 (Thursday)
In that case, if you had chosen the correct path, the liar will tell you it's the wrong path, but the honest one will tell you it's correct.
You need to ask one of them, "Which path would the other person tell me to take?" in order to XNOR them. Then take the opposite path.
Mr. Grim is correct. If the person you asked was the liar, he has to tell you the path the truthful person will tell you, however he has to lie so he will tell you the wrong one. Then, the person who cannot lie will have to tell you the path the liar with tell you. Since the liar has to lie, the truthful person will tell you the wrong path as well. So, either way you just go the opposite way they tell you.
Or as Grim put it so elegantly, this question will XNOR them.
Quote from: Mark Sands on 2008-12-18T00:46:02-06:00 (Thursday)
I'll go ahead and ask the next puzzle..if I may do so
There are 5 houses in 5 different colors. In each house lives a person with a different nationality. The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, and keep a certain pet. No owners have the same pet, smoke the same brand of cigar, or drink the same beverage.
Somebody owns a fish. The question is: who?
Hints
* The Brit lives in the red house.
* The Swede keeps dogs as pets.
* The Dane drinks tea.
* The green house is on the left and next to the white house.
* The green homeowner drinks coffee.
* The person who smokes Pall Mall rears birds.
* The owner of the yellow house smokes Dunhill.
* The man living in the center house drinks milk.
* The Norwegian lives in the first house.
* The man who smokes Blends lives next to the one who keeps cats.
* The man who keeps the horse lives next to the man who smokes Dunhill.
* The owner who smokes Bluemaster drinks beer.
* The German smokes Prince.
* The Norwegian lives next to the blue house.
* The man who smokes Blends has a neighbor who drinks water.
It is the Norwegain who lives in the Yellow house, that smokes Dunhill Cigs, and drinks water
Just to see if I am right, this is what I have for everyone. They are in order of whole lives next to who, left to right. Norwegian being the furthest left and Swede being furthest right.
Nationality House Color Gigs Drink Pet
Norwegian Yellow Dunhill water fish
Dane Blue Blends tea horses
Brit Red Pall Mal milk Bird
German Green Prince coffee cat
Swede White Bluemaster Beer Dog
Tony, "The man who smokes Blends lives next to the one who keeps cats." ...???
Quote from: William Grim on 2008-12-18T01:30:02-06:00 (Thursday)
In that case, if you had chosen the correct path, the liar will tell you it's the wrong path, but the honest one will tell you it's correct.
Nope. My way works. The liar will say "no the truthteller won't tell you the left path is correct!" because he's lying.. and the truthteller will say "no the liar won't tell you the left path is correct" because the liar lies of course. Reversal if left is actually the wrong path. But whatever.
@Tony you were very close, you had the Norwegian and the German switched on pets. but the answer is the German. (Also this riddle is known as Einsteins riddle)
Nationality House Color Gigs Drink Pet
Norwegian Yellow Dunhill water cat
Dane Blue Blends tea horses
Brit Red Pall Mal milk Bird
German Green Prince coffee fish
Swede White Bluemaster Beer Dog
Man, I don't know what I did wrong. I will have to go through it again and see. I know I probably just got ahead of myself and put something in the wrong spot near the end that threw me off. Oh well. Good riddle though. Crazy how I got everything right but got them mixed up on their pets lol.
Here is another Riddle/Interview question. You have a sheet cake and there is a rectangle missing from somewhere in the cake. The location and size of the rectangle is arbitrary. How can you divide the cake with only one cut where the cake will be divided into two exactly equal pieces. You cannot cut the cake horizontally. In other words, you make a cut on the top of the cake.
I am sure a lot of people have heard this one, but it is pretty kewl. Don't cheat and Google it.
Does the cut have to be a straight line?
Are the sides of the missing rectangle parallel to the sides of the cake?
Quote from: blacklee on 2008-12-20T08:47:43-06:00 (Saturday)
Does the cut have to be a straight line?
Are the sides of the missing rectangle parallel to the sides of the cake?
The cut has to be one done by a knife. One single cut. The rectangle can be anywhere on the cake, in any arrangement.
No answers? It is a lot easier than you think. I will give it one more day and I will post the answer.
You find the center of the cake (P1) and the center of the piece that had been cut out of the cake (P2). You then cut along the line from P1 to P2.
Quote from: Justin Camerer on 2008-12-23T23:33:38-06:00 (Tuesday)
You find the center of the cake (P1) and the center of the piece that had been cut out of the cake (P2). You then cut along the line from P1 to P2.
Yup. I figured either you or Grim would get it.
Got another one.
Interview Question: You have 8 balls. One of them is defective and weighs less than others. You have a balance to measure balls against each other. In 2 weighings how do you find the defective one?
You weigh 3 balls on each side, leaving 2 off.
If one side weighs less than the other, discard all balls except those that were on the side that weighed less. Take the remaining 3 and weigh 1 on both sides, leaving the last one off. If one side weighs less, this is the defective ball. Else, the ball you didnt weigh is the defective one.
Else, weigh the 2 balls that you didnt weigh to find the defective one..
w00t!
^
Shoot, I knew that one; too late! =P
Good job on the cake one though, I couldn't figure it out.
Given a set of numbers from 1 to 2^N, they are randomly ordered, and one is missing. Find me the missing number using only one variable other than the input array and your loop counter.
Next, assume you have a set of 1 to N (note: this is not the same condition as above) unsigned numbers, and they are randomly ordered. Assume your computer registers are of infinite size. Find me the K missing numbers using no variables other than the input array, your loop counter, and the output array (which is write-once per cell only).
In both cases, you know what N is.
Quote from: William Grim on 2008-12-24T20:04:11-06:00 (Wednesday)
Given a set of numbers from 1 to 2^N, they are randomly ordered, and one is missing. Find me the missing number using only one variable other than the input array and your loop counter.
Next, assume you have a set of 1 to N (note: this is not the same condition as above) unsigned numbers, and they are randomly ordered. Assume your computer registers are of infinite size. Find me the K missing numbers using no variables other than the input array, your loop counter, and the output array (which is write-once per cell only).
In both cases, you know what N is.
In the second one, k missing numbers. So, that means there can be multiple missing numbers and we have to give them all to you inside an output array which is write-once only per cell?
For the first part can you just set up a loop as follows?
int sum = 0;
for(int i = 1; i <= N; i++)
{
sum += i;
}
Then
for(int i = 0; i < inputArraySize; i++)
{
sum -= inputArray[ i];
}
sum will be what number is missing and you only used one variable.
I am still working on the other one.
Quote from: Tony on 2008-12-26T15:46:19-06:00 (Friday)
In the second one, k missing numbers. So, that means there can be multiple missing numbers and we have to give them all to you inside an output array which is write-once only per cell?
Yes, there are K numbers, such that K is a non-negative integer. Yes, the output array is write-once per cell, meaning once A_i is set, it cannot be changed.
Quote from: Tony on 2008-12-26T16:16:48-06:00 (Friday)
For the first part can you just set up a loop as follows?
int sum = 0;
for(int i = 1; i <= N; i++)
{
sum += i;
}
Then
for(int i = 0; i < inputArraySize; i++)
{
sum -= inputArray[ i];
}
sum will be what number is missing and you only used one variable.
I am still working on the other one.
Yeah, that's a correct and reasonable answer. However, can you do it in just a single loop?
For a hint at solving the one with K missing numbers, maybe I should make it more clear that you can do whatever you want to the input array.
Quote from: William Grim on 2008-12-26T21:45:54-06:00 (Friday)
Yeah, that's a correct and reasonable answer. However, can you do it in just a single loop?
I guess I could just do...
int sum1 = 0;
int sum2 = 0;
for(int i = 1; i <= n; i++)
{
sum1 += i;
if(i != n)
{
sum2 += inputArray[ i - 1];
}
}
int answer = sum - sum2;
I haven't started working on the second part yet, been too busy, but I am about to do it now. So, I will let you know shortly lol.
For the second part, if we can "do whatever we want" to the array, can't we just resize it by 1, then iterate the array to find the largest value in the array, and place it in the new spot of the array? Then make the output array the size of the max number + 1 and initialize all the values to be -1, since they are non-negative numbers, then start placing the numbers in the index of the new array that match its value. So, if you come across a 42, the number 42 would be put in the 42nd place of the output array. This would sort the numbers. Next you can just iterate through the array again and every time you come across a value of -1 you would place that in the outputArray[cnt] where cnt is a count that keeps track of how many -1s you have found. Since, there will never be more -1s than indexes in the array, you would never get ahead of yourself and overwrite one of the values you have not checked yet. After you reach the end of the array you can just resize the array back down to the size of cnt+1. Does that make sense or did I break some rules of the problem?
Quote from: Tony on 2008-12-28T18:27:36-06:00 (Sunday)
For the second part, if we can "do whatever we want" to the array, can't we just resize it by 1, then iterate the array to find the largest value in the array, and place it in the new spot of the array? Then make the output array the size of the max number + 1 and initialize all the values to be -1, since they are non-negative numbers, then start placing the numbers in the index of the new array that match its value. So, if you come across a 42, the number 42 would be put in the 42nd place of the output array. This would sort the numbers. Next you can just iterate through the array again and every time you come across a value of -1 you would place that in the outputArray[cnt] where cnt is a count that keeps track of how many -1s you have found. Since, there will never be more -1s than indexes in the array, you would never get ahead of yourself and overwrite one of the values you have not checked yet. After you reach the end of the array you can just resize the array back down to the size of cnt+1. Does that make sense or did I break some rules of the problem?
Sorry, when I said that you could do anything you want to the input array, I meant you could read and write to each cell of the array, not resize it. I didn't mean to be vague, but that would be like creating new variables :-D
You can just assume the output array is length N. You cannot assume anything in particular about the values in each cell of the output array. If the cells are initialized with any value, then those cells are set and cannot be changed.
I'll post a solution soon if it's still causing some issues. You do have the correct general idea though, but think about the fact that you can use the input array's cells for read/write storage and that the numbers are guaranteed to be non-negative (i.e. unsigned). What can you do with the input array to capture information in a similar fashion as your -1 idea?
Quote from: Tony on 2008-12-28T18:11:59-06:00 (Sunday)
I guess I could just do...
int sum1 = 0;
int sum2 = 0;
for(int i = 1; i <= n; i++)
{
sum1 += i;
if(i != n)
{
sum2 += inputArray[ i - 1];
}
}
int answer = sum - sum2;
I haven't started working on the second part yet, been too busy, but I am about to do it now. So, I will let you know shortly lol.
The original problems states that you only have the input array, your loop counter, and one other variable. You have a couple variables.
The original problem didn't explicitly state this but should have: the data types you're working with are integers. However, you seem to have picked up on this.
I'll post a solution this evening after work.
Well, is there no number larger than N? If there is not, you can just make your array of size N and initialize every value to -1 like I stated before, and then iterate through the array once placing each number in the index that matches that number. Then when that is done iterate the loop again and each time you read a -1 place it in index value cnt, where cnt is equal to the number of -1s you have found. At the end you can just place a -1, or a null value for all remaining indexes in the array. Is that valid?
As for the second part I guess I could just do
int answer = 0;
for(int i = 1; i < n; i++)
{
answer += i - inputArray[ i];
}
answer += n; //adds in the final value since there is one less value in the inputArray
return answer;
Quote from: Tony on 2008-12-29T20:25:28-06:00 (Monday)
Well, is there no number larger than N? If there is not, you can just make your array of size N and initialize every value to -1 like I stated before, and then iterate through the array once placing each number in the index that matches that number. Then when that is done iterate the loop again and each time you read a -1 place it in index value cnt, where cnt is equal to the number of -1s you have found. At the end you can just place a -1, or a null value for all remaining indexes in the array. Is that valid?
In the original problem, the input array can be 2^N long. In the second problem, the input array can be N long.
Your algorithm looks like it's on the right track, but the answer I'm looking for is the most efficient in terms of speed and space. However, I believe I mispoke when I said that the valid range of input values is 1 to 2^N. I should've either said 1 to (2^N)+1 or 0 to 2^N. I'm sorry about that.
Since you know that the maximum number is 2^N, you can take advantage of XOR:
Let's assume you have the input array: {4,2,3}. The missing number would be 1. This is the algorithm you would follow to find it:
- Shift all numbers by -1, implicitly, leaving you with an implicit array of {3,1,2}.
- Initialize your variable to 0.
- Iterate your array, XOR'ing your variable with the implicit value from the array (see the first step).
- Return your final value + 1 to shift it back to the original offset the array was using.
This is the answer I was hoping you'd get:
#include <stdio.h>
unsigned findXor(const unsigned const vals[], size_t len) {
unsigned val = 0;
for (int i = 0; i < len; ++i) {
val ^= (vals[i]-1);
}
return val+1;
}
int main() {
unsigned vals[] = {1,2,3,4,5,6,7};
size_t n = sizeof(vals) / sizeof(int);
printf("%u\n", findXor(vals, n));
return 0;
}
Hmmm, I was thinking about XOR, but wasn't sure if you needed it on this problem. I was just wondering though, couldn't you just take the input array and XOR it with the value of i as you iterate through the input array? Then if i = the max range, then just XOR the last number with 0 (essentially XORing the missing number with 0). Wouldn't that give you the missing value as well? That will only work for the first one, because there is 1 missing number only. In the grand scheme of things, you can look at it as if every number was XORed by itself except the missing number. Right?
You still need to store your transient value somewhere; so, you may as well just stick to the simpler solution without trying to complicate the algorithm with the loop counter. I don't think that solution would yield the correct value.
Tony, do you remember me asking you a question like that in snrprj? I think I got that same question in an interview. That is a good one.
For the one with K missing numbers, you need to use a bit map. However, you can't create any variables other than your input array, loop counter, and output array (which is write-once per cell only). It would also be fair to let you use a constant that knows the bitmask for the sign bit if your unsigned numbers were signed. I.e. if 7 is the largest value in the input, then your bitmask would be 1000.
You then go through your input array, masking out the MSB and being left with an unsigned number (you have an input array of unsigned to begin, but you'll see why this is important later). Let your input array be called I and the index i. You then set the MSB in I[I[i]]
After you are finished setting all the MSBs, traverse the input array again. Find all the unset MSBs and put those indices in the output array. You have found the K missing numbers.
Yeah Justin, the one you had was if you have a list of size N but every number is duplicated once, except once. How can you find that single number in constant time and constant space. The answer was using XOR also, which is why I was thinking about it for this problem, but didn't quite hit the mark I guess lol.
A problem from my discrete math class:
You are driving from point A to point B 200 miles apart. You drove first 100 miles with the average speed 25 mph. What should be your speed for the remaining 100 miles in order for the overall average speed of the trip to equal 50 mph?
Quote from: blacklee on 2009-01-06T20:01:10-06:00 (Tuesday)
A problem from my discrete math class:
You are driving from point A to point B 200 miles apart. You drove first 100 miles with the average speed 25 mph. What should be your speed for the remaining 100 miles in order for the overall average speed of the trip to equal 50 mph?
75 MPH based on a weighted average of "differing distances", which in this case aren't actually different. I do hope people would get a question like that.
50 = (25 * 100 + x * !00) / 200, solve for x
Quote from: William Grim on 2009-01-07T12:14:49-06:00 (Wednesday)
75 MPH based on a weighted average of "differing distances", which in this case aren't actually different. I do hope people would get a question like that.
50 = (25 * 100 + x * !00) / 200, solve for x
Not quite right. Since you'd be travelling 75 mph for 1 hour and 20 minutes and 25 mph for 4 hours, the overall average would be 36 mph.
It's an impossible question. In order for the average speed to be 50 mph, you would have to get through the entire 200 mile trip in 4 hours (200 miles / 4 hours = 50 mph). Since the first 100 miles takes the whole 4 hours at 25 mph, it's impossible to average 50 mph.
Quote from: CoryLehan on 2009-01-07T16:12:24-06:00 (Wednesday)
Not quite right. Since you'd be travelling 75 mph for 1 hour and 20 minutes and 25 mph for 4 hours, the overall average would be 36 mph.
It's an impossible question. In order for the average speed to be 50 mph, you would have to get through the entire 200 mile trip in 4 hours (200 miles / 4 hours = 50 mph). Since the first 100 miles takes the whole 4 hours at 25 mph, it's impossible to average 50 mph.
You're right. I did not sanity check.
Yes Cory, you got it!
Quote from: William Grim on 2009-01-07T12:14:49-06:00 (Wednesday)
I do hope people would get a question like that.
Only one or two people in the class solved it correctly
(I was not one of them :oops:
Arrrrrrrgh! :pirate:
<--- ***GLEAMS***