forked from rootusercop/IMP-Interview-Questions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
IMP Questions
286 lines (215 loc) · 10 KB
/
IMP Questions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
*******************************************************************************************************************
2 SUM Problem
http://coderevisited.com/2-sum-problem/
http://www.careercup.com/question?id=15206700
The 2 sum problem is a classic variation of the subset sum problem. It is defined as the following:
You have an unsorted array, and you are given a value S. Find all pairs of elements in the array that
add up to value S.
2 solutions - one minimizes space complexity, and the other time. As stated in the "hint",
one approach is to hash the entire array, and then for each element check if S-array[j] is in the
hash table. This takes O(n) time and O(n) space to store the array.
Alternatively, if one wishes to minimize space complexity, simply sort the array. Then, have two
pointers - one initialized to array[0] and the other array[length-1]. Then check the sums; if the
sum is > S, decrement the right pointer. If it is < S, increment the left pointer.
Sample Java code for the second method of finding 2sum:
public static void findTwoSum(int[] A, int x) {
Arrays.sort(A);
int start = 0;
int end = A.length - 1;
boolean found = false;
while (!found && start < end) {
if (A[start] + A[end] == x)
found = true;
else if (A[start] + A[end] > x)
end--;
else if (A[start] + A[end] < x)
start++;
}
if (found)
System.out.println("Sum " + x
+ " is found, values the making sum are " + A[start] + " , "
+ A[end]);
else
System.out.println("No pair exists whose sum is " + x);
}
***********************************************************************************************************
To reverse a string in Java:
package BST_Demo;
public class ReverseArray {
public static void main(String[] args) {
String givenString = "Am I bad ? ";
StringBuilder reverse=new StringBuilder(givenString.length());
for(int i=givenString.length()-1;i>=0;i--){
reverse.append(givenString.charAt(i));
}
System.out.println(reverse.toString());
}
}
How to implement a stack which will support following operations in O(1) time complexity?
1) push() which adds an element to the top of stack.
2) pop() which removes an element from top of stack.
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element.
Push and pop are standard stack operations.
http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/
Very IMP Q -> Disadvantages of HashMap or Hashtable OR Why is BALANCED TREES better than using Hashtable
or HashMap?
Ans ->
Very IMP Q -> Disadvantages of HashMap or Hashtable OR Why is BALANCED TREES better than using Hashtable
or HashMap?
Ans ->
In short:
1) Requires more main memory
2) Hashing algorithm does not result in spatial locality. Because hash tables cause
access patterns that jump around, this can trigger microprocessor cache misses that cause long delays.
3) Similar key types will result in more collision and hence the hashtable would be more like a linkedlist.
Collisions also ruin memory utilization- if I have 70 elements in 100 buckets, but those 70 elements hash to
only 4 buckets (and yes, Virginia, I’ve seen collision rates this bad), then 96 of my buckets aren’t doing
me any good at, I’m just wasting that space.
4) Occasionally HashMap/Hashtable requires resizing when the original size of HashMap/Hashtable buckets
are full. Resizing takes O(n) time as the elements from the previous hashtable/HashMap are transferred to
a new bigger Hashtable/HashMap. This is not good for implementation.
5) The concept that Hashtables/HashMap offers O(constant) (aka O(1) ) time complexity
for insertion, deletion and searchingis something to rethink on as the datastructure givies that
time complexity on a average scale, which is called as "AMORTIZED" time complexity. That means that there
would be atleast on instance out of n instances where the Time Complexity would be O(n) and not O(constant).
This is the time when the HashMap/Hashtable requires resizing.
http://stackoverflow.com/questions/6924852/what-are-the-disadvantages-to-hashmaps
http://web.archive.org/web/20090430172748/http://enfranchisedmind.com/blog/posts/problems-with-hash-tables/
http://en.wikipedia.org/wiki/Hash_table#Drawbacks
/* Program to find the 2nd minimum element in the array */
#include <stdio.h>
#include <limits.h> /* For INT_MAX */
/* Function to print first smallest and second smallest elements
Algorithm:
1) Initialize both first and second smallest as INT_MAX
first = second = INT_MAX
2) Loop through all the elements.
a) If the current element is smaller than first, then update first
and second.
b) Else if the current element is smaller than second then update
secondAlgorithm:
*/
void print2Smallest(int arr[], int arr_size)
{
int i, first, second;
/* There should be atleast two elements */
if (arr_size < 2)
{
printf(" Invalid Input ");
return;
}
first = second = INT_MAX;
for (i = 0; i < arr_size ; i ++)
{
/* If current element is smaller than first then update both
first and second */
if (arr[i] < first)
{
second = first;
first = arr[i];
}
/* If arr[i] is in between first and second then update second */
else if (arr[i] < second && arr[i] != first)
second = arr[i];
}
if (second == INT_MAX)
printf("There is no second smallest element\n");
else
printf("The smallest element is %d and second Smallest element is %d\n",
first, second);
}
/* Driver program to test above function */
int main()
{
int arr[] = {12, 13, 1, 10, 34, 1};
int n = sizeof(arr)/sizeof(arr[0]);
print2Smallest(arr, n);
return 0;
}
******************************************************************************************************
Longest Common SubSequence Problem:
/*
Question: Find the longest common subsequence between two strings
Question and Answer Source: http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
Algortihm: 1. declare a matrix of s1.length()+1 and s2.length()+1.
+1 is to store the results of the previous matches
2. initialize row = 0 OR column = 0 to 0 which indicates that the previous matches was 0
3. for i=1 to s1.length+1
for j=1 to s2.length+1
if(s1.charAt(i-1)==s2.charAt(j-1))
dp[i][j]= dp[i-1][j-1]+1 // current match = previous match +1
else
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])
// if the characters don't then the current matches = max of(previous matches)
*/
package SubstringAndSubsequenceProblems.Subsequence;
import java.util.Scanner;
public class LongestCommonSubsequence {
private static int[][] dp; // matrix to store the match results
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
try{
System.out.println("LONGEST COMMON SUBSEQUENCE PROGRAM");
System.out.println("Enter the two strings");
String s1 = in.nextLine();
String s2 = in.nextLine();
System.out.println("The Longest common SUBSTRING using DP is: "+usingDP(s1,s2));
// Printing the Logest Common Subsequence
int lengthOfLCSubSequence = usingDP(s1,s2);
// we will construct a String of LCS from right to left. Hence we will use char array
// instead of using StringBuilder which is used to construct the string from left to right
char[] LCSubSequence = new char[lengthOfLCSubSequence];
// pass this char array along with the matrix and 2 strings to get the result of matches
String longestCommonSubsequence = buildLCSubsequence(LCSubSequence,s1,s2);
System.out.println("The Longext Common SubSequence is: "+longestCommonSubsequence);
}
finally{
in.close();
}
}
private static int usingDP(String s1, String s2) {
dp = new int[s1.length()+1][s2.length()+1]; // additional +1 to store the previous match result which is 0
// fill the row with s1
for(int i=0;i<(s1.length()+1);i++)
dp[i][0] = 0;
// fill the column with s2
for(int j=0;j<(s2.length()+1);j++)
dp[0][j] = 0;
int result = 0; // to store the length of MAX COMMON SUBSEQUENCE MATCH
// fill the remaining rows and columns based on matches
for(int i=1;i<(s1.length()+1);i++){
for(int j=1;j<(s2.length()+1);j++){
// if current characters match then the length of the substring is previous matches + 1
if(s1.charAt(i-1)==s2.charAt(j-1))
dp[i][j] = dp[i-1][j-1]+1;
else // if doesnt match then current match = Max of (previous matches)
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
result = Math.max(result,dp[i][j]); // this is to check the maximum match found
}
}
return result;
}
private static String buildLCSubsequence(char[] LCSubSequence, String s1, String s2) {
int i = s1.length();
int j = s2.length();
int index = LCSubSequence.length-1;
while(i>0 && j>0){ // greater than 0 because there is nothing at 0th row and 0th column in the match matrix
if(s1.charAt(i-1)==s2.charAt(j-1)){ // -1 because i and j start from their respective lengths
// append the character
LCSubSequence[index]=s1.charAt(i-1);
// decrement the index
index--;
// decrement the i and j pointers
i--;
j--;
}
// if the characters do not match then go in the max direction in the match matrix
else if(dp[i-1][j]>dp[i][j-1])
i--;
else
j--;
}
return String.valueOf(LCSubSequence); // convert char array to string and return
}
}