Q1. Given an array of integers, arrange the array such that all the positive and negative integers are grouped in contiguous manner and the relative ordering of elements in each group is preserved.
Example: [ 2, 12, -3, 0, 4, -2, -6, 1]
Answer: [ 2, 12, 4, 1, 0, -3, -2, -6]
Q2. Given an array of integers, find the maximum sum of contiguous elements.
Hint: Kadane's Algorithm
Kadane's Algorithm for a Matrix
Q3. Given a circular linked list of integers, find the maximum sum of contiguous elements.
Q4. There are 3 employees. They need to compute the average of their total salary without communicating the true salary of each other. Design a mechanism for the same.
Hint: These are important questions for secure distributed computing. A naive mechanism is as follows:
Let A, B, and C are the employees with salary a , b, and c respectively.
Each employee adds a random amount to their salary, i.e., a+x, b+y, and c+z
They broadcast their fake salaries.
Average of fake salaries = ((a+b+c/3) + (x+y+z/3))
Now use a circular protocol. A takes the average and subtracts x/3 from the fake average. A sends the result to either B or C. B subtracts y/3 from the fake average and sends it to C. Finally, C subtracts z/3 and broadcasts the actual average.
Q5. Design an algorithm to write all the permutations of a given string.
Q6. Given an unsorted array of size n, what is the minimum number of comparisons that are required to find out the median.
Q7. Given a set, design an algorithm to generate its power set.
Q8. Given two very large arrays of numbers. Design an efficient algorithm to
a) Find all the common elements in the two arrays.
b) Find the dot product of the two arrays.
Hint a.1) Bloom filter is the fastest approach but probabilistic.
a.2) Put each array in a hashset. Let the smaller hashset be A and the larger be B. Test each element of A if it is present in B.
a.3) Sort both the arrays. Perform a mechanism like merge sort to detect common elements.
b.1) Create a hashmap for each array. Store the non-zero values in a hashmap with the position of the value as key. Let the smaller hashmap be A and the larger be B. For each value in A, search it in B and multiply. Some of all the multiplications would the dot product.
Q9. Given 3 strings, design an algorithm to find out all ways in which first and second string can be used to generate the third string.
Q10. We have a set of 10,000 numbers. Each number use b bits, e.g., b = 16. Design an algorithm to sort the set.
Hint: Important thing to note is that it is a set of numbers, therefore there are no duplicates. Secondly, the maximum bit used by any number is b = 16. This limits the maximum and minimum number that may be in the in the set. For example, for b = 16 and unsigned integer, min_number = 0 and max_number = 65535. For b = 16 and signed integer, min_number = -32768 and max_number = 32767.
We take a bit array of the size of (maximum number - minimum number +1). We find the index i of a number in the bit array, i = number + |min_number. Flag on the bits corresponding to the numbers in the array. Finally, traverse the bit array to get the numbers in the sorted order.
No comments:
Post a Comment