<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Curt Corginia on Medium]]></title>
        <description><![CDATA[Stories by Curt Corginia on Medium]]></description>
        <link>https://medium.com/@corgicorporation?source=rss-88466123bc8d------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*3XRFAA2w7C3q70i_r1tqhA.jpeg</url>
            <title>Stories by Curt Corginia on Medium</title>
            <link>https://medium.com/@corgicorporation?source=rss-88466123bc8d------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 07:15:13 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@corgicorporation/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Computer Science Fundamentals — Pointers, Revisited]]></title>
            <link>https://corgicorporation.medium.com/computer-science-fundamentals-pointers-revisited-e690efa6f1f4?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/e690efa6f1f4</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 15 Sep 2023 20:44:40 GMT</pubDate>
            <atom:updated>2023-09-15T20:44:40.569Z</atom:updated>
            <content:encoded><![CDATA[<h3>Computer Science Fundamentals — Pointers, Revisited</h3><h4>Because Life Is Not Complete Without The Asterisk</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OLzo92MQgGnceyk0-Dg9YA.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@eltercero?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Víctor Martín</a> on <a href="https://unsplash.com/photos/G_LwkPWkYcg?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a>. I am reusing this photo from last year.</figcaption></figure><p>About a year ago, I started (and apparently never continued) a series called “Computer Science Fundamentals.” You are welcome to read it, but it is a bit of a mess — it gets really bogged down in personal anecdotes about my college experiences, as well as this quote by Joel Spolsky, the creator of Trello and co-founder of StackOverflow.</p><blockquote>I’ve come to realize that understanding pointers in C is not a skill, it’s an aptitude. In first year computer science classes, there are always about 200 kids at the beginning of the semester, all of whom wrote complex adventure games in BASIC for their PCs when they were 4 years old. They are having a good ol’ time learning C or Pascal in college, until one day the professor introduces pointers, and suddenly, <em>they don’t get it</em>. They just don’t understand anything any more. 90% of the class goes off and becomes Political Science majors, then they tell their friends that there weren’t enough good looking members of the appropriate sex in their CompSci classes, that’s why they switched. <em>For some reason most people seem to be born without the part of the brain that understands pointers.</em> Pointers require a complex form of doubly-indirected thinking that some people just can’t do, and it’s pretty crucial to good programming. A lot of the “script jocks” who started programming by copying JavaScript snippets into their web pages and went on to learn Perl never learned about pointers, and they can never quite produce code of the quality you need.<br> — <a href="https://www.joelonsoftware.com/2006/10/25/the-guerrilla-guide-to-interviewing-version-30/">Source</a></blockquote><ul><li>A pointer is an object that stores a memory address</li><li><a href="https://www.quora.com/Why-are-pointers-used-in-C-C++">A pointer allows for more efficiency</a></li><li>In C and C++, pointers can be used to return multiple parameters in a single function, and to avoid the generally frowned-upon usage of global variables</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/607/1*8T3T0mz_hU0vDYIsJZkaKQ.png" /><figcaption>“No lunch for you.” Image source: <a href="https://www.teamblind.com/post/Ok-to-use-global-variables-in-interview-ixRSzqLY">https://www.teamblind.com/post/Ok-to-use-global-variables-in-interview-ixRSzqLY</a></figcaption></figure><p>Here is the original blog post I wrote a year ago</p><p><a href="https://corgicorporation.medium.com/computer-science-fundamentals-pointers-bf9aa6f3f55c">Computer Science Fundamentals: Pointers</a></p><h4>First Stop: Low Level Learning</h4><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F2ybLD6_2gKM%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D2ybLD6_2gKM&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F2ybLD6_2gKM%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/80d806e37ad7cdae7586d2b459e78c92/href">https://medium.com/media/80d806e37ad7cdae7586d2b459e78c92/href</a></iframe><p>Say we have the line</p><blockquote>int x = 4;</blockquote><p>This line of C, Low Level Learning explains, allocates memory on the stack so that the value of 4 is now stored at a particular address. For the sake of example, he draws a chart and states that the address for value 4 is 0x1000. That is a hex value.</p><p>Now, he continues, consider this line</p><blockquote>int* px = &amp;x;</blockquote><p>In English, this can be read as: The integer pointer named px is set to the value of address x. A pointer is just a value that happens to be an address. <a href="https://cplusplus.com/doc/tutorial/pointers/">&amp; is the address-of operator</a>. <a href="https://learn.microsoft.com/en-us/cpp/cpp/pointers-cpp?view=msvc-170">A pointer is a variable that stores the memory address of an object.</a> The * and &amp; symbols can be thought of as complements.</p><p>Low Level Learning concludes by stating that pointers allow programmers to avoid global variables, and (as a separate use) to reduce space by not making copies.</p><p>The line <em>int* px = &amp;x</em> declares a pointer to a variable. * has a second use, which is to dereference. <a href="https://cplusplus.com/doc/tutorial/pointers/">The dereference operator is used to directly access a variable a pointer points to</a>. This was confusing as hell for me until I had to use it in actual code. Even in the field, <a href="https://cplusplus.com/doc/tutorial/pointers/">I constantly found myself revisiting this webpage</a>.</p><p>In case these two lines of code do not explain very much out of context, here is the example I made a year ago. It was me doing my best to recreate a college example we saw over and over again.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/cc44b5eb0a34f6b8830d27fec54e8da3/href">https://medium.com/media/cc44b5eb0a34f6b8830d27fec54e8da3/href</a></iframe><p>Foo is a method that uses pointers. It accepts the address of originalNum, value 42, as a parameter. Foo uses the derefrence operator to modify the value of originalNum itself. The value of originalNum changes from 42 to 100.</p><p>pointerlessFoo, in contrast, has no impact on originalNum2. It accepts 88 as a parameter, attempts to set the value to 100, but actually just creates a local variable that gets set, goes out of scope, and is then lost. The value of 100 from pointerlessFoo never makes it back to main, whereas the one passed to foo does.</p><h4>Applications</h4><p>An array works like a pointer to the first array element.</p><p>You can use character pointers, and the topic of pointers is fundamentally connected to how linked lists work, regardless of whether or not you are a C/C++ programmer.</p><h4>Resources And Closing Thoughts</h4><p>This is my class’ syllabus, a year after I took it</p><p><a href="https://csiflabs.cs.ucdavis.edu/~ssdavis/30/homepage.html">ECS 30 Homepage</a></p><p>That syllabus page links to this 30-page explanation of pointers by a Stanford professor.</p><iframe src="https://drive.google.com/viewerng/viewer?url=https%3A//csiflabs.cs.ucdavis.edu/%7Essdavis/30/PointersAndMemory.pdf&amp;embedded=true" width="600" height="780" frameborder="0" scrolling="no"><a href="https://medium.com/media/a14b08b57e8ecea8f8ad02da0b5670c7/href">https://medium.com/media/a14b08b57e8ecea8f8ad02da0b5670c7/href</a></iframe><p>That Stanford webpage also links to a video called “Binky Pointer Fun Video.” This YouTube link is not official, but I do not think they would mind the fact that it exists, considering they wanted this Stanford resource to be open to the public (I could be wrong, though; I am not the one who uploaded this to YouTube)</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fi49_SNt4yfk%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Di49_SNt4yfk&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fi49_SNt4yfk%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/33f0f085cea8c58a32e0578483c015de/href">https://medium.com/media/33f0f085cea8c58a32e0578483c015de/href</a></iframe><p>I’d like to continue the series and revisit my old college notes, especially since some things like the virtual table, polymorphism, and dynamic_cast have come up for me in actual interviews. But first I wanted to redo the “pointers” blog post because I thought it was a mess.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e690efa6f1f4" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Baseline System Design — Databases, Part 1/?]]></title>
            <link>https://corgicorporation.medium.com/baseline-system-design-databases-part-1-e0e6a702629?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/e0e6a702629</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 01 Sep 2023 08:05:30 GMT</pubDate>
            <atom:updated>2023-09-01T08:05:30.591Z</atom:updated>
            <content:encoded><![CDATA[<h3>Baseline System Design — Databases, Part 1/?</h3><h4>Adventures In Toy Facebook Continue</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Yc1Xkqjw0Ez4kgd6Kl0_xQ.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@campaign_creators?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Campaign Creators</a> on <a href="https://unsplash.com/photos/IKHvOlZFCOg?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a>. I could have used my own marker, but how would I erase it from the mirror?</figcaption></figure><p>Last time I wrote about Facebook fanout, but got bogged down in trying to figure out what Facebook actually did. A requirement for Facebook is that users can publish posts; another requirement is that users can receive posts (“news”). We can implement this with the push/fanout-on-write approach, or the pull/fanout-on-load approach. In the former, the newsfeed is generated during read time. In the latter, the newsfeed is precomputed during write time and new posts are delivered to friends’ caches immediately after publication.</p><p>An advantage of using a cache is speed, but a disadvantage is the “hotkey problem” — it is really slow for celebrities who have many friends. We can use a hybrid approach and have the majority of users use fanout-on-write while celebrities use fanout-on-load, but this is not necessarily what Facebook actually does.</p><p><a href="https://corgicorporation.medium.com/baseline-system-design-facebook-newsfeed-and-fanout-e95311d52f65">Baseline System Design — Facebook Newsfeed And “Fanout”</a></p><h4>The Database Tangent Begins</h4><p>I have purchased <a href="https://www.designgurus.io/course/grokking-the-system-design-interview?utm_source=goog_ad&amp;utm_medium=txt_ad&amp;utm_campaign=Perf_Max_SD_US&amp;gclid=Cj0KCQjwl8anBhCFARIsAKbbpyTe5lDWBrs_aprLGM5Fs-kCGuYAYLPlnO-cgAA56e3jk74C5Mw5BgMaAnzFEALw_wcB">Grokking The System Design Interview</a>, a kind of $60 EBook not to be confused with the similarly named Educative.io course, and whatever weird history caused DesignGurus to split from them before Educative apparently rolled out their own ripoff (to be clear, I am not sure if that is actually what happened and do not want to summon their lawyers; that is just how it looks to me). One thing I noticed is that the “Design Facebook Newsfeed” page quickly dives into database design, without really explaining what SQL is or how to read a database diagram. They include their own section on why you might choose SQL or NoSQL, but it seems they treat SQL itself as prerequisite knowledge.</p><p>So…let’s see:</p><p><a href="https://hackernoon.com/dbdiagram-io-a-database-diagram-designer-built-for-developers-and-analysts-975f310d4f13">A Database Diagram Designer Built for Developers and Analysts | HackerNoon</a></p><p>This HackerNoon article is more or less an advertisement for software I have never used, but I do like how they include a diagram example.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2RTgqtnHLEe565MJVUzMCA.jpeg" /></figure><p>Primary Keys and Foreign Keys are explained in the resource below, from a website called learnsql. I really like how the website includes actual code, in addition to its tables.</p><p><a href="https://learnsql.com/blog/why-use-primary-key-foreign-key/">Why Do Relational Databases Use Primary Keys and Foreign Keys?</a></p><p><a href="https://learnsql.com/blog/why-use-primary-key-foreign-key/">This is a huge simplification, but a primary key uniquely identifies each row in a table, and a foreign key links a table to another</a>. <a href="https://en.wikipedia.org/wiki/Varchar">A varchar is a set of character data of indeterminate length.</a></p><p>DesignGurus lays out a database design like this: The objects are User, Entity (such as page or group), and FeedItem/post. This is a little different from the database design proposed by a site called systemdesignprep, but please check out their site if you want to see a hand-drawn diagram.</p><p>Their user table has user id (primary key), username, email, creation date, and description. Their user post table has post id (primary key), text, media URL, and timestamp. Please consult the link itself to view the other tables and foreign keys:</p><p><a href="https://systemdesignprep.com/newsfeed">Interview Question - Design Newsfeed - System Design Prep</a></p><h4>The SQL vs NoSQL Question</h4><p>A <a href="https://www.quora.com/What-NoSQL-technologies-does-Facebook-use">Quora post</a> written ten years ago by a Facebook engineer says they use a variety of NoSQL solutions, including HBase, Hadoop, and Memcached; MySQL is their primary data store. This information could very well be out of date.</p><p>DesignGurus, in their solution, suggests that you COULD use a relational database (hence their diagram). Alex Xu’s solution in <em>System Design Interviews</em>, unless I misread something, does not seem to touch on the SQL vs. NoSQL question at all.</p><p>This is, once again, a huge oversimplification but <a href="https://www.integrate.io/blog/the-sql-vs-nosql-difference/">SQL databases are relational and NoSQL databases are non-relational</a>. Interviewers in system design questions commonly ask whether you would choose SQL or NoSQL, and why. SQL, from that integrate.io source, is ACID (atomicity, consistency, isolation, durability) compliant and NoSQL is not necessarily ACID-compliant; <a href="https://www.ibm.com/blog/sql-vs-nosql/">what you get with NoSQL is horizontal scalability</a>. In the words of that IBM article I just linked, you can add additional servers in a NoSQL schema to increase load, whereas a SQL schema is vertically scalable and you would have to migrate to a larger server.</p><p>I had thought the trade-off was that NoSQL is simply faster, and SQL is ACID-compliant, but <a href="https://softwareengineering.stackexchange.com/questions/175542/why-is-nosql-faster-than-sql">now I think I was wrong</a>.</p><h4>Closing Thoughts</h4><p>For your entertainment, you can read Sebastian Carlos’ s***post about SQL. Just don’t take it seriously.</p><p><a href="https://sebastiancarlos.com/why-sql-is-a-fad-57a117b67f48">Why SQL is a Fad</a></p><p>Sebastian Carlos is a man of focus, git commitment, and sheer will. He is currently on a one-man crusade to prove that the software engineer community on Medium has no sense of humor.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e0e6a702629" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Baseline System Design — Facebook Newsfeed And “Fanout”]]></title>
            <link>https://corgicorporation.medium.com/baseline-system-design-facebook-newsfeed-and-fanout-e95311d52f65?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/e95311d52f65</guid>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[social-media]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[software-development]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 18 Aug 2023 17:38:34 GMT</pubDate>
            <atom:updated>2023-08-18T17:38:34.219Z</atom:updated>
            <content:encoded><![CDATA[<h3>Baseline System Design — Facebook Newsfeed And “Fanout”</h3><h4>Comparing Resources Like “Grokking The System Design Interview” To The Actual Facebook Blog</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MCBiFp4fib65mByevcoxRg.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@iamromankraft?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Roman Kraft</a> on <a href="https://unsplash.com/photos/_Zua2hyvTBk?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a>. If I photoshopped a giant Facebook logo over the newspaper, would it no longer be licensed under Unsplash?</figcaption></figure><p>I had a few ideas for how to make Baseline System Design interesting — my best one was to look at resources like <a href="https://www.designgurus.io/course/grokking-the-system-design-interview">Grokking</a> to find out how they designed <em>hypothetical</em> systems, then compare this to how systems are actually designed. So far I have had mixed success with Facebook Newsfeed.</p><p>For anyone skimming this, here is the short version: <a href="https://www.ijcaonline.org/archives/volume179/number48/sudhakaran-2018-ijca-917224.pdf">This published paper from the International Journal Of Computer Applications</a> <a href="https://engineering.fb.com/2015/03/10/production-engineering/serving-facebook-multifeed-efficiency-performance-gains-through-redesign/">references this Facebook blog pos</a>t, and goes on to state that Facebook uses a primarily “pull-based architecture” /fanout-on-load when it generates its newsfeed. Resources like “Grokking The System Design Interview” argue instead for a hybrid approach similar to what Twitter does.</p><p>If I were to simply regurgitate things like “Grokking,” I would probably be better off pointing readers to System Design Primer.</p><p><a href="https://github.com/donnemartin/system-design-primer/blob/master/solutions/system_design/twitter/README.md">system-design-primer/solutions/system_design/twitter/README.md at master · donnemartin/system-design-primer</a></p><p>…this is my first complaint with System Design Primer — it simply lumps “Facebook Newsfeed” in with “Twitter Timeline,” as if the two were designed exactly the same way.</p><p>After what I have read about Facebook Newsfeed, I am starting to see why so many writers and bloggers do things this way. Unlike Twitter, some of Facebook’s engineering blog posts are rather vague and read like advertisements. Simply searching Google is even harder, as looking up “Facebook Newsfeed” will yield a number of results that simply explain how to make your Facebook posts trend.</p><h4>An Explanation Of Fanout</h4><p>This is one small part of a hard question you can find under “Grokking The System Design Interview.” Facebook Newsfeed is what updates the results on Facebook’s homepage, such that your brother’s engagement photo appears before your aunt’s YouTube link of two corgis playing tetherball.</p><p>There are a number of really interesting technical questions that “Grokking” glosses over, like how Facebook actually uses machine learning to determine its rankings.</p><p><a href="https://engineering.fb.com/2021/01/26/ml-applications/news-feed-ranking/">How machine learning powers Facebook&#39;s News Feed ranking algorithm</a></p><p>When a person publishes a post, the post is pushed to all followers in something called <strong>fanout</strong>. <a href="https://www.designgurus.io/course-play/grokking-the-system-design-interview/doc/638c0b73ac93e7ae59a1b065">The push approach is called fanout-on-write, and the pull approach is called fanout-on-load</a>.</p><p><a href="https://www.designgurus.io/course-play/grokking-the-system-design-interview/doc/638c0b73ac93e7ae59a1b065">Grokking the System Design Interview</a></p><p>Alex Xu’s book essentially describes the exact same thing, but in a slightly clearer way.</p><p><a href="https://www.amazon.com/System-Design-Interview-insiders-Second/dp/B08CMF2CQF">System Design Interview - An insider&#39;s guide</a></p><p>In Fanout-on-write, the newsfeed is precomputed during write time. A new post is delivered to friends’ caches immediately after publication. Fetching is fast, but it has the “hotkey problem” — it is really slow for celebrities with many friends.</p><p>In fanout-on-load, the newsfeed is generated during read time. There is no hotkey problem, but fetching is slow.</p><p>The hybrid approach is to let followers pull the updates for celebrities, but have “normies” carry out the writes. In other words, the majority of users use “fanout-on-write,” but not celebrities.</p><h4>Down The Rabbit Hole</h4><p>From the <a href="https://engineering.fb.com/2015/03/10/production-engineering/serving-facebook-multifeed-efficiency-performance-gains-through-redesign/">Facebook blog</a>:</p><blockquote>We leveraged the disaggregation concept to redesign Multifeed, a distributed backend system that is involved in News Feed. When a person goes to his or her Facebook feed, Multifeed looks up the user’s friends, finds all their recent actions, and decides what should be rendered based on a certain relevance and ranking algorithm. The disaggregation results with respect to infrastructure were impressive across multiple areas tracked.</blockquote><p>This, I imagine, is where the researchers who wrote “A Hybrid Approach To Social Network User Feed Generation” got their data to conclude that “Facebook uses a model that is primarily pull based.” The conclusion seems a little bit sketchy to me, but they are published researchers and I am in a long list of random people on Medium who have blogs.</p><p>I feel a little bit like I am trying to solve a murder mystery: Where did the creators of DesignGurus get the information that Facebook uses a hybrid approach to fanout? To be fair, they have never claimed to actually be proposing how Facebook is truly designed. But Alex Xu proposed the exact same design, prompting me to wonder if they have more information from sources at Facebook, if the two are collaborating, or if one of them simply took the idea from the other.</p><p>My best guess is that they were simply pretending Facebook was designed exactly like Twitter. That is covered in both the twitter blogs and in this book:</p><p><a href="https://www.amazon.com/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321">Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems</a></p><h4>Closing Thoughts</h4><p>Since this ended up being an entire blog post about one small part of Facebook newsfeed, it may be good to go into another portion of the proposed Facebook newsfeed design, or return to Twitter.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e95311d52f65" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[New Series — Baseline System Design]]></title>
            <link>https://corgicorporation.medium.com/new-series-baseline-system-design-896bd2a6bd9b?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/896bd2a6bd9b</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[system-design-interview]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[interview]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 04 Aug 2023 07:35:32 GMT</pubDate>
            <atom:updated>2023-08-04T07:35:32.350Z</atom:updated>
            <content:encoded><![CDATA[<h3>New Series — Baseline System Design</h3><h4>Starting Resources For A System Design Interview</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WDuJhdMB38Z-1ENC16bVuQ.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@alexbemore?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Alexander Shatov</a> on <a href="https://unsplash.com/photos/mr4JG4SYOF8?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>For reasons that are unclear to me, DesignGurus has apparently severed its connection to Educative and <a href="https://www.designgurus.io/course/grokking-the-system-design-interview">Grokking The System Design Interview</a> is now only available through the designgurus.io site. Educative now has a different course they call “Grokking MODERN System Design Interview FOR ENGINEERS &amp; MANAGERS,” and I would love to hear the story behind that. I have had a couple interactions with Arslan Ahmad, as I contributed a couple of times to a <a href="https://interviewnoodle.com/4">Medium publication he curates</a>, but I certainly have not had enough interactions to ask him about it.</p><p>Though it is not necessarily related, I see that Yangshun Tay has removed his Educative sponsorship links in <a href="https://www.techinterviewhandbook.org/grind75">Grind75</a>.</p><p>So, as it currently stands today, if you want to study for a system design interview you can:</p><ul><li>Pay $16 a month to use <a href="https://www.designgurus.io/course/grokking-the-system-design-interview">Grokking The System Design Interview</a></li><li>Pay $59 for lifetime access to Grokking The System Design Interview, with that exact same link</li><li>Pay $16, $24, or $30 a month for Educative (at a glance, the $16 a month option looks fine), which has lots of courses but is something I explicitly purchased (and no longer have) for the two Grokking courses it no longer has. I cannot speak to their replacement one</li></ul><p>Or, you can</p><ul><li>Look at <a href="https://github.com/donnemartin/system-design-primer">System Deisgn Primer</a> for free</li><li>Watch Guaguarav Sen for free</li></ul><p><a href="https://www.youtube.com/channel/UCRPMAqdtSgd0Ipeef7iFsKw">Gaurav Sen</a></p><ul><li>Read Medium blog posts with a $5-a-month subscription, targeting reputable people like the creator of <em>Grokking The System Design Interview</em></li></ul><p><a href="https://arslan-ahmad.medium.com/">Arslan Ahmad - Medium</a></p><p>…or you could do a mix of the two.</p><p>I have seen these two GitHub resources recommended, as well:</p><ul><li><a href="https://github.com/madd86/awesome-system-design">GitHub - madd86/awesome-system-design: A curated list of awesome System Design (A.K.A. Distributed Systems) resources.</a></li><li><a href="https://github.com/rxin/db-readings">GitHub - rxin/db-readings: Readings in Databases</a></li></ul><h4>Some Of My Random Thoughts</h4><p>I thought that I had written quite a bit about system design on this blog, but I was mistaken. The only thing I wrote was this, which provided just a little bit of information about how Twitter works:</p><p><a href="https://corgicorporation.medium.com/elon-musk-and-twitters-system-design-8bc2a97680e6">Elon Musk and Twitter’s System Design</a></p><p>I had a series I was starting called “Software Engineer Failures,” which allowed me to read some interesting papers on the Therac-25 disaster, but I think I speak for everyone when I say that just because you know how to <em>crash a car</em> does not mean you know how to design one.</p><p>Twitter, I think, could serve as a quick “resource comparison” because so much of its design is up in the air now. Instead of discussing its strengths and shortcomings in some sort of private company email, Twitter’s internal engineer arguments have taken place on Twitter.</p><p>In spite of my confusion with the Educative/DesignGurus split, I did enjoy Fahim ul Haq’s blog post about Twitter’s new design.</p><p><a href="https://www.educative.io/blog/twitter-design">Educative: Interactive Courses for Software Developers</a></p><p>This lays out how Twitter <em>actually</em> works, including names such as Manhattan, their key-value store, Gizmoduck, which stores all user information in profiles, and Tweety Pie, an object that represents a tweet in the Tweet API. I wanted to find something from Twitter itself to corroborate the use of Gizmoduck, and…there it is.</p><iframe src="https://cdn.embedly.com/widgets/media.html?type=text%2Fhtml&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;schema=reddit&amp;url=https%3A//www.reddit.com/r/ProgrammerHumor/comments/yz8zas/elons_10_pm_whiteboard_twitter_for_dummies/%3Frdt%3D33651&amp;image=https%3A//i.embed.ly/1/image%3Furl%3Dhttps%253A%252F%252Fpreview.redd.it%252Felons-10-pm-whiteboard-twitter-for-dummies-v0-oxn1q6iayv0a1.jpg%253Fwidth%253D640%2526crop%253Dsmart%2526auto%253Dwebp%2526s%253De95c73f1eb8cc1dc8b31caf56dee5c591924e6b8%26key%3Da19fcc184b9711e1b4764040d3dc5c07" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/e9851bf9c77920d5c14853e627a622d5/href">https://medium.com/media/e9851bf9c77920d5c14853e627a622d5/href</a></iframe><p>It is near the bottom, right below Manhattan. This was Twitter’s design nine months ago.</p><p>Here is the Twitter technical blog, writing about Manhattan ten years ago:</p><p><a href="https://blog.twitter.com/engineering/en_us/a/2014/manhattan-our-real-time-multi-tenant-distributed-database-for-twitter-scale">Manhattan, our real-time, multi-tenant distributed database for Twitter scale</a></p><p>In contrast, System Design Primer and “Grokking The System Design Interview” both focus on “Toy Twitter,” a hypothetical sketch you might make of how Twitter MIGHT work if it were designed in 45 minutes. “System Design Primer” and “Grokking” are not carbon copies by any means — I find “Grokking” to be much easier to navigate, with “System Design Primer” often dropping links and, in this case, covering just one specific part of Twitter.</p><p>Both emphasize, even in “Toy Twitter,” that Twitter is read-heavy. From there, the two diverge.</p><ul><li>Only “Grokking” mentions an emphasis on availability over consistency</li><li>Only “Grokking” goes into some detail about sharding, whereas “System Design Primer” simply references the word</li><li>“System Design Primer” explicitly mentions “Fanning out” tweets, which is what Twitter really does</li></ul><blockquote>The <strong>Fanout Service</strong> is a potential bottleneck. Twitter users with millions of followers could take several minutes to have their tweets go through the fanout process. This could lead to race conditions with @replies to the tweet, which we could mitigate by re-ordering the tweets at serve time.</blockquote><blockquote>We could also avoid fanning out tweets from highly-followed users. Instead, we could search to find tweets for highly-followed users, merge the search results with the user’s home timeline results, then re-order the tweets at serve time.<br> — From System Design Primer <a href="https://github.com/donnemartin/system-design-primer/blob/master/solutions/system_design/twitter/README.md">https://github.com/donnemartin/system-design-primer/blob/master/solutions/system_design/twitter/README.md</a></blockquote><p>SQL vs. NoSQL makes for a more interesting discussion here. You can read about Twitter’s “chronological evolution of scale” here, in that section, but it is a little more complicated than simply choosing SQL or NoSQL. They originally used MySQL, then moved to many replicated MySQL clusters with Gizzard, then…for lack of much more description…FlockDB, Snowflake, and Cassandra entered the mix. Cassandra did not fully replace MySQL, and in 2014 they launched Manhattan.</p><p><a href="https://blog.twitter.com/engineering/en_us/topics/infrastructure/2017/the-infrastructure-behind-twitter-scale">The Infrastructure Behind Twitter: Scale</a></p><p>Here is more about how Twitter actually does sharding.</p><p><a href="https://blog.twitter.com/engineering/en_us/topics/infrastructure/2021/sharding-simplification-and-twitters-ads-serving-platform">Sharding, simplification, and Twitter&#39;s ads serving platform</a></p><h4>Closing Thoughts</h4><p>Going over the Twitter blog links could probably be its own blog post, making this one a two-part miniseries.</p><p>The YouTube channel below argues that system design interviews are not a great indicator of skill</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FrKgtPABz9AY%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DrKgtPABz9AY&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FrKgtPABz9AY%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/1000215620369102258849a4c87d0d1a/href">https://medium.com/media/1000215620369102258849a4c87d0d1a/href</a></iframe><p>…but it’s such a “me” thing to link a video like that prematurely. The truth is, at least in my opinion, everything a person studies for a system design interview is potentially useful in the field.</p><p>A wise engineer may hypothetically argue, however, that we should genuinely study system design by reading books like this:</p><p><a href="https://www.amazon.com/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321">Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=896bd2a6bd9b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Thoughts On Software Engineer Job Interviews]]></title>
            <link>https://corgicorporation.medium.com/thoughts-on-software-engineer-job-interviews-6a790db08d10?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/6a790db08d10</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[humor]]></category>
            <category><![CDATA[software-development]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 21 Jul 2023 15:25:43 GMT</pubDate>
            <atom:updated>2023-07-21T15:25:43.214Z</atom:updated>
            <content:encoded><![CDATA[<h4>If you are looking for a coherent post, keep looking — this is 100% rambling</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*lmMpx3H1MLuc5jU8cw_40Q.jpeg" /><figcaption>GENERIC UNSPLASH INTERVIEW PHOTO #5000</figcaption></figure><p>Once again, for the sake of sparing embarrassment I will not reveal when this interview took place — whether it was a week ago, a year ago, or ten years ago. This was my most recent software engineer interview, and there is a twist: I got it. I got an offer. I also did not take it, for reasons I would prefer not to go into (they include some things I learned in the interview itself about what the project was), but the experience taught me a few things:</p><ul><li>Some large companies are willing to hire after just one technical interview</li><li>Some large companies are willing to hire without requiring a single coding test</li><li>Soft skills are important, as is the ability to simply have a conversation. Maybe this is more like a test, but you can benefit from making it seem more like a conversation</li></ul><p>This last one was from Smack , who heard the story. His belief, which I disagree with, is that everything can boil down to a behavioral interview. Coding interviews can be exaggerated through “confident delivery.” Technical achievements can be exaggerated. Another coworker gave this advice: Throw away your interview books and purchase a joke book instead. If you can make your interviewer laugh twice, you get the job. If they do not laugh because they are too serious and uptight, then you do not want to work for them anyway.</p><p>I only made mine laugh once and got an offer anyway, so there.</p><p>A typical software engineer “circuit,” in my experience, consists of an initial phone screen with HR, followed by a coding test very similar to LeetCode, followed by a system design interview, followed by a behavioral interview. Then you have to do everything all over again in a three-and-a-half hour final interview.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F314OLE6mKOo%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D314OLE6mKOo&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F314OLE6mKOo%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/ff0b985dcfeaaf87d7ed3807c08817df/href">https://medium.com/media/ff0b985dcfeaaf87d7ed3807c08817df/href</a></iframe><p>This one was basically a 45-minute conversation in which we talked about, among other things:</p><ul><li>The actual job description and what they were looking for</li><li>My proudest technical achievement</li><li>Web frameworks and microservices</li></ul><p>For full context, I have to admit that I thought I failed within the first few minutes. Perhaps <em>because of this</em>, I had something that was more like a casual conversation for the remainder of the interview.</p><h4>How Confidence Can Help In Any Interview</h4><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Ff2rgzsO-AMM%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Df2rgzsO-AMM&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Ff2rgzsO-AMM%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/51a36794ddfe8b2b5e1d64a7a845f218/href">https://medium.com/media/51a36794ddfe8b2b5e1d64a7a845f218/href</a></iframe><p>For a long time, I dismissed people from other fields who gave me advice on interviewing. How could they know? The had not seen what I had seen. The nested for loops. The 2D arrays. They had not watched as their dream jobs disappeared within those endless labyrinths, the places we had pursued into that darkness.</p><blockquote>Interviewer: What do you sacrifice?<br>Interviewee: Love. Family. 9–5. I’ve given up all chance at inner peace. I’ve made my mind a sunless space and shared my dreams with computers. My anger, my ego, my unwillingness to go outside, my eagerness to do LeetCode instead of making friends, they’ve set me on a path from which there is no escape. I yearned to get that dream job without contemplating the cost and by the time I looked down there was no longer any ground beneath my feet. What is my sacrifice? I burn my sanity and my happiness and my freedom for a position that will no longer exist by the time the interviews are over. <br> — Definitely not ripped off from <a href="https://scatteredquotes.com/what-do-i-sacrifice-everything/">Andor</a></blockquote><p>…but actually, confidence and calm could have helped me in my worst interviews. Let me think back to the top three.</p><p>My third worst interview, in a now-infamous story that has been ridiculed so much that it has almost achieved meme-worthiness, is <a href="https://www.reddit.com/r/business/comments/pbxe0f/comment/haz6sqj/?context=3">when I tried to solve the string compression problem with a hashmap</a>.</p><p><a href="https://corgicorporation.medium.com/repeat-code-with-leetcode-string-compression-88f854e56a56">Repeat Code with Leetcode: String Compression</a></p><p>Why did I do this? I had not thought the problem through and only wanted to start coding as soon as possible. This was a test, and what kind of student wastes valuable time on a test?</p><p>In my second worst interview, I thought I would have a choice of programming language, but the interviewer told me it would have to be in Java. I will never know exactly what his side of the story was, but what I <em>do </em>know is that nothing went well. I asked if I could use C++, and the interviewer said the question made him very concerned. I started to write Java and asked how large of an input this would have to process, and the interviewer said it did not matter. I asked how efficient it had to be, and he said it did not matter. Confidence may have helped me get out of this funk.</p><p>If you are interested, the entire story is here:</p><p><a href="https://corgicorporation.medium.com/not-all-companies-give-you-a-choice-of-programming-language-a9295561e183">Not All Companies Give You a Choice of Programming Language</a></p><p>My worst interview has actually never been blogged about here — it was with a startup that has about 300 employees and 100 million users. The interviewer was perfectly polite, and he asked me a coding problem to find the three most popular videos where popularity was determined by unique user ID. Confidence was definitely a factor here as well, though the other takeaway was directly tied to hashmaps. It seemed like a perfect use case for a hashmap, but using a hashmap requires at least a basic understanding of key/value (as in, if you are going to use a hashmap, specify what you are using as a key and what you are using as a value), and the ability to do basic hashmap operations in your programming language. I don’t think I had to know the internals of how a hashmap works under the hood — like how it deals with collisions, for example — though this knowledge would have helped.</p><p>Then I explained it to a friend, who explained in detail how he would solve the problem. He readily admitted that he would not be able to code it in an interview — he had not interviewed in a while, after all — but without writing any code, his ability to articulate a solution seemed so much better than the performance I gave. All I did was continue to code while digging myself further and further into a hole. He seemed confident, enthusiastic, and knowledgeable, and I imagine he would have been open to discussion.</p><h4>Story-Telling</h4><p>“What is your proudest technical achievement?” is, in my opinion, a good interview question. A candidate can say virtually anything, and a technical interviewer can drill down into specifics to assess areas of expertise. It is also a question I anticipated.</p><p>I had a story prepared. It had characters. It had conflict. It even had a joke sprinkled in. I think the story could have gone over well, had it been field tested on more interviewers. The problem is that the story was about data serialization, and the interviewer had just established that he was interested in frontend web development. I had much more luck conversing with him about frontend web development.</p><h4>Closing Thoughts</h4><p>I’ve said it before, and I’ll say it again: Companies can ask virtually anything. They can hire after one interview or seven, and everything from soft skills to very specific certifications can matter tremendously to different people.</p><p>I imagine the blog will quickly transition back to its usual format, but this anecdote made for an interesting change of pace.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6a790db08d10" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Repeat Code With LeetCode — Valid Parentheses, But With JavaScript]]></title>
            <link>https://medium.com/repeat-code-with-leetcode/repeat-code-with-leetcode-valid-parentheses-but-with-javascript-4e07d0cbc97c?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/4e07d0cbc97c</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 07 Jul 2023 22:27:52 GMT</pubDate>
            <atom:updated>2024-12-26T20:56:45.260Z</atom:updated>
            <content:encoded><![CDATA[<h3>Repeat Code With LeetCode — Valid Parentheses, But With JavaScript</h3><p>If you thought solving it one time was not enough fun, wait until you see it get solved a second time!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*q9X72khX77ZgSUYNNo-xGw.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@bnimit?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Apaha Spi</a> on <a href="https://unsplash.com/photos/2VMDforsMBI?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a>. If you look closely, you will find sideways parentheses!!</figcaption></figure><p>I spent a long time browsing <a href="https://interviewnoodle.com/">InterviewNoodle</a> in search of the blogger who said LeetCode is a great resource for practicing multiple programming languages, but I never found it. In the process, though, I stumbled on a couple articles I really liked.</p><ul><li><a href="https://interviewnoodle.com/i-got-interviews-with-all-of-faang-as-a-new-grad-swe-ed57c5a58f86">I got interviews with all of FAANG as a New Grad (SWE)</a></li><li><a href="https://interviewnoodle.com/what-to-make-of-a-failed-job-interview-16a062d54fd4">What to make of a failed job interview?</a></li></ul><p>It has been quite a while since I interviewed anywhere, but the process can be rather discouraging. The second blogger, who states that he has conducted numerous interviews himself, says:</p><ul><li>The process is imperfect. He is actually a fan of LeetCode, but candidates face a variety of factors, from their mental state, to the current mood of the interviewer, to the simple fact that some candidates get unlucky and receive questions they do not know how to answer, in spite of being competent in their fields</li><li>Sometimes there are multiple people who are qualified, and the company simply selects the one who seems most qualified. This sounds obvious, but the author points it out to remind us that a rejection is not the company telling us we are not good enough</li></ul><p>…and the first blogger writes:</p><blockquote>A hard truth I have learned is that as much as you prep and really want something, things don’t always work. Interviewers are rude or in a bad mood. You get a complete curveball question. You get nervous. I think often we forget although we are being interviewed as candidates, you should be assessing the company as well. How did they treat you and make you feel throughout the process? Do your values align with theirs?<br> —<a href="https://medium.com/interviewnoodle/i-got-interviews-with-all-of-faang-as-a-new-grad-swe-ed57c5a58f86"> Source</a></blockquote><p>I can certainly identify with getting a “rude interviewer.” I myself encountered a very rude interviewer, though that is just my side of the story and for all I know, he is currently blogging about his “entitled interviewee.” While searching his LinkedIn I learned that he has since been promoted from manager to director at a major company — I need to acknowledge that maybe, just maybe, I gave him a bad demonstration.</p><h4>The Problem</h4><p><a href="https://leetcode.com/problems/valid-parentheses/">Valid Parentheses</a></p><p>Difficulty: Easy</p><p>Skill required: Stacks</p><p>Description: <em>Given a string </em><em>s containing just the characters </em><em>&#39;(&#39;, </em><em>&#39;)&#39;, </em><em>&#39;{&#39;, </em><em>&#39;}&#39;, </em><em>&#39;[&#39; and </em><em>&#39;]&#39;, determine if the input string is valid.</em></p><p><em>An input string is valid if:</em></p><ol><li><em>Open brackets must be closed by the same type of brackets.</em></li><li><em>Open brackets must be closed in the correct order.</em></li><li><em>Every close bracket has a corresponding open bracket of the same type.</em></li></ol><h4>The JavaScript Angle</h4><p>I already covered this problem in C++, but there are a couple of mental leaps. First of all, a Stack is the perfect data structure. If you receive an opening character, push to the stack. If you receive a closing character, pop from the stack. Verify that the character you popped off the stack matches. If it does, keep processing. If it does not, you do not have a valid set of matching parentheses and should return “false/invalid” on the entire string.</p><p>The second mental leap is that you need a way to map the values. Two weeks ago I did this with a function, but you can easily achieve the same thing with a hashmap. A ( maps to ), a [ maps to ], a { maps to }.</p><p>For your entertainment, I am going to show you my first accepted LeetCode JavaScript solution.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/30d9544bf5300e8b9ce2656af3ed9261/href">https://medium.com/media/30d9544bf5300e8b9ce2656af3ed9261/href</a></iframe><p>Why did I bring up the “rude interviewer” story? Was it just my excuse to vent and rage against a person I am not identifying, at a company I am not identifying? Well…yes…but it is also a story that demonstrates the importance of programming language. In LeetCode, you can just switch language. In a real interview, like that one, the interviewer may require you to pick one language. That is what happened there. I could not use C++ and really stumbled.</p><p>First thing: <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map">This is a map in JavaScript</a>. To add key-value pairs to the map, you can use the set function. To retrieve values by key, you can use the get function. Why my frustrated console.log statements? You can use get(), but you cannot simply retrieve values using square brackets, the way you might in C++.</p><p>The second set of console.log statements were me working through another bug. I was trying to go from value to key instead of key to value, which is <a href="https://stackoverflow.com/questions/47135661/how-can-i-get-a-key-in-a-javascript-map-by-its-value">technically possible, but less efficient</a>…and arguably defeats the purpose of using a map in that manner.</p><p>A bit confusing for me — JavaScript does not have a data structure explicitly called the stack, but <a href="https://stackoverflow.com/questions/1590247/how-do-you-implement-a-stack-and-a-queue-in-javascript">it has arrays and arrays have push and pop methods that behave exactly like those of a stack</a>. The array does <em>not</em> have a method called top(), meaning I used the rather confusing <em>s1[s1.length-1]</em> to retrieve the top.</p><p>This, at least in my opinion, is counterintuitive. You can read more about it on <a href="https://stackoverflow.com/questions/38127958/how-to-get-the-last-item-of-array-without-pop">StackOverflow here</a>, but a stack is first-in, last-out and you want the <em>last</em> element in the array. So you can use array[array.length-1] to get top, and not array[0].</p><p>Here is the code again, cleaned up:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/e26af4bb58cbd4b39249fa705496b0a4/href">https://medium.com/media/e26af4bb58cbd4b39249fa705496b0a4/href</a></iframe><p>Note that line 26 was changed to ===. The use of == there was a mistake.</p><p><a href="https://softwareengineering.stackexchange.com/questions/268124/does-using-in-javascript-ever-make-sense">There is some debate over == vs === on StackExchange</a>. Some say that == is <em>never</em> good, and others argue that only a Sith believes in absolutes, but I used == simply out of habit.</p><p><a href="https://www.freecodecamp.org/news/var-let-and-const-whats-the-difference/">Let, var, and const are explained here</a>. This is a big topic and is worth revisiting. For now, I <em>hope</em> I made the correct decisions in let vs. const vs. var (I did not use var here at all), but to some extent it is a matter of preference and there is some debate on StackOverflow over which is most error-prone.</p><h4>Closing Thoughts</h4><p>This could take some getting used to.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4e07d0cbc97c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/repeat-code-with-leetcode/repeat-code-with-leetcode-valid-parentheses-but-with-javascript-4e07d0cbc97c">Repeat Code With LeetCode — Valid Parentheses, But With JavaScript</a> was originally published in <a href="https://medium.com/repeat-code-with-leetcode">Repeat Code With LeetCode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Repeat Code With LeetCode — Valid Parentheses]]></title>
            <link>https://medium.com/repeat-code-with-leetcode/repeat-code-with-leetcode-valid-parentheses-d8e1dda6d909?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/d8e1dda6d909</guid>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 23 Jun 2023 15:55:15 GMT</pubDate>
            <atom:updated>2024-12-26T20:56:43.239Z</atom:updated>
            <content:encoded><![CDATA[<h3>Repeat Code With LeetCode — Valid Parentheses</h3><h4>If you add a colon and turn your face sideways, it looks like a smiley face!!!</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Ox-OT1nH7dWiCwGMmT54-g.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/pt-br/@abischreider?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Abi Schreider</a> on <a href="https://unsplash.com/photos/yb16pT5F_jE?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a>. CLOSE ENOUGH.</figcaption></figure><p>The real motivation here was to start using a programming language other than C++, starting with something easy, but this easy problem was “hard” enough for me that I decided to cover it again in two or three parts. This will be the C++ version.</p><p>I actually encountered it before in an interview for a series C startup, and I passed, with the two caveats that I had 15 minutes but only had to explain <em>how</em> I would solve it. If I remember correctly, our conversation went something like this:</p><blockquote>Me: I would use a stack. I would push to the stack every time I have an opening character, and pop from the stack every time I find a corresponding closing character <br>Interviewer: Fine. Let’s say you had an opening curly brace. Then you had a closing curly brace. How would you know what maps to what?<br>Me: Well, I suppose I could use an unordered map. It doesn’t have to be an unordered map, though…it could just be a vector of structs</blockquote><p>This problem is basically a perfect use case for a stack, which you can think of as a….</p><p>…uh…please don’t kill me…</p><p>…a stack. A stack is a stack. <a href="https://en.wikipedia.org/wiki/Stack_(abstract_data_type)">It is best characterized as last in, first out</a>, but even that takes a bit away from the metaphor. Think of a stack of plates, as Wikipedia shows us. If you want to add to a stack, you put something at the top. If you want to take elements out of the stack, you have to take from the top as well. You also have a “peek” operation, which gives you the ability to look at the top element.</p><p>Instead of just closing with “use a stack and you are good,” I thought I would share with you some of my struggles with this problem.</p><h4>The Problem</h4><p><a href="https://leetcode.com/problems/valid-parentheses/description/">Valid Parentheses</a></p><p>Difficulty: Easy</p><p>Skills Required: Stacks</p><p>Problem Description: <em>Given a string </em><em>s containing just the characters </em><em>&#39;(&#39;, </em><em>&#39;)&#39;, </em><em>&#39;{&#39;, </em><em>&#39;}&#39;, </em><em>&#39;[&#39; and </em><em>&#39;]&#39;, determine if the input string is valid.</em></p><p><em>An input string is valid if:</em></p><ol><li><em>Open brackets must be closed by the same type of brackets.</em></li><li><em>Open brackets must be closed in the correct order.</em></li><li><em>Every close bracket has a corresponding open bracket of the same type.</em></li></ol><h4>The (Rough) Solution</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1c40b2acd08d259aa40d927daf5559c7/href">https://medium.com/media/1c40b2acd08d259aa40d927daf5559c7/href</a></iframe><p>The above is some code I wrote that LeetCode accepted, with all of its comments and print statement glory. Here are a few things that I was thinking about:</p><p>First of all, my first implementation today failed because I did not do any kind of verification. If I saw an opening character I would push, and if I saw a closing character I would pop. This would fail on something like “[)”, as all the code would check is that there was an opening element, followed by a closing one.</p><p>Second, I did not think to use a hashmap (or unordered_map, which is a close approximation of a hashmap). Instead, I wrote a helper function that simply returned a corresponding closing character. This effectively achieved the same thing, but I can’t imagine anyone including that in a book solution.</p><p>Next were edge cases. If the size is 1, return false. If it begins with a closing character, return false.</p><p>Finally, I did some debugging (thought maybe my helper function was failing) until arriving at line 61. If you fail to obtain the correct closing character for the one you are checking, throw it out. The entire string is false.</p><h4>The Cleaner Solution</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/d005887cc400484595f6b98d0ee36ae6/href">https://medium.com/media/d005887cc400484595f6b98d0ee36ae6/href</a></iframe><p>The code above is a little easier to read. I wrote it some time ago. I saw it was doing a % 2 at the beginning, which I found clever, prompting me to wonder if I stole the code from someone else. Then I saw the code was using the stupid variable name “thisChar,” so it does look like my work.</p><p>To paraphrase the LeetCode explanation, the algorithm is:</p><ul><li>Find an opening bracket/character, push it to stack</li><li>Find a closing bracket/character, check top element of stack. If they are the same type (as in a pair, like ()), pop off stack and keep processing. Otherwise you reject the entire thing and return false</li></ul><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FWTzjTskDFMg%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DWTzjTskDFMg&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FWTzjTskDFMg%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/009eaa5a935458a624dfc8f7d29274ac/href">https://medium.com/media/009eaa5a935458a624dfc8f7d29274ac/href</a></iframe><h4>Closing Thoughts</h4><p>So…a few thoughts.</p><p>First of all, NeetCode is leaving Google to return to coding interview videos full-time. This is a good thing for us, but I cannot help but feel disappointed. The Software Engineer Prophecy wrote that a Chosen One would obtain a job at Google, then change their interview process. I may have been misreading the prophecy, though.</p><p>Second, another programming language would be useful. I have had more than a few experiences of an interviewer expecting a specific programming language.</p><p>This could double with my other blog, allowing me to gain and demonstrate basic competencies in other programming languages.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d8e1dda6d909" width="1" height="1" alt=""><hr><p><a href="https://medium.com/repeat-code-with-leetcode/repeat-code-with-leetcode-valid-parentheses-d8e1dda6d909">Repeat Code With LeetCode — Valid Parentheses</a> was originally published in <a href="https://medium.com/repeat-code-with-leetcode">Repeat Code With LeetCode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Repeat Code With LeetCode — Number Of Islands]]></title>
            <link>https://medium.com/repeat-code-with-leetcode/repeat-code-with-leetcode-number-of-islands-d331c530414b?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/d331c530414b</guid>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[interview]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 09 Jun 2023 14:54:39 GMT</pubDate>
            <atom:updated>2024-12-26T20:56:41.613Z</atom:updated>
            <content:encoded><![CDATA[<h3>Repeat Code With LeetCode — Number Of Islands</h3><h4>Flood the islands to get rejected by Amazon</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*TFErQ3H2DXpLunOhDSt3dg.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@michael75?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Michael</a> on <a href="https://unsplash.com/photos/DXQB5D1njMY?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></figcaption></figure><p>This is going to be a pretty quick post — not because the problem is easy, per se, but because it’s really not that different from Flood Fill. In fact, you can think of the core algorithm as a flood fill problem. Traverse every square in the matrix, flood fill every island, and return the final count. This does not just work on an intuitive level, but on a pun level as well. Flood the islands.</p><p><a href="https://corgicorporation.medium.com/repeat-code-with-leetcode-floodfill-b7b2edadee92">Repeat Code With LeetCode — Floodfill</a></p><h4>The Problem</h4><p><a href="https://leetcode.com/problems/number-of-islands">Problem: LeetCode 200</a></p><p>Difficulty: Medium</p><p>Skills Required: 2D arrays, graph theory, DFS (depending on implementation)</p><p>Description: Given an m x n 2D binary grid grid which represents a map of &#39;1&#39;s (land) and &#39;0&#39;s (water), return <em>the number of islands</em>.</p><p>An <strong>island</strong> is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.</p><h4>The Solution</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/80e9879c5292d00a05c7186f5151e2cd/href">https://medium.com/media/80e9879c5292d00a05c7186f5151e2cd/href</a></iframe><p>If you are like me and have LeetCode Premium, you may find yourself staring at their solution for a while. It works, but I did not find it 100% clear <em>why</em> it worked until I thought about it for a little while. Essentially, you are applying the “flood fill” operation repeatedly. Every “1” signifies an island, increments the count, and triggers a DFS. Every time you do this, have DFS set the starting value to 0. If you work this out with an example, I think it will become clear why the “repeated flood fill method” will not double-count anything from the same island, but will instead return the correct number of islands.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fo8S2bO3pmO4%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Do8S2bO3pmO4&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fo8S2bO3pmO4%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/fd7c2460e3f7dc3cd5654c07bd24c3d5/href">https://medium.com/media/fd7c2460e3f7dc3cd5654c07bd24c3d5/href</a></iframe><p>Kevin Naugthon Jr’s solution is a little clearer than mine, but I chose to write mine the way I wrote Flood Fill. When you see a recursive function, you are probably used to seeing something like this:</p><ul><li>Some base case is stated, causing the function to exit prematurely under certain conditions (most commonly when a value is NULL)</li><li>Some recursive call is made</li></ul><p>Kevin’s code has the base case segregated like that. Mine still has a base case, but it is implicit. Eventually dfs will stop being called because of how the grid’s bounds are defined.</p><p>He also verifies that the grid is not empty. I got the solution accepted by LeetCode, but in an interview this would be important.</p><h4>LeetCode Continuation</h4><p>I am not sure what else to say about this particular problem. This is the second problem I have done in a while on LeetCode, after a pretty long break.</p><p>Someone in the comments section wrote that Amazon failed them on the example LeetCode solution. The reason was that they did not support actually modifying the original grid. Instead, the candidate was expected to make a new 2D array and keep track of things that way.</p><p>At this point, I have been doing this for a pretty long time. Someone on r/leetcode asked how many problems a candidate has to do. The best answer was that this is the wrong metric — it’s more about having the ability to solve a random medium in 30–45 minutes.</p><iframe src="https://cdn.embedly.com/widgets/media.html?type=text%2Fhtml&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;schema=reddit&amp;url=https%3A//www.reddit.com/r/leetcode/comments/qadu8y/how_many_leetcode_questions_do_you_complete/&amp;image=" width="600" height="400" frameborder="0" scrolling="no"><a href="https://medium.com/media/e258737f45e62206e90be2bfe443412d/href">https://medium.com/media/e258737f45e62206e90be2bfe443412d/href</a></iframe><p>Which kind of begs the question — is this worthwhile? That’s the million dollar question. I have already complained about how it is not, and some commenters responded that LeetCode questions are used to assess problem solving ability. I guess what I still dislike is Jeff Atwood’s “<a href="https://blog.codinghorror.com/why-cant-programmers-program/">most candidates can’t even solve the simplest problems” attitude</a>, but that starts to bleed into other topics.</p><p>A coding interview is not standardized, as there is no universal “license to code” or “general programming certification” to insert into job applications. Yet somehow we have found ourselves in a world where so many companies model their interview process after Google that entire courses and boot camps have emerged that specifically coach people in the ability to pass programming interviews.</p><p>I guess all of this is to say — no problem is necessarily easy, at least not at first. The worst interviewers you encounter will look at you like the problem they just assigned is the easiest thing they have ever seen, and how dare you waste their time with your pitiful brute force implementation. Clearly your inability to solve “number of islands” in 30 minutes with an optimal algorithm means you have never written code before, you incompetent imposter.</p><p>We all have to start somewhere, we are all steadily learning, and sooner or later we all suffer the consequences of interviews that are not that similar to actual tasking for software engineers.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d331c530414b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/repeat-code-with-leetcode/repeat-code-with-leetcode-number-of-islands-d331c530414b">Repeat Code With LeetCode — Number Of Islands</a> was originally published in <a href="https://medium.com/repeat-code-with-leetcode">Repeat Code With LeetCode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Repeat Code With LeetCode — Floodfill]]></title>
            <link>https://medium.com/repeat-code-with-leetcode/repeat-code-with-leetcode-floodfill-b7b2edadee92?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/b7b2edadee92</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[software-development]]></category>
            <category><![CDATA[software-engineering]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 26 May 2023 14:13:03 GMT</pubDate>
            <atom:updated>2024-12-26T20:56:40.352Z</atom:updated>
            <content:encoded><![CDATA[<h3>Repeat Code With LeetCode — Floodfill</h3><h4>A foray into the 2D array</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SfosTayelpwWuzdmXE1k8Q.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@sigmund?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Sigmund</a> on <a href="https://unsplash.com/photos/bY4qZelcnTw?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a>. I really couldn’t find a good Unsplash photo for this</figcaption></figure><p>I purchased an annual subscription to LeetCode Premium several months ago, which was great and useful until I promptly stopped using it. The value, in my opinion, is in their well-written solutions — <a href="https://leetcode.com/problems/flood-fill/description/">Flood Fill</a> contains an exceptionally bad LeetCode Premium solution that is essentially just “Use DFS,” followed by the code.</p><p>Before I continue, let me address the elephant in the room: Another Medium blog called “Chunks” has already covered this better than I have.</p><p><a href="https://codechunkers.medium.com/solution-to-leetcodes-flood-fill-a84b3917ee1b">Solution to Leetcode’s Flood Fill</a></p><p>The problem is ranked as an “easy,” but the candidate has to work with a 2D array. I have seen 2D arrays come up in real interviews before. CodeSignal, unless the test has changed significantly, ALWAYS has a difficult 2D array problem as #3. One company, a major financial institution headquartered in Manhattan, asked me to solve <a href="https://codechunkers.medium.com/solution-to-leetcodes-flood-fill-a84b3917ee1b">Word Search</a>. Another company, my dream company, asked me to take a 2D array with a collection of arbitrarily placed people and to then optimally place a coffee shop such that the people had to walk a minimum distance.</p><p>Are these kinds of problems actually useful in the field? Sure. 2D array problems really do show up in the field, I just have yet to find a situation in which someone has to solve one in 45 minutes.</p><h4>The Problem</h4><p><a href="https://leetcode.com/problems/flood-fill/description/">733. Flood Fill</a></p><p>Description: An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.</p><blockquote>You are also given three integers sr, sc, and color. You should perform a <strong>flood fill</strong> on the image starting from the pixel image[sr][sc].</blockquote><blockquote>To perform a <strong>flood fill</strong>, consider the starting pixel, plus any pixels connected <strong>4-directionally</strong> to the starting pixel of the same color as the starting pixel, plus any pixels connected <strong>4-directionally</strong> to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.</blockquote><blockquote>Return <em>the modified image after performing the flood fill</em>.</blockquote><p>Difficulty: Easy</p><p>Skills Required: 2D arrays; DFS; recursion</p><h4>The Solution</h4><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/dd844c425e008eb7b0476784d2f4bc08/href">https://medium.com/media/dd844c425e008eb7b0476784d2f4bc08/href</a></iframe><p>On the LeetCode discussion board for this problem, one user complained that 4-directionally is confusing. I suppose a better term may have been “adjacent, non-diagonal.” Before solving this problem, it helps to work out the example on paper. As Nick White explains (his video will be linked shortly), the 1 on the bottom right never changes because it is surrounded by 0s — there is no way to possibly reach it.</p><p>In spite of being a ranked “easy,” I think there are a few things that are easy to screw up here:</p><ul><li>Without line 30, you get a stack overflow</li><li>Without proper bounds checking, you get a…wait for it…out-of-bounds exception</li><li>It’s row, column. That’s something you have to know to solve these kinds of problems, and something you may have had beaten over you in college exams. <a href="http://www2.dsu.nodak.edu/users/mberg/Matrix/matrices.htm">Some people suggest thinking about RC Cola</a>, which would be an excellent mnemonic if anyone I knew drank it</li><li>Notice the difference between lines 12 and 20. Either you get the number of rows, which is the size of the 2D array, or you retrieve any row and get its number of columns</li></ul><p>What I wrote is based on the LeetCode solution. Nick White’s solution may be easier to digest. The code above does use recursion and does have a base case, but Nick White’s base case is more explicit.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FaehEcTEPtCs%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DaehEcTEPtCs&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FaehEcTEPtCs%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="640" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/6b85403f84f4366dbfc20b18513c6d43/href">https://medium.com/media/6b85403f84f4366dbfc20b18513c6d43/href</a></iframe><p>To put this as simply as possible, you solve this problem using a recursive implementation of DFS. You need to do bounds checking, and you “fan out” to do your flood fill, keeping track of your original color in the process.</p><h4>Closing Thoughts</h4><p>I thought this would be longer, but I guess that’s kind of it.</p><p>I am hoping to get back into LeetCode now.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F8wysIxzqgPI%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D8wysIxzqgPI&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F8wysIxzqgPI%2Fhqdefault.jpg&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/fc0486d3620903f0e771657594302c9d/href">https://medium.com/media/fc0486d3620903f0e771657594302c9d/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b7b2edadee92" width="1" height="1" alt=""><hr><p><a href="https://medium.com/repeat-code-with-leetcode/repeat-code-with-leetcode-floodfill-b7b2edadee92">Repeat Code With LeetCode — Floodfill</a> was originally published in <a href="https://medium.com/repeat-code-with-leetcode">Repeat Code With LeetCode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Very, Very Surface-Level Look At Transformers]]></title>
            <link>https://corgicorporation.medium.com/a-very-very-surface-level-look-at-transformers-in-gpt-412b6f16face?source=rss-88466123bc8d------2</link>
            <guid isPermaLink="false">https://medium.com/p/412b6f16face</guid>
            <category><![CDATA[software-engineering]]></category>
            <category><![CDATA[artificial-intelligence]]></category>
            <category><![CDATA[chatgpt]]></category>
            <category><![CDATA[data-science]]></category>
            <category><![CDATA[software-development]]></category>
            <dc:creator><![CDATA[Curt Corginia]]></dc:creator>
            <pubDate>Fri, 12 May 2023 17:56:33 GMT</pubDate>
            <atom:updated>2023-05-12T20:58:11.916Z</atom:updated>
            <content:encoded><![CDATA[<h4>Or “Documenting My Struggle To Understand Transformers”</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*w9_idU5dKb54V7d-cxEXQw.jpeg" /><figcaption>Photo by <a href="https://unsplash.com/@tetrakiss?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Arseny Togulev</a> on <a href="https://unsplash.com/photos/uPuh-VwJRM0?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a>. I didn’t understand the diagrams, so here’s me stupidly linking a picture of the anime mech.</figcaption></figure><p>Transformers are a key part of what makes models like GPT-3, GPT-4, and chatbots like ChatGPT so powerful. In 2017, a paper came out called <a href="https://arxiv.org/pdf/1706.03762.pdf">Attention Is All You Need</a> — the paper is only 15 pages long but has been cited more than 70,000 times. You can find a number of blog posts on Medium that reference the paper, a <a href="https://www.youtube.com/watch?v=rURRYI66E54">2020 YouTube video by Computerphile</a> that references the paper, and <a href="https://jalammar.github.io/illustrated-transformer/">this illustrated guide to the paper on GitHub.io</a>, licensed under Creative Commons and open for redistribution, so long as it is not done for commercial purposes (note the lack of a star or paywall on this blog post). If you can read the 15-page paper and understand everything, great. You probably have background knowledge in this, and you have saved time.</p><p>For the rest of us…</p><p>GPT stands for Generative Pretrained Transformer. You can <a href="https://openai.com/blog/chatgpt">try ChatGPT here</a>, and they released GPT-4 about two months ago. A <strong>Transformer</strong> is a model that uses attention, and this approach is now a reliable alternate to the Recurrent Neural Network, which Computerphile characterizes as “inherently serial,” so that it cannot scale in the same way. Transformers, on the other hand, <a href="https://jalammar.github.io/illustrated-transformer/">lend themselves to parallelization</a>. From the IBM blog post about recurrent neural networks:</p><blockquote>Like feedforward and convolutional neural networks (CNNs), recurrent neural networks utilize training data to learn. They are distinguished by their “memory” as they take information from prior inputs to influence the current input and output. While traditional deep neural networks assume that inputs and outputs are independent of each other, the output of recurrent neural networks depend on the prior elements within the sequence.<br> — <a href="http://Like feedforward and convolutional neural networks (CNNs), recurrent neural networks utilize training data to learn. They are distinguished by their “memory” as they take information from prior inputs to influence the current input and output. While traditional deep neural networks assume that inputs and outputs are independent of each other, the output of recurrent neural networks depend on the prior elements within the sequence.">Source</a></blockquote><p>If you know what these terms mean, great. If not, you probably have the following questions:</p><ul><li>What is a Recurrent Neural Network, and how does it work?</li><li>WHY is a transformer able to overcome a limitation of Recurrent Neural Networks?</li><li>What is attention and how does attention work?</li></ul><p>What I had wanted to do was title this blog post something like “A Gentle Introduction To Transformers,” “Transformers Explained,” or “Why We Care About Transformers And How They Work.” Instead, I want to put my writing out there for entertainment value. I will start with the least confusing and least debatable topics, then fan out to the point that I will be going over the actual math involved…and mainly just using quotes, because I do not follow it all.</p><p>(Edit: The diagrams and explanations you see here will be for transformers in general. GPT still uses transformers, but will not follow this exact architecture. ChatGPT, for example, <a href="https://datascience.stackexchange.com/questions/118260/chatgpts-architecture-decoder-only-or-encoder-decoder#:~:text=%22As%20a%20language%20model%2C%20ChatGPT%20does%20not%20have,sequences%20and%20generate%20outputs%20based%20on%20that%20input.">is a decoder-only model</a>)</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FrURRYI66E54%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DrURRYI66E54&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FrURRYI66E54%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/c3e2fb3e3dd44ea4886a8d589ceca0f2/href">https://medium.com/media/c3e2fb3e3dd44ea4886a8d589ceca0f2/href</a></iframe><p><a href="https://jalammar.github.io/illustrated-transformer/">The Illustrated Transformer</a></p><h4>The Surface-Level Explanation</h4><p>Transformers are used in OpenAI language models. You will notice that most of these sources are from several years ago, but transformers are still very relevant today.</p><p>From this TowardsDataScience post by Giuliano Giacaglia:</p><p><a href="https://towardsdatascience.com/transformers-141e32e69591">Transformers</a></p><ul><li>Transformers solve the problem of sequence transduction, meaning they transform an input sequence to an output sequence. For example, maybe we are translating an input sentence into French</li><li>Recurrent Neural Networks have been used to deal with this problem in the past. They have a chain-like structure</li><li>A transformer uses a self-attention layer. A decoder focuses on relevant parts of the input sentence, analogous to how real human attention works</li></ul><h4>Recurrent Neural Networks</h4><p>From <a href="https://jalammar.github.io/visualizing-neural-machine-translation-mechanics-of-seq2seq-models-with-attention/">Alammar</a>:</p><ul><li>A sequence-to-sequence model is made up of an encoder and a decoder, both of which tend to be recurrent neural networks</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/998/1*p9XoIbg81TO1urljJMCw3g.png" /><figcaption>Source: <a href="https://jalammar.github.io/visualizing-neural-machine-translation-mechanics-of-seq2seq-models-with-attention/">https://jalammar.github.io/visualizing-neural-machine-translation-mechanics-of-seq2seq-models-with-attention/</a></figcaption></figure><ul><li>The decoder maintains a hidden state that it passes from one step to the next (if you visit the above, that screenshot is a full video translating a French sentence to an English sentence. As already stated, memory is crucial here and all states impact the one that comes next — it’s linear)</li><li>The mechanism is described in much more detail <a href="https://proceedings.neurips.cc/paper_files/paper/2014/file/a14ac55a4f27472c5d894ec1c3c743d2-Paper.pdf">here</a> and <a href="https://emnlp2014.org/papers/pdf/EMNLP2014179.pdf">here</a>. These are two pioneering papers about recurrent neural networks, totaling about 30 pages in length</li></ul><p>I have another example of a recurrent neural network. It’s me using CakeChat on one of my sister blogs, many months ago, blindly copying steps from the GitHub to train a chatbot from some canned Twitter data and then interface with the backend using Telegram. Anyone can tell you that this is not a fair representation of <em>all</em> recurrent neural networks, but it’s also a GitHub that very clearly articulates that it turned into an archive because transformers outperformed recurrent neural networks like itself.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/451/1*5ZsR9DhzKiTwXlN3m7DFog.png" /></figure><p>This is Sharon. Sharon sucks. I wanted to make my own Replika, which I believe was based on GPT-3 at the time. Replika is a good chatbot. ChatGPT is a good chatbot. The above is just dumb.</p><h4>Attention</h4><blockquote>We propose a new simple network architecture, the Transformer, based solely on attention mechanisms, dispensing with recurrence and convolutions entirely. Experiments on two machine translation tasks show these models to be superior in quality while being more parallelizable and requiring significantly less time to train<br> — From the key paper, <a href="https://arxiv.org/pdf/1706.03762.pdf">Attention Is All You Need</a></blockquote><p>Here is a picture of the transformer architecture.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*gjENAaiqb3WStfWGuv8XTQ.png" /><figcaption>By Yuening Jia — DOI:10.1088/1742–6596/1314/1/012186, CC BY-SA 3.0, <a href="https://commons.wikimedia.org/w/index.php?curid=121340680">https://commons.wikimedia.org/w/index.php?curid=121340680</a></figcaption></figure><p>You can find Pytorch implementation annotations on the Attention paper, and they also have a GitHub. So…here.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/652/1*roSq3ghC8DCh6sJNPRRbDw.png" /><figcaption>Source: <a href="https://github.com/harvardnlp/annotated-transformer/blob/master/the_annotated_transformer.py">https://github.com/harvardnlp/annotated-transformer/blob/master/the_annotated_transformer.py</a></figcaption></figure><p>…hopefully that clears everything up.</p><p>At a basic level, encoders in transformers use a self-attention layer. The encoder “<a href="https://jalammar.github.io/illustrated-transformer/">looks at other words in the input sentence as it encoders a specific word</a>.” The decoder has an attention layer that focuses on relevant parts of the input sentence — it is analogous to how real human attention works.</p><p><a href="https://ai.stackexchange.com/questions/20075/why-does-the-transformer-do-better-than-rnn-and-lstm-in-long-range-context-depen">Transformers are non-sequential</a>. They overcome the limitations of recurrent neural networks by providing a different underlying model, one that is more easily parallelizable.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/998/1*zbD-NjfcjRwsHAch55uReg.png" /><figcaption><a href="https://jalammar.github.io/illustrated-transformer/">https://jalammar.github.io/illustrated-transformer/</a></figcaption></figure><p>Now I am going to just go off, doing my best to summarize the steps of self-attention from the GitHub I keep referencing. To understand it better, please read the actual GitHub.</p><p>Calculate self-attention by creating three vectors from each of the encoder’s input vectors. Create a query vector, a key vector, and a value vector per word. I refuse to elaborate.</p><p>Calculate scores by taking the dot product of the query vector and the key vector of the respective word you are scoring.</p><p>Divide scores by 8 to achieve a stable gradient, then use softmax for normalization.</p><p>Multiply by software score. Sum weighted values.</p><p>Okay, I am going to put this on my to-do list. Here is a class I found <a href="https://web.stanford.edu/class/cs224n/index.html#coursework">called CS224N, from Stanford</a>. I see their slides are publicly available at the bottom of the page.</p><p>Here is one of their assignments, <a href="https://web.stanford.edu/class/archive/cs/cs224n/cs224n.1214/assignments/a5.pdf">assignment 5</a>, that challenges students to explore the math behind self-attention. <a href="https://web.stanford.edu/class/cs224n/readings/cs224n-self-attention-transformers-2023_draft.pdf">Here is a reading they posted that will probably help</a>. Unfortunately for my readers, I do not see any publicly available midterms/answer keys they put up. In fact, it doesn’t look like this course even has midterms.</p><p>So yeah, I will be sure to read all their slides, learn all the math, and solve some of their problem sets. Someday. Of course.</p><p>Until then, I do not understand the math behind this.</p><h4>Closing Thoughts</h4><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2FOWIxzE2D7Xk%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DOWIxzE2D7Xk&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2FOWIxzE2D7Xk%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/d08937cead0911ba23c28da19a182ade/href">https://medium.com/media/d08937cead0911ba23c28da19a182ade/href</a></iframe><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=412b6f16face" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>