Answers for MISC questions

39. Find first non repeating character in a string.
a) Bruteforce: TC: o(n2) SC: o(1)
b) use another array or use hashtable

40. Find whether two arrays of same size have same values.
Go through first array, hash every element and increment the count if repeated.
Go through second and decrement count for every element and at the lost every index should be having zero.

41. Given a minheap find the max element.
Sol) max element will always be at leaf, take the last element in heap and find its parent which will be always the last non leaf node. Find the max element after the last non leaf node and last node.

42. Convert an array to heap.
a) Sort the array and sorted array is always min heap.
b) Add the first element in heap and then second. Now particulate for heap property. Keep adding element and managing heap property.
c) Bottom up heap building ( I really did not understand this concept. Please google).
43. Kth element in a Min heap.
a) Bruteforce: Call delete min () k times. TC (nlog n);
b) Can there could be a better approach? I am sure there will be, if you know please post.

44. implement a stack using heap.
Stack : push, pop and top
Heap: insert, delete and Findmin.
a) Maintain extra index key in the heap.
Push ( O(log n)), pop (O (long n) ) top (O(1))
45. Implement queue using heap.
Use the same approach as stack, use the negative index for stack and positive for queue.

46. Find union of k sorted list.
a) Create the min heap from the first elements of all arrays.
Delete the first element and put the deleted element in a new array.
Insert a new element from the deleted array. Maintain separate index for every array, so that we can figure out which array to take next element.
b) Use divide and conquer, merge sort.
c) Bruteforce: merging first two array and then resulting array with next one.
47. Merge the two heap.
a) take element from one heap and insert in second heap. O(min(m log m+n, n log m+n)).
b) Append first array to second and then convert array to heap. O(m+n).

48. Fibonocci with memorization/ Dynamic programming.
Int f ( int n)
{
If ( n<= 1) return n;
If ( fib[n] != -1 ) return fib[n];
Fib[n] = f ( n-1) + f (n-2);
Return fib[n];
}

49. Find no of BST can be formed with n nodes.
BST(n) = 1 if n == 0
= 1 if n == 1
= i=1 to n BST(i-1) * BST(n-i) for n >2
Int BST(int n)
{
Int count = 0;
If ( n <= 1 ) return 1;
For ( I =1;i<= n;i++)
Count += BST(i-1)*BST(n-i);
Return count;
}
Not optimized, use memozation technique.
50. Find no of legal path between x and y which does not include ‘+’
A
- + - - +
- - - - -
+ - + + -
- - - - -
B

For ( int I =0; i<= m ;i++) p[i][0] =0;
For ( int j = 0; j <= n; j++) p[0][j] = 0;
For ( I = 1; i<= m;i++ )
{
For ( j = 1;j<=n ;j++ )
{
If ( a[i][j] == ‘.’ ) p[i][j] = p[i-1][j]+p[i][j-1];
Else p[i][j] = 0;
}
}
Return p[m][n];

51. Find the largest common subsequence between two given strings.
LCS(I,j) = max (LCS(I,j-1), LCS(i-1,j)) if s1[i] != s2[j].
LCS(I,j) = 1+ LCS(I-1,j-1) if s1[i] == s2[j].
LCS(I,j) = 0 if i==0 or j == 0.

52. Find the shortest common super sequence.
SCS(I,j) = 1+ min (LCS(I,j-1), LCS(i-1,j)) if s1[i] != s2[j].
SCS(I,j) = 1+ SCS(I-1,j-1) if s1[i] == s2[j].
SCS(I,j) = max(I,j) if i==0 or j == 0.

53. In a string, find the longest substring which is palindrome.
a) Reverse the first string and find the longest common substring.
b)
54. Find the maximum sum subarray without selecting two consecutive number.
S[i] = max (a[0], a[1]) if I == 1
S[i] = max (a[i]+s[i-2], s[i-1]) if I > 1
Int maximalsum ( int a[], int n)
{
S[0] = a[0];
S[1] = max (a[0],a[1])’;
For ( i= 2; i< n; i++)
S[i] = max(s[i-1],s[i-2]+a[i]);
Return s[n-1];
}

55. optimal matrix chain multiplication.
M[I,j] = 0 if i==j
M[I,j] = min ( m(I,k)+m(k+1,i)+ri*ck*cj) if I <= k < j.

56. Generate binary sequence of constant ‘N’.
Void binary ( int a[], int n)
{
If ( n == 2 )print(a), return;
a[i] =0;
binary(a,n+1);
a[i] =1;
binary(a,n+1);
return;
}
57. Given an array generate all the possibilities of array.
Void generate( int in[], int out[], int I, int n)
{
Int j;
If ( I == n ) print(out), return;
For ( j = 0; j < n; j++)
{
Out[i] = in[j];
Generate(in,out,i+1,n);
}
}

58. Given an array generate the permutation of array.
Void permute( int in[], int out[],int used, int I, int n)
{
Int j;
If ( I == n ) print(out), return;
For ( j = 0; j < n; j++)
{
If ( used[j] ) continue;
Used[j] = true;
Out[i] = in[j];
permute(in, out, used, i+1,n);
used[j] = false;
}
}

59. Given an array generate the combination of array.
Void combination ( int in[], int out[], int n, int k, int I, int start )
{
If ( I == k ) printf(out,k),return;
For ( j = start; j < n-k+start;j++ )
{
Out[i] = in[j];
Combination(in,out,n,k,i+1,j+1);
}
}
60. Find distinct partitions of a number i.e. for 3(1,1,1)(1,2)

61. In a matrix find the largest square with all 1’s
0 0 0 0 1
0 1 1 0 1
0 0 1 0 1
1 1 0 0 1
0 1 1 1 0
A[I,j] = 0 if I == 0 or j == 0
A[I,j] = 0 if c[i][j] == 0
A[I,j] = min(A[i-1][j],A[i-1][j-1], A[i][j-1]+1)