Reverse the bits of a 32-bit integer

For example, given an integer i = 0x00000001,

i	0000	0000	0000	0000	0000	0000	0000	0001
reversal(i)	1000	0000	0000	0000	0000	0000	0000	0000

the reversed result is: 80000000.

One approach is to construct a byte wise look up table. The table is a <byte, reversal byte> container which has reversal outcome of all possible byte values indexed by the byte value. Given a particular byte value, the table provides its corresponding reversal order. For a 32-bit integer, four look ups are needed. Start the look up from the zeroth byte of the input and place the outcome as the third byte in the output. This approach can be extended to a 64-bit integer as well with a 16-bit look up table implementation. This is an efficient approach but requires additional memory to store the look up table.

Another approach is to perform an in place reversal by following the following steps. For example, let the input is 12345670.

1. Consider adjacent bits. Swap them.

i	0001	0010	0011	0100	0101	0110	0111	0000
reversal(i)	0010	0001	0011	1000	1010	1001	1011	0000

2. Consider two bits at a time in the output from step 1. Swap them.

i	0010	0001	0011	1000	1010	1001	1011	0000
reversal(i)	1000	0100	1100	0010	1010	0110	1110	0000

3. Consider four bits at a time in the output from step 2. Swap them.

i	1000	0100	1100	0010	1010	0110	1110	0000
reversal(i)	0100	1000	0010	1100	0110	1010	0000	1110

4. Consider eight bits at a time in the output from step 3. Swap them.

i	0100	1000	0010	1100	0110	1010	0000	1110
reversal(i)	0010	1100	0100	1000	0000	1110	0110	1010

5. Consider 16 bits at a time in the output from step 4. Swap them.

i	0010	1100	0100	1000	0000	1110	0110	1010
reversal(i)	0000	1110	0110	1010	0010	1100	0100	1000

The output of step 5 is the reversal outcome of the 32-bit input. The answer (in hex) in our example is 0e6a2c48.

Here is the C++ code:

void BitReversal(int inp_int) {

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

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

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

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

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

  printf("%x\n",inp_int);

}

An additional 32-bit shift step is required for a 64-bit integer reversal.

Finding distinct elements in an array

For example, consider an array of ten elements {4, 7, 3, 6, 4, 9, 6, 2, 9, 0}. The distinct elements are {4, 7, 3, 6, 9, 2, 0}. The element ordering in the output need not be maintained.

A simple approach is to sort the input array and find the distinct elements by comparing the adjacent elements. The time complexity is O(nlogn).

An efficient approach is to use a hash set/unordered set. A hash set is a data structure which holds distinct elements. It is an unordered collection of elements which provides insertion and look up operations in O(1) time. It uses a hashing algorithm to distribute the elements into buckets.

Read each of the input elements into a hash set. Once the entire array is read, just iterate over the hash set to get the distinct elements. The time complexity of this approach is O(n) as we are going over all the array elements exactly once.

Here is the C++ code:

int input_array[ARRAYSIZE] = {4, 7, 3, 6, 4, 9, 6, 2, 9, 0};

void RemoveDuplicates(const int* input_array) {

  unordered_set<int> input_distinct;

  for(int i = 0; i < ARRAYSIZE; ++i) {

    input_distinct.insert(input_array[i]);

  }

  unordered_set<int>::const_iterator iter;

  for(iter = input_distinct.begin(); iter != input_distinct.end(); ++iter) {

    cout << *iter << " ";

  }

}

Invoke the function as: RemoveDuplicates(input_array);

Nth element from the end of a linked list

Let us consider a linked list with five nodes:

For n = 2, the second element from the tail, which is 98, has to be returned.

Given a linked list, whose size is unknown, the element which is at the n^th position from the end of the linked list has to be found.

A straight-forward approach is to traverse the linked list once to calculate its size k. Perform a second traversal of (k-n+1) steps to point to the n^th node from the end of the list. This method requires two traversals.

A better approach is to perform only one traversal. Use two pointers – say, prev and cur. To initialize the pointers, position the prev pointer to the head node and advance the cur pointer so that it points to the n^th node from the head.

From this point onwards, advance both the pointers by one step at a time until the cur reaches the end of the list. At this point, the prev pointer will be pointing to the n^th node from the end of the list. The complexity is still O(n) but requires only one traversal.

Consider the following node structure:

struct Node {

  int data;

  Node* next;

};

Here is the C++ code:

void NthToLastElement(int n, Node* head) {

  Node* prev = head;

  Node* cur = head;

  int i = 0;

  while(i < n && cur != NULL) { //advance the cur pointer by n steps

    cur = cur->next;

    ++i;

  }

  if(cur == NULL) { //n > k

    cout << "Not enough elements";

    exit(0);

  }

  while(cur != NULL) {

    cur = cur->next;

    prev = prev->next;

  }

  cout << "Nth element from the end: " << prev->data << endl;

}

Misread OTP

OTP (One Time Password) is a token used for a multi-factor authentication. A time synchronized OTP is associated with a hardware device known as a secure token (a sample shown below). A random number is generated based on the password generation algorithm and the clock. The user enters this generated OTP to authenticate himself.

The generated OTP can vary in length based on the implementation. Let us consider a six digit OTP generator. There are some OTP which appear like a valid number even when read upside down, but the authentication fails as it is not the same as the generated OTP. For example, an OTP 126850 can be misread as 058921. Given a six digit OTP scenario, what percentage of the passwords can be misread?

There are six digits in an OTP and ten possible values for each of the digits. The total number of six digit passwords is 10^6.

The numbers which make a valid number even when read upside down are 0, 1, 2, 5, 6, 8, 9, which is seven possible values. Even if one of the digits is in the remaining set of 3, 4, or 7, the six digit OTP cannot be misread as they do not make a valid number. Hence, the total number of OTP possible which can be misread is 7^6 (seven possible values for each of the six digits).

The percentage of passwords which can be misread are 7^6/10^6 = 11%. 11 in a hundred OTP can be misread. 

Coin-row problem

A set of n coins is placed in a row. The coins have positive values which need not be distinct. Find the maximum amount that can be collected given the constraint that no two adjacent coins can be picked up.

Consider n coins with values {v1, v2, v3, …, vn} and let amount(i) represent the maximum amount that can be collected after 'i' coins. As we see each coin, we will have to decide if the coin has to be picked up or not. To make this decision, two cases have to be considered –

If we pick the i'th coin, we cannot pick the (i - 1)th coin, The payoff is amount(i -2) + v(i) or

we skip the current coin and the payoff is the amount(i - 1)

This can be stated with the recursive relation

Amount(n) = max{ v(n) + Amount(n-2), Amount(n-1) } and Amount (1) = v(1)

For example, consider the coins set with values {5, 1, 2, 10, 5, 2}. Here is the step-by-step manner to fill the amount array.

Step 1: Initialize amount(0) = 0 and amount(1) = coins(1)

coins	-	5	1	2	10	5	2
amount	0	5

Step 2: amount(2) = max{ coins(2) + amount(0), amount(1) }

                             = max{ 1+0, 5} = 5

coins	-	5	1	2	10	5	2
amount	0	5	5

Step 3: amount(3) = max{ coins(3) + amount(1), amount(2) }

                             = max{ 2+5, 5} = 7

coins	-	5	1	2	10	5	2
amount	0	5	5	7

Step 4: amount(4) = max{ coins(4) + amount(2), amount(3) }

                             = max{ 10+5, 7} = 15

coins	-	5	1	2	10	5	2
amount	0	5	5	7	15

Step 5: amount(5) = max{ coins(5) + amount(3), amount(4) }

                             = max{ 5+7, 15} = 15 

coins	-	5	1	2	10	5	2
amount	0	5	5	7	15	15

Step 5: amount(6) = max{ coins(6) + amount(4), amount(5) }

                             = max{ 2+15, 15} = 17

coins	-	5	1	2	10	5	2
amount	0	5	5	7	15	15	17

The value at amount(6) represents the maximum possible amount that can be collected by considering a set of 6 coins placed in a row with the given constraint.

Here is the C++ code. A '0' is inserted as the first entry in the coins array to enhance readability.

int coins[7] = {0, 5, 1, 2, 10, 5, 2};

int amount[7];

void MaxAmount(int* amount, const int* coins) {

  amount[0] = 0;

  amount[1] = coins[1];

  for(int i = 2; i < 7; ++i) {

    amount[i] = max(coins[i] + amount[i-2], amount[i-1]);

  }

  cout << amount[6] << endl;

}

We can compute the amount array by checking all the coins exactly once. This dynamic programming approach has a time complexity of O(n) and takes an additional array space of O(n).

Search in a rotated sorted array

Given a sorted array which has been rotated such as A = {5,6,1,2,3,4}, find an element in it.

If the array is sorted, we can perform a binary search on the array. We partition the array into two halves, say left and right. We determine the half in which the element can be found and proceed by reducing the problem by half at each step. The complexity is O(log n).

If the array is rotated after sorting, we partition the array into two halves, say left and right. In this case, only one half is sorted. We determine if the search element can be found in the sorted half or the unsorted half. If the element is in the sorted half, we perform a binary search on that half. If the element is in the unsorted half, we proceed by recursively applying our algorithm to the unsorted half. We continue the process until we have found the search element or we have no more elements in the partition (in which case, the search element is not found). At each step, we are reducing the problem by half. The complexity of this approach is O(log n).

Here is the C++ code:

void FindInRotatedArray(const int* a, int key, int low, int high) {

  while(low <= high) {

  int mid = (low + high) / 2;

  if(key == a[mid]) { //found the key

    cout << "Found the key at " << mid << endl;

    return;

  }

// the left half is sorted

  if (a[low] <= a[mid]) {

    if (a[low] <= key && key < a[mid]) //key is in the sorted half

      high = mid - 1;

    else

      low = mid + 1; //key is in the unsorted half

  }

// the right half is sorted

  else {

    if (a[mid] < key && key <= a[high]) //key is in the sorted half

      low = mid + 1;

    else

      high = mid - 1; //key is in the unsorted half

  }

}

cout << "Key not found" << endl;

}

Invoke the function as: FindInRotatedArray(a,6,0,5);