Past Notes

All:
​
W8:
w9:
W10:
📗
​
GS Interview Questions:
​
1
//Search Tree
2
/*
3
 Instructions to candidate.
4
  1) Run this code in the REPL to observe its behaviour. The
5
   execution entry point is main().
6
  2) Implement the "put" and "contains" methods.
7
  3) Fix the "inOrderTraversal" method.
8
  4) Add additional relevant tests
9
  5) If time permits, try to improve your implementation.
10
*/
11
dln;
12
​
13
let _ = require("underscore");
14
​
15
class Node {}
16
​
17
function put(node, value) {
18
    // TODO implement me
19
}
20
​
21
function contains(node, value) {
22
    // TODO implement me
23
}
24
​
25
function inOrderTraversal(node) {
26
    return inOrderTraversalAcc(node, []);
27
}
28
​
29
function inOrderTraversalAcc(node, acc) {
30
    if (!node.value) {
31
        return acc;
32
    }
33
​
34
    inOrderTraversalAcc(node.left, acc);
35
    acc.push(node.value);
36
    inOrderTraversalAcc(node.right, acc);
37
    return acc;
38
}
39
​
40
function assert(condition) {
41
    if (!condition) throw new Error();
42
}
43
​
44
function testTree() {
45
    let tree = new Node();
46
    put(tree, 3);
47
    put(tree, 1);
48
    put(tree, 2);
49
    put(tree, 5);
50
    assert(!contains(tree, 0));
51
    assert(contains(tree, 1));
52
    assert(contains(tree, 2));
53
    assert(contains(tree, 3));
54
    assert(!contains(tree, 4));
55
    assert(contains(tree, 5));
56
    assert(!contains(tree, 6));
57
    assert(_.isEqual(inOrderTraversal(tree), [1, 2, 3, 5]));
58
}
59
​
60
function doTestsPass() {
61
    testTree();
62
    // TODO add more tests
63
}
64
​
65
/**
66
 * Main execution entry.
67
 */
68
doTestsPass();
69
console.log("Success!");
70
​
71
let _ = require("underscore");
72
​
73
class Node {}
74
​
75
function put(node, value) {
76
    if (!value) {
77
        return;
78
    }
79
​
80
    if (!node.value) {
81
        node.value = value;
82
        node.left = new Node();
83
        node.right = new Node();
84
    } else {
85
        if (value < node.value) {
86
            put(node.left, value);
87
        } else {
88
            put(node.right, value);
89
        }
90
    }
91
}
92
​
93
function contains(node, value) {
94
    if (!node || !value) {
95
        return false;
96
    } else if (node.value === value) {
97
        return true;
98
    } else if (node.value && value < node.value) {
99
        return contains(node.left, value);
100
    } else {
101
        return contains(node.right, value);
102
    }
103
}
104
​
105
function inOrderTraversal(node) {
106
    return inOrderTraversalAcc(node, []);
107
}
108
​
109
function inOrderTraversalAcc(node, acc) {
110
    if (!node.value) {
111
        return acc;
112
    }
113
​
114
    inOrderTraversalAcc(node.left, acc);
115
    acc.push(node.value);
116
    inOrderTraversalAcc(node.right, acc);
117
    return acc;
118
}
119
​
120
function assert(condition) {
121
    if (!condition) {
122
        throw new Error();
123
    }
124
}
125
​
126
function testTree() {
127
    let tree = new Node();
128
    put(tree, 3);
129
    put(tree, 1);
130
    put(tree, 2);
131
    put(tree, 5);
132
    assert(!contains(tree, 0));
133
    assert(contains(tree, 1));
134
    assert(contains(tree, 2));
135
    assert(contains(tree, 3));
136
    assert(!contains(tree, 4));
137
    assert(contains(tree, 5));
138
    assert(!contains(tree, 6));
139
    assert(_.isEqual(inOrderTraversal(tree), [1, 2, 3, 5]));
140
}
141
​
142
function testEmptyTree() {
143
    let emptyTree = new Node();
144
    assert(_.isEqual(inOrderTraversal(emptyTree), []));
145
}
146
​
147
function testNegative() {
148
    let negativeTree = new Node();
149
    put(negativeTree, -1);
150
    put(negativeTree, 11);
151
    put(negativeTree, -10);
152
    put(negativeTree, 50);
153
    assert(contains(negativeTree, -10));
154
    assert(contains(negativeTree, -1));
155
    assert(contains(negativeTree, 11));
156
    assert(contains(negativeTree, 50));
157
    assert(_.isEqual(inOrderTraversal(negativeTree), [-10, -1, 11, 50]));
158
}
159
​
160
function testDupes() {
161
    let dupeTree = new Node();
162
    put(dupeTree, 1);
163
    put(dupeTree, 2);
164
    put(dupeTree, 1);
165
    put(dupeTree, 2);
166
    assert(contains(dupeTree, 1));
167
    assert(contains(dupeTree, 2));
168
    assert(_.isEqual(inOrderTraversal(dupeTree), [1, 1, 2, 2]));
169
}
170
​
171
function testUndefined() {
172
    let undefinedTree = new Node();
173
    put(undefinedTree, undefined);
174
    assert(!contains(undefinedTree, undefined));
175
    assert(_.isEqual(inOrderTraversal(undefinedTree), []));
176
}
177
​
178
function testNull() {
179
    let nullTree = new Node();
180
    put(nullTree, null);
181
    assert(!contains(nullTree, null));
182
    assert(_.isEqual(inOrderTraversal(nullTree), []));
183
}
184
​
185
function doTestsPass() {
186
    testTree();
187
    testEmptyTree();
188
    testNegative();
189
    testDupes();
190
    testUndefined();
191
    testNull();
192
}
193
​
194
/**
195
 * Main execution entry.
196
 */
197
doTestsPass();
198
console.log("Success!");
199
//Second Smallest
200
/**
201
 * Returns the second smallest element in the array x.
202
 * Returns 0 if the array has fewer than 2 elements.
203
 */
204
function secondSmallest(x) {
205
    // todo: implement this function
206
    return 0;
207
}
208
​
209
/**
210
 * Returns true if all tests pass; otherwise, returns false.
211
 */
212
function doTestsPass() {
213
    // todo: add more test cases
214
    let testArrays = [[0], [0, 1]];
215
    let testResults = [0, 1];
216
​
217
    // Run through the tests and make assertions
218
    for (let i = 0; i < testArrays.length; i++) {
219
        if (secondSmallest(testArrays[i]) != testResults[i]) {
220
            return false;
221
        }
222
    }
223
    return true;
224
}
225
​
226
/**
227
 * Main execution entry.
228
 */
229
if (doTestsPass()) {
230
    console.log("All tests pass!");
231
} else {
232
    console.log("There are test failures.");
233
}
234
​
235
function secondSmallest(x) {
236
    // First check if the array is large enough
237
    if (x.length < 2) {
238
        return 0;
239
    }
240
​
241
    // Start these at infinity so that they're always bigger
242
    // than the input
243
    let smallest = Number.POSITIVE_INFINITY;
244
    let secondSmallest = Number.POSITIVE_INFINITY;
245
    let current;
246
​
247
    // Loop through the input and keep updating our
248
    // smallest and second smallest
249
    for (let i = 0; i < x.length; i++) {
250
        current = x[i];
251
        if (current < smallest) {
252
            secondSmallest = smallest;
253
            smallest = current;
254
        } else if (current < secondSmallest) {
255
            secondSmallest = current;
256
        }
257
    }
258
    return secondSmallest;
259
}
260
dln;
261
/**
262
 * Returns true if all tests pass; otherwise, returns false.
263
 */
264
function doTestsPass() {
265
    // todo: add more test cases
266
    let testArrays = [[], [0], [0, 1], [-1, 0, 1, -2, 2], [1, 1, 2]];
267
    let testResults = [0, 0, 1, -1, 1];
268
​
269
    // Run through the tests and make assertions
270
    for (let i = 0; i < testArrays.length; i++) {
271
        if (secondSmallest(testArrays[i]) != testResults[i]) {
272
            return false;
273
        }
274
    }
275
    return true;
276
}
277
​
278
/**
279
 * Main execution entry.
280
 */
281
if (doTestsPass()) {
282
    console.log("All tests pass!");
283
} else {
284
    console.log("There are test failures.");
285
}
Copied!

Part 2

Command Line Reference

Last modified 2d ago

Copy link

Contents

All:

W8:

W10:

GS Interview Questions:

All:

​

W8:

W10:

GS Interview Questions: