Programming Problems: Advanced Algorithms

Question 1

Setting the least significant bit to zero

Answer 1

unsigned clear_last_bit(unsigned x) {

return x & (x - 1);

}

Question 2

Lowest bit set - retain only the lowest set bit

(10100 -> 00100)

Answer 2

unsigned lowest_set_bit(unsigned x) {

return x & ~(x-1);

}

Question 3

Counting the number of bits in a number

Answer 3

While the number is not zero clear the least significant bit.

Clearing least significant bit: x & (x-1)

Question 4

Folding over

(Setting all bits after the MSB to 1)

Answer 4

x |= (x >> 1);

x |= (x >> 2);

x |= (x >> 4);

x |= (x >> 8);

x |= (x >> 16);

Question 5

Isolate the highest bit

Answer 5

x = foldOver(x); // makes all bits 1 after the highest bit

result = x & ~(x>>1)

Question 6

Rounded log2 of an integer

Answer 6

x = x-1 // x must be unsigned int

x = foldOver(x)

x=x+1

result = 0;

while (x!=0) {

x>>=1; result++;

}

Question 7

Next power of 2 that is larger than the input

Answer 7

result = foldOver(x) + 1

Question 8

Reverse the bits in a 32bit integer

(using O(logn) time complexity)

Answer 8

x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);

x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);

x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);

x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);

x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);

return x;

Question 9

Int multiplication using bitwise operators

Answer 9

int multiply(int x, int y) {

int product = 0;

while (y) {

product += x << log_x(lowest_set_bit(y));

y = clear_last_bit(y);

}

return product;

Question 10

General fibonacci expression

Answer 10

F(0)=0; F(1)=1;

F(n)=F(n-1)+F(n-2);

Question 11

Recursive fibonacci algorithm

Answer 11

if (n==0) return 0;

if (n==1) return 1;

return fib(n-1)+fib(n-2);

Question 12

What is the runtime of the reecursive fibonacci algorithm?

Answer 12

Exponential function of the input.

Question 13

Iterative fibonacci algorithm

Answer 13

if (n==0) return 0; if (n==1) return 1;

int cur = 0; int trailing = 1;

for (int i=0;i<n></n>

<p> int temp = cur;</p>

<p> cur = cur + trailing;</p>

<p> trailing = temp;}</p>

<p>return cur;</p>

</n>

Question 14

Fibonacci with tail recursion

Answer 14

int fiboTail(int n, int fib1, int fib2) {

if (1==n) return fib1;

return fibTail(n-1,fib2,fib1+fib2);

}

int fibo(int n) {

if (0==n) return 0;

return fiboTail(n,0,1);

}

Question 15

Closed formula for calculating the nth fibonacci element

Answer 15

Question 16

Optimized naive prime testing

Answer 16

1. Check if the number is 0,1 or divisible by 2 –> return immediately
2. Iterate from 3 to sqrt(n) by 2 and try to divide n

Question 17

Eratosthene prime algorithm

Answer 17

1. Make a boolean array of size sqrt(n)
2. i = 2 to sqrt(n)
   
   1. If i is prime
      
      1. if i divides n –> return true
      2. j = 2*i to sqrt(n) by i: mark j not prime

Question 18

Add arithmetic operators to make the following expression true: 3 1 3 6 = 8. You can use any parentheses you’d like.

Answer 18

((3 + 1)/(3/6)=8

Question 19

Write a function that swaps two numbers without using a temporary variable.

Answer 19

a = a^b;

b=a^b;

a=a^b;

Question 20

Find the max of a and b without using comparision operators

Answer 20

int c = a - b;

int k = (c >> 31) & 0x1;

int max = a - k * c;

return max;

Question 21

How do you know from the binary representation of a number that it is negative?

Answer 21

The MSB is set to 1 (if it is an int then the 32th bit is 0)

Question 22

How do you multiply number by -1 using bitwise operators?

(in 2’s complement representation)

Answer 22

1. Use binary NOT operator first (invert the bits)
2. Add 1 to the result

For example: 5 = 0000 0101 –> -5 = 1111 1010 + 1 = 1111 1011

Question 23

Algorithm to calculate the approximate square of an integer.

Answer 23

Use a binary search algorithm.

Check if the square of the middle of the current range is larger, equal or less than the original number. Alter the range accordingly or stop. Stop also when the upper range is not larger than the lower range.

SQRT for decimals is similar, but alter the stop condition, so that stop, when the range is smaller than a given delta.

Question 24

How would you look for the nearest coordinate in a plane given a list of points?

Answer 24

Using a k-d tree with 2 dimensions.

Question 25

What are the time complexities of a 2 dimensional k-d tree regarding the following operations:

building, insert a point, remove a point, range search

Answer 25

1. building: O(n*logn)
2. insert O(logn)
3. remove O(logn)
4. range query O(n^(1-1/k)+m) where m is the number of points returned