Walter Reid
The Downfall of the Programming Interview (cont.)
Easy
Give a very good method to count the number of ones in a “n” (e.g. 32) bit number.
Give a one-line C expression to test whether a number is a power of 2 without the use of loops.
Give a fast way to multiply a number by 7.
Swap the contents of two variables without the use of a temporary variable. Can you do it without the use of addition, subtraction, multiplication or division symbols?
Medium
Write a function that takes in 2 integers “X” and “Y” and returns a value “Z” that represents “X / Y” without actually using the division symbol.
Write a function that takes in 2 integers “X” and “Y” and returns a value “Z” that represents “X * Y” without actually using the multiplication symbol.
How do we test most simply if an unsigned integer is a power of two?
Set the highest significant bit of an unsigned integer to zero.
A character set has 1 and 2 byte characters. One byte characters have 0 as the first bit. You just keep accumulating the characters in a buffer. Suppose at some point the user types a backspace, how can you remove the character efficiently. (Note: You cant store the last character typed because the user can type in arbitrarily many backspaces)
Write a function “reverse(char *string)” to reverse a string without allocating a temporary buffer.
Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all.
Write a SetPixel(x, y) function, given a pointer to the bitmap. Each pixel is represented by 1 bit. There are 640 pixels per row. In each byte, while the bits are numbered right to left, pixels are numbered left to right. Avoid multiplications and divisions to improve performance.
Hard
Reverse the bits of an unsigned integer.
Compute the number of ones in an unsigned integer.
Compute the discrete log of an unsigned integer.
Write a function that takes in 2 floats “X” and “Y” and returns a value “Z” that represents “X / Y” without actually using the division symbol.
Write a function that takes in 2 floats “X” and “Y” and returns a value “Z” that represents “X * Y” without actually using the multiplication symbol.
84. If you’re familiar with the ? operator x ? y : z
you want to implement that in a function: int cond(int x, int y, int z); using only ~, !, ^, &, +, |, <<, >> no if statements, or loops or anything else, just those operators, and the function should correctly return y or z based on the value of x. You may use constants, but only 8 bit constants. You can cast all you want. You’re not supposed to use extra variables, but in the end, it won’t really matter, using vars just makes things cleaner. You should be able to reduce your solution to a single line in the end though that requires no extra vars.
Write a function “int increment(int val)” that returns val + 1 without using plus or minus’s anywhere in your code. Yes, you will probably need to do some bitwise operations to accomplish this.
Write a function “void noparens(char * expression)” that prints all the possible different results you can get from different grouping of parentheses in the given expression.
The string ‘expression’ contains the operators ’+’, ’-’, ’*’ and positive integers (or possibly no operators and just one integer). The expression is entirely unparenthesized. Your function should determine the result of every possible parenthesization of the expression and print the distinct ones.
Don’t worry about overflowing int or strange formatting of the expression.
Examples:
A. expression “1 + 2 – 3 * 4”
(((1 + 2) – 3) * 4) = 0
((1 + 2) – (3 * 4)) = -9
((1 + (2 – 3)) * 4) = 0
(1 + ((2 – 3) * 4)) = -3
(1 + (2 – (3 * 4))) = -9
There were five possible, but two were the same, so your function should print:
3 unique { 0, -9, -3 }
Click here for a other articles in the blog section.