(public).sospep.subjects ~ view article ~ how-to-rock-an-algorithms-interview

<h1 style="text-align: center;">how to rock an algorithms interview</h1>
<h2>[WHAT]</h2>
<ol>
<li>] by Kevin @ palantir -&nbsp;</li>
<ol>
<li>] the original URL redirects to palantirs home page</li>
<li>] found a copy of that on the wayback machine, link seems to be inconsistent to access the article, view view snapshot on 2011-09-29</li>
<li>] copied article text into body&nbsp;</li>
</ol></ol>
<h2>[WHY]</h2>
<ol>
<li>]&nbsp;</li>
</ol>
<h2>[WHERE]</h2>
<ol>
<li><strong>] READ THE FULL ARTICLE</strong></li>
<ol>
<li>]&nbsp;</li>
<li>]&nbsp;<a href="https://web.archive.org/web/20110929132042/http://blog.palantir.com/2011/09/26/how-to-rock-an-algorithms-interview/%20" target="_blank">https://web.archive.org/web/20110929132042/http://blog.palantir.com/2011/09/26/how-to-rock-an-algorithms-interview/</a>&nbsp;</li>
<li>]&nbsp;https://web.archive.org/web/20110929132042/http://blog.palantir.com/2011/09/26/how-to-rock-an-algorithms-interview/</li>
</ol></ol>
<h2>[WHEN]</h2>
<ol>
<li>] SUMM published 2017-01-28</li>
<li>] ART published 2011-09-26</li>
</ol>
<h2>[EXAMPLE]</h2>
<ol>
<li>] understand the problem</li>
<li>] come up with a solution (any solution)</li>
<li>] start writing on the board</li>
<li>] talk it through</li>
<li>] <span style="text-decoration: underline;">think algorithms</span></li>
<li>] <span style="text-decoration: underline;">think data-structures</span></li>
<li>] think related-problems</li>
<li>] think decomposition - modify the problem by breaking it up into smaller problems</li>
</ol>
<h2>[HOW-TO]</h2>
<ol>
<li>]</li>
</ol>
<h2>[REFERENCE]</h2>
<ol>
<li>] SRC = HN, (#)<a href="https://news.ycombinator.com/item?id=3039873" target="_blank">comments</a>(#)</li>
</ol>
<h2>[RELATED]</h2>
<div><ol>
<li>] <a href="/view/chapters?id=182" target="_blank">BOOK-algorithms</a></li>
<li>] palantir</li>
<li>] are there any open source alternatives to palantir</li>
</ol></div>
<div><hr /></div>
<div>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;"><span style="color: #444444; font-family: Verdana, Helvetica, sans-serif;"><span style="font-size: 12px;"><a href="http://www.xkcd.com/399/" target="_blank">http://www.xkcd.com/399/</a></span></span></p>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">&nbsp;</p>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">We do a lot of interviewing at Palantir, and let me tell you: it&rsquo;s hard. I don&rsquo;t mean that we ask tough questions (although we do). I mean that the task of evaluating a candidate is hard.</p>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">The problem? Given a whiteboard and one hour, determine whether the person across from you is someone you&rsquo;d like to work with, in the trenches, for the next n years. A candidate&rsquo;s performance during an interview is only weakly correlated with his or her true potential, but we&rsquo;re stuck with the problem of turning the chickenscratch on the whiteboard into an &lsquo;aye&rsquo; or &lsquo;nay&rsquo;. Sometimes it feels like a high-stakes game of reading tea leaves. Believe me we&rsquo;re doing our best, but we&rsquo;re often left the nagging worry that we&rsquo;re passing up brilliant people who just had a bad day or who didn&rsquo;t click with a particular problem.</p>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">In an effort to improve this situation, we wanted to write up a guide that will help candidates make sense of this process, or at least the part known as an Algorithms Interview. At Palantir we ask questions that test for a lot of different skills &mdash; coding, design, systems knowledge, etc. &mdash; but one of our staple interviews is to ask you to design an algorithm to solve a particular problem.</p>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">It usually starts like this:</p>
<blockquote style="margin: 0px; padding: 0px 0px 0px 2em; border-left: 2px solid #ff5400; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em;">Given X, figure out an efficient way to do Y.</p>
</blockquote>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;"><strong>First: Make sure you understand the problem</strong>. You&rsquo;re not going to lose points asking for clarifications or talking through the obvious upfront. This will also buy you time if your brain isn&rsquo;t kicking in right away. Nobody expects you to solve a problem in the first 30 seconds or even the first few minutes.</p>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">Once you understand the problem,&nbsp;<strong>try to come up with a solution &ndash; any solution whatever</strong>. As long as it&rsquo;s valid, it doesn&rsquo;t matter if your solution is trivial or ugly or extremely inefficient. What matters is that you&rsquo;ve made progress. This does two things: (1) it forces you to engage with the structure of the problem, priming your brain for improvements you can make later, and (2) it gives you something in the bank, which will in turn give you confidence. If you can achieve a brute force solution to a problem, you&rsquo;ve cleared a major hurdle to solving it in a more efficient way.</p>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">Now comes the hard part. You&rsquo;ve given an O(n^3) solution and your interviewer asks you to do it faster. You stare at the problem, but nothing&rsquo;s coming to you. At this point, there are a few different moves you can make, depending on the problem at hand and your own personality. Almost all of these can help on almost any problem:</p>
<ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;"><ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">
<li style="margin: 0px; padding: 0px;"><strong>Start writing on the board</strong>. This may sound obvious, but I&rsquo;ve had dozens of candidates get stuck while staring at a blank wall. Maybe they&rsquo;re not visual people, but still I think it&rsquo;s more productive to stare at some examples of the problem than to stare at nothing. If you can think of a picture that might be relevant, draw it. If there&rsquo;s a medium-sized example you can work through, go for it. (Medium-sized is better than small, because sometimes the solution to a small example won&rsquo;t generalize.) Or just write down some propositions that you know to be true. Anything is better than nothing.</li>
</ol></ol>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em;">&nbsp;</p>
<ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;"><ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">
<li style="margin: 0px; padding: 0px;"><strong>Talk it through</strong>. And don&rsquo;t worry about sounding stupid. If it makes you feel better, tell your interviewer, &ldquo;I&rsquo;m just going to talk out loud. Don&rsquo;t hold me to any of this.&rdquo; I know many people prefer to quietly contemplate a problem, but if you&rsquo;re stuck, talking is one way out of it. Sometimes you&rsquo;ll say something that clearly communicates to your interviewer that you understand what&rsquo;s going on. Even though you might not put much stock in it, your interviewer may interrupt you to tell you to pursue that line of thinking. Whatever you do, please DON&rsquo;T fish for hints. If you need a hint, be honest and ask for one.</li>
</ol></ol>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em;">&nbsp;</p>
<ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;"><ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">
<li style="margin: 0px; padding: 0px;"><strong>Think algorithms</strong>. Sometimes it&rsquo;s useful to mull over the particulars of the problem-at-hand and hope a solution jumps out at you (this would be a bottom-up approach). But you can also think about different algorithms and ask whether each of them applies to the problem in front of you (a top-down approach). Changing your frame of reference in this way can often lead to immediate insight. Here are some algorithmic techniques that can help solve more than half the problems we ask at Palantir:
<ul style="margin: 0px 0px 1em 2em; padding: 0px; list-style: disc;">
<li style="margin: 0px; padding: 0px;">Sorting (plus searching / binary search)</li>
<li style="margin: 0px; padding: 0px;">Divide-and-conquer</li>
<li style="margin: 0px; padding: 0px;">Dynamic programming / memoization</li>
<li style="margin: 0px; padding: 0px;">Greediness</li>
<li style="margin: 0px; padding: 0px;">Recursion</li>
<li style="margin: 0px; padding: 0px;">Algorithms associated with a specific data structure (which brings us to our fourth suggestion&hellip;)</li>
</ul>
</li>
</ol></ol>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em;">&nbsp;</p>
<ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;"><ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">
<li style="margin: 0px; padding: 0px;"><strong>Think data structures</strong>. Did you know that the top 10 data structures account for 99% of all data structure use in the real world? Probably not, because I just made those numbers up &mdash; but they&rsquo;re in the right ballpark. Yes, on occasion we ask a problem whose optimal solution requires a&nbsp;<a style="color: #e33e0e; text-decoration-line: none;" href="https://web.archive.org/web/20110929132042/http://en.wikipedia.org/wiki/Bloom_filter">Bloom filter</a>&nbsp;or&nbsp;<a style="color: #e33e0e; text-decoration-line: none;" href="https://web.archive.org/web/20110929132042/http://en.wikipedia.org/wiki/Suffix_tree">suffix tree</a>, but even those problems tend to have a near-optimal solution that uses a much more mundane data structure. The data structures that are going to show up most frequently are:
<ul style="margin: 0px 0px 1em 2em; padding: 0px; list-style: disc;">
<li style="margin: 0px; padding: 0px;">Array</li>
<li style="margin: 0px; padding: 0px;">Stack / Queue</li>
<li style="margin: 0px; padding: 0px;">Hashset / Hashmap / Hashtable / Dictionary</li>
<li style="margin: 0px; padding: 0px;">Tree / binary tree</li>
<li style="margin: 0px; padding: 0px;">Heap</li>
<li style="margin: 0px; padding: 0px;">Graph</li>
</ul>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em;">You should know these data structures inside and out. What are the insertion/deletion/lookup characteristics? (O(log n) for a balanced binary tree, for example.) What are the common caveats? (Hashing is tricky, and usually takes O(k) time when k is the size of the object being hashed.) What algorithms tend to go along with each data structure? (<a style="color: #e33e0e; text-decoration-line: none;" href="https://web.archive.org/web/20110929132042/https://secure.wikimedia.org/wikipedia/en/wiki/Dijkstra%27s_algorithm">Dijkstra&rsquo;s</a>&nbsp;for a graph.) But when you understand these data structures, sometimes the solution to a problem will pop into your mind as soon as you even think about using the right one.</p>
</li>
</ol></ol>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em;">&nbsp;</p>
<ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;"><ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">
<li style="margin: 0px; padding: 0px;"><strong>Think about related problems you&rsquo;ve seen before and how they were solved</strong>. Chances are, the problem you&rsquo;ve been presented is a problem that you&rsquo;ve seen before, or at least very similar. Think about those solutions and how they can be adapted to specifics of the problem at hand. Don&rsquo;t get tripped up by the form that the problem is presented &ndash; distil it down to the core task and see if matches something you&rsquo;ve solved in the past.</li>
</ol></ol>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em;">&nbsp;</p>
<ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;"><ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">
<li style="margin: 0px; padding: 0px;"><strong>Modify the problem by breaking it up into smaller problems.</strong>&nbsp;Try to solve a special case or simplified version of the problem. Looking at the corner cases is a good way to bound the complexity and scope of the problem. A reduction of the problem into a subset of the larger problem can give a base to start from and then work your way up to the full scope at hand.
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em;">Looking at the problem as a composition of smaller problems may also be helpful. For example, &ldquo;find a number in a sorted array which has been shifted cyclically by an unknown constant k&rdquo; can be solved by (1) first figuring out &ldquo;k&rdquo; and then (2) figuring out how to perform binary search on a shifted array).</p>
</li>
</ol></ol>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em;">&nbsp;</p>
<ol style="margin: 0px 0px 1em 2em; padding: 0px; list-style-position: initial; list-style-image: initial; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">
<li style="margin: 0px; padding: 0px;"><strong>Don&rsquo;t be afraid to backtrack</strong>. If you feel like a particular approach isn&rsquo;t working, it might be time to try a different approach. Of course you shouldn&rsquo;t give up too easily. But if you&rsquo;ve spent a few minutes on an approach that isn&rsquo;t bearing any fruit and doesn&rsquo;t feel promising, back up and try something else. I&rsquo;ve seen more candidates who overcommit than undercommit, which means you should (all else equal) be a little more willing to abandon an unpromising approach.</li>
</ol>
<p style="margin: 0px 0px 1em; padding: 0px; line-height: 1.5em; color: #444444; font-family: Verdana, Helvetica, sans-serif; font-size: 12px;">Incidentally, trying out a few different approaches (rather than sticking with a single approach) tends to work well in interviews, because the problems we choose for an interview usually have many different solutions. Happily, the same is true for the problems we solve on the job =)</p>
</div>
<h1 style="text-align: center;">&nbsp;</h1>

~ view article ~ Chapter] index FROM [ Book] algorithm IN [ libraries] technology-developer-software