· 6 years ago · Mar 12, 2020, 04:58 AM
1============================
2 1. Flatten array
3============================
4Flatten array. This array can have multiple types: {}, [], "", undefined, null, 123 are all valid types inside the array.
5
6In JavaScript, write a function that takes an array as input that can contain both ints and more arrays (which can also contain an array or int) and return the flattened array.
7ex. [1, [2, [ [3, 4], 5], 6]] => [1, 2, 3, 4, 5, 6]
8
9function flatten(array) {
10 if (!Array.isArray(array)) {
11 return array;
12 }
13
14 return array.reduce((acc, cur) => {
15 if(cur){
16 acc = acc.concat(flatten(cur));
17 }
18 return acc;
19 }, []);
20}
21
22
23==============================
24 2. Decode
25==============================
26
27Given a grid of characters output a decoded message. The message for the following would be IROCLED. (diagonally down right and diagonally up right if you can't go further .. you continue doing this)
28
29[
30 ['I', 'B', 'C', 'A', 'L', 'K', 'A'],
31 ['D', 'R', 'F', 'C', 'A', 'E', 'A'],
32 ['G', 'H', 'O', 'E', 'L', 'A', 'D']
33]
34
35var decode = (grid) => {
36 let [row,col] = [0, 0];
37 let str = "";
38 let isDown = true;
39 if(grid.length === 1) return grid[0].join("");
40 while(col<=grid[0].length-1){
41 str += grid[row][col];
42 col++;
43 if(row === grid.length-1){
44 isDown = false;
45 } else if (row === 0){
46 isDown = true;
47 }
48 row = isDown ? row + 1 : row - 1;
49 }
50 return str;
51}
52
53==============================
54 3. New index
55==============================
56Given an input array and another array that describes a new index for each element, mutate the input array so that each element ends up in their new index. Discuss the runtime of the algorithm and how you can be sure there won't be any infinite loops.
57
58var newIndex = (arr,indices)=>{
59 return indices.map((curr,index)=>arr[indices.indexOf(index)]);
60}
61
62==============================
63 4. Debounce & Throttling
64==============================
65Debounce: debouncing ensures that exactly one signal is sent for an event that may be happening several times. help performance
66Usage:
67* onInput in the textbox, Amazon Translate, wait 0.5 seconds to save what user typed.
68* scroll, resize event handler, autosave
69
70
71Throttling: restricts the frequency of calls that a function receives to a fixed time interval. It is used to ensuring that the target function is not invoked more often than the specified delay. last invocation to happen after the throttle is over.
72Usage:
73* Service API Throttling. 1 min makes 3 calls. List view have describe calls.
74* button spam click, API call, mousemove/touchmove event handler
75
76const debounce = (fn, delay) => {
77 let timeOut;
78 return function(...args){
79 clearTimeout(timeOut);
80 timeout = setTimeout(() => fn.apply(this, args), delay)
81 }
82}
83
84const throttling = (fn, limit) => {
85 let isThrottle = false;
86 return function(...args){
87 if(!isThrottle){
88 isThrottle = true;
89 fn.apply(this, args);
90 setTimeout(() => isThrottle = false, limit)
91 }
92
93 }
94}
95
96const throttling_last = (fn, delay) => {
97 let lastTime;
98 let timeOut;
99 return function(...args){
100 if(!lastTime){
101 fn.apply(this, args);
102 lastTime = Date.now();
103 }else{
104 clearTimeout(timeOut);
105 timeOut = setTimeout(()=>{
106 fn.apply(this, args);
107 lastTime = Date.now();
108 },delay-(Date.now()-lastTime))
109 }
110 }
111}
112
113
114const throttling_all = (fn, limit) => {
115 let isInitiated = false;
116 let interval;
117 let count = 0;
118 return function(...args){
119 count++;
120 if(!isInitiated){
121 isInitiated = true;
122 interval = setInterval(() => {
123 fn.apply(this, args);
124 count--;
125 if(count === 0) {
126 clearInterval(interval);
127 isInitiated = false;
128 }
129 }, limit)
130 }
131 }.bind(this);
132
133
134==================================
135search tool - internship
136==================================
137If you were building a search tool and wanted search results to pop up as you typed but the server call was taxing, write a function that gets called on every key down but calls the server when the user stops typing for 400ms.
138
139https://www.glassdoor.com/Interview/If-you-were-building-a-search-tool-and-wanted-search-results-to-pop-up-as-you-typed-but-the-server-call-was-taxing-write-a-QTN_835901.htm
140
141
142==============================
143 5. Hover
144==============================
145Using HTML and CSS, show how you would create an image that would display another image (aligned to the bottom, right) when the user hovers over the image.
146
147ex. The Facebook "edit profile picture" icon
148
149<img src="a.jpg" onmouseover="this.src='b.jpg'" onmouseout="this.src='a.jpg'" />
150
151CSS
152a.logo {
153 display:block;
154 width: 100px;
155 height: 100px;
156 background: url(/path/to/logo.png) no-repeat center center;
157 background-size: contain;
158}
159
160a.logo:hover {
161 background-image: url(/path/to/logo-hover.png);
162}
163HTML
164<a href="#" class="logo"></a>
165
166
167var img = document.getElementById('myImg');
168
169img.onmouseout = function () {
170 this.src = 'b.jpg';
171};
172
173img.onmouseover = function () {
174 this.src = 'a.jpg';
175};
176
177
178==================================
179 6. design/code a poll widget
180==================================
181Use case:
1821. Start a new poll with name, choices.
1832. Vote for a choice.
1843. Can't re-vote.
1854. View total votes.
1865. End a poll.
187
188API:
189POST /newPoll
190{
191 name:string,
192 choices:string[] - name array,
193 creatorID: number
194}
195Response:
196{
197 pollID: number;
198}
199
200GET /poll
201{
202 pollID: number
203}
204Response:
205{
206 closed: boolean;
207 choices:{choice:vote}
208}
209
210POST /vote
211{
212 selectedChoice: string[]
213 userID: number
214}
215{
216 success: boolean;
217 choices:{choice:vote}
218}
219
220POST /closePoll
221{
222 pollID: number;
223 userID: number;
224}
225{
226 success: boolean;
227 finalWinner: name;
228}
229
230Database:
231PollID, creatorID, {options:votes},votedUserID,closed
232PollID,votedUserID, options
233
234
235name
236radio group
237progress bar - percentage caculation
238
239<progress> doesn't support IE < 9.0.
240<input class="color-input" type="radio" name="colors" value="red">Pink
241<progress value="10" max="20"></progress>
242let selected = document.querySelector('input:checked').value;
243
244==================================
245 7.Design Search Typeahead
246==================================
247The architecture interview was more about how you would approach a front end problem and how you would structure your code, whether it's about HTML, CSS or Javascript. This one didn't seem to be too hard, if you have enough experience with layouts and front end issues, it shouldn be fine.
248
2491. Use cases
250Given a query, give me 10 most frequent search terms with the query as strict prefix
251Given a search term, update the frequencies.
252Spelling check.
253low latency, high availabilty, eventual consistency
254
2552. Estimation
256upperbound: 4 Billion queries/day * 25 letters/query = 100 Billion
257Write: 100 * 10% = 10 Billion / 1024/1024/1024 = 9GB / day
258
2593. High level Graph: client -> web server -> Cache -> DB
260
2614. API & Database schema
262Read: List(string) getTopSuggestions(string currentQuery)
263GET /suggestions {q: string} => {suggestions: string[]}
264
265Write: void updateSuggestions(string searchTerm)
266POST /suggestions {q: string}
267
268Data structure: Trie Tree - Trie ( in memory ) + Serialized Trie ( on disk ).
269Node{
270 top10:[{query: frequency}] || [node]
271 childrenMap
272}
273Anytime, a node’s frequency gets updated, we traverse back from the node to its parent till we reach the root to check if current query should be in top 10.
274
275Or DB
276Word count table: keyword | hitCount
277Prefix table: prefix | keywords list
278
279Data collections service
280* Once per week aggregate data.
281* Sampling: update with 1/10,000 probability.
282* Offline update: Instead of updating frequency of a single word every time it appears, updating frequency of a single word if it appears in a specific time period (100ms) or query amount (100 queries).
283* All in-memory trie must have already been serialized. Read QPS already really high. Do not write to in-memory trie directly.
284
285
2865. Scale:
287Client -> LB -> Multiple web server
288
289How to reduce response time?
290Cache result: Front-end browser cache the results
291Pre-fetch: Fetch the latest 1000 results
292
293
294[Sharding]
295sharding till the second or third level and we optimize for load here.
2961) Lets also say that we have the data around the expected load for every prefix. We keep traversing the 2 letter prefixes in order ('a', 'aa', 'ab', 'ac',...) and break when the total load exceeds an threshold load and assign that range to a shard.
297We will need to have a master which has this mapping with it, so that it can route a prefix query to the correct shard.
298
2992) Use consistent hashing to decide which machine a particular string belongs to.
300
301[Replica]
302we can maintain multiple replica of each shard and an update goes to all replicas. The read can go to multiple replicas (not necessarily all) and uses the first response it gets.
303Update replica:
3041. the replica which comes back up can read the whole data from one of the older working replica while keeping the new incoming writes in a queue.
3052. There is a queue with every server which contains the changelog or the exact write query being sent to them. The replica can request any of the other replicas in its shard for all changelog since a particular timestamp and use that to update its trie.
306
307
308
309==================================
310 8. animateRight
311==================================
312Implement funtion animateRight(element, duration, distance) to make element smoothly move given distance in given time.
313 let ele = document.createElement('p');
314 ele.textContent = "Hello FB";
315 document.body.appendChild(ele);
316 const animateRight = (element, duration, distance) => {
317 const startTime = new Date().getTime();
318 let endTime = null;
319 const ani = setInterval(()=> {
320 endTime = new Date().getTime();
321 const percent = (endTime - startTime) / duration;
322 if( percent>= 1){
323 clearInterval(ani);
324 }
325 element.style.marginLeft = percent * distance + "px";
326 }, 20);
327 }
328 animateRight(ele,1000,300)
329---------------------------------------------------------------------
330 let ele = document.createElement('p');
331 ele.textContent = "Hello FB";
332 document.body.appendChild(ele);
333 var getNumAndUnit = (distance) => {
334 const unit = distance.match(/\D/g)[0];
335 const num = parseFloat(distance.match(/\d+/g)[0]);
336 return [num, unit];
337 }
338
339 var getCurrMarginLeft = () => {
340 return getNumAndUnit(window.getComputedStyle(ele).marginLeft)[0];
341 }
342
343 var animateRight = (ele, duration, distance) => {
344 let [distance_num, unit] = getNumAndUnit(distance);
345 let move = distance_num/duration;
346 let initialLeft = getCurrMarginLeft();
347 let interval;
348 interval = setInterval(()=>{
349 let currLeft = getCurrMarginLeft() + move;
350 ele.style.marginLeft = currLeft + 'px';
351 if(currLeft- initialLeft === distance_num){
352 clearInterval(interval);
353 }
354 },1000);
355
356 }
357 animateRight(ele,5,'300px')
358
359
360==================================
361 9. DOMStore
362==================================
363Implement DOMStore：
364const el = document.getElementById('my-element')
365DOMStore.set(el, 'chandler')
366DOMStore.get(el)
367DOMStore.has(el)
368
369Followup: how to optimize? Possible solution: hash?
370
371
372
373==================================
374 10. lc roman to integer
375==================================
376
377
378
379==============================
380 Async
381==============================
382Basic JavaScript async stuff (you should know event bubbling, debounce (its variant)... know how to code it). It would be a good idea to be aware of JS closure as well.
383
384 I was asked to write how I would implement visual UI features, array search/mutation algorithms, and JS performance functions.
385
386
387
388
389*** SYSTEM DESIGN ***
390
391Design messaging system ---- 我觉得这个偏backend, 因为数据量比较大，db设计也比较复杂，感觉后端很有考点。
392Design instagram --- 这个我觉得像API design， 因为我觉得和news feed很像。。。
393Design news feed API --- 这个肯定是API咯
394Design POI, Design typeahead --- 这两个都用比较特别的data structure来存储数据 （quadtree/geohash, trie), 所以应该偏后端
395Design web-crawler --- 这个应该也是后端， 因为本身就不是面对用户的产品。
396Design memcache --- 这个应该也是后端
397Design search system --- 这个像API， 因为前端蛮多use case的， 觉得API有些讲头
398Design internatlionalization service --- 这个也是API， db没啥可讲。。。。
399设计一个系统, 返回用户最近7天听过最多的歌 --- 这个也像是backend, 因为use case比较单一，难点在后端.