Job Interview Challenge Last week I posted  A Programming Job Interview Challenge which was very successful, both in the amount of page views and, in the amount of comments and mails we received. This fact made us (the Dev102 team) decide to add a weekly programming job interview challenge column to www.Dev102.com.

The format:

  • We post a “Job Interview” question about
    software development and programming.
  • You, the readers have the opportunity to
    accept the challenge, think and provide
    your answer.

You can:

  • Write a post in your blog (if you have one) that links to our challenge post and contains your solution to the challenge. You will get a link from us in the next weeks challenge…
  • Add a comment which will not be approved until next weeks challenge (if readers will see the correct answer in one of the comments, it will become pointless). When we post the next challenge, all of the comments will be approved and we will also mention them in the new post.
  • Send a mail through the contact page. Your mails will also be mentioned in the next post.
  • In the following week, a new programming job interview challenge post will be published. The new post post will contain:
    • The correct answer of last weeks challenge.
    • Readers answers to last weeks challenge.
    • A new “Job Interview” question.

Lets start the fun with this weeks question:

Given a 1000X1000 grayscale image where each pixel is 8 bits, you need to reverse the order of the bits in each pixel. Example: 10001101 becomes 10110001, 00111101 becomes 10111100 and so on. Provide the most efficient solution in the manner of performance because another input is that you need to handle many images per second.

Think… Do you know the answer? Accept our challenge and provide your answer… Enjoy.

Tags :

39 Responses to “A Programming Job Interview Challenge #2”


  1. Randoom

    Said on May 5, 2008 :

    “you need to switch the order of the bits in each pixel”

    you mean revert

  2. Shahar Y

    Said on May 5, 2008 :

    Randoom,

    The post was fixed to make it clearer, thanks.

  3. BillB

    Said on May 5, 2008 :

    I think the correct word here is “reverse”. Revert means to set back to the previous state.

  4. james hollingworth

    Said on May 5, 2008 :

    is this not simply big endian to little endian? in which case value = ((value >> 8) | (value << 8))

  5. test1

    Said on May 5, 2008 :

    are you just asking to apply NAND or XOR bitwise op for each group of pixel bytes against an 0xFF (or more for say 64 bit) mask ? If you machine is 64 bit can do 8 pixels at a time in one cpu op call. ie. block of mem, move the pointer in mem n bytes (either say 4 or 8 for 32 or 64 bit) and NAND with 0xFFFFFFFF or 0xFFFFFFFFFFFFFFFF (32 or 64 bit) ? did I understand the question correctly ?

  6. Shahar Y

    Said on May 5, 2008 :

    james hollingworth,

    Big endian to little endian means changing the bytes order. I ment to change the bits order.
    Clarification: you need to reverse the bits order.
    Comments with answers are not yet approved (as written in the post) until next week.

  7. Mike Agar

    Said on May 5, 2008 :

    This is a Big “O” problem that screams for a LUT. 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.

  8. Trung Dinh

    Said on May 5, 2008 :

    My attempt at a solution written in taak:

    http://www.taak.org/challenge2.htm

  9. Heiko Hatzfeld

    Said on May 5, 2008 :

    I think the best solution for this problem would be the construction of an array to store the inverted bits for each byte. After you have calculated this array, you can easily look up the solution via its index. in the array.

    This should be much faster then reversing the order of every bit you encounter by hand.

    The size of this cache is minimal… we only need to store 256 entries here – Compared to the 1.000.000 swapping opperations for each picture.

    I will leave the implementation of this to someone else, since I am about to get of work ;)

  10. Joe

    Said on May 5, 2008 :

    My answer would be, “Use the reverse bits in a byte equation for each byte”. I would need to lookup the equation because I can never remember the exact numbers to use but if I had it would be.

    b = (byte)(((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16);

  11. Adrian Aisemberg

    Said on May 5, 2008 :

    Keep a 256 size array of bytes (byte[256]).
    For each byte we calculate, we keep its result value in the array, as: arr[x]=f(x), so next time we get the same byte, we have its calculation in O(1).
    So our function will run maximum 256 times.

  12. Bill Krueger

    Said on May 5, 2008 :

    First thought as a general solution.

    Construct a byte array of 256 elements and use the source bytes as an index into the array.

    To eek out additional speed, construct the array as a static final by hand.

    Second thought would be to play with larger elements in the array as the source is 1000bytes wide and converting two bytes at a time would be faster.

    Other considerations would be to see if using multi-processors can be made part of the solution and split the processing into threads.

    Bill

  13. Rob Conery

    Said on May 5, 2008 :

    So what happens when the interviewer asks the wrong question? :p

  14. Hitesh

    Said on May 5, 2008 :

    Use the XOR operator as such:
    result = value XOR 0xFF

  15. Tim

    Said on May 5, 2008 :

    Lookup table?

  16. Niki

    Said on May 5, 2008 :

    I think there is only correct answer to this question in a job interview: If this is really performance critical, I can’t answer it without implementing at least the two most obvious solutions (using an LUT or using logical operations+SIMD), and profiling them. Anything else would be guesswork and superstition, todays’s CPUs are to complex to decide something like this in an interview.

  17. Kevin I

    Said on May 5, 2008 :

    Create a precomputed 256-byte lookup table where table[i] contains the binary reverse of i. Iterate through the pixels in your image and replace each value with the result from the lookup table.

  18. Nathan

    Said on May 5, 2008 :

    I’m guessing the fastest way is to take 4 or 8 byte chunks and reverse all the bytes simultaneously. Something like this.

    reversed =
    ((value & (1<<0 | 1<<8 | 1<<16 | 1<<24)) << 7) |
    ((value & (1<<1 | 1<<9 | 1<<17 | 1<<25)) << 5) |

  19. Chris Miller

    Said on May 6, 2008 :

    A 256-byte array lookup table and a couple of for loops.

  20. will

    Said on May 6, 2008 :

    1000*1000 pixels with eachone 8 bits means there are a lot of duplicates, so apply reverse to all the duplicates at once, should reduce a lot cost

  21. Compuboy

    Said on May 6, 2008 :

    first pre-compute all reverses in a byte array simply like this:

    byte[] reverse = new byte[256];

    for (int x = 0; x < 256; x++)
    reverse[x] = (byte) (((x & 1) << 7) + ((x & 2) << 5) + ((x & 4) << 3) + ((x & 8) <> 1) + ((x & 32) >> 3) + ((x & 64) >> 5) + ((x & 128) >> 7));

    And then we simply iterate the pixels of our image and foreach pixel value ‘x’ we will substitute it with reverse[x].

    ‘reverse’ can be computed once and will be reused for each image.

  22. Eugene Efimochkin

    Said on May 6, 2008 :

    I think a lookup in a prefilled table with already reversed bits is the most fast solution trading less than 1 KB memory for it and no functions or bitwise operations used. The whole processing becomes bytewise this way.

  23. leppie

    Said on May 6, 2008 :

    You are only dealing with 8 bits, hence just make a lookup table of size 256, with all the reversed numbers mapped. Eg:

    Lookup[25] = 19
    Lookup[123] = 111

  24. bartek szabat

    Said on May 6, 2008 :

    There is only 256 possible argument values for reversing function. the fastest solution will be to use precalcutaion.

    1. create lookup array:

    byte pre[256];

    2. fill it using any method.

    3. use: byte reverse(byte x){return pre[x];}

  25. boobooboo

    Said on May 6, 2008 :

    How many cores do I have? This is perfectly distributable. Single machine op per pixel.

  26. Shahar Y

    Said on May 6, 2008 :

    boobooboo,

    Assume that your code should work on every machine and every processor. Distribution is great but try to find an efficient answer without dealing with specific hardwares.

  27. Anton Irinev

    Said on May 6, 2008 :

    static class Task
    {
    private static byte[] table = new byte[256]; // 256 = 2^8;
    private static byte[] pow2 = new byte[8] { 1, 2, 4, 8, 16, 32, 64, 128 };

    static Task()
    {
    for (int i = 0; i < table.Length; i++)
    {
    // reverse i and save the result in table[i]
    for (int j = 0; j 0) table[i] |= pow2[8 – j – 1];
    }
    }
    }

    public static void ReverseBitmap(byte[,] bitmap)
    {
    for (int i = 0; i < bitmap.GetUpperBound(0) + 1; i++)
    {
    for (int j = 0; j < bitmap.GetUpperBound(1) + 1; j++)
    {
    bitmap[i, j] = table[bitmap[i, j]];
    }
    }
    }
    }

  28. Adam B.

    Said on May 7, 2008 :

    My solution to this problem is on my blog at http://programmersthoughts.blogspot.com/

  29. denis.gz

    Said on May 10, 2008 :

    If I had such question, I’d write something like this (C#):

    pubic static void ReverseBits(byte[] pic)
    {
    for (int i = 0; i < pic.Length; i++)
    {
    int b = pic[i];
    int t = 0;

    b <> 8;
    b <> 7;
    b <> 6;
    b <> 5;
    b <> 4;
    b <> 3;
    b <> 2;
    b <> 1;

    pic[i] = (byte) t;
    }
    }

  30. denis.gz

    Said on May 12, 2008 :

    Dammit, something has eaten my code… Anyway, a table lookup is a much better solution.

  31. Jonathan Gilbert

    Said on May 14, 2008 :

    The “official” solution suggests using a 256-entry LUT. It would be even faster to use a 16-bit LUT. At 65,536 16-bit entries, the LUT will use 128 KB of memory — but if you have to process many large images every second, that is almost negligible.

    A 128 KB LUT does not entirely fit into the L1 cache of most processors, but it does make it into the L2 cache, and in my testing it is a good 25% faster.

    ushort *lut_16b = new ushort[65536];

    for (int i=0; i > 8] << 8) | lut_8b[i & 255];

    ushort *image_16b = (ushort *)image;

    for (int i=0; i < 1000 * 1000 / 2; i++)
    image_16b[i] = lut_16b[image_16b[i]];

  32. Jonathan Gilbert

    Said on May 14, 2008 :

    Ah, curses. The blog software screwed up my post. Must have thought it contained HTML. :-(

    for (int i=0; 65536 > i; i++)
    lut_16b[i] = (lut_8b[i >> 8] << 8 ) | lut_8b[i & 255];

  33. Brian H

    Said on June 25, 2008 :

    LOL, I love the solution that uses a class for this

  34. Joshua

    Said on October 7, 2008 :

    Create a 65536 element LUT, and process two pixels at a time. CPU caches are big enough that this should give a factor of two increase over the single-pixel-at-a-time method.

  35. Jimi

    Said on June 16, 2009 :

    i found a good algorithm to reverse bit inside a integer here:
    http://algorithms-and-data-structures.blogspot.com/2009/06/reverse-bit-order.html

4 Trackback(s)

  1. May 6, 2008: Dew Drop - May 6, 2008 | Alvin Ashcraft's Morning Dew
  2. May 9, 2008: Igor Ostrovsky Blogging » Programming Job Interview Challenge
  3. May 12, 2008: A PROGRAMMING JOB INTERVIEW CHALLENGE #3 | Dev102.com
  4. Jun 9, 2008: BLOG STATS - MAY 2008 | Dev102.com

Post a Comment