Puzzles you can't solve with Google
One of the techniques that people commonly use in interviewing software engineers is to use puzzle questions to ascertain the problem solving process of candidates. However, the problems themselves are generally drawn from commonly asked puzzle questions, some of them even famous puzzle problems, which lets candidates solve them either by search engine, or by memorization.
So what's a good source of problems to ask which are not generally available on the internet? Well, many college mathematics or computer science textbooks contain obscure and hard example problems which are not generally covered in internet discussions.
One of them, that I encountered over 12 years ago, still burns in my memory today because of connections with quite beautiful mathematical structures. I will reproduce the problem below, obfuscated from the original way it was stated, in order to avoid book searches. I have only seen this problem discussed twice by others in 20 years of internet usage. It has analogous solutions in some ACM/IEEE/CiteSeer references, but in general is not discussed in IT or Puzzle literature.
I will post the solution later in another message.
The Balsa Wood RAM Machine
You are given a computer attached to a unique memory device consisting of a number of sticks of Balsa Wood, 7 to be exact. The computer can read from this memory by checking to see whether a given stick of wood in position X is either broken or unbroken, representing a 1 or a 0 respectively. The computer can also write to this memory, but it can only write *1* bits, it cannot write a 0, that is, it can break sticks, but it cannot repair a broken stick.
The computer operates on decimal number in the range 0-6, and the question arises, how many times can the computer write a number to the RAM and read it back? What would the read and write procedures look like?
As an example, you can imagine that if the RAM is empty, if you want to write a decimal value X, you place a 1 in the Xth RAM position (break stick X). You read this value back by observing which position contains a broken stick.
The RAM however has 6 more unbroken sticks, can't we use this to support multiple writes? Yes, a second write could be supported for value Y by breaking all sticks except Y, in which the read procedure would be to observe which stick is left unbroken.
Those are the trivial procedures. What about 3 writes or 4? It turns out that 4 writes are possible. So, the question is:
Specify an algorithm for writing 4 values into the RAM and being able to read them back at each step, without foreknowledge of what was written before.
That is, your task is to produce two procedures: WRITE(BitSet current, Integer valueFromZeroToSix) -> returning BitSet and READ(BitSet current) -> returning Integer, in which the following is true:
1) WRITE returns a new BitSet produced by taking the old BitSet and changing only 0 to 1s. It also replaces the current bitset with the return value.
2) READ(WRITE(current, X)) == X
3) Any sequence of WRITE and READ operations may occur as long as the number of WRITE operations is less than 5.
I will post the solution some time in the future.
-Ray
One of the techniques that people commonly use in interviewing software engineers is to use puzzle questions to ascertain the problem solving process of candidates. However, the problems themselves are generally drawn from commonly asked puzzle questions, some of them even famous puzzle problems, which lets candidates solve them either by search engine, or by memorization.
So what's a good source of problems to ask which are not generally available on the internet? Well, many college mathematics or computer science textbooks contain obscure and hard example problems which are not generally covered in internet discussions.
One of them, that I encountered over 12 years ago, still burns in my memory today because of connections with quite beautiful mathematical structures. I will reproduce the problem below, obfuscated from the original way it was stated, in order to avoid book searches. I have only seen this problem discussed twice by others in 20 years of internet usage. It has analogous solutions in some ACM/IEEE/CiteSeer references, but in general is not discussed in IT or Puzzle literature.
I will post the solution later in another message.
The Balsa Wood RAM Machine
You are given a computer attached to a unique memory device consisting of a number of sticks of Balsa Wood, 7 to be exact. The computer can read from this memory by checking to see whether a given stick of wood in position X is either broken or unbroken, representing a 1 or a 0 respectively. The computer can also write to this memory, but it can only write *1* bits, it cannot write a 0, that is, it can break sticks, but it cannot repair a broken stick.
The computer operates on decimal number in the range 0-6, and the question arises, how many times can the computer write a number to the RAM and read it back? What would the read and write procedures look like?
As an example, you can imagine that if the RAM is empty, if you want to write a decimal value X, you place a 1 in the Xth RAM position (break stick X). You read this value back by observing which position contains a broken stick.
The RAM however has 6 more unbroken sticks, can't we use this to support multiple writes? Yes, a second write could be supported for value Y by breaking all sticks except Y, in which the read procedure would be to observe which stick is left unbroken.
Those are the trivial procedures. What about 3 writes or 4? It turns out that 4 writes are possible. So, the question is:
Specify an algorithm for writing 4 values into the RAM and being able to read them back at each step, without foreknowledge of what was written before.
That is, your task is to produce two procedures: WRITE(BitSet current, Integer valueFromZeroToSix) -> returning BitSet and READ(BitSet current) -> returning Integer, in which the following is true:
1) WRITE returns a new BitSet produced by taking the old BitSet and changing only 0 to 1s. It also replaces the current bitset with the return value.
2) READ(WRITE(current, X)) == X
3) Any sequence of WRITE and READ operations may occur as long as the number of WRITE operations is less than 5.
I will post the solution some time in the future.
-Ray
Labels: puzzles
posted by Ray Cromwell at 5:21 PM
4 Comments:
This comment has been removed by the author.
My previous question was whether the same value could be written twice, but it's clear that it can be.
Yeah, but it would be a no-op if they were right after one another. The solution can probably be brute forced Karnaugh-map style, but there's an elegant geometry and theory behind the true solution.
Interesting one. Thanks for the share. I was very interesting and information. Keep posting such kind of post on your blog. I bookmarked it for continuous visit.
html5 video player| html5 player
Post a Comment
<< Home