August 08, 2003
back
A whole month has passed since my last entry. I guess I was Spirited Away (had to sneak this link in, just watched the movie last night and it was magical, can't wait to watch it again tonight). It so happened that during my silence a lot of math/cs problems and puzzles have piled up on my desk so with some luck I will be more active in the next weeks. Most of the problems came from the unlikely fact that our group at work got an open req suddenly and we had to do interviews. Boy were we rusty. We haven't had an open req forever. But it lead to us talking about interviews (btw a good discussion on the web about interviews is here) and what questions to ask. This lead to cs puzzles and then to problems which some of the group members knew and liked (not exactly suited for 1-hour interviews though).
So here are the problems:
1.) Prison cells. A prison has n cells with all cell doors shut initially. The warden is a little weird so he walks the whole row of cells and opens every cell door. Then he walks the whole row again and shuts every other cell door. Then he walks the whole row again and opens every third door then walks the row again and shuts every 4th door etc. You can assume that the doors are numbered 0 to (n - 1) and the warden always starts at 0 and walks them in order. Which doors will stay open when the warden is done ?
2.) 2D bitmask. Given a n x n grid of 0's and 1's find the largest square within the grid that only contains 0's.
3.) 2D grid of integers. Given a n x n grid of integers (not all positive) find the rectangle within the grid with the largest sum.
4.) S and P. Of two unknown integer numbers in the range [2..99] inclusive a person P is told the product and a person S is told the sum. When asked whether they know the numbers, the following dialogue takes place:
P: "I don't know them."
S: "I already knew that."
P: "Then I now know the numbers."
S: "Then I now know them too."
The problem is to determine the two numbers from the above data and to prove that the solution is unique. (this problem is note EWD666 from the delightful website EWD)
5.) Repetition. Given a sequence of comparable items (let's say characters) calculate the maximum number of consecutive equal subsequences (of any length). Consecutive means that when one subsequence ends the next one starts. Example: sequence abababbb has consecutive equal subsequences of length 2 ab ab ab, has consecutive subsequences of length 1 b b b etc.
I'm going to do the usual thing: try solving them and keep you posted in this blog about my progress then do a write-up in TeX for the ones I successfully solved.
