-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathcoding-test_result.txt
256 lines (189 loc) · 6.04 KB
/
coding-test_result.txt
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
Test 1 description: given an array of integers and a value, determine if there are any three
integers in the array whose sum equals the given value.
The integer array is 3, 7, 1, 2, 8, 4, 5
Use brute force method
There are 3 numbers sum up to 20
There are no 3 numbers sum up to 21
Sort it before attempting it
There are 3 numbers sum up to 20
There are no 3 numbers sum up to 21
Use Divide & Conquer and Binary way of brute force method
There are 3 numbers sum up to 20
There are no 3 numbers sum up to 21
Use brute force but simple recursive method
There are 3 numbers sum up to 20
There are no 3 numbers sum up to 21
Test 2 description: given a list of intervals, merge all the overlapping intervals to produce a list
that has only mutually exclusive intervals.
1...3, 4...6, 5...8, 9...12, 10...15, 14...16, 17...18
after merged
1...3, 4...8, 9...16, 17...18
Test 3 description: search for a given number in a sorted array, with unique elements,
that has been rotated by some arbitrary number. Return -1 if the number does not exist.
On none-rotated list
1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
data 3, key = 1
data 7, key = 3
data 8, key = -1
data 17, key = 8
On rotated list
15, 17, 19, 1, 3, 5, 7, 9, 11, 13,
data 3, key = 4
data 7, key = 6
data 8, key = -1
data 17, key = 1
Test 4 description: given a positive integer, target, print all possible combinations of
positive integers that sum up to the target number.
find all sum combination of 5
4, 1
3, 2
3, 1, 1
2, 3
2, 2, 1
2, 1, 1, 1
1, 4
1, 3, 1
1, 2, 1, 1
1, 1, 1, 1, 1
Test 5 description: reverse the order of words in a given sentence (an array of characters).
String = "1 23 45 6 789"
Reversing words, result string = "789 6 45 23 1"
Reversing words again, result string = "1 23 45 6 789"
String = " abc xyz "
Reversing words, result string = " xyz abc "
Reversing words again, result string = " abc xyz "
Test 6 description: find total ways to achieve a given sum with `n` throws of dice having `k` faces
if throw is 2 and sum value is 10, then we have the following: (6, 4), (4, 6), (5, 5).
Number of throws = 2, desired sum = 10
4, 6
5, 5
6, 4
Number of throws = 3, desired sum = 8
1, 1, 6
1, 2, 5
1, 3, 4
1, 4, 3
1, 5, 2
1, 6, 1
2, 1, 5
2, 2, 4
2, 3, 3
2, 4, 2
2, 5, 1
3, 1, 4
3, 2, 3
3, 3, 2
3, 4, 1
4, 1, 3
4, 2, 2
4, 3, 1
5, 1, 2
5, 2, 1
6, 1, 1
Test 7 description: given a double, x and an integer n, write a function to calculate x raised to the power n.
2 ^ 5 = 32.000000
3 ^ 4 = 81.000000
1.5 ^ 3 = 3.375000
2 ^ -2 = 0.250000
Test 8 description: given that integers are read from a data stream. Find median of elements
read so for in efficient way. For simplicity assume there are no duplicates.
Adding 5, median = 5.00
Adding 15, median = 10.00
Adding 1, median = 5.00
Adding 3, median = 4.00
Adding 2, median = 3.00
Adding 4, median = 3.50
Test 9 description: the permutations of string ABC is "ABC ACB BAC BCA CBA CAB".
ABC
BAC
CBA
BCA
CBA
CAB
Test 10 description: implementing AVL (Adelson-Velsky and Landis) self-balancing binary search tree.
Adding a list of integer arrays in the following order1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
The tree topology:
8 (L=4, R=3)
10 (L=1, R=2)
12 (L=1, R=1)
13 (L=0, R=0)
-
-
11 (L=0, R=0)
-
-
9 (L=0, R=0)
-
-
3 (L=2, R=3)
6 (L=2, R=1)
7 (L=0, R=0)
-
-
5 (L=1, R=0)
-
4 (L=0, R=0)
-
-
2 (L=1, R=0)
-
1 (L=0, R=0)
-
-
Test 11 description: finding the largest possible sum of a contiguous subarray, within
a given one-dimensional array A[1…n] of numbers.
The integer array is -4, 2, -5, 1, 2, 3, 6, -5, 1
Maximum subarray is 1, 2, 3, 6
Test 12 description: Find the rotating point of an array that is sorted, but the starting point can be in middle.
The integer array1 is 5, 1, 2, 3, 4
The rotating point is at index 1 and value is 1
The integer array2 is 4, 5, 6, 1, 2, 3
The rotating point is at index 3 and value is 1
The integer array3 is 4, 5, 6, 7, 8, 0, 1, 2, 3
The rotating point is at index 5 and value is 0
Test 13 description: check if a binary tree is binary search tree.
root1 is a binary search tree
The tree topology:
2 (L=1, R=2)
3 (L=0, R=1)
4 (L=0, R=0)
-
-
-
1 (L=0, R=0)
-
-
root2 is not a binary search tree
The tree topology:
4 (L=2, R=1)
5 (L=0, R=0)
-
-
2 (L=0, R=1)
6 (L=0, R=0)
-
-
-
Test 14 description: check that two lists are combined into a final list in a 1st come 1st serve ordering.
list1 = 17, 8, 24
list2 = 12, 19, 2
list3 = 17, 8, 12, 19, 24, 2
list1 and list2 are served in order
list4 = 1, 3, 5
list5 = 2, 4, 6
list6 = 1, 2, 4, 6, 5, 3
list4 and list5 are not served in order
Test 15 description: given two strings s1 and s2, find the length of the longest substring common in both the strings.
The common longest substring of "abdca" and "cbda" is bd
The common longest substring of "passport" and "ppsspt" is ssp
Test 16 description: given a sequence, find the length of its Longest Palindromic Subsequence (or LPS).
In a palindromic subsequence, elements read the same backward and forward.
The longest palinidromic subsequence of "axbba" is 4
The longest palinidromic subsequence of "abdbca" is 5
The longest palinidromic subsequence of "cddpd" is 3
The longest palinidromic subsequence of "pqr" is 1
The longest palinidromic subsequence of "abbdcacb" is 5
Test 17 description: given two strings s1 and s2, find the length of the longest subsequence which is common in both the strings
The longest substring of "abdca" and "cbda" is 3
The longest substring of "passport" and "ppsspt" is 5
The longest substring of "abc" and "xzabtttabcg" is 3