Search a sorted list with interspersed empty slots

© Parineeth M R

Question 42. Consider the sorted array of strings A= {“”, “apple”, “”, “”, “ball”, “cat”, “”, “dog”, “”, “”, “”, “egg”, “”}. The array has empty strings interspersed in it. How will you efficiently search for strings in such an array?


We can use binary search to search the array of sorted strings. However since the array has empty strings in it, suppose we hit an empty string during binary search, we won’t know how to continue the search. To solve this problem we slightly modify the binary search and use the following strategy:

1. Binary search will occur between indexes low and high. If A[high] is an empty string, then we go on decrementing high till A[high] is a non-empty string. (Suppose we don’t find a non-empty string and we reach A[low], then all elements between low and high are empty strings. So we simply return indicating the search string was not found.)

2. We then find the mid element between low and high. If A[mid] is a non-empty string, then we proceed with the usual binary search. If A[mid] however is an empty string, then we go on incrementing mid till A[mid] is a non-empty string. Since A[high] already has a non-empty string, we will surely find a non-empty string when we keep incrementing mid.

C/C++


/*
strings: sorted array of strings in which some of the strings can be empty ("")
num_strings: number of strings present (including empty strings)
x: string to be searched
Returns: index of x in the array strings if found, -1 otherwise
*/
int search(char *strings[], int num_strings, char *x)
{
	int mid, result;
	int low = 0;
	int high = num_strings - 1;
	
	while (low <= high) {
		/*If we hit an empty string at position high, then keep decreasing
		high till we get a non-empty string*/
		while (low <= high && strcmp(strings[high], "") == 0) {
			--high;
		}

		/*If we have only empty strings between low and high, then return
		not found*/
		if (low > high)
			return -1;
		mid = (low + high) / 2;

		/*If we get an empty element at mid, then keep incrementing mid. 
		We are guaranteed to find a non-empty string since strings[high]
		is non-empty*/
		while (strcmp(strings[mid], "") == 0)
			mid = mid + 1; 

		/*Compare the mid element with the element being searched*/
		result = strcmp(strings[mid], x);

		if (result == 0) {
			return mid;
		} else if (result < 0) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return -1;
}



Java


/*
strings: sorted array of strings in which some of the strings can be empty ("")
x: string to be searched
Returns: index of x in the array strings if found, -1 otherwise
*/
public static int search(String[] strings, String x) {
	int low = 0;
	int high = strings.length - 1;

	while (low <= high) {
		/*If we hit an empty string at position high, then keep 
		decreasing high till we get a non-empty string*/
		while (low <= high && strings[high] == "") 
			--high;

		/*If we have only empty strings between low and high, then return
		 not found*/
		if (low > high)
			return -1;

		int mid = (low + high) / 2;
 
		/*If we get an empty element at mid, then keep incrementing mid. 
		We are guaranteed to find a non-empty string since strings[high]
		is non-empty*/ 
		while (strings[mid] == "")
			mid = mid + 1; 

		/*Compare the mid element with the element being searched*/
		int result = strings[mid].compareTo(x);

		if (result == 0) {
			return mid;
		} else if (result < 0) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return -1;
}



Python


#strings: sorted list of strings in which some of the strings can be empty ('')
#x: string to be searched
#Returns: index of x in the strings list if found, -1 otherwise
def search(strings, x) :
	low = 0
	high = len(strings) - 1

	while (low <= high) :
		#If we hit an empty string at position high, then keep decreasing
		#high until we get a non-empty string
		while (low <= high and strings[high] == '') :
			high = high - 1
		
		#If we have only empty strings between low and high, then return
		#not found
		if (low > high):
			return -1

		mid = (low + high) // 2

		#If we get an empty element at mid, then keep incrementing mid.
		#We are guaranteed to find a non-empty string since strings[high]
		#is non-empty
		while (strings[mid] == ''):
			mid += 1

		#Compare the mid element with the element being searched
		if (strings[mid] == x) :
			return mid
		elif (strings[mid] < x) :
			low = mid + 1
		else :
			high = mid - 1
		
	return -1



I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Find the first element larger than k in a sorted array

© Parineeth M R

Question 41. Find the first element larger than k in a sorted array


Consider the sorted array A = {10, 20, 20, 30, 40, 50}. The first element larger than 25 is 30. In normal binary search, we search for a particular element and stop when we find the element. When we are trying to find the first element larger than k, k may not even exist in the array. So we instead use a modified form of binary search where we keep track of the first element larger than k as we search the array. The time complexity is O(logn). The code is given below

C/C++


/*
a: sorted array containing elements in non-decreasing order
length: number of elements in the array
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
		MAX_INT otherwise
*/
int find_next_higher(int a[], int length, int k)
{
	int low, high, mid, result;

	low = 0; 
	high = length - 1;

	result = MAX_INT;
	while (low <= high) {
		mid = (low + high) / 2;

		if (a[mid] > k) {
			result = a[mid]; /*update the result and continue*/
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	} 

	return result;
}



Java


/*
a: sorted array containing elements in non-decreasing order
k: we are searching for the number immediately above k
Returns: the number immediately greater than k in the array if it exists,
	MAX_INT otherwise
*/
public static int findNextHigher(int[] a, int k) {
	int low = 0; 
	int high = a.length - 1;

	int result = MAX_INT;
	while (low <= high) {
		int mid = (low + high) / 2;

		if (a[mid] > k) {
			result = a[mid]; /*update the result and continue*/
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	} 

	return result;
}



Python


#a: sorted list containing elements in non-decreasing order
#k: we are searching for the number immediately above k
#Returns: the number immediately greater than k in the list if it exists,
#		MAX_INT otherwise
def find_next_higher(a, k) :
	low = 0 
	high = len(a) - 1

	result = MAX_INT
	while (low <= high) :
		mid = (low + high) // 2

		if (a[mid] > k) :
			result = a[mid] #update the result and continue
			high = mid - 1
		else :
			low = mid + 1

	return result 



I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Find the first occurrence of an element in a sorted array

© Parineeth M R

Question 40. Find the first occurrence of a number in a sorted array


Consider the sorted array A = {10, 10, 20, 20, 30, 30, 30}. If we are asked to return the first occurrence of 30, then we return the index 4. If we are asked to return the first occurrence of a number not present in the array such as 15, then we return -1.

We can do this using modified binary search in O(logn). In normal binary search, we stop as soon as we find the element being searched. In the modified binary search, we continue the binary search if the found element is not the first occurrence of the element in the array. The code is given below

C/C++


/*
a: array being searched
n: number of elements in array
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
int find_first(int a[], int n, int x)
{
	int start, end, mid;

	start = 0;
	end = n - 1;

	while (start <= end) {
		mid = (start + end) / 2;

		if (a[mid] == x) {
			if (mid == 0 || a[mid - 1] != x)
			     return mid;
			else
			     end = mid - 1;

		} else if (a[mid] > x) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return -1;
}



Java


/*
a: array being searched
x: element being searched
Return value: first position of x in a, if x is absent -1 is returned
*/
public static int findFirst(int[] a, int x) {
	int n = a.length;
	int start = 0;
	int end = n - 1;

	while (start <= end) {
		int mid = (start + end) / 2;

		if (a[mid] == x) {
			if (mid == 0 || a[mid - 1] != x)
			     return mid;
			else
			     end = mid - 1;

		} else if (a[mid] > x) {
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return -1;
}



Python


#a: list being searched
#x: element being searched
#Return value: first position of x in a, if x is absent -1 is returned
def find_first(a, x) :
	n = len(a)
	start = 0
	end = n - 1

	while (start <= end) :
		mid = (start + end) // 2

		if (a[mid] == x) :
			if (mid == 0 or a[mid - 1] != x):
			     return mid
			else:
			     end = mid - 1

		elif (a[mid] > x) :
			end = mid - 1
		else :
			start = mid + 1
		
	return -1



I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Find max and min using least operations

© Parineeth M R

Question 39. Find the maximum and minimum elements in an array using the least number of comparisons


In the simple approach, we will compare each element of the array with the maximum value and minimum value obtained so far. So for every element, we need 2 comparisons.

In the efficient approach, we pick all pairs of consecutive numbers in the array and first compare the numbers within each pair. Then we compare the highest in the pair with the maximum value and the lowest in the pair with the minimum value. So we need 3 comparisons for 2 elements instead of 4 comparisons needed by the simple approach.

Since we will be picking pairs of consecutive numbers, if we have odd number of elements in the array, the last element will be left unpaired. To avoid this problem, if we have odd elements, we will initialize the max value and the min value to the first element in the array and then go on picking pairs of numbers from the second element onwards.

C/C++


/*a:input array 
length: number of elements in array a
min_value: the minimum value is returned here
max_value: the maximum value is returned here*/
void find_min_max(int a[], int length, int *min_value, int *max_value) {
	int i = 0;
	*max_value = MIN_INT;
	*min_value = MAX_INT;
	if (length % 2 == 1) {
		/*If there are odd number of elements, then initialize 
		max_value and min_value with a[0]*/
		*max_value = *min_value = a[0];
		i = 1;
	}

	for (; i < length; i += 2) {
		if (a[i] > a[i+1]) {
			if (a[i] > *max_value) 
				*max_value = a[i];
			if (a[i+1] < *min_value)
				*min_value = a[i+1];
		} else {
			if (a[i] < *min_value)
				*min_value = a[i];
			if (a[i+1] > *max_value)
				*max_value = a[i+1];
		}
	}
}



Java


/*a:input array 
result: the minimum value is returned in result[0] and 
	the maximum value is returned in result[1]*/
public static void findMinMax(int[] a, int[] result) {
	int length = a.length;
	int maxValue = MIN_INT;
	int minValue = MAX_INT;
	int i = 0;
	if (length % 2 == 1) {
		/*If there are odd number of elements, then initialize 
		maxValue and minValue with a[0]*/
		maxValue = minValue = a[0];
		i = 1;
	}

	for (; i < length; i += 2) {
		if (a[i] > a[i+1]) {
			if (a[i] > maxValue) 
				maxValue = a[i];
			if (a[i+1] < minValue)
				minValue = a[i+1];
		} else {
			if (a[i] < minValue)
				minValue = a[i];
			if (a[i+1] > maxValue)
				maxValue = a[i+1];
		}
	}
	result[0] = minValue;
	result[1] = maxValue;
}




Python


#a: input list 
#Returns: the minimum value and maximum value in list are returned
def find_min_max(a) :
	length = len(a)
	max_value = MIN_INT
	min_value = MAX_INT

	i = 0
	if (length % 2 == 1) :
		#If there are odd number of elements, then initialize 
		#max_value and min_value with a[0]
		max_value = min_value = a[0]
		i = 1
	
	while ( i < length ) :
		if (a[i] > a[i+1]) :
			if (a[i] > max_value) :
				max_value = a[i]
			if (a[i+1] < min_value):
				min_value = a[i+1]
		else :
			if (a[i] < min_value):
				min_value = a[i]
			if (a[i+1] > max_value):
				max_value = a[i+1]
		
		i += 2

	return min_value, max_value




I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Find the smallest and second smallest

© Parineeth M R

Question 38. Find the smallest and second smallest numbers in an array


We can find the smallest and second smallest numbers in a single scan of the array. We will maintain another array called min_values for storing the 2 smallest numbers. min_values[0] will store the smallest value and min_values[1] will store the second smallest value. min_values[0] and min_values[1] are initialized to MAX_INT. As we traverse the main array, we do the following

– If the current element is smaller than min_values[0], then we move min_values[0] to min_values[1] and store the current element in min_values[0]

– If the current element is larger than min_values[0] but smaller than min_values[1], then we store the current element in min_values[1]

The code is given below:

C/C++


/*
a:input array 
length: number of elements in array a
min_value: the two smallest values will be returned here
*/
void find_two_smallest(int a[], int length, int min_value[])
{
	int i;

	min_value[0] = min_value[1] = MAX_INT;

	for (i = 0; i < length; ++i) {
		if (a[i] < min_value[0]) {
			min_value[1] = min_value[0];
			min_value[0] = a[i];
		} else if (a[i] < min_value[1]) {
			min_value[1] = a[i];
		}
	}
}



Java


/*
a:input array 
minValue: the two smallest values will be returned here
*/
public static void findTwoSmallest(int[] a, int[] minValue) {
	minValue[0] = minValue[1] = MAX_INT;

	for (int curVal : a) {
		if (curVal < minValue[0]) {
			minValue[1] = minValue[0];
			minValue[0] = curVal;
		} else if (curVal < minValue[1]) {
			minValue[1] = curVal;
		}
	}
}



Python


#a:input list 
#Return value: the two smallest values will be returned 
def find_two_smallest(a) :
	length = len(a)

	min_value = [MAX_INT, MAX_INT]

	for  cur_val in a:
		if (cur_val < min_value[0]) :
			min_value[1] = min_value[0]
			min_value[0] = cur_val 
		elif (cur_val  < min_value[1]) :
			min_value[1] = cur_val 
		
	
	return min_value[0], min_value[1]



I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Find maximum of two integers without if-else and comparison

© Parineeth M R

Question 37. Find the maximum of 2 integers without using if-else or any other comparison operator


We can find the maximum of 2 integers without making use of if else or any comparison operator using the function below

C/C++


/*Returns the maximum of x and y without using if-else and comparison*/
int find_max(int x, int y) {
	int difference = x - y;
	int sign_bit = 	(difference >> 31) & 0x1;
	/*
	Sign bit can be 0 or 1
	If sign bit is 0, max = x - (0 * difference) = x
	If sign bit is 1, max = x - (1 * (x-y)) = x - x + y = y 
	*/
	int max = x  - (sign_bit * difference);
	return max;
}



Java


/*Returns the maximum of x and y without using if-else and comparison*/
public static int findMax(int x, int y) {
	int difference = x - y;
	int signBit = 	(difference >> 31) & 0x1;
	/*
	Sign bit can be 0 or 1
	If sign bit is 0, max = x - (0 * difference) = x
	If sign bit is 1, max = x - (1 * (x-y)) = x - x + y = y 
	*/
	int max = x  - (signBit * difference);
	return max;
}



Python


#Returns the maximum of x and y without using if-else and comparison
# Maximum value of x and y should not exceed 31 bits
def find_max(x, y) :
	difference = x - y
	sign_bit = (difference >> 31) & 0x1
	
	#Sign bit can be 0 or 1
	#If sign bit is 0, max = x - (0 * difference) = x
	#If sign bit is 1, max = x - (1 * (x-y)) = x - x + y = y 
	max_value = x  - (sign_bit * difference)
	return max_value



First we compute the difference between x and y. Next we find the sign bit of the difference. In the 2’s complement notation, the most significant bit indicates the sign of the number. If the sign bit is 0, then the number is positive and if the bit is 1, then the number is negative.

If x >= y, then the difference x – y is positive and so the sign bit of the difference is 0.

If x < y, then the difference x – y is negative and sign bit of the difference is 1.

Then we compute max = x – (sign_bit * difference).

If x >= y, then sign_bit = 0 and max = x – (0 * difference) = x. So we return x as the maximum value

If x < y, then sign_bit = 1 and max = x - (1 * difference) = x - difference = x - (x - y) = y. So we return y as the maximum value

I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Circular left shift and circular right shift on integer

© Parineeth M R

Question 36. Implement circular shift left and circular shift right on an unsigned integer


Let n be the number of bits to shift. Let m be the total number of bits present in the integer. If we circular shift an integer m times then we get back the original integer. So the actual number of shifts we need to perform is n % m.

The functions for circular shift left (also called left shift rotate) and circular shift right (right shift rotate) are given below

C/C++


/*
input: input value which has to be circularly shifted left
n: number of positions to shift
Return value: result after circularly left shifting input
*/
unsigned int circular_left_shift(unsigned int input, int n)
{
	unsigned int size = sizeof(unsigned int) * 8;
	unsigned int result;
	
	n = n % size;
	result = input << n | input >> (size - n);
	return result;
}


/*
input: input value which has to be circularly shifted right
n: number of positions to shift
Return value: result after circularly right shifting input
*/
unsigned int circular_right_shift(unsigned int input, int n)
{
	unsigned int size = sizeof(int) * 8;
	unsigned int result;

	n = n % size;
	result = input >> n | input << (size - n);
	return result;
}



Java


/*
input: input value which has to be circularly shifted left
n: number of positions to shift
Return value: result after circularly left shifting input
*/
public static int circularLeftShift(int input, int n) {
	int numBitsInInt = 32;
	n = n % numBitsInInt;
	int result = input << n | input >>> (numBitsInInt - n);
	return result;
}


/*
input: input value which has to be circularly shifted right
n: number of positions to shift
Return value: result after circularly right shifting input
*/
public static int circularRightShift(int input, int n) {
	int numBitsInInt = 32;
	n = n % numBitsInInt;
	int result = input >>> n | input << (numBitsInInt - n);
	return result;
}




Python


#value: input value which has to be circularly shifted left
#n: number of positions to shift
#Return value: result after circularly left shifting input value
def circular_left_shift(value, n) :
	num_bits_in_int = 32
	n = n % num_bits_in_int
	mask = (1 << num_bits_in_int) - 1
	result = (value << n) | (value >> (num_bits_in_int - n))
	result = result & mask
	return result


#value: input value which has to be circularly shifted right
#n: number of positions to shift
#Return value: result after circularly right shifting input
def circular_right_shift(value, n) :
	num_bits_in_int = 32
	n = n % num_bits_in_int
	mask = (1 << num_bits_in_int) - 1
	result = (value >> n) | (value << (num_bits_in_int - n))
	result = result & mask
	return result



I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Copy bits from one integer to another

© Parineeth M R

Question 35. Copy the bits between the specified start bit and end bit positions of one integer into another integer. For instance if source integer is 0xBBB and destination integer is 0xAEC and we copy the bits from 4 to 7 from source to destination, the result is 0xABC


Let the source integer be 0xBBB, destination integer be 0xAEC and we have to copy bits from position 4 to 7. The strategy we use is as follows:

1. Construct a mask (let’s call it ones mask) in which all the bits are initially set to 1. If we need to copy n bits and the total number of bits in the integer is m, then right shift the ones mask by (m-n). So if we need to copy 4 bits between bit 4 and bit 7, and total number of bits in integer is 32, we perform ones_mask >> (32 – 4). So ones_mask will have a value 0xF.

2. Left shift the ones mask to the starting position from where we have to copy the bits. The ones mask will now have 1’s from the start bit position to the end bit position. In this example, starting bit position is 4, so we perform (ones_mask << 4) = (0xF << 4) = 0xF0.

3. Construct a zeroes mask which is the complement of the ones mask. The zeroes mask will have 0’s from the start bit to the end bit. So if ones mask is 0xF0, then zeroes mask will be 0xFFFFFF0F.

4. AND the destination integer with the zeroes mask to clear out the bits in the destination from start bit to end bit. So if destination is 0xAEC, then 0xAEC & 0xFFFFFF0F will give 0xA0C

5. AND the source integer with the ones mask so that only the bits from start and end bit positions remain and the rest of the bits are cleared. If the source integer is 0xBBB, then 0xBBB & 0xF0 will give 0xB0

6. OR the source and destination. So 0xA0C | 0xB0 will give 0xABC

C/C++


/*
dest: destination integer into which the bits have to be copied
src: source integer from which the bits have to be copied 
end_pos: Most Significant bit position upto where the bits should be copied
start_pos: Least Significant bit position from where the bits should be copied
	end_pos should be >= start_pos
Return value: result integer after copying bits from source to destination
*/
unsigned int copy_bits(unsigned int dest, unsigned int src, 
			unsigned int end_pos, unsigned int start_pos)
{
	unsigned int num_bits_to_copy = end_pos - start_pos + 1;
	unsigned int num_bits_in_int = sizeof(unsigned int) * 8;
	unsigned int zeroes_mask;
	unsigned int ones_mask = ~((unsigned int) 0); /*all ones*/

	/*Use the bit-wise right shift operator to remove the excess 1's 
	in the mask*/
	ones_mask = ones_mask >> (num_bits_in_int - num_bits_to_copy);

	/*Left shift the 1's to the starting position. ones_mask will contain 1's
	from start_pos to end_pos*/
	ones_mask = ones_mask << start_pos;

	/*zeroes_mask will contain 0's from start_pos to end_pos*/
	zeroes_mask = ~ones_mask;

	/*clear the bits in destination from start_pos to end_pos*/
	dest = dest & zeroes_mask;

	/*retain the bits in source from start_pos to end_pos and clear the 
	remaining bits*/
	src = src & ones_mask;
	
	/*copy the source bits into the destination*/
	dest = dest | src;
	
	return dest;
}




Java


/*
dest: destination integer into which the bits have to be copied
src: source integer from which the bits have to be copied 
endPos: Most Significant bit position upto where the bits should be copied
startPos: Least Significant bit position from where the bits should be copied
	endPos should be >= startPos
Return value: result integer after copying bits from source to destination
*/
public static int copyBits(int dest, int src,  int endPos,  int startPos) {
	 int numBitsToCopy = endPos - startPos + 1;
	 int numBitsInInt = 32;
	 int onesMask = ~(0); /*Initialize the mask to all 1's*/

	/*Use the bit-wise right shift operator to remove the excess 1's 
	in the mask*/
	onesMask = onesMask >>> (numBitsInInt - numBitsToCopy);

	/*Left shift the 1's to the starting position. onesMask will contain 
	1's from startPos to endPos*/
	onesMask = onesMask << startPos;

	/*zeroesMask will contain 0's from startPos to endPos*/
	int zeroesMask = ~onesMask;

	/*clear the bits in destination from startPos to endPos*/
	dest = dest & zeroesMask;

	/*retain the bits in source from startPos to endPos and clear 
	the remaining bits*/
	src = src & onesMask;

	/*copy the source bits into the destination*/
	dest = dest | src;

	return dest;
}



Python


#dest: destination integer into which the bits have to be copied
#src: source integer from which the bits have to be copied 
#end_pos: Most Significant bit position upto where the bits should be copied
#start_pos: Least Significant bit position from where the bits should be copied
#	end_pos should be >= start_pos
#Return value: result integer after copying bits from source to destination
def copy_bits(dest,  src,  end_pos,  start_pos) :
	num_bits_to_copy = end_pos - start_pos + 1
	num_bits_in_int = 32
	ones_mask = (1 << 32) - 1

	#Use the bit-wise right shift operator to remove the excess 1's 
	#in the mask
	ones_mask = ones_mask >> (num_bits_in_int - num_bits_to_copy)

	#Left shift the 1's to the starting position. ones_mask will contain 1's
	#from start_pos to end_pos
	ones_mask = ones_mask << start_pos

	#zeroes_mask will contain 0's from start_pos to end_pos
	zeroes_mask = ~ones_mask

	#clear the bits in destination from start_pos to end_pos
	dest = dest & zeroes_mask

	#retain the bits in source from start_pos to end_pos and 
	#clear the remaining bits
	src = src & ones_mask

	#copy the source bits into the destination
	dest = dest | src

	return dest



I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Compute parity bit

© Parineeth M R

Question 34. Given an integer, compute the parity bit for the integer


There are two types of parity bit schemes

1. Even parity: if the total number of 1’s is odd, then the parity bit will be 1 to make the total number of 1’s (including the parity bit) even

2. Odd parity: if the total number of 1’s is even, then the parity bit will be 1 to make the total number of 1’s (including the parity bit) odd.

We will implement an even parity scheme here. We count the number of 1’s in the integer using the scheme described in problem 29

C/C++


/*
x: input integer
Return value: parity bit, 1 if there are odd number of 1's, 0 otherwise
*/
unsigned int compute_parity(unsigned int x) 
{
	/*for each bit set to 1 in x, toggle the parity bit*/
	unsigned int parity = 0;
	while (x != 0) {
		parity = parity ^ 1;
		x = x & (x - 1);
	}

	return parity;
}



Java


/*
x: input integer
Return value: parity bit, 1 if there are odd number of 1's, 0 otherwise
*/
public static int computeParity( int x) {
	/*for each bit set to 1 in x, toggle the parity bit*/
	int parity = 0;
	while (x != 0) {
		parity = parity ^ 1;
		x = x & (x - 1);
	}

	return parity;
}



Python


#x: input integer
#Return value: parity bit, 1 if there are odd number of 1's, 0 otherwise
def compute_parity(x):
	#for each bit set to 1 in x, toggle the parity bit
	parity = 0
	while (x):
		parity = parity ^ 1
		x = x & (x - 1)

	return parity



I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.

Swap bits in an integer

© Parineeth M R

Question 33. Given an integer, swap the bit at position 1 with the bit at position 2


We first extract the bits at position 1 and position 2. We then have to swap the two bits only if the two bits are different. The code for swapping the bits is given below

C/C++


/*
x: integer in which the bits should be swapped
pos1: position of first bit to be swapped
pos2: position of the second bit to be swapped
*/
unsigned int swap_bits(unsigned int x, int pos1, int pos2) 
{
	/*get the bits at position pos1 and pos2*/
	int bit1 = (x >> pos1) & 1;
	int bit2 = (x >> pos2) & 1;

	/*swap the bits if the bits are different*/
	if (bit1 != bit2) {
		x = write_bit(x, bit1, pos2);
		x = write_bit(x, bit2, pos1);
	}

	return x;
}

/*writes the bit_value (0/1) into position pos in x and returns the result*/
unsigned int write_bit(unsigned int x, int bit_value, int pos) 
{
	unsigned int mask = 1 << pos;
	if (bit_value)
		x = x | mask;
	else
		x = x & ~mask;

	return x;
}




Java


/*
x: integer in which the bits should be swapped
pos1: position of first bit to be swapped
pos2: position of the second bit to be swapped
*/
public static int swapBits(int x, int pos1, int pos2) {
	/*get the bits at position pos1 and pos2*/
	int bit1 = (x >> pos1) & 1;
	int bit2 = (x >> pos2) & 1;

	/*swap the bits*/
	if (bit1 != bit2) {
		x = writeBit(x, bit1, pos2);
		x = writeBit(x, bit2, pos1);
	}

	return x;
}

 
/*writes the bitValue (0/1) into position pos in x and returns the result*/
public static int writeBit( int x, int bitValue, int pos)  {
	int mask = 1 << pos;
	if (bitValue == 1)
		x = x | mask;
	else
		x = x & ~mask;

	return x;
}



Python


#writes the bit_value (0/1) into position pos in x and returns the result
def write_bit(x, bit_value, pos):
	mask = 1 << pos
	if (bit_value == 1):
		x = x | mask
	else:
		x = x & ~mask

	return x

#x: integer in which the bits should be swapped
#pos1: position of first bit to be swapped
#pos2: position of the second bit to be swapped
def swap_bits(x, pos1, pos2):
	#get the bits at position pos1 and pos2
	bit1 = (x >> pos1) & 1
	bit2 = (x >> pos2) & 1

	#swap the bits
	if (bit1 != bit2) :
		x = write_bit(x, bit1, pos2)
		x = write_bit(x, bit2, pos1)

	return x




I hope you liked the article. I have written “The Big Book of Coding Interviews” in C/C++, Java and Python. If you are a US resident and want a free copy of the book, please send an email to

Mention the programming language of your choice in the e-mail. I will mail the Amazon Giveaway link to you. If you like the book please give your review comments on Amazon. If you didn’t like the book, please mail me what you didn’t like and I will be glad to make the required changes.