Q1. Find the square root of a number x.
Hint: Use Newton Raphson method or Bisection Method / Binary Search Method.
Let y^2=x => y^2 - x = 0
Let f(y) = y^2 -x
y_n = y_(n-1) - f(y)/f ' (y)
Q2. Given an array of numbers, find the first number that is unique in the array.
Hint: Use a LinkedHashMap
Different implementations of Map in java are : Hashtable (obsolete), HashMap (Supports null key and null value ), LinkedHashMap, TreeMap (Red-Black tree Navigable Key Sorted Map), EnumMap ( Uses Enum keys and sorted on natural order of Enum keys), ConcurrentSkipListMap (SkipList based implementation ), ConcurrentHashMap (Supports concurrency), IdentityHashMap (Uses reference-equality rather than Object-equality for comparing keys), and WeakHashMap.
Q3. There is a file which has n numbers in the nth line. For example,
7
2 9
8 3 1
2 7 9 1
Now, starting from the top and moving down using the adjacent numbers in the below row, find the maximum sum of such a path. For example, adjacent numbers for 2nd number 9 in the row 2 are 8, 3, and 1 in row 3.
Hint: Use dynamic programming. Start from nth row and traverse back. Let the input file is stored in a half matrix/ 2-D array A. For an element at A[i][j],
A[i][j] = max(sum(A[i][j]+A[i+1][j]), sum(A[i][j]+A[i+1][j-1]),sum(A[i][j]+A[i+1][j+1]))
Pick the max sum for i = 0, i.e., 0th row.
Q4. Given n points on a circle, find the different number of ways of drawing non-intersecting chords between the n points.
Hint: Motzkin number
Q5. Given an unsorted array A where ith element A[i] is within k position from its position j in the sorted array, i.e., |j-i|=k, design an algorithm to efficiently sort the array.
Hint: Sort using a heap of size 2k. Create a minimum heap using the first 2K elements A[0 - (2k-1)]. Remove the head of the heap which is the smallest element and place at A[0]. Reorganize the heap. Insert A[2k] element in the heap. Remove the head and place at A[1]. Continue till we reach the end of the array. This gives sorted array till A[n-k]. Finally, a heap sort is used on the remainder of the heap to get the last (2k-1) elements in sorted order. Time complexity: O(N logk).
Q6. Given a palindrome date 2001/10/02, find the next date which is palindrome.
Hint: 20011002 is palindrome. increment 2001 till we get last 2 digits which gives a possible month when the digits are flipped. That is the next date.
Q3. There is a file which has n numbers in the nth line. For example,
7
2 9
8 3 1
2 7 9 1
Now, starting from the top and moving down using the adjacent numbers in the below row, find the maximum sum of such a path. For example, adjacent numbers for 2nd number 9 in the row 2 are 8, 3, and 1 in row 3.
Hint: Use dynamic programming. Start from nth row and traverse back. Let the input file is stored in a half matrix/ 2-D array A. For an element at A[i][j],
A[i][j] = max(sum(A[i][j]+A[i+1][j]), sum(A[i][j]+A[i+1][j-1]),sum(A[i][j]+A[i+1][j+1]))
Pick the max sum for i = 0, i.e., 0th row.
Q4. Given n points on a circle, find the different number of ways of drawing non-intersecting chords between the n points.
Hint: Motzkin number
Q5. Given an unsorted array A where ith element A[i] is within k position from its position j in the sorted array, i.e., |j-i|=k, design an algorithm to efficiently sort the array.
Hint: Sort using a heap of size 2k. Create a minimum heap using the first 2K elements A[0 - (2k-1)]. Remove the head of the heap which is the smallest element and place at A[0]. Reorganize the heap. Insert A[2k] element in the heap. Remove the head and place at A[1]. Continue till we reach the end of the array. This gives sorted array till A[n-k]. Finally, a heap sort is used on the remainder of the heap to get the last (2k-1) elements in sorted order. Time complexity: O(N logk).
Q6. Given a palindrome date 2001/10/02, find the next date which is palindrome.
Hint: 20011002 is palindrome. increment 2001 till we get last 2 digits which gives a possible month when the digits are flipped. That is the next date.
Q7. Given an unsorted array of numbers, find the longest sub-array whose elements form a continuous sequence.
Example: A = {12, 1, 19, 16, 15, 18, 17, 2, 5}
Answer: {19, 16, 15, 18, 17}
Q8. Given a stream of characters, design an algorithm to find a given string in it.
Hint: Knuth-Morris-Pratt Algorithm
Q9. Given a sorted array of numbers having multiple duplicates, find the first occurrence of a given number.
Hint: Perform a binary search. Once we find the element at ith position, we check if A[i-1] < 0 or i=0. If not, we continue search in the left sub-array.
Q10. Given an array of numbers and a set of operators ( +, -, *, /), find the smallest number that can not be formed by the numbers and operators. Order of the numbers in the array needs to be maintained while forming an expression with the operators.
Example: A = {12, 1, 19, 16, 15, 18, 17, 2, 5}
Answer: {19, 16, 15, 18, 17}
Q8. Given a stream of characters, design an algorithm to find a given string in it.
Hint: Knuth-Morris-Pratt Algorithm
Q9. Given a sorted array of numbers having multiple duplicates, find the first occurrence of a given number.
Hint: Perform a binary search. Once we find the element at ith position, we check if A[i-1] < 0 or i=0. If not, we continue search in the left sub-array.
Q10. Given an array of numbers and a set of operators ( +, -, *, /), find the smallest number that can not be formed by the numbers and operators. Order of the numbers in the array needs to be maintained while forming an expression with the operators.
No comments:
Post a Comment