You can google the answer, but try not to; think about it first.

An evil king has n bottles of wine, and a spy has just poisoned one of them. Unfortunately, they don't know which one it is. The poison is very deadly; just one drop diluted even a billion to one will still kill. Even so, it takes a full month for the poison to take effect. Design a scheme for determining exactly which one of the wine bottles was poisoned in just one month's time while expending less than C log2(n) taste testers (for some constant C.)


(Mods, this puzzle is a programming/algorithms/math puzzle in disguise, so please don't delete or move to jokes section)

You can assume that n is a power of 2, just to keep things simple.

.

Can you remove the code and answer? Or provide the link only? This is one of those things it is better to think about for a while before just looking at the answer.

Also, I'm not looking for a "code" answer so much (it isn't hard to too hard to code once you figure out the idea behind it), so much as an explanation of how to do it.

This problem is kind of visual. . . you can draw a picture that illustrates how to solve it. Or explain in words, etc, etc.

ekt_bear:

Can you remove the code and answer? Or provide the link only? This is one of those things it is better to think about for a while before just looking at the answer.

I removed all.

This one was given to me today. Unlike the first problem, I wasn't able to solve this w/o googling (I found a similar problem online somewhere, then saw the trick behind it and used it to solve this)

Here it is:

There are 15 pennies on a table, 4 of them are heads up, 11 tails up. You are blindfolded. Divide the 15 pennies into two separate piles by flipping as many as you wish and dividing them how ever you wish such that both piles have the same number of heads. No cheating.

This one was given to me by a friend. Evidently it is a question that was actually asked at an interview. I was able to solve it without looking up the answer (good), but I took too long (bad).


Given a sequence of integers a_1, a_2,. . . , a_N derive a quadratic time algorithm (i.e. O(N^2) ) for finding all unique triples (a_i, a_j ,a_k) such that

a_i+a_j+a_k=0.

Hints:
1) It might help to think of this problem in two steps: first write an algorithm to find all pairs of numbers such that a_i + a_j=m (for a fixed integer m).
2) You may want to sort the list first (One thing to observe is that since you can sort a list in O(Nlog(N)) time, and your budget is O(N^2), you can sort once without exceeding your budget. So you may as well assume that the list is sorted.)
3) You can get an O(N^2 log(N)) algorithm in a fairly straightforward way. Question is, how do you get down to N^2? If you can get this far you are nearly there. . . just need to find the bottleneck and eliminate it.


Again, you don't really need to write code for this. Pseudo-code is fine. Or even better, explain in words how to do it.

.

Here is an old one I posted:

https://www.nairaland.com/nigeria/topic-749853.0.html

so you will design a scheme to kill people for testing? I'd rather design a scheme to trace the spy and make him/her tell which one poisoned in less than three days :p

skydancer:

so you will design a scheme to kill people for testing? I'd rather design a scheme to trace the spy and make him/her tell which one poisoned in less than three days :p

Hehehe

Tough questions. I'm out.

This doesn't need any codes. If it takes a month for the poison to get active. So Quarantine all bottles and wait for a month to pass. The bad bottle will be discovered.

Number_One:

This doesn't need any codes. If it takes a month for the poison to get active. So Quarantine all bottles and wait for a month to pass. The bad bottle will be discovered.

Even if you isolate each bottle, nobody says the poison will do anything to the bottle after 1 month. Btw, I just read the solution online and it sounds like a wack idea . . . even for testing purposes.

Perhaps it will help to post the Googled result here.
What I mean is if the poison is active in 1 month, then perhaps you can give a month for it to become active. At that point, anyone tasting it will get instant death. So if it is tasted and the person lives, there's nothing wrong with that bottle. Elimination.

Even so, that will be practically a wrong way to go about it. The only reason why finding the poisoned bottle should be attempted is if we don't want anyone to die, and as such, the perpetrator should be found.

Hehe

The ethical questions are interesting, but perhaps better to actually solve the problem asked rather than posing another one

More of these coming up soon, just been a bit busy with other stuff.

I posed this problem (https://www.nairaland.com/nigeria/topic-752857.0.html#msg9107748) to a friend. Out of our discussions of it, she then came up with two other puzzles that I thought were interesting, which neither of us know the answer to.


[size=15pt]#1[/size]
I have N sorted lists, each of length M. How much time does it take me to produce an N times M sized sorted list which contains all the numbers?

At first I thought you could do something cool where you where you wind up and down each list and can sort in NM time. Then I realized this isn't possible (or at least, I don't see how to do it. If you know of a way, let me know.) You could also do a sort of simple thing which sorts in (NM)log(NM) time (using quicksort, mergesort or some other sort algorithm.)

But this doesn't take advantage of the additional information you have. She came up with an algorithm that can do N^2 log(M) (See if you can figure out how she did this! It is kind of cool, or at least cool to me as a non-expert on this type of stuff.)

However, is it possible to do better than this O(N^2 log(M)) algorithm of hers?

(One comment about this. Notice that for her solution, when N=M, you are doing no better than the obvious solution which doesn't use any information, since O(N^2 log(N)) = O(N^2 log(N^2)) So it might be possible to do much better than the solution she had. If so, I'm not sure how.)

[size=15pt]#2[/size]
What if the lists are sorted in both directions? That is, not only is each list sorted, but also we have that the 1st element of each list is sorted, 2nd list sorted, etc. Can you take advantage of this additional information to do better than N^2 log(M)? We thought about this for a while, but couldn't come up with an answer (both of us are non-experts at this type of game.) (Well, there is a sort of easy thing you can do just using her solution for #1 and picking which direction you want to go. This will give you the smaller of N^2 log(M) and M^2 log(N).)

(BTW just to be clear what I mean when I say the lists are sorted in both directions, I mean that if the lists like this:
L_1 = (First number of L_1, Second number of L_1, Third number of L_1. . ., Nth number of L_1  )
L_2 = (First number of L_2, Second number of L_2, Third number of L_2. . ., Nth number of L_1)
. . .
L_M = (First number of L_M, Second number of L_M, Third number of L_M. . ., Nth number of L_1)

Then not only is the list L_1 sorted in increasing order, but we also have that the first numbers of each list are sorted, second number of each list sorted, etc.)

I got this at a job interview today. Actually got the problem kind of wrong, lol (well, the second part at least.)

You are given a string of length N. Pretend it is stored in a character array or something.

Imagine that you want to write a function that does K circular shift of strings.

In other words, given a string of length N, it shifts every character over by K.

As an example, suppose we are given the string S defined as follows:
S = "Ekt_bear is solving a puzzle"

If we do a K=3 circular shift of S, we get as output
"zleEkt_bear is solving a puz"

Two questions:
1) How can we solve this problem, assuming no constraints on memory usage?
2) How can we sove this problem, if the only extra memory we have is a single character variable called temp? This of course means that you are not allowed to create a new array and use this to solve the problem.

There is a small typo in the above that causes the code to hang. You probably mean to increment "i", not K.

The above works, and is essentially what I did.

But it is a K^2 algorithm. Each character only gets moved over one each iteration. Would be nice if each character gets moved over K in each iteration.

Can you do it in O(K)? This is what I was asked which I messed up on.

Indeed, i should have written K*N and N, respectively.

O(N) iterations is very possible.

Perhaps a good place to start is with a very small string "abcde" and K=2.

Try to move characters over by 2.

Yep, I guess it is pretty easy with a doubly linked list, assuming you have a tail pointer.

You can just delete the last K elements and and insert each of them at the start of the list. Update your tail pointer after each element is removed.

Almost works with SLL, just cannot update tail pointer cheaply.

Err, it works with SLL too.

Just delete from start and move to end.

@omo_to_dun: Thanks, I saw your message. I actually have a book of programming puzzles that I'm working through now though. Thanks for those too, though.

If it is accounting related i would be able to contribute.

The answer is simple:

C is a constant. N is a variable = 30 days in a month

SUbsitute in the equation you