Q1. Reverse the bits of an integer in-place, e.g., 11001 -> 10011.
Q2. A list contains repeated numbers. All numbers are repeated odd number of times except one that is repeated even number of times. Find the number that is repeated even number of times.
Q3. Remove duplicates from a heap.
Q4. Given a document and set of words, design an algorithm to find the smallest window that contains all the keywords at least once. Sequence of the words is immaterial. Let the words of a document are incrementally assigned positions starting from 0 for the first word. Then, the length of a window for a set of words is the difference in the position of the last word and the first word.
Example:
Words set: Buddhism, Gautama
Document: In the late Vedic period, around the 5th century BCE, the small chiefdoms of the Ganges Plain and the north-western regions had consolidated into 16 major oligarchies and monarchies that were known as the mahajanapadas. The emerging urbanisation and the orthodoxies of this age also created the religious reform movements of Buddhism and Jainism, both of which became independent religions. Buddhism, based on the teachings of Gautama Buddha attracted followers from all social classes excepting the middle class; chronicling the life of the Buddha was central to the beginnings of recorded history in India.Jainism came into
We see that there are two occurrences of word "Buddhism". The highlighted part of the document is the smallest window containing both the words Buddhism and Gautama.
Q5. There are N players in a tournament. Each player has played against every other player. Results of each game is known. Arrange the players in a row such that for any ith player, all the players winning against her is on the left and all the players losing against her are on the right.
Hint: Create a DAG of the players. Each player is a vertex in the DAG. A directed edge from a player A to B implies that A has won the match against B. A
topological sorting will either give a ordering or detect a cycle in which case there is no such ordering.
Q6. a) Given an array of numbers and a value N, find all the pairs which sum to N.
b) Given an array of numbers and a value N, find all the combinations of numbers in the array which sum to N.
c) Given an array of numbers and a value N, find a combination of the numbers in the array having the least size that sums to N.
Example:
A = 2, 10, 12 , -5 , 0, -3, 1, 5
N = 5
a) Pairs: 10, -5 and 0, 5
b) Combinations: 1) 5 (size 1);
2) 10, -5 (size 2);
3) 0, 5 (size 2);
4) 2, -3 , 1, 5 (size 4);
5) 2, -3 , 1, 5, 0 (size 5);
6) 10, -5 (size 2)
7) 12, -5, -3, 1 ( size 3 )
c) Combination of the least size : a) 5 (size 1)
Hint: a.1) Put the numbers in a hashmap. For every number A[i] in the array, find the residue R = (N-A[i]). Search R in the hashmap.
a.2) Sort the array. For every number A[i] in the array, find the residue R = (N-A[i]). Perform a binary search for R in the array. Take care of duplicates.
b) A recursive solution. Sort the array. For every number A[i] in the array, find the residue R = (N-A[i]). Perform the search for R in subb-array A'= [A[i+1], ..., A[length(A)-1]]
Q7. Given two strings, design an algorithm to print all the interleavings of the two strings. Here interleaving means that the if a character B comes after character A in a string, then B should also come after A in the interleaved string.
Example:
String1 = AB and String2 = CD
Interleaved Strings:
ABCD, ACBD, ACDB, CABD, CADB, CDAB
Q8. Sort a binary array [0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1].
Hint: Perform a quick sort using 0 as pivot. It has O(n) time complexity.
Q9. A data stream is a sequence of unsorted numbers received or transmitted over a period of time. A machine is receiving a data stream. Design a data structure and an algorithm to efficiently report the median whenever a new number is received by the machine in the stream.
Q10. Given an array of unsorted numbers, design a algorithm to find all the pairs (i,j) such that for i < j, A[i] > A[j].
Hint: A O(n log n) solution possible using the idea of quick sort and binary search tree. Use quick sort to build a BST. An idea for the
solution.
