I wrote earlier that I know very few decent programming puzzles. To be more precise, I know one, The Prisoners Riddle. So I was reading that The Art of Multiprocessor Programming book (I already made a post influenced by what I read there, and I'll soon make another one--stay tuned). Some very interesting things the book tells about can be formulated as puzzles. Here's one.
Two threads need a mutex object with Lock and Unlock methods, but they only have three usual shared boolean variables. How to implement such a mutex?
Every thread can call GetThreadId() function which returns 0 for one thread and 1 to the other, and the boolean variables are automatically initialized to false before threads execute.
If you solved it, congratulations; you have just reinvented this wheel.
Since I know the solution, I can't really understand if it's a good riddle or not. It's definitely too hard for a job interview, but still, it can be a good one. So I need your comments. What do you think? Could you solve it?
Author Paul Shved
Modified April 27, 2013
License CC BY-SA 3.0