PageSourceSearch

https://okc1.github.io/

html okc1.github.io collected 2026-10-03 09:42:31 UTC 34,954 bytes, 1,159 lines download raw bytes

1
2<!DOCTYPE html>
3<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
4<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
5<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
6<head>
7  <meta charset="utf-8">
8  <title>Woodstock Blog</title>
9  <meta name="author" content="Kevin Durant">
10
11  
12  <meta name="description" content="Question link Given a trie data struture, implement add() and search() method, which support wildcard matching. eg. If trie contains [&ldquo;cool& &hellip;">
13  
14
15  <!-- http://t.co/dKP3o1e -->
16  <meta name="HandheldFriendly" content="True">
17  <meta name="MobileOptimized" content="320">
18  <meta name="viewport" content="width=device-width, initial-scale=1">
19
20  
21  <link rel="canonical" href="http://www.shuati123.com/">
22  <link href="/favicon.png" rel="icon">
23  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
24  <link href="/atom.xml" rel="alternate" title="Woodstock Blog" type="application/atom+xml">
25  
25<script src="/javascripts/modernizr-2.0.js"></script>
25
26  
26<script src="//ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
26
27  
27<script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
27
28  
28<script src="/javascripts/octopress.js" type="text/javascript"></script>
28
29  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
30<link href="//fonts.googleapis.com/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
31<link href="//fonts.googleapis.com/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
32
33  
34
35</head>
36
37<body   >
38  <header role="banner"><hgroup>
39  <h1><a href="/">Woodstock Blog</a></h1>
40  
41    <h2>a tech blog for general algorithmic interview questions</h2>
42  
43</hgroup>
44
45</header>
46  <nav role="navigation"><ul class="subscription" data-subscription="rss">
47  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
48  
49</ul>
50  
51<form action="https://www.google.com/search" method="get">
52  <fieldset role="search">
53    <input type="hidden" name="sitesearch" value="www.shuati123.com">
54    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
55  </fieldset>
56</form>
57  
58<ul class="main-navigation">
59  <li><a href="/">Blog</a></li>
60  <li><a href="/blog/archives">Archives</a></li>
61</ul>
62
63</nav>
64  <div id="main">
65    <div id="content">
66      <div class="blog-index">
67  
68  
69  
70    <article>
71      
72  <header>
73    
74      <h1 class="entry-title"><a href="/blog/2017/05/22/Trie-Wildcard-String-Matching/">[Question] Trie Wildcard String Matching</a></h1>
75    
76    
77      <p class="meta">
78        
79
80
81
82
83<time class='entry-date' datetime='2017-05-22T00:00:00-07:00'><span class='date'><span class='date-month'>May</span> <span class='date-day'>22</span><span class='date-suffix'>nd</span>, <span class='date-year'>2017</span></span> <span class='time'>12:00 am</span></time>
84        
85      </p>
86    
87  </header>
88
89
90  <div class="entry-content"><h1>Question</h1>
91
92<p><a href="https://discuss.leetcode.com/topic/54332/wildcard-on-trie/2">link</a></p>
93
94<blockquote><p>Given a trie data struture, implement add() and search() method, which support wildcard matching.</p></blockquote>
95
96<p>eg. If trie contains [&ldquo;cool&rdquo;, &ldquo;kid&rdquo;, &ldquo;kindle&rdquo;, &ldquo;kind&rdquo;]</p>
97
98<p>These would match: &ldquo;co<em>l&rdquo;, &ldquo;kind&rdquo;, &ldquo;</em>**&rdquo;</p>
99
100<p>These won&rsquo;t: &ldquo;<em>*&rdquo;, &ldquo;kid</em>&rdquo;, &ldquo;coo&rdquo;</p>
101
102<h1>Solution</h1>
103
104<p>First, know how to build a trie, then know how to search in Trie. This could be tricky. Do Read On!</p>
105
106<ol>
107<li>Trie (root) start with an empty node.</li>
108<li>When do searching, <strong>ALWAYS assumes that current TrieNode is matched</strong>. I.e. do not check value of current TrieNode. Instead, check current TrieNode&rsquo;s children, and find a match.</li>
109<li>The only case <strong>you return true</strong>, is when matching reaches current TrieNode, and <strong>current TrieNode is an terminating node for a word</strong>.</li>
110<li>Be careful and <strong>do not confuse yourself</strong> for which node you gonna match, and when you return true.</li>
111</ol>
112
113
114<p>Read the code below. If you still have a hard time, read #2 and #3 above, again.</p>
115
116<h1>Code</h1>
117
118<pre><code>public boolean solve(TrieRoot trie, String word) {
119    if (word == null || word.length() == 0) {
120        return false;
121    }
122    return matchFromChildren(trie.getRoot(), word, 0);
123}
124
125private boolean matchFromChildren(TrieNode node, String word, int index) {
126    // [important note] 
127    // regardless of the value of node.letter, match word[index...] from node.children
128
129    if (index &gt; word.length()) {
130        // impossible to reach here
131        return false;
132    } else if (index == word.length()) {
133        // word is now fully matched, check if isTerminalNode(node)
134        return node.isEndOfWord();
135    }
136
137    char curLetter = word.charAt(index);
138    if (curLetter == '*') {
139        for (TrieNode child: node.getAllChildren()) {
140            if (matchFromChildren(child, word, index + 1)) {
141                return true;
142            }
143        }
144        return false;
145    } else {
146        TrieNode nextNode = node.getChild(curLetter);
147        if (nextNode == null) {
148            return false;
149        } else {
150            return matchFromChildren(nextNode, word, index + 1);
151        }
152    }
153}
154</code></pre>
155</div>
156  
157  
158
159
160    </article>
161  
162  
163    <article>
164      
165  <header>
166    
167      <h1 class="entry-title"><a href="/blog/2017/05/13/dutch-national-flag/">[Question] Dutch National Flag Problem</a></h1>
168    
169    
170      <p class="meta">
171        
172
173
174
175
176<time class='entry-date' datetime='2017-05-13T00:00:00-07:00'><span class='date'><span class='date-month'>May</span> <span class='date-day'>13</span><span class='date-suffix'>th</span>, <span class='date-year'>2017</span></span> <span class='time'>12:00 am</span></time>
177        
178      </p>
179    
180  </header>
181
182
183  <div class="entry-content"><h1>Question</h1>
184
185<p><a href="https://en.wikipedia.org/wiki/Dutch_national_flag_problem">link</a></p>
186
187<blockquote><p>Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.</p></blockquote>
188
189<pre><code>Example
190Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
191Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
192</code></pre>
193
194<h1>Solution</h1>
195
196<p>3-way sort: <a href="http://www.geeksforgeeks.org/3-way-quicksort-dutch-national-flag/">http://www.geeksforgeeks.org/3-way-quicksort-dutch-national-flag/</a></p>
197
198<h1>Code</h1>
199
200<pre><code>public int[] threePointerSort(int[] input) {
201    if (input == null || input.length &lt;= 1) {
202        return input;
203    }
204
205    // left is at the leftmost non-0 position
206    // right is at rightmost non-2
207    // mid is currently being evaluated (before mid, it's sorted)
208    int left = 0, right = input.length - 1;
209    int mid = left;
210
211    while (mid &lt;= right) {
212        if (input[mid] &gt; 1) {
213            Common.swap(input, mid, right);
214            right--;
215        } else if (input[mid] &lt; 1) {
216            Common.swap(input, left, mid);
217            left++;
218            mid++;
219        } else {
220            mid++;
221        }
222    }
223
224    return input;
225}
226</code></pre>
227</div>
228  
229  
230
231
232    </article>
233  
234  
235    <article>
236      
237  <header>
238    
239      <h1 class="entry-title"><a href="/blog/2016/08/01/how-to-design-logging/">[Design] How to Design Logging</a></h1>
240    
241    
242      <p class="meta">
243        
244
245
246
247
248<time class='entry-date' datetime='2016-08-01T00:00:00-07:00'><span class='date'><span class='date-month'>Aug</span> <span class='date-day'>1</span><span class='date-suffix'>st</span>, <span class='date-year'>2016</span></span> <span class='time'>12:00 am</span></time>
249        
250      </p>
251    
252  </header>
253
254
255  <div class="entry-content"><h1>Logging</h1>
256
257<p>Conecting between <strong>information</strong> and <strong>knowledge</strong>.</p>
258
259<ol>
260<li>Information: it&rsquo;s just bits</li>
261<li><strong>Knowledge</strong>: drives product direction</li>
262</ol>
263
264
265<h2>Logging is all about Event</h2>
266
267<p>Q1. shall we log it live? what should we log? how to do it (on different platforms)?</p>
268
269<p>Not live. Do it asynchronously.</p>
270
271<p><strong>Demand and product design</strong> drives logging.</p>
272
273<p>Logs represent event, so all your logging should be <strong>based around the events</strong>.</p>
274
275<blockquote><p>eg. who click the button, the user ID, but do not log the age, because you can find it somewhere else!</p></blockquote>
276
277<h2>Think about &ldquo;what&rdquo; to log and &ldquo;why&rdquo;</h2>
278
279<p><strong>&ldquo;How&rdquo; is just coding</strong>. Happy Logging!</p>
280</div>
281  
282  
283
284
285    </article>
286  
287  
288    <article>
289      
290  <header>
291    
292      <h1 class="entry-title"><a href="/blog/2016/07/31/mvc-mvp-mvvm/">[Design] MVC, MVP and MVVM</a></h1>
293    
294    
295      <p class="meta">
296        
297
298
299
300
301<time class='entry-date' datetime='2016-07-31T00:00:00-07:00'><span class='date'><span class='date-month'>Jul</span> <span class='date-day'>31</span><span class='date-suffix'>st</span>, <span class='date-year'>2016</span></span> <span class='time'>12:00 am</span></time>
302        
303      </p>
304    
305  </header>
306
307
308  <div class="entry-content"><h1>MVC Pattern</h1>
309
310<p>Model-View-Controller.</p>
311
312<p>The model and controller logic are <strong>decoupled from user interface (view)</strong>.</p>
313
314<p><img class="middle" src="/assets/images/mvc-pattern.png"></p>
315
316<ol>
317<li><p>Model</p>
318
319<p> business model + <strong>data access operations</strong> (i.e. data model)</p></li>
320<li><p>View</p>
321
322<p> <strong>only for displaying data</strong> (received from the controller, transforms the model into UI)</p></li>
323<li><p>Controller <strong>(IMPORTANT)</strong></p>
324
325<p> <strong>process incoming requests</strong>. It receives input from users via the View, then process the user&rsquo;s data with the help of Model and passing the results back to the View. Typically, it acts as the coordinator between the View and the Model.</p></li>
326</ol>
327
328
329<h2>example</h2>
330
331<p>Ruby on Rails, Spring Framework, Apple iOS Development and ASP.NET MVC.</p>
332
333<p>Softwares (not web apps).</p>
334
335<h1>MVP pattern</h1>
336
337<p>separate the presentation layer from the logic</p>
338
339<p>The Presenter is responsible for handling all UI events on behalf of the view.</p>
340
341<p><img class="middle" src="/assets/images/mvp-pattern.png"></p>
342
343<p>Unlike view and controller, view and presenter are completely decoupled from each other’s and communicate to each other’s by an interface.</p>
344
345<p>Also, presenter does not manage the incoming request traffic as controller.</p>
346
347<h2>Key Points about MVP</h2>
348
349<ol>
350<li><p>User interacts with the View.</p></li>
351<li><p>There is one-to-one relationship between View and Presenter means one View is mapped to only one Presenter.</p></li>
352<li><p>View has a reference to Presenter but View has not reference to Model.</p></li>
353<li><p>Provides two way communication between View and Presenter.</p></li>
354</ol>
355
356
357<h2>example</h2>
358
359<p>Android, ASP.NET Web Forms applications</p>
360
361<h1>MVVM pattern</h1>
362
363<p>This pattern supports two-way data binding between view and View model.</p>
364
365<p>This enables automatic propagation of changes, within the state of view model to the View.</p>
366
367<p>Typically, <strong>the view model uses the observer pattern</strong>
367 to notify changes in the view model to model.</p>
368
369<p><img class="middle" src="/assets/images/mvvm-pattern.png"></p>
370
371<h2>details</h2>
372
373<p>The View Model is responsible for exposing methods, commands, and other properties that helps to maintain the state of the view, manipulate the model as the result of actions on the view, and trigger events in the view itself.</p>
374
375<h2>Key Points about MVVM</h2>
376
377<ol>
378<li><p>User interacts with the View.</p></li>
379<li><p>There is many-to-one relationship between View and ViewModel means many View can be mapped to one ViewModel.</p></li>
380<li><p>View has a reference to ViewModel but View Model has no information about the View.</p></li>
381<li><p>Supports two-way data binding between View and ViewModel.</p></li>
382</ol>
383
384
385<h2>example</h2>
386
387<p>Ember.js, WPF, Silverlight</p>
388
389<h1>Ref</h1>
390
391<p>Main: <a href="http://www.dotnet-tricks.com/Tutorial/designpatterns/2FMM060314-Understanding-MVC,-MVP-and-MVVM-Design-Patterns.html">http://www.dotnet-tricks.com/Tutorial/designpatterns/2FMM060314-Understanding-MVC,-MVP-and-MVVM-Design-Patterns.html</a></p>
392
393<p>TLDR: <a href="http://www.beyondjava.net/blog/model-view-whatever/">http://www.beyondjava.net/blog/model-view-whatever/</a></p>
394</div>
395  
396  
397
398
399    </article>
400  
401  
402    <article>
403      
404  <header>
405    
406      <h1 class="entry-title"><a href="/blog/2016/07/11/design-twitter/">[Design] Design Twitter</a></h1>
407    
408    
409      <p class="meta">
410        
411
412
413
414
415<time class='entry-date' datetime='2016-07-11T00:00:00-07:00'><span class='date'><span class='date-month'>Jul</span> <span class='date-day'>11</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>12:00 am</span></time>
416        
417      </p>
418    
419  </header>
420
421
422  <div class="entry-content"><h1>System design evaluation form</h1>
423
424<ol>
425<li>work solution</li>
426<li>special cases</li>
427<li>analysis</li>
428<li>trade off</li>
429<li>knowledge base</li>
430</ol>
431
432
433<h1>Design guideline: 4S</h1>
434
435<ol>
436<li><p>Scenario</p>
437
438<p> ask, features, qps, DAU, interfaces</p></li>
439<li><p>Service</p>
440
441<p> split, application, module</p></li>
442<li><p>Storage</p>
443
444<p> schema, data, sql, NoSql, file system</p></li>
445<li><p>Scale</p>
446
447<p> sharding, optimize, special case</p></li>
448</ol>
449
450
451<h1>Scenario</h1>
452
453<h2>DAU?</h2>
454
455<p>Whta&rsquo;s the DAU/MAU rate?</p>
456
457<p>Chatting apps like wechat/whatapp has a rate of around 75%, but facebook/twitter is lower at 60%.</p>
458
459<h2>Enumerate the functions</h2>
460
461<ol>
462<li>registration</li>
463<li>user profile display/edit</li>
464<li>upload image/video</li>
465<li>search</li>
466<li>post a tweet</li>
467<li>share a tweet</li>
468<li>timeline</li>
469<li>newsfeed</li>
470<li>follow/unfollow</li>
471</ol>
472
473
474<h2>QPS</h2>
475
476<ol>
477<li><p>concurrent user</p>
478
479<p> 150M user * 60 query/user / 60<em>60</em>24s = average QPS = 100K</p>
480
481<p> <strong>peak QPS = 3 * average QPS = 300K</strong></p>
482
483<p> fast growing product = 2 * peak QPS = 600K</p></li>
484<li><p>read qps: 300K QPS</p></li>
485<li>write qps: 5K QPS</li>
486</ol>
487
488
489<p>On average, <strong>a web server support around 1000 QPS</strong>, thus in this case, we need 300 servers to support the system.</p>
490
491<h1>Service</h1>
492
493<h2>4 services for Twitter</h2>
494
495<p><img class="middle" src="/assets/images/jiuzhang-four-service.png"></p>
496
497<ol>
498<li>user service
499
500<ol>
501<li>register</li>
502<li>login</li>
503</ol>
504</li>
505<li>tweet service
506
507<ol>
508<li>post tweet</li>
509<li>news feed</li>
510<li>timeline</li>
511</ol>
512</li>
513<li>media service
514
515<ol>
516<li>upload image</li>
517<li>upload video</li>
518</ol>
519</li>
520<li>friendship service
521
522<ol>
523<li>follow</li>
524<li>upfollow</li>
525</ol>
526</li>
527</ol>
528
529
530<h1>Storage</h1>
531
532<ol>
533<li><p>SQL</p>
534
535<p> <strong>Good for</strong> accurate, small amount of data, more read than write.
536 user table</p></li>
537<li><p>NoSQL</p>
538
539<p> <strong>Good for</strong> large amount of read/write, high scalability.
540 tweets
541 social graph (follower)</p></li>
542<li><p>File System</p>
543
544<p> <strong>Good for</strong> media files
545 photo, video</p></li>
546</ol>
547
548
549<h2>Select the right DB</h2>
550
551<p><img class="middle" src="/assets/images/jiuzhang-db-selection.png"></p>
552
553<p><strong>Question: can we use file system for tweets</strong>?</p>
554
555<p>No, it&rsquo;s hard to query. Eg. query all tweets of my friends.</p>
556
557<h2>Design data schema</h2>
558
559<p>(optional) 3 tables needed:</p>
560
561<ol>
562<li>user table</li>
563<li>tweet table</li>
564<li>friendship table: this is not as straight forward, as it shall contain double directions info</li>
565</ol>
566
567
568<p><img class="middle" src="/assets/images/jiuzhang-data-schema.png"></p>
569
570<h1>Important: News Feed</h1>
571
572<h2>pull model</h2>
573
574<p>Read top 50 feeds from top 100 friends, then merge sort by date. (note that user is getting sync-blocked here).</p>
575
576<p>Post tweet is simple 1 DB write.</p>
577
578<p><strong>This design is bad, because file-system/DB read is slow</strong>. If you have N friends, you query O(N) DB queries. <strong>It&rsquo;s too slow (and user is getting sync-blocked, too)</strong>. We should have, ideally, &lt;= 7 DB queries per web page.</p>
579
580<p><img class="middle" src="/assets/images/jiuzhang-pull-diagram.png"></p>
581
582<p><img class="middle" src="/assets/images/jiuzhang-pull-code.png"></p>
583
584<h3>problem</h3>
585
586<ol>
587<li>synchronously block user from getting news feed</li>
588<li>too many DB reads</li>
589</ol>
590
591
592<h2>push model</h2>
593
594<p>Each person have a list storing new feeds. When friend post tweet, <strong>fanout</strong> to my feed list.</p>
595
596<p>When I read, I simply read top 100 from the feed list. <strong>So read is 1 DB read</strong>.</p>
597
598<p>Post tweet is N DB writes, which is slow. <strong>However this is done async, so it does not matter</strong>.</p>
599
600<p><img class="middle" src="/assets/images/jiuzhang-push-diagram.png"></p>
601
602<p><img class="middle" src="/assets/images/jiuzhang-push-code.png"></p>
603
604<p>One example of async implementation: <strong>RabbitMQ</strong></p>
605
606<h1>Scale</h1>
607
608<h2>optimize pull model</h2>
609
610<p>Although it looks like push is faster than pull, <strong>facebook and twitter both use pull model</strong>.</p>
611
612<ol>
613<li>
613add cache for DB, reduce # of DB read</li>
614<li><p>also cache each user&rsquo;s news feed</p>
615
616<p> your yesterday&rsquo;s feeds are all cached, thus don&rsquo;t need to read everytime.</p></li>
617</ol>
618
619
620<h2>optimize push model</h2>
621
622<ol>
623<li>disk waste a lot, although disk is cheap</li>
624<li><p>inactive user!</p>
625
626<p> rank follower by weight, and don&rsquo;t write to inactive user (eg. last login time)</p></li>
627<li><p>if follower is toooo much, like Lady Gaga, user pull for Lady Gaga.</p>
628
629<p> Tradeoff: Push + Pull model.</p></li>
630</ol>
631
632
633<h2>optimize &lsquo;Like&rsquo; info</h2>
634
635<p>In tweet table, if we need to count(user) who liked, it&rsquo;s gonna take forever.</p>
636
637<p><strong>We must denormalize this data</strong>!</p>
638
639<p><img class="middle" src="/assets/images/jiuzhang-denormalize.png"></p>
640
641<p>Denormalize: it&rsquo;s duplicate info but we store in table, because of performance improvement.</p>
642
643<p><strong>Shortcoming: inconsistency</strong>!</p>
644
645<ol>
646<li>unless using SQL transaction, async failure can result in wrong counting number</li>
647<li>race condition</li>
648</ol>
649
650
651<p>Solution: 1. use atomic operation 2. every day, schedule to update this number.</p>
652
653<h2>optimize thundering herd problem</h2>
654
655<p>When cache fails, all DB query will go to DB. This results in DB crash.</p>
656
657<p>Hot spot (thundering herd)</p>
658
659<p><img class="middle" src="/assets/images/jiuzhang-thundering-herd.png"></p>
660
661<p>Solution: hold all incoming queries (who fails cache), and only send 1 DB query. When result is returned, return to every query.</p>
662</div>
663  
664  
665
666
667    </article>
668  
669  
670    <article>
671      
672  <header>
673    
674      <h1 class="entry-title"><a href="/blog/2016/06/11/add-aside-content-octopress/">[Octopress] Add Aside Content to Octopress</a></h1>
675    
676    
677      <p class="meta">
678        
679
680
681
682
683<time class='entry-date' datetime='2016-06-11T00:00:00-07:00'><span class='date'><span class='date-month'>Jun</span> <span class='date-day'>11</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>12:00 am</span></time>
684        
685      </p>
686    
687  </header>
688
689
690  <div class="entry-content"><h1>Aside</h1>
691
692<p>Example of this is the &lsquo;categories&rsquo; list on the right hand side of the blog page. It&rsquo;s always pinned on RHS, regardless of page content.</p>
693
694<h1>Instruction</h1>
695
696<ol>
697<li><p>Add to source/_includes/asides/category_list.html with the following content. (remember to delete [delete-this-tag])</p>
698
699<pre><code> &lt;section class="well"&gt;
700   &lt;h1&gt;Categories&lt;/h1&gt;
701   &lt;ul id="categories" class="nav nav-list"&gt;
702     {[delete-this-tag]% category_list %[delete-this-tag]}
703   &lt;/ul&gt;
704 &lt;/section&gt;
705</code></pre></li>
706<li><p>Go to _config.yml and modify default_asides.</p>
707
708<pre><code> default_asides: [asides/category_list.html, asides/recent_posts.html, asides/github.html, asides/delicious.html, asides/pinboard.html, asides/googleplus.html, asides/advertise.html]
709</code></pre></li>
710<li><p>Since the &lsquo;category_list&rsquo; tag is not natively supported. Add plugins/category_list_tag.rb with the <a href="https://kaworu.ch/blog/2013/09/23/categories-page-with-octopress/">followin content</a>.</p>
711
712<pre><code> module Jekyll
713   class CategoryListTag &lt; Liquid::Tag
714     def render(context)
715       html = ""
716       categories = context.registers[:site].categories.keys
717       categories.sort.each do |category|
718         posts_in_category = context.registers[:site].categories[category].size
719         category_dir = context.registers[:site].config['category_dir']
720         category_url = File.join(category_dir, category.gsub(/_|\P{Word}/, '-').gsub(/-{2,}/, '-').downcase)
721         html &lt;&lt; "&lt;li class='category'&gt;&lt;a href='/#{category_url}/'&gt;#{category} (#{posts_in_category})&lt;/a&gt;&lt;/li&gt;\n"
722       end
723       html
724     end
725   end
726 end
727
728 Liquid::Template.register_tag('category_list', Jekyll::CategoryListTag)
729</code></pre></li>
730<li><p>rake generate &amp;&amp; rake preview</p></li>
731</ol>
732
733</div>
734  
735  
736
737
738    </article>
739  
740  
741    <article>
742      
743  <header>
744    
745      <h1 class="entry-title"><a href="/blog/2016/05/08/user-registry-table-design/">[Design] User Registry Table Design</a></h1>
746    
747    
748      <p class="meta">
749        
750
751
752
753
754<time class='entry-date' datetime='2016-05-08T00:00:00-07:00'><span class='date'><span class='date-month'>May</span> <span class='date-day'>8</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>12:00 am</span></time>
755        
756      </p>
757    
758  </header>
759
760
761  <div class="entry-content"><h1>First word</h1>
762
763<p>
763Designing a system like twitter, facebook or airbnb, first step is often <strong>User Registry</strong>.</p>
764
765<p>The tables, <strong>we must use RDBMS</strong>, as it&rsquo;s more reliable.</p>
766
767<h2>Table design</h2>
768
769<p><strong>Friendship table</strong> is important:</p>
770
771<p><img class="middle" src="/assets/images/design-user-registry-tables.png"></p>
772</div>
773  
774  
775
776
777    </article>
778  
779  
780    <article>
781      
782  <header>
783    
784      <h1 class="entry-title"><a href="/blog/2015/11/22/challenges-writing-crawler/">[Design] Designing a Simple Web Crawler</a></h1>
785    
786    
787      <p class="meta">
788        
789
790
791
792
793<time class='entry-date' datetime='2015-11-22T00:00:00-08:00'><span class='date'><span class='date-month'>Nov</span> <span class='date-day'>22</span><span class='date-suffix'>nd</span>, <span class='date-year'>2015</span></span> <span class='time'>12:00 am</span></time>
794        
795      </p>
796    
797  </header>
798
799
800  <div class="entry-content"><h1>1. Choose a framework</h1>
801
802<p>Assuming we use Python to do this.</p>
803
804<h2>plain python?</h2>
805
806<p>We can write a simple Python crawler with the code below:</p>
807
808<pre><code>import re, urllib
809
810textfile = file('depth_1.txt','wt')
811print "Enter the URL you wish to crawl.."
812print 'Usage  - "http://phocks.org/stumble/creepy/" &lt;-- With the double quotes'
813myurl = input("@&gt; ")
814for i in re.findall('''href=["'](.[^"']+)["']''', urllib.urlopen(myurl).read(), re.I):
815    print i  
816    for ee in re.findall('''href=["'](.[^"']+)["']''', urllib.urlopen(i).read(), re.I):
817        print ee
818        textfile.write(ee+'\n')
819textfile.close()
820</code></pre>
821
822<h2>Scrapy?</h2>
823
824<ol>
825<li>You only define the rules, Scrapy do the rest</li>
826<li>easily plugin extensions</li>
827<li>portable + python runtime.</li>
828</ol>
829
830
831<h3>Why Scrapy</h3>
832
833<blockquote><p><a href="https://www.quora.com/What-are-the-advantages-of-Scrapy-compared-to-Beautiful-Soup">scrapy has the tools to manage every stage of a web crawl</a>, just to name a few:</p>
834
835<ol>
836<li><p>Requests manager - in charge of downloading pages all concurrently behind the scenes! You won&rsquo;t need to invest a lot of time in concurrent architecture.</p></li>
837<li><p>Selectors -  parse the html document (eg. XPath)</p></li>
838<li><p>Pipelines - after you retrieve the data, there&rsquo;s a bunch of functions to modify the data.</p></li>
839</ol>
840</blockquote>
841
842<p>Following the spirit of other don’t repeat yourself frameworks, such as Django:</p>
843
844<blockquote><p><a href="https://en.wikipedia.org/wiki/Scrapy">it makes it easier to build and scale large crawling projects</a> by allowing developers to re-use their code.</p></blockquote>
845
846<p>For more, read <a href="http://doc.scrapy.org/en/latest/topics/architecture.html">Scrapy Architecture </a>.</p>
847
848<p><img class="middle" src="/assets/images/scrapy_architecture.png"></p>
849
850<ol>
851<li><p>Scrapy Engine</p>
852
853<p> control data flow</p></li>
854<li><p>Scheduler</p>
855
856<p> receives requests from the engine and enqueues them for feeding them later</p></li>
857<li><p>Downloader</p></li>
858<li><p>Spiders</p></li>
859<li><p>Item Pipeline</p></li>
860<li><p>Downloader middlewares</p>
861
862<p> specific hooks that sit between the Engine and the Downloader and process requests</p></li>
863<li><p>Spider middlewares</p>
864
865<p> specific hooks that sit between the Engine and the Spiders and are able to process spider input (responses) and output (items and requests).</p></li>
866</ol>
867
868
869<h1>2. Schedule a Scrapy job</h1>
870
871<p>APScheduler? (todo)</p>
872
873<p>add/remove jobs</p>
874
875<h1>3. Choose a DB</h1>
876
877<p>I chose NoSQL/MongoDB. <a href="http://stackoverflow.com/a/11980154">But why</a>?</p>
878
879<ol>
880<li><p>there&rsquo;s only a few tables with few columns</p></li>
881<li><p>no overly complex associations between nodes</p></li>
882<li><p>huge amount of time-based data</p></li>
883<li><p>scaling requirements: MongoDB better horizontal scaling</p></li>
884<li><p>different field names: dynamical storage</p></li>
885</ol>
886
887
888<h1>4. Technical Difficulty?</h1>
889
890<h2>4.1 differrent way to crawl.</h2>
891
892<p>We need to check AJAX response sometime and study each website&rsquo;s API.</p>
893
894<p>Some site would <strong>close certain APIs</strong> if they found out too many queries requests.</p>
895
896<h2>4.2 Difficulty navigating pages</h2>
897
898<p>Study their URL structure.</p>
899
900<p>eg.</p>
901
902<pre><code>www.abc.com/index.html?page=milk&amp;start_index=0
903</code></pre>
904
905<p>Just play with the url params!</p>
906
907<h2>4.3 What is key?</h2>
908
909<p>I defined extra column only to store keys (combine a few key columns, and convert to lower-case).</p>
910
911<p>We can search using <strong>regex</strong> though, but:</p>
912
913<blockquote><p><a href="http://stackoverflow.com/a/7880894">Mongo (current version 2.0.0) doesn&rsquo;t allow</a> case-insensitive searches against indexed fields. For non-indexed fields, the regex search should be fine.</p></blockquote>
914
915<p>How to go about it:</p>
916
917<blockquote><p><a href="http://stackoverflow.com/a/4441412">searching with regex&rsquo;s case insensitive</a> means that mongodb cannot search by index, so queries against <strong>large datasets can take a long time</strong>.</p>
918
919<p>Even with small datasets, it&rsquo;
919s not very efficient&hellip; which could become an issue if you are trying to achieve scale.</p>
920
921<p>As an alternative, you can store an uppercase copy and search against that&hellip;</p>
922
923<p>If your field is large, such as a message body, duplicating data is probably not a good option. I believe using <strong>an extraneous indexer like Apache Lucene</strong> is the best option in that case.</p></blockquote>
924
925<h2>4.4 A lot bad data</h2>
926
927<ol>
928<li><p>write a sophisticated pipeline()</p></li>
929<li><p>try not let bad data reach pipeline() - <strong>better</strong></p></li>
930</ol>
931
932
933<p>Make your spider better!</p>
934
935<h2>4.5 NLP: brand names</h2>
936
937<p>how? (todo)</p>
938</div>
939  
940  
941
942
943    </article>
944  
945  
946    <article>
947      
948  <header>
949    
950      <h1 class="entry-title"><a href="/blog/2015/11/21/swizzle-sort/">[Question] Swizzle Sort</a></h1>
951    
952    
953      <p class="meta">
954        
955
956
957
958
959<time class='entry-date' datetime='2015-11-21T00:00:00-08:00'><span class='date'><span class='date-month'>Nov</span> <span class='date-day'>21</span><span class='date-suffix'>st</span>, <span class='date-year'>2015</span></span> <span class='time'>12:00 am</span></time>
960        
961      </p>
962    
963  </header>
964
965
966  <div class="entry-content"><h1>Question</h1>
967
968<p><a href="http://www.mitbbs.com/article_t/Recommend/31493121.html">link</a></p>
969
970<blockquote><p>输入一个数组,要求输出满足:a[0]&lt;=a[1]>=a[2]&lt;=a[3]>=…</p></blockquote>
971
972<h1>Solution</h1>
973
974<blockquote><p>O(n),一边扫描即可。发现不符合条件的只要跟前面一个数对调就可以,</p></blockquote>
975
976<h1>Code</h1>
977
978<pre><code>public int[] solve(int[] input) {
979    boolean incr = true;
980    int len = input.length;
981    int p = 1;
982    while (p &lt; len) {
983        if (incr ^ (input[p - 1] &lt; input[p])) {
984            Common.swap(input, p - 1, p);
985        }
986        p++;
987        incr = !incr;
988    }
989    return input;
990}
991</code></pre>
992</div>
993  
994  
995
996
997    </article>
998  
999  
1000    <article>
1001      
1002  <header>
1003    
1004      <h1 class="entry-title"><a href="/blog/2015/11/21/generate-maze/">[Design] How to Generate Maze</a></h1>
1005    
1006    
1007      <p class="meta">
1008        
1009
1010
1011
1012
1013<time class='entry-date' datetime='2015-11-21T00:00:00-08:00'><span class='date'><span class='date-month'>Nov</span> <span class='date-day'>21</span><span class='date-suffix'>st</span>, <span class='date-year'>2015</span></span> <span class='time'>12:00 am</span></time>
1014        
1015      </p>
1016    
1017  </header>
1018
1019
1020  <div class="entry-content"><h1>Question</h1>
1021
1022<p><a href="http://www.glassdoor.com/Interview/Design-a-2D-dungeon-crawling-game-It-must-allow-for-various-items-in-the-maze-walls-objects-and-computer-controlled-c-QTN_57.htm">link</a></p>
1023
1024<blockquote><p>Design a 2D dungeon crawling game. It must allow for   various items in the maze - walls, objects, and computer-controlled characters.</p></blockquote>
1025
1026<h1>Part 1: API design</h1>
1027
1028<p>Serialize:</p>
1029
1030<blockquote><p><a href="http://qr.ae/RbRhHv">if a certain cell has a wall</a> to the North and West but not to the South or East, it would be represented as 1001, or 9&hellip; (e.g., &ldquo;9,6,11,12\n3,10,10,4\n13,9,12,5\n3,6,1,6&rdquo; in a 4x4 maze)</p></blockquote>
1031
1032<p>Design API~</p>
1033
1034<h1>Part 2: Algorithm</h1>
1035
1036<h2>Depth-first search</h2>
1037
1038<p>This is most common and <a href="https://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search">one of the simplest ways to generate a maze using a computer</a>. It&rsquo;s commonly implemented using <strong><a href="https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_backtracker">Recursive backtrack</a></strong>.</p>
1039
1040<ol>
1041<li><p>from a random cell, select a random neighbour that hasn&rsquo;t been visited.</p></li>
1042<li><p>removes the &lsquo;wall&rsquo; and adds the new cell to a stack.</p></li>
1043<li><p>a cell with no unvisited neighbours is considered <strong>dead-end</strong>.</p></li>
1044<li><p>When at a dead-end it backtracks through the path until it reaches a cell with unvisited neighbours, continuing from there.</p></li>
1045<li><p>until every cell has been visited, the computer would backtrack all the way to the beginning cell.</p></li>
1046<li><p>Entire maze space is guaranted a complete visit.</p></li>
1047</ol>
1048
1049
1050<h3>side note</h3>
1051
1052<blockquote><p>To add difficulty and a fun factor to the DFS, you can <strong>influence the likelihood of which neighbor you should visit</strong>, instead of completely random.</p>
1053
1054<p>By making it more likely to visit neighbors to your sides, you can have a more horizontal maze generation.</p></blockquote>
1055</div>
1056  
1057  
1058
1059
1060    </article>
1061  
1062  <div class="pagination">
1063    
1064      <a class="prev" href="/posts/2">&larr; Older</a>
1065    
1066    <a href="/blog/archives">Blog Archives</a>
1067    
1068  </div>
1069</div>
1070<aside class="sidebar">
1071  
1072    
1072<script data-cfasync='false' type='text/javascript' src='//clksite.com/adServe/banners?tid=29011_299115_3&size=158x21'></script>
1072<section class="well">
1073  <h1>Categories</h1>
1074  <ul id="categories" class="nav nav-list">
1075    <li class='category'><a href='/blog/categories/cc150v4/'>cc150v4 (34)</a></li>
1076<li class='category'><a href='/blog/categories/cc150v5/'>cc150v5 (28)</a></li>
1077<li class='category'><a href='/blog/categories/design/'>design (83)</a></li>
1078<li class='category'><a href='/blog/categories/experience/'>experience (5)</a></li>
1079<li class='category'><a href='/blog/categories/fundamental/'>fundamental (18)</a></li>
1080<li class='category'><a href='/blog/categories/java-oop/'>java oop (36)</a></li>
1081<li class='category'><a href='/blog/categories/leetcode/'>leetcode (177)</a></li>
1082<li class='category'><a href='/blog/categories/leetcode-plus/'>leetcode_plus (9)</a></li>
1083<li class='category'><a href='/blog/categories/lintcode/'>lintcode (16)</a></li>
1084<li class='category'><a href='/blog/categories/ninechap/'>ninechap (25)</a></li>
1085<li class='category'><a href='/blog/categories/q-google/'>q-google (63)</a></li>
1086<li class='category'><a href='/blog/categories/question/'>question (144)</a></li>
1087<li class='category'><a href='/blog/categories/testing/'>testing (5)</a></li>
1088<li class='category'><a href='/blog/categories/z-string-search/'>z-string-search (18)</a></li>
1089<li class='category'><a href='/blog/categories/z-testing/'>z-testing (2)</a></li>
1090<li class='category'><a href='/blog/categories/z-top-k/'>z-top-k (6)</a></li>
1091
1092  </ul>
1093</section>
1094<section>
1095  <h1>Recent Posts</h1>
1096  <ul id="recent_posts">
1097    
1098      <li class="post">
1099        <a href="/blog/2017/05/22/Trie-Wildcard-String-Matching/">[Question] Trie Wildcard String Matching</a>
1100      </li>
1101    
1102      <li class="post">
1103        <a href="/blog/2017/05/13/dutch-national-flag/">[Question] Dutch National Flag Problem</a>
1104      </li>
1105    
1106      <li class="post">
1107        <a href="/blog/2016/08/01/how-to-design-logging/">[Design] How to Design Logging</a>
1108      </li>
1109    
1110      <li class="post">
1111        <a href="/blog/2016/07/31/mvc-mvp-mvvm/">[Design] MVC, MVP and MVVM</a>
1112      </li>
1113    
1114      <li class="post">
1115        <a href="/blog/2016/07/11/design-twitter/">[Design] Design Twitter</a>
1116      </li>
1117    
1118  </ul>
1119</section>
1120
1121
1122
1123
1124
1125  
1126</aside>
1127
1128    </div>
1129  </div>
1130  <footer role="contentinfo"><p>
1131  Copyright &copy; 2017 - Kevin Durant -
1132  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
1133</p>
1134
1135</footer>
1136  
1137
1138
1139
1140
1141
1142
1143
1144  
1144<script type="text/javascript">
1145    (function(){
1146      var twitterWidgets = document.createElement('script');
1147      twitterWidgets.type = 'text/javascript';
1148      twitterWidgets.async = true;
1149      twitterWidgets.src = '//platform.twitter.com/widgets.js';
1150      document.getElementsByTagName('head')[0].appendChild(twitterWidgets);
1151    })();
1152  </script>
1152
1153
1154
1155
1156
1157
1158</body>
1159</html>

Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.