Q1. Given an 2-D array MxN of numbers, write a program to print the array in clockwise or anti-clockwise. For clockwise, it should be like First row, last column, last row, and then first row and so on.
Q2. Given an array of non-zero numbers, find the first subarray (contiguous set of numbers) that sum to zero.
Related reading : Subset sum problem
Hint: The problem can be solved in O(n) time complexity.
Construct a cumulative sum array S. The ith value of S, i.e., S[i], contains the sum of all the values from S[0] to S[i]. If any of the values S[j] is 0, then the subarray S[0-j] is the answer and the algorithm terminates. Otherwise, if these is any subarray whose sum is ), then there must be duplicate sum values in S. Next, the task is to find the first sum which is a duplicate. Create a HashMap<K,V> from the sum array. Key K in the HashMap<K, V> is the sum S[i] in the array S. The value V is a linked list of the positions at which the sum occurs. Traverse the hashmap to find the smallest index of the sum that repeats.
Q3. Design an algorithm to efficiently compute the value of a^b.
Hint. Use divide and conquer called exponentiation by squaring.
Q4. Given an array A such that A[i] = A[i]+1 or A[i]= A[i]-1. Design an efficient algorithm to determine if a given number k is present in A or not.
Q5. Given a number N and K, design an efficient method to verify if N^N = K.
Hint: Use log to verify if N*log(N) is equal to K.
Q6. Given an array of numbers, design an algorithm to
a) find the longest increasing sub-array (contiguous elements).
b) find the longest increasing sub-sequence ( elements are not required to be contiguous).
Hint: a) Longest increasing subarray can be solved in O(n) time complexity by a sequential scan of the array.
Q7. Given an array of numbers, design an algorithm to find the top-k most frequent numbers.
Q8. Reverse first k elements of a n-size linked list.
Q9. In an unsorted array of first N +ve integer numbers, there is one duplicated and one missing number. Design a mechanism to find the missing and the duplicate number.
Hint:
Let denote a number from 1 to N as A[i]
Let denote a given number by B[i]
Let the missing number be X. Let the duplicate number be Y.
Sum of the first N +ve integer numbers S'= sum(A[i]) = N*(N+1)/2
Let the sum of the given numbers be S = sum(B[i])
Q10. Design a quicksort with two pivots. Also analyze its complexity.
Q8. Reverse first k elements of a n-size linked list.
Q9. In an unsorted array of first N +ve integer numbers, there is one duplicated and one missing number. Design a mechanism to find the missing and the duplicate number.
Hint:
Let denote a number from 1 to N as A[i]
Let denote a given number by B[i]
Let the missing number be X. Let the duplicate number be Y.
Sum of the first N +ve integer numbers S'= sum(A[i]) = N*(N+1)/2
Let the sum of the given numbers be S = sum(B[i])
Equation 1: S'-S = Y - X
Equation 2: product(A[i]/B[i]) for 1< i < N = X/Y
Q10. Design a quicksort with two pivots. Also analyze its complexity.
No comments:
Post a Comment