We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
This post is third in the series of programming job interview challenge, if you are not yet familiar with these series please take your time and read:
Well, last weeks challenge was very successful, all of the comments which contain answers to the question are now approved and can be viewed in challenge #2 post.
The correct answer to challenge #2:
As our first commentator (who answered correctly), Mike Agar said:
This is a Big “O” problem that screams for a LUT (Look Up Table). Don’t spin on each pixel, create your 256 entry look up table of all possible reversals, and do a quick pass over the 1000×1000 array by simply indexing into the table with the original value as the lookup.
Those guys provided the correct answer in their blogs:
Trung Dinh solution : http://www.taak.org/challenge2.htm.
Adam B answer : http://programmersthoughts.blogspot.com/
Igor Ostrovsky answer: http://igoro.com/archive/programming-job-interview-challenge/
Those guys provided the correct answer by leaving a comment:
Anton Irinev who provided an implementation, Heiko Hatzfeld, Bill Krueger, Niki, Kevin I, Chris Miller, Will (didn’t mention LUT but its very close), Compuboy, Eugene Efimochkin, Adrian Aisemberg, Tim, leppie and bartek szabat.
Roberto Orsini wrote a really great implementation of how to parallelise the problem here - http://blog.fogbank.org/ , using threads from the threadPool, but he didn’t use LUT to reverse the bits. Although this problem is perfectly parallelizable, you can’t rely on the fact that there is more than one CPU (unless stated it in the question). All of the others who provided bitwise operations: even if your solution is correct (XOR with 0xFF is wrong for instance) it is not the most efficient one, you should assume that your code should work on every machine and every processor and you can’t rely on specific hardware where a specific operation may be very efficient.
Edward Shen gave a very detailed answer by mail ,which is currently for the Dev102 eyes only (unlike comments and blog post which are public). We (Dev102 team) realized that we made a mistake because we introduced mail as one of the options to send answers. So, I would like to emphasize that:
This weeks question:
Your input is mXn numeric matrix which is made up from sorted rows and sorted columns. Take a look at the following example, notice that all rows are sorted and all columns are sorted. What is the most efficient way to find an item in this matrix and what is the complexity of the solution.
Take your time…, do you know the answer?
Accept the challenge and provide your solution.
Tags :answerchallengecorrecteficienthi techimagesjob interviewpixelproblemprogrammingquestionsolution
Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd