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 [“cool& …"> 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 [“cool”, “kid”, “kindle”, “kind”]</p> 97 98<p>These would match: “co<em>l”, “kind”, “</em>**”</p> 99 100<p>These won’t: “<em>*”, “kid</em>”, “coo”</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’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 > 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 <= 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 <= right) { 212 if (input[mid] > 1) { 213 Common.swap(input, mid, right); 214 right--; 215 } else if (input[mid] < 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’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 “what” to log and “why”</h2> 278 279<p><strong>“How” 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’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’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’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’s too slow (and user is getting sync-blocked, too)</strong>. We should have, ideally, <= 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’s news feed</p> 615 616<p> your yesterday’s feeds are all cached, thus don’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’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 ‘Like’ info</h2> 634 635<p>In tweet table, if we need to count(user) who liked, it’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’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 ‘categories’ list on the right hand side of the blog page. It’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> <section class="well"> 700 <h1>Categories</h1> 701 <ul id="categories" class="nav nav-list"> 702 {[delete-this-tag]% category_list %[delete-this-tag]} 703 </ul> 704 </section> 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 ‘category_list’ 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 < 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 << "<li class='category'><a href='/#{category_url}/'>#{category} (#{posts_in_category})</a></li>\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 && 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’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/" <-- With the double quotes' 813myurl = input("@> ") 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’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’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’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’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&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’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’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’
919s not very efficient… 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…</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]<=a[1]>=a[2]<=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 < len) { 983 if (incr ^ (input[p - 1] < 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… (e.g., “9,6,11,12\n3,10,10,4\n13,9,12,5\n3,6,1,6” 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’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’t been visited.</p></li> 1042<li><p>removes the ‘wall’ 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">← 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 © 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.