Maximum profit given stock prices

Question 52. Given a set of stock prices over a period of time, find the maximum profit possible by buying and selling the stocks. For instance, if the stock prices are 100, 90, 200, 20, 70, 150, 10 and 40, then the maximum profit = 150 – 20 = 130


If we use a brute force approach, then we will compare every pair of numbers to find the maximum profit possible. This requires O(n2) operations. However using the greedy approach we can solve the problem in O(n). The main idea of the greedy approach is that it is sufficient to maintain the minimum stock price that we have encountered so far as we traverse the stock prices.

The procedure is as follows: as we traverse the stock price list, subtract the minimum stock price seen so far from the current stock price to figure out the profit. If the profit is greater than the maximum profit so far, then update the maximum profit.

The working of the algorithm on the stock prices {100, 90, 200, 20, 70, 150, 10, 40} is given below. The minimum stock price is initialized to the first element 100. The max profit is initialized to 0. We start from the second stock price onwards.

C/C++


/*
stock_price: array of stock price values
n: number of elements in the array
Return value: maximum profit possible
*/
int find_max_profit(int stock_price[], int n)
{
	int i, min_stock_price, cur_profit, max_profit;

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

	min_stock_price = stock_price[0];

	for (i = 1; i < n; ++i) {
		
		cur_profit = stock_price[i] - min_stock_price;

		if (cur_profit > max_profit)
			max_profit = cur_profit;

		if (stock_price[i] < min_stock_price)
			min_stock_price = stock_price[i];
	}

	return max_profit;
}



Java


/*
stockPrice: array of stock price values
Return value: maximum profit possible
*/
public static int findMaxProfit(int[] stockPrice) {
	int n = stockPrice.length;

	int maxProfit = 0;
	if (n <= 1)
		return maxProfit;

	int minStockPrice = stockPrice[0];

	for (int i = 1; i < n; ++i) {
	
		int curProfit = stockPrice[i] - minStockPrice;

		if (curProfit > maxProfit)
			maxProfit = curProfit;

		if (stockPrice[i] < minStockPrice)
			minStockPrice = stockPrice[i];
	}

	return maxProfit;
}



Python


#stock_price: list of stock price values
#Return value: maximum profit possible
def find_max_profit(stock_price) :
	n = len(stock_price)

	max_profit = 0
	if (n <= 1):
		return max_profit

	min_stock_price = stock_price[0]

	for  i in range(1, n):
		cur_profit = stock_price[i] - min_stock_price

		if (cur_profit > max_profit):
			max_profit = cur_profit

		if (stock_price[i] < min_stock_price):
			min_stock_price = stock_price[i]
	
	return max_profit



rand7 given rand5

Question 51. Suppose you are given a random number generator that generates numbers uniformly in the range 1 to 5. How will you generate numbers uniformly in the range 1 to 7?


Let’s us say that we are provided with the rand5() function that generates values uniformly from 1 to 5. We can generate values uniformly from 0 to 4 by subtracting 1 from the result of rand5(). Now using rand5() we can uniformly generate numbers in the range 0 to 24 using the following formula

(rand5() – 1) + 5 * (rand5() – 1)

Now to generate numbers uniformly from 1 to 7, we use rejection sampling. If the above formula generates a random number in the range 0 to 20, we accept the number. If the formula generates a number in the range 21 to 24, then we reject the number and re-try the formula till we get a number in the range 0 to 20. We then find the remainder when the number in range 0 to 20 is divided with 7. The remainder will be uniformly distributed in the range 0 to 6. We then add 1 to the remainder to get the result which will be uniformly distributed in the range 1-7.

The rejection sampling in this case can be visualized with a 5 * 5 grid, where in if we throw a dart and the dart randomly lands on a cell, the number in the grid is accepted for some cells and rejected for others.

C/C++


int rand7() {
	int result;
	while(1) {
		result = (rand5() - 1) + (5 * (rand5() - 1) );
		if (result <= 20)
			break;
	}
	result = 1 + (result % 7);
	return result;
}



Java


public static int rand7() {
	int result;
	while(true) {
		result = (rand5() - 1) + (5 * (rand5() - 1));
		if (result <= 20)
			break;
	}
	result = 1 + (result % 7);
	return result;
}



Python


def rand7() :
	while(True) :
		result = (rand5() - 1) + (5 * (rand5() - 1))
		if (result <= 20):
			break

	result = 1 + (result % 7)
	return result



Generate all prime numbers up to N

Question 50. Generate all the prime numbers that are less than or equal to N


To generate all prime numbers <= N, we make use of the sieve of Eratosthenes where we do the following 1. We generate the numbers from 2 to N and for each number X, we mark all multiples of X up to N to indicate that these multiples can’t be primes 2. If a number is not a multiple of any of the numbers preceding it, then it is a prime

We skip 0 and 1 as they are not considered to be prime. 2 is the first prime number. Then all multiples of 2 up to N are marked to indicate that these multiples can’t be primes. The next number is 3. Since 3 is not a multiple of any number before it (note that we have skipped 1 and so we ignore the fact that 3 is a multiple of 1), 3 is a prime. We then mark all multiples of 3. The next number is 4. Since 4 has been marked to be a multiple, it can’t be prime. We then mark all the multiples of 4 and this process continues till N

C/C++


/*sets the bit at position pos to 1 in the bitmap*/
void set_bit(unsigned char bitmap[], int pos)
{
	int byte_pos = pos / 8;
	int bit_pos = pos % 8;

	bitmap[byte_pos] |= 1u << bit_pos;	
}

/*Returns the bit at position pos in the bitmap*/
int get_bit(unsigned char bitmap[], int pos)
{
	int byte_pos = pos / 8;
	int bit_pos = pos % 8;

	if (bitmap[byte_pos] & (1u << bit_pos) )
		return 1;
	else 
		return 0;
} 

 
/*
n: Upto what number the primes should be generated
*/
void generate_primes(int n)
{
	int i, j;
	int total_num_bytes = 1 + (n / 8);

	/*is_multiple_bmp will be initialized with zeroes since we have not yet 
	identified the multiples*/
	unsigned char *is_multiple_bmp = (unsigned char*) calloc(1, 
								total_num_bytes);

	/*We don't consider 0 and 1 as prime. Start from 2*/
	for (i = 2; i <= n; ++i) {
		if (get_bit(is_multiple_bmp, i)) 
			continue; /*i is a multiple, so it can't be prime*/
		
		printf("%d is prime\n", i);

		/*Mark all multiples of i (2i, 3i, 4i, etc) starting from 2*i */
		for (j = 2*i; j <= n; j += i) {
			set_bit(is_multiple_bmp, j);
		} 
	}

	free(is_multiple_bmp);
}




Java


/*
n: Upto what number the primes should be generated
*/
public static void generatePrimes(int n) {
	/*isMultiple will be initialized with false since we have not yet 
	identified the multiples*/
	boolean[] isMultiple = new boolean[n+1];

	/*We don't consider 0 and 1 as prime. Start from 2*/
	for (int i = 2; i <= n; ++i) {
		if (isMultiple[i]) 
			continue; /*i is a multiple, so it can't be prime*/
	
		System.out.println(i + " is prime ");

		/*Mark all multiples of i (2i, 3i, 4i, etc) starting from 2i */
		for (int j = 2*i; j <= n; j += i) {
			isMultiple[j] = true;
		} 
	}

} 



Python


#n: Upto what number the primes should be generated
def generate_primes(n) :
	#is_multiple will be initialized with False since we have not yet 
	#identified the multiples
	is_multiple = [False] * (n+1)

	#We don't consider 0 and 1 as prime. Start from 2
	for  i in range(2, n+1):
		if (is_multiple[i]) :
			continue #i is a multiple, so it can't be prime
	
		print('{} is prime '.format(i) )

		#Mark all multiples of i (2i, 3i, 4i, etc) starting from 2i 
		for  j in range(2*i, n+1, i):
			is_multiple[j] = True 



Find the missing integer

Question 49. An unsorted array contains all integers from 1 to N except one integer. All the elements in the array are unique. Find the missing integer in O(n) time and O(1) space. For instance in the array {5, 1, 3, 2}, the missing element is 4


All integers from 1 to N are present in the array except one integer. To find the missing integer we do the following

1. Calculate the expected_sum of integers from 1 to N. We know that the sum of integers from 1 to N is given by the formula N * (N+1) / 2

2. Calculate the total_sum of the N-1 elements in the array.

3. The difference between expected_sum and the total_sum will give the missing element.

So if N = 5, and array is {5, 1, 3, 2}, then expected sum = 5 (5 + 1) / 2 = 15. The total sum of elements in the array = 5 + 1 + 3 + 2 = 11. So missing number = 15 – 11 = 4.

C/C++


/*
a: array of unique numbers. A number can have a value between 1 to n.
n: maximum value that can be stored in array. array has n-1 elements
Return value: missing element in the array
*/
int find_missing(int a[], int n)
{
	int i, total_sum, expected_sum;
	int missing_num;

	/*Since 1 element is missing, there are only n-1 elements in the array*/
	total_sum = 0;
	for (i = 0; i < n - 1; ++i) { 
		total_sum += a[i];
	}

	expected_sum = n * (n+1) / 2;

	missing_num = expected_sum - total_sum;

	return missing_num;
}



Java


/*
a: array of unique numbers. A number can have a value between 1 to n.
n: maximum value that can be stored in array. array has n-1 elements
Return value: missing element in the array
*/
public static int findMissing(int[] a, int n) {
	/*Since 1 element is missing, there are only n-1 elements in the array*/
	int totalSum = 0;
	for (int i = 0; i < n - 1; ++i) { 
		totalSum += a[i];
	}

	int expectedSum = n * (n+1) / 2;

	int missingNum = expectedSum - totalSum;

	return missingNum;
}



Python


#a: list of unique numbers. A number can have a value between 1 to n
#n: maximum value that can be stored in the list. list has n-1 elements
#Return value: missing element in the list
def find_missing(a, n) :
	#Since 1 element is missing, there are only n-1 elements in the list
	total_sum = 0
	for  i in range(0, n - 1):
		total_sum += a[i]
	
	expected_sum = n * (n+1) // 2

	missing_num = expected_sum - total_sum
	return missing_num



Swap two variables without using temporary variable

Question 48. Swap two variables without using a temporary variable


There are two ways to solve this problem. The first uses XOR and the second uses addition and subtraction. The XOR technique can be used for swapping any two variables whereas the addition and subtraction technique can only be used for numbers. The two techniques are described below

Greatest Common Divisor

Question 47. Find the Greatest Common Divisor of two numbers


The Greatest Common Divisor (GCD) of two numbers a and b is the largest number that divides a and b without leaving a remainder. For instance, the GCD of 12 and 20 is 4. It is also called Greatest Common Factor, Highest Common Factor, etc. To find the GCD we use Euclid’s algorithm which is as follows:
gcd(a, 0) = a

gcd(a, b) = gcd(b, a mod b)

So, suppose we have to calculate gcd(12, 20) then we get

gcd(12, 20) = gcd(20, 12 mod 20) = gcd(20, 12)

gcd(20, 12) = gcd(12, 20 mod 12) = gcd(12, 8)

gcd(12, 8) = gcd(8, 12 mod 8) = gcd(8, 4)

gcd(8, 4) = gcd(4, 8 mod 4) = gcd(4, 0) = 4

C/C++


/*
a, b: Two integers. a may be greater than, equal to or less than b
Return value: Greatest common divisor
*/
int gcd(int a, int b)
{
	if (b == 0)
		return a;

	/*Find the GCD of b and the remainder of a/b*/
	return gcd(b, a%b);
}



Java


/*
a, b: Two integers. a may be greater than, equal to or less than b
Return value: Greatest common divisor
*/
public static int gcd(int a, int b) {
	if (b == 0)
		return a;

	/*Find the GCD of b and the remainder of a/b*/
	return gcd(b, a % b);
}



Python


#a, b: Two integers. a may be greater than, equal to or less than b
#Return value: Greatest common divisor
def gcd(a, b) :
	if (b == 0):
		return a

	#Find the GCD of b and the remainder of a/b
	return gcd(b, a % b)



Sort a linked list containing 3 different types of elements

Question 46. Given a linked list where the nodes can have the values 0 or 1 or 2, sort it in a single pass. For instance 2->1->0->0->2->0>1 should be sorted as 0->0->0->1->1->2->2


To sort the linked list in a single pass, we make use of the fact that there are only 3 possible values for the nodes in the linked list. So as we traverse the linked list, we can remove the nodes from the original linked list and append them into 3 separate linked lists based on the value of the nodes. At the end we can merge the 3 linked lists. The procedure we can use to solve the problem is as follows

1. Maintain the head and tail pointers for linked list-0 (will contain nodes with value 0), linked list-1 (will contain nodes with value 1) and linked list-2 (will contain nodes with value 2)

2. As we traverse through the original linked list, remove each node from the original linked list and add it to linked list-0 or linked list-1 or linked list-2 based on the value of the node.

3. At the end connect the tail of linked list-0 to the head of linked list-1 and the tail of linked list-1 to the head of linked list-2

C/C++


/*
head: array of head pointers of the separated lists
tail: array of tail pointers of the separated lists
cur_node: current node being processed
i: data value of the node
*/
void add_node(struct node *head[], struct node *tail[], 
		struct node *cur_node, int i)
{
	cur_node->next = head[i];
	head[i] = cur_node;
	if (!tail[i])
		tail[i] = cur_node;

}


/*first_node: first node in list to be sorted 
num_distinct_values: number of distinct values in the nodes
Return value: head of the sorted list
*/
struct node * sort_list(struct node *first_node, int num_distinct_values)
{
	struct node **head, **tail; 
	struct node *result = NULL, *cur_node, *next_node, *last_element;
	int i;

	if (!first_node)
		return NULL;

	head = (struct node**) calloc(num_distinct_values, sizeof(struct node*));
	tail = (struct node**) calloc(num_distinct_values, sizeof(struct node*)); 

	for (i = 0; i < num_distinct_values; ++i) {
		head[i] = NULL;
		tail[i] = NULL;
	}

	/*Partition the list into separate lists, (0-list, 1-list, 2-list)
	based on the data in the node*/
	cur_node = first_node;
	while (cur_node) {
		next_node = cur_node->next;
		add_node(head, tail, cur_node, cur_node->data);
		cur_node = next_node;
	}

	/*Connect the tail of first linked list with head of second linked list
	and so on*/
	result = head[0];
	last_element = tail[0];
	for (i = 1; i < num_distinct_values; ++i) {
		if (!result)
			result = head[i];

		/*Link last element of previous list with head of current list*/
		if (last_element)
			last_element->next = head[i];

		/*update the last element to the tail of current list*/
		if (tail[i])
			last_element = tail[i];
	}

	free(head);
	free(tail);

	return result;
}



Java


/*
head: array of heads of the separated lists
tail: array of tails of the separated lists
curNode: current node being processed
i: data value of the node
*/
public static void addNode(LinkedListNode[] head, LinkedListNode[] tail, 
			LinkedListNode curNode, int i) {
	curNode.next = head[i];
	head[i] = curNode;
	if (tail[i] == null)
		tail[i] = curNode;

}

/*firstNode: first node in the list to be sorted 
numDistinctValues: number of distinct values 
Return value: head of the sorted list
*/
public static LinkedListNode sortList(LinkedListNode firstNode, 
				int numDistinctValues) {
	LinkedListNode[] head = new LinkedListNode[numDistinctValues]; 
	LinkedListNode[] tail = new LinkedListNode[numDistinctValues];
	LinkedListNode result = null;

	if (firstNode == null)
		return null;

	int i;
	for (i = 0; i < numDistinctValues; ++i) {
		head[i] = null;
		tail[i] = null;
	}

	/*Partition the list into separate lists (0-list, 1-list and 2-list)
	based on the data in the node*/
	LinkedListNode curNode = firstNode;
	while (curNode != null) {
		LinkedListNode nextNode = curNode.next;
		addNode(head, tail, curNode, curNode.data);
		curNode = nextNode;
	}

	/*Connect the tail of first linked list with head of second linked list
	and so on*/
	result = head[0];
	LinkedListNode lastElement = tail[0];
	for (i = 1; i < numDistinctValues; ++i) {
		if (result == null)
			result = head[i];

		/*Link last element of previous list with head of current list*/
		if (lastElement != null)
			lastElement.next = head[i];

		/*update the last element to the tail of current list*/
		if (tail[i] != null)
			lastElement = tail[i];
	}

	return result;
}


Python


#head: list having head nodes of all the separated linked lists
#tail: list having tail nodes of all the separated linked lists
#cur_node: current node being processed
#i: data value of the node
@staticmethod
def add_node(head, tail, cur_node, i) :
	cur_node.next = head[i]
	head[i] = cur_node
	if (tail[i] == None):
		tail[i] = cur_node


#first_node:  first node in the linked list to be sorted
#num_distinct_values: number of distinct values 
#Return value: head of the sorted linked list
@staticmethod
def sort_linked_list(first_node, num_distinct_values) :
	head = [None] * num_distinct_values 
	tail = [None] * num_distinct_values
	result = None

	if (not first_node):
		return None

	#Partition the input linked list into separate linked lists 
	#(0-list, 1-list and 2-list) based on the data in the node
	cur_node = first_node
	while (cur_node) :
		next_node = cur_node.next
		LinkedListNode.add_node(head, tail, cur_node, cur_node.data)
		cur_node = next_node
	
	#Connect the tail of first linked list with head of second linked list
	#and so on
	result = head[0]
	last_element = tail[0]
	for  i in range(1, num_distinct_values):
		if (not result):
			result = head[i]

		#Link last element of previous linked list with head of 
		#current linked list
		if (last_element):
			last_element.next = head[i]

		#update the last element to the tail of current linked list
		if (tail[i] != None):
			last_element = tail[i]
	

	return result


Merge M sorted arrays

Question 45. Given m sorted arrays each of which has a size n, merge the arrays in sorted order into a single array of size m*n


To efficiently solve the problem we use a heap which has a maximum size of m (number of sorted arrays). If the arrays are sorted in non-decreasing order, then we maintain a min heap otherwise we maintain a max heap. The algorithm is as follows

1. Pick the first element from each array, add it to the heap and construct the heap using the heapify function

2. Add the topmost element in the heap to the result array. Then replace the topmost element of the heap with the next element from the same array as the topmost element. Re-adjust the heap using the heapify function. Suppose all elements in the same array are over, then add a MAX_INT for non-decreasing order (MIN_INT for non-increasing order) into the root of the heap and re-adjust the heap using heapify. Repeat this step until all elements in all the arrays are processed.

Inserting an element into a heap of size m takes O(logm). Since we have n*m elements, the time complexity of this approach is O(nm * logm).

The code for merging k sorted lists is given below.

C/C++


/*
arrays: the arrays to be merged. arrays[0] has the first array, arrays[1] has 
		the second array and so on
n: number of elements in each array
k: number of arrays
result: the merged results are passed back in this array
*/
void merge_k_sorted_arrays(int arrays[][MAX_NUM_ELEMENTS], int n, int k, 
			int *result)
{
	struct node *heap = (struct node*) calloc(k, sizeof(struct node));
	int *arr_pos = (int*) calloc(k, sizeof(int));
	int i, pos, res_index, array_no;

	/*Store the first element in each array into the heap*/
	for (i = 0; i < k; ++i) {
		heap[i].value = arrays[i][0];
		heap[i].array_no = i;
		arr_pos[i] = 1;
	}

	/*Construct the initial heap using the heapify procedure*/
	for (i = k - 1; i >= 0; --i)
		heapify(heap, i, k);
	
	/*
	Process the remaining elements in the arrays. When all elements in the 
	arrays have been processed, MAX_INT will be present at root of heap
	*/
	res_index = 0;
	while (heap[0].value != MAX_INT) {
		/*
		root of the heap will have the lowest value. So store
		it into the result
		*/
		result[res_index++] = heap[0].value;

		array_no = heap[0].array_no;
		pos = arr_pos[array_no];

		/*
		If the root belongs to array x, then replace the root with
		the next element in array x
		*/
		if (pos >= n) {
			/*If we have exhausted all elements in the array, 
			then insert MAX_INT into the heap*/
			heap[0].value = MAX_INT;
			heap[0].array_no = array_no;
		} else {
			heap[0].value = arrays[array_no][pos];
			heap[0].array_no = array_no;
		}

		/*Re-adjust the heap after replacing the root*/
		heapify(heap, 0, k);

		arr_pos[array_no]++;
	}

	free(arr_pos);
	free(heap);
}


/* Helper function to perform heapify
heap: min heap.  Maximum number of elements in heap is k
pos: position of the heap that may need to be fixed
heap_size: current number of nodes in the heap
*/
void heapify(int heap[], int pos, int heap_size)
{
	int left = 2 * pos;
	int right = (2 * pos) + 1;
	int ix_of_smallest = pos;

	/*Find which of the three are the smallest: heap[pos] OR left child
	OR right child*/
	if (left < heap_size && heap[pos] > heap[left])
		ix_of_smallest = left;
	if (right < heap_size && heap[ix_of_smallest] > heap[right])
		ix_of_smallest = right;

	if (ix_of_smallest != pos) {
		/*
		If pos doesn't contain the smallest value,
		then swap the smallest value into pos 
		*/
		int temp = heap[pos];
		heap[pos] = heap[ix_of_smallest];
		heap[ix_of_smallest] = temp;

		/*Recursively re-adjust the heap*/
		heapify(heap, ix_of_smallest, heap_size);
	}
}



Java


/*
arrays: the arrays to be merged. arrays[0] has the first array, arrays[1] has
		the second array and so on
Return value: the merged results are passed back in this array
*/
public static int[] mergeKSortedArrays(int[][] arrays) {
	int k = arrays.length;	/*number of arrays*/
	int n = arrays[0].length; /*number of elements in each array*/
	Node[] heap = new Node[k];
	int[] arrPos = new int[k];
	int[] result = new int[k * n];

	/*Store the first element in each array into the heap*/
	int i;
	for (i = 0; i < k; ++i) {
		heap[i] = new Node();
		heap[i].value = arrays[i][0];
		heap[i].arrayNo = i;
		arrPos[i] = 1;
	}

	/*Construct the initial heap using the heapify procedure*/
	for (i = k - 1; i >= 0; --i)
		heapify(heap, i, k);

	
	/*
	Process the remaining elements in the arrays. When all elements in the
	arrays have been processed, MAX_INT will be present at root of heap
	*/
	int resIndex = 0;
	while (heap[0].value != MAX_INT) {
		/*
		root of the heap will have the lowest value. So store
		it into the result
		*/
		result[resIndex++] = heap[0].value;

		int arrayNo = heap[0].arrayNo;
		int pos = arrPos[arrayNo];

		/*
		If the root belongs to array x, then replace the root with
		the next element in array x
		*/
		if (pos >= n) {
			/*If we have exhausted all elements in the array, 
			then insert MAX_INT into the heap*/
			heap[0].value = MAX_INT;
			heap[0].arrayNo = arrayNo;
		} else {
			heap[0].value = arrays[arrayNo][pos];
			heap[0].arrayNo = arrayNo;
		}

		/*Re-adjust the heap after replacing the root*/
		heapify(heap, 0, k);

		arrPos[arrayNo]++;
	}

	return result;
}

/* Helper function to perform heapify
heap: min heap.  Maximum number of elements in heap is k
pos: position of the heap that may need to be fixed
heapSize: current number of nodes in the heap
*/
public static void heapify(int[] heap, int pos, int heapSize) {
	int left = 2 * pos;
	int right = (2 * pos) + 1;
	int ixOfSmallest = pos;

	/*Find which of the three are the smallest - heap[pos] OR left child
	OR right child*/
	if (left < heapSize && heap[pos] > heap[left])
		ixOfSmallest = left;
	if (right < heapSize && heap[ixOfSmallest] > heap[right])
		ixOfSmallest = right;


	if (ixOfSmallest != pos) {
		/*
		If pos doesn't contain the smallest value,
		then swap the smallest value into pos 
		*/
		int temp = heap[pos];
		heap[pos] = heap[ixOfSmallest];
		heap[ixOfSmallest] = temp;

		/*Recursively re-adjust the heap*/
		heapify(heap, ixOfSmallest, heapSize);
	}
}




Python


#lists:  the lists to be merged. lists[0] has the first list, lists[1] has 
#		the second list and so on
#Return value:  the merged results are passed back in this list
def merge_k_sorted_lists(lists) :
	k = len(lists)	#number of lists
	n = len(lists[0]) #number of elements in each list
	heap = []
	arr_pos = []

	#Store the first element in each list into the heap
	for  i in range(0, k):
		new_node = Node()
		new_node.value = lists[i][0]
		new_node.list_no = i
		heap.append(new_node)
		arr_pos.append(1)
	
	#Construct the initial heap using the heapify procedure
	for  i in range(k - 1, -1,-1):
		heapify(heap, i, k)

	#Process the remaining elements in the lists. When all elements in  
	#the lists have been processed, MAX_INT will be present at root of heap
	result = [] 
	while (heap[0].value != MAX_INT) :
		#root of the heap will have the lowest value. So store
		#it into the result
		result.append(heap[0].value)

		list_no = heap[0].list_no
		pos = arr_pos[list_no]

		#If the root belongs to list x, then replace the root with
		#the next element in list x
		if (pos >= n) :
			#If we have exhausted all elements in the list, 
			#then insert MAX_INT into the heap
			heap[0].value = MAX_INT
			heap[0].list_no = list_no
		else :
			heap[0].value = lists[list_no][pos]
			heap[0].list_no = list_no
		

		#Re-adjust the heap after replacing the root
		heapify(heap, 0, k)

		arr_pos[list_no] += 1
	
	return result

#Helper function to perform heapify
#heap: min heap.  Maximum number of elements in heap is k
#pos: position of the heap that may need to be fixed
#heap_size: current number of nodes in the heap
def heapify(heap, pos, heap_size) :
	left = 2 * pos
	right = (2 * pos) + 1
	ix_of_smallest = pos

	#Find which of the three are the smallest - value at pos OR left child
	#OR right child
	if (left < heap_size and heap[pos] > heap[left]):
		ix_of_smallest = left
	if (right < heap_size and heap[ix_of_smallest] > heap[right]):
		ix_of_smallest = right
 
	if (ix_of_smallest != pos) :
		#If pos doesn't contain the smallest value,
		#then swap the smallest value into pos 
		heap[pos], heap[ix_of_smallest] = heap[ix_of_smallest], heap[pos]

		#Recursively readjust the heap
		heapify(heap, ix_of_smallest, heap_size)




Merge a small sorted array into a larger sorted array

Question 44. Given a small array of size n having n sorted elements and a big array of size m+n having m sorted elements at the beginning of the big array, merge the two arrays and store them in the big array


There is just enough free space in the big array to accommodate the elements of the small array. The two sorted arrays can be merged in O(m+n). The trick is to start filling up the big array from the end where the free space is present. The code for this is given below

C/C++


/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
void merge_arrays(int a[], int b[], int m, int n)
{
	int i, j, fill_pos;

	i = m - 1;
	j = n - 1;
	fill_pos = m + n - 1; /*Start filling from the rear of the array*/

	while (i >= 0 && j >= 0) {
		if (a[i] > b[j]) {
			a[fill_pos--] = a[i--];
		} else {
			a[fill_pos--] = b[j--];
		}
	}

	/*Fill up the remaining elements of array a if any*/
	while (i >= 0)
		a[fill_pos--] = a[i--];

	/*Fill up the remaining elements of array b if any*/
	while (j >= 0)
		a[fill_pos--] = b[j--];

} 



Java


/*
a: array of size m+n which has m elements at beginning and n spaces at end
b: array of size n with n elements
m: number of elements in array a
n: number of elements in array b
*/
public static void mergeArrays(int[] a, int[] b, int m, int n) 	{
	int i = m - 1;
	int j = n - 1;
	int fillPos = m + n - 1; /*Start filling from the rear of the array*/

	while (i >= 0 && j >= 0) {
		if (a[i] > b[j]) {
			a[fillPos--] = a[i--];
		} else {
			a[fillPos--] = b[j--];
		}
	}

	/*Fill up the remaining elements of array a if any*/
	while (i >= 0)
		a[fillPos--] = a[i--];

	/*Fill up the remaining elements of array b if any*/
	while (j >= 0)
		a[fillPos--] = b[j--];
}  



Python


#a: list of size m+n which has m elements at beginning 
#b: list of size n with n elements
#m: number of elements in list a
#n: number of elements in list b
def merge_lists(a, b, m, n) :
	i = m - 1
	j = n - 1
	fill_pos = m + n - 1 #Start filling from the rear of list a

	while (i >= 0 and j >= 0) :
		if (a[i] > b[j]) :
			a[fill_pos] = a[i]
			fill_pos -= 1
			i -= 1
		else :
			a[fill_pos] = b[j]
			fill_pos -= 1
			j -= 1
		
	#Fill up the remaining elements of list a if any
	while (i >= 0):
		a[fill_pos] = a[i]
		fill_pos -= 1
		i -= 1

	#Fill up the remaining elements of list b if any
	while (j >= 0):
		a[fill_pos] = b[j]
		fill_pos -= 1
		j -= 1



Wave sort

Question 43. Re-arrange the elements in an array like a wave so that the values of the array alternately increase and decrease. The elements in the array are unique. For instance, if A = {50, 10, 20, 30, 40}, after re-arranging A can be {10, 30, 20, 50, 40} where in the value of consecutive elements alternately increases and decreases


This problem can be solved in O(nlogn) without additional memory as follows:

1. First sort the entire array in ascending order. So {50, 10, 20, 30, 40} becomes {10, 20, 30, 40, 50}

2. Then starting from index 1 in the array, swap the neighboring elements. So {10, 20, 30, 40, 50} becomes {10, 30, 20, 50, 40}

C/C++


/*
a: array that has to be sorted so that the values in it alternatively increase
	and decrease. The elements should be unique
length: number of elements in the array. should be >= 1
*/
void wave_sort(int a[], int length)
{
	int i, temp;

	/*Sort the elements in ascending order*/
	qsort(a, length, sizeof(int), cmp_function);

	/*Swap the alternate elements*/
	for (i = 1; i < length - 1; i += 2) {
		temp = a[i];
		a[i] = a[i+1];
		a[i+1] = temp;
	}
}



Java


/*
a: non-empty array that has to be sorted so that the values in it 
	alternatively increase and decrease. The elements should be unique
*/
public static void waveSort(int[] a) {
	/*Sort the elements in ascending order*/
	Arrays.sort(a);

	/*Swap the alternate elements*/
	for (int i = 1; i < a.length - 1; i += 2) {
		int temp = a[i];
		a[i] = a[i+1];
		a[i+1] = temp;
	}
}



Python


#a: non-empty list that has to be sorted so that the values in it 
#	alternatively increase and decrease. The elements should be unique
def wave_sort(a) :
	#Sort the elements in ascending order
	a.sort()

	#Swap the neighboring elements
	for  i in range(1, len(a) - 1, 2):
		a[i], a[i+1] = a[i+1], a[i]