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 >> | (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 * 0×0802LU & 0×22110LU) | (b * 0×8020LU & 0×88440LU)) * 0×10101LU >> 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 & <> 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] << | 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