10 ms·

Ask HN: How can I prepare for a coding interview in a week?

170 points by mattdue 8y ago

I am from ECE background, been working in machine learning, and data analysis fields for couple of years, and have decent coding experience in Python and C/C++. I am about to be interviewed by one of the big five (they reached out to me, I wasn't actively preparing for interviews). Not being from a CS or software engineering background, I never took an algorithm and data structure course, and from what I know the coding test mainly involves those. I know there are a ton of resources online for coding interview preparation, but I wanted to seek suggestions on an efficient/quick resource given that I have strong coding skills but not familiar with data structure/CS algorithm.

mailjenil 8y ago
https://www.interviewcake.com/ https://www.interviewcake.com/ Perfect if you want to crack something in a week
pushedx 8y ago
https://codesignal.com https://codesignal.com has a good intro-level course, make sure to focus on the "medium" difficulty and above problems
bunny9 8y ago
https://www.interviewbit.com https://www.interviewbit.com is a good platform to practice algorithm and data structure questions as if in an interview environment.
- shreyanshd 8y ago
  +1 for interviewbit. But it cannot be completed in a week if OP tries to solve all the problems. Instead focus should be on solving few questions from each category.
pmlnr 8y ago
Prepair on theoretical level as well, O notations, and such.
unixhero 8y ago
Probably good to know git
- unixhero 8y ago
  Currently downvoted by zealots. However this is a real requirement. I have friends who focus mostly on Git knowledge, in their interviews because it informs a lot about general knowledge of the developer. Trunking, merging and so on.
- expertentipp 8y ago
  yup. "git push -f" - allow it or ban it? Should git hooks run all tests locally?
  - pjc50 8y ago
    - Ban it for everyone; if you need it, temporarily grant power to the admin to fix something. - Only if they take a completely trivial amount of time
  - darepublic 8y ago
    may the force push with you. always.
fahimulhaq 8y ago
https://www.educative.io/d/InterviewPrep https://www.educative.io/d/InterviewPrep has courses to brush up on DS/Algorithms and problems to practice coding interviews.
hanselot 8y ago
I know this is going to come across as a stupid question, but I would like to ask what the point is of studying for an interview? I am self-taught (under guidance from a mentor) with no formal training, and don't understand why one would prepare for an interview by studying. Isn't that dishonest in a way? Shouldn't an interview determine if you are comfortable providing a service and (ultimately) generating profit for the company hiring you?
- fsloth 8y ago
  Um, yeah, not everything is completely rational. But look at it this way: if you want to hire a musician to a band, and you do large scale hiring, you probably want to put some minimum requirments like being able to play, and maybe handling rudimentary musical theory and being able to read sheet music. CS 101 stuff is exactly this - you understand the fundamental concepts and are capable of conversing in them. Musicians who have formal degrees are understood to handle the basic theory and everything that matters is how well they can play. There is no degree in CS that would guarantee you understand the fundamentals or you know how to combine the basic concepts into practice. I presume this is one of the rationales for whiteboarding. Of course, there are all sorts of weird and wacky bands that have other hiring policies but the big five are not weird nor wacky. Apparently how well the hiring went does not predict anything abouy on-job performance, but probably some whiteboarding will not let those people in who would be totally incapable of operating with basic CS theory. Sure, this leaves lot of potential talent out, but often hiring a bad apple is lot more expensive than discarding an ok candidate.
  - meggar 8y ago
    Actually bands hire the musician who has the look, sound and personality that fits whatever they're going for. Most of them don't know any theory beyond blues and folk chords. They might test them by jamming with them, but the decision has nothing to do with musical skills. So it's actually very similar to hiring in tech.
- dewey 8y ago
  It's not always about what you know, it's if you are able to read up on something and teach yourself. There's a high chance that you'll experience a lot of things at your job that you didn't know before and you'll have to read up on the topic and figure out how it works. Not much different from studying for a code interview.
shankr 8y ago
Truthfully, you don't have enough time. There are so many candidates who basically eat and breathe Data Structure and Algorithm for at least few months so that they can get into big five that your last one week preparation might not match up to them, especially without any prior experience like a course. I don't want to demoralize you, but how about you tell them that you aren't prepared right now, and would like to interview after 4-5 months. I think these companies are always looking for good talent, and don't mind interviewing someone later if they find the profile interesting.
- Yoric 8y ago
  I second that. I had no problem rescheduling interviews by several months with Big Five-style companies (including Big Five) in the past.
  - hackandtrip 8y ago
    OT question: what do you do in the meantime? Usually, those months prepping for interviews are: - if a graduating student, while you are graduating? - grabbing a "worse" job waiting for the interview?
    - zaptheimpaler 8y ago
      Ideally you are in college or in a job already. I guess if you’re in between then it makes sense to get another job. After all there is really no guarantee you will land the job at big 5 even after all the prep.
      - gcheong 8y ago
        "It makes sense to get another job". The problem there though is that almost every company now, at least in the Bay Area, seems to be doing these coding screens as that is now the standard set by the big 5. I guess you could consider it live practice.
- caseymarquis 8y ago
deleted 8y ago
[deleted]
Improvotter 8y ago
You could try reading/skimming over the book "Cracking the code interview" to get some insight in how the company handles interviews. The big five are in there so you'd get more information that way. Besides that, a week should be okay if you study hard and got good resources.
wodenokoto 8y ago
Ask your recruiter what the test contains and how it relates to the position they are interested in hiring you for, and then just strait up tell them, that you are not strong in algorithms and data structures, but you are strong in ECE and machine learning, and they should hire you for those things.
netgusto 8y ago
I'm in a similar situation RN, and this is my battle plan: 𝗗𝗮𝘆 01 * Backtracking - know how to solve 1 problem (Knight's tour) * Tree - implement BST * Tree traversal - implement DFS, BFS & DFS iterative 𝗗𝗮𝘆 02 * Quicksort - know how to implement * Mergesort - know how to implement * Binary search - know how to implement * Min/Max Heap (priority queue) - know how to implement 𝗗𝗮𝘆 03 * Graph - implement adjacency list * Graph traversal - implement DFS, BFS & DFS iterative * Graph algo - implement "Prim Minimum Spanning Tree" * Graph algo - Implement "Detect Cycles algo" 𝗗𝗮𝘆 04 * Graph algo - Implement "Detect Connected Components" algo * Graph algo - Implement "Lowest Common Ancestor" algo * Graph algo - Implement Djikstra single shortest path algo 𝗗𝗮𝘆 05 * Sets - Determine all subsets of a set * Sets - Determine Maximum consecutive subarray sum * Sets - Determine 2 sets intersection 𝗗𝗮𝘆 06 * String - Implement Levensthein Edit distance * String - Implement Polynomial Hash * String - Determine all substrings * String - Find anagrams 𝗗𝗮𝘆 07 * String - Implement KNP algorithm for pattern matching * Basic DS - Implement Queue, Stack, Dynamic array, Linked list absolutely cold ---- I chose javascript as the language for all this brushing up (no need to manage memory, and I can focus on the algo) It's a big list, but it's a traversal of the CS engineering domain that makes sense to me, and it's only a fraction of the expected knowledge for that kind of interview. ---- Edit: I pushed some of the code of this list on GH here: https://github.com/netgusto/brushup https://github.com/netgusto/brushup I struggle to implement each concept in the smallest, simplest way possible. I'll keep adding code as I write it.
- rimliu 8y ago
  Why would you want to work for a company which asks these question in the interview?
  - chosenbreed 8y ago
    > Why would you want to work for a company which asks these question in the interview? Presumably because it is one of the big five (I didn't know there was such a thing). I suspect it looks good on your CV. You'll always be a big five alumni :-)
    - 8y ago
rhizome31 8y ago
If the company is Google, be aware that they contact pretty much everybody. You shouldn't feel special because they contacted you. Why not stick to data science, which is very hot right now?
- tiborsaas 8y ago
  You think for data science position they won't test you with the usual algo questions?
hal9000xp 8y ago
I'm surprised nobody mentioned LeetCode. You can start solving 100 most popular interview questions (sort them by difficulty first): https://leetcode.com/problemset/top-100-liked-questions/ https://leetcode.com/problemset/top-100-liked-questions/ If you've never took any algorithm course and have only a week for preparation, it would be very difficult to prepare for coding interview. But I think you can at least finish all easy problems from this list. In this case, you may at least pass screening coding interview. Right now, I'm very actively interviewing with pretty selective high-frequency trading companies. I can say that LeetCode has pretty relevant set of interview problems. One more thing. Even if you solved a problem, always look at description of solution, if there is no description of solution, you should look at discussion. From there, you can find references to common algorithms/themes like binary search etc.
LandR 8y ago
Man, I've never studied for an interview... I turn up on the day, but then these interviews asking difficult algorithm question seem to be a rarity in the UK, thankfully. Our interview process seems to be much more reasonable.
- some_account 8y ago
  Because it's insane. You will not use of those algorithms in your job, and even if you do, they are ready to use in modules already. It's just a way to see who can learn those algorithms because the big five need to filter out most people somehow. This is their method of doing it.
  - hanselot 8y ago
    As a filtering method it still seems illogical. Since there are essentially only two positions you need to hire for. Junior and Senior. If the position is senior, grill them on the complicated technical stuff, because in their position they could potentially cost you millions with a small mistake, however this is also why they get paid so well. For junior, hire four people, do normal HR and resume checks to establish that they are a safe hire, and let the actual work filter them out. Additionally, once you have established which of the hires are good fits, see if you can find other positions internally for the ones that aren't, as they now have already been inducted and understand company policy/culture etc, plus you have already spent resources hiring them. The hirees gain from the watercooler effect and start building loyalty towards their employer as opposed to leaving at the drop of a hat, since their company seems to care about their well-being. Am I insane for thinking this way? Please tell me if I'm missing something.
  - nwbrown 8y ago
    More likely they aren't testing your knowledge of the algorithm but testing your ability to write code.
- chosenbreed 8y ago
  > I turn up on the day, but then these interviews asking difficult algorithm question seem to be a rarity in the UK, thankfully. Perhaps...I've seen a few share of those in interview situations or in pre-interview screening tests. I like the fact the fact that is a standard test that every candidate faces. I'm not sure that the nature of the tests has any relation to the type of work one will be required to in some of these places...
baruchthescribe 8y ago
I was in this exact position a month ago and I landed a great job because of doing very well in two technical interviews. I also am a strong Python programmer who was rusty on the classic CS stuff. Go to Codility's programming lessons page: https://app.codility.com/programmers/lessons/1-iterations/ https://app.codility.com/programmers/lessons/1-iterations/ and try to do at least two exercises from each lesson up to lesson 15 if you can. The open reading material at the top of each section is excellent and discusses all the CS theory you will need. Good luck!
skate22 8y ago
Glassdoor is a decent website to guage the type of questions you'll get during an interview for a specific position. Ive had interviews that re use the exact same questions (fortune 100 companies)
alaq 8y ago
Coderust has been an invaluable resource to me. Yes, it won't give you what a CS degree gives you, but it's enough to make you feel confident in a week or less. https://www.educative.io/collection/5642554087309312/5679846214598656 https://www.educative.io/collection/5642554087309312/5679846...
Shish2k 8y ago
I'm doing a lot of interviewing at a big five company, but speaking personally and unofficially - when it comes to code, I'm looking for fluency more than anything else. At the phone screen level (which I assume is where you're at), the questions I ask are in the same complexity ballpark as fizzbuzz (ie the task will be fully specified in 5 sentences and assumes no prior knowledge), and I expect a candidate to be able to implement that without having to google for "how do I access an array element in <language that the candidate has freely chosen and claims to have mastered>?". The bar for on-site interviews is somewhat higher, but for the first round of interviews, just "do they struggle with basic syntax" is enough to filter out a remarkably large number of people... Also (again personal opinion) - python is the most practical language for doing interview questions, because interviews are heavily time-constrained and python allows the developer to go from idea to implementation in the shortest amount of time. I'm not going to penalize anyone for their language choice, but somebody who completes the task in 5 minutes and then spends 25 minutes getting bonus points for things like "what if the input data is larger than RAM?" is going to come across stronger than someone who spends 30 minutes on parsing the input and runs out of time before they get to the algorithm.
- shoo 8y ago
  > python is the most practical language for doing interview questions, because interviews are heavily time-constrained and python allows the developer to go from idea to implementation in the shortest amount of time. i'm not sure if python is the best, but it's a very strong choice. python also has a lot of built in data structures that are relatively non-broken and highly useful for the archetypical algorithm-prototyping interview questions e.g. if you are using a language that only lets you use strings or ints as keys for dicts/hashmaps - instead of say letting you use immutable compound values as keys, or a language that doesnt give you set data-structures which support basic set operations (contains, equal, subset, superset, intersect, union, etc), or a language that requires you to write a paragraph of OOP-boilerplate to encode e.g. a list of pairs of values, you're making life harder for yourself than necessary. also, i claim without evidence that prolonged and continuous exposure to working with languages that dont offer sensible data structures, or only offer broken data structures, may over time hamper your ability to think and problem solve clearly.
nwbrown 8y ago
You aren't going to gain the skills gained by a four year education in a week. And if you try it will likely be obvious. Interviewers (at least the good ones) aren't looking for someone who knows a particular algorithm by memory, they are looking for someone who is familiar with the concepts. And familiarity is easy to distinguish from rote memorization. The good news though is that unless you lied on your resume, they already know that and are still interested in you. So you likely have other characteristics they are interested in. I would concentrate instead on learning about the company you are interested in. That's something you can do in the course of a week.
- xenihn 8y ago
  >You aren't going to gain the skills gained by a four year education in a week. I know someone who was able to pull it off in 2 weeks, though they were unemployed at the time. They got into Google with 7 years of prior experience at the time. He admits a lot of it was luck. But it's possible.
  - nwbrown 8y ago
    I'm guessing it's the 7 years of experience that impressed Google, not the two weeks of cramming.
    - xenihn 8y ago
      Your background only matters for getting the interview. Whether or not you are hired depends on your actual performance during the onsite.
      - nwbrown 8y ago
        Yes, but his performance was more aided by his 7 years of experience than his two weeks of cramming.
- closeparen 8y ago
  >the skills gained by a four year education Algorithms and data structures are 1-3 classes out of ~45.
nslindtner 8y ago
I would recommend 'the imposter syndrome". https://shop.bigmachine.io/products/the-imposters-handbook https://shop.bigmachine.io/products/the-imposters-handbook
badatshipping 8y ago
Read chapters 2-5 of Skiena’s book, then do leetcode eight hours a day until your interview. Start with high-pass-rate mediums, then work your way up, and try to solve some hards. Spend about half an hour on each problem, and if you can’t think of an answer, look at the solution, reimplement it, and think hard about the underlying concepts. This will not guarantee you a pass — honestly, some people spend months preparing for the big 5 interviews — but it may give you a fighting chance, and either way it will give you a good foundation for future interviews.
- johan_larson 8y ago
  Leetcode is a good idea. https://leetcode.com/problemset/all/ https://leetcode.com/problemset/all/ And frankly, given your lack of background in this area, it would do you a world of good to get more time to prepare. Try to push the interview back a bit. Even one extra week would be an improvement.
dharness 8y ago
Not that this answers the question, but if they're big 5 they should be willing to give you more time. Ask them for a month and see what they say.
bsvalley 8y ago
Based on what you've described (not familiar with data structure/CS algorithm) the answer is very simple - you can't prepare in a week. Don't do it. Tell the recruiter you need a month to prepare or they will have to skip the CS basic screen for you in order to fast forward the process. If you're one of these niche developers (python/C++), you might have a little power when it comes to asking you the right questions. Same goes when a company originally contacted you, you're in a position of power.
- sgillen 8y ago
  Sorry, are you saying knowing python/C++ makes OP a niche developer? I was under the impression these were very common languages at the big-N? Or is it something else about their background? Not trying to correct you, I'm really just curious since I have a similar background and an in a similar situation to the OP.
nwsm 8y ago
Can anyone with experience with "big 5" interviews tell me what to expect out of web development job application process? As someone who is coming from another web dev job, not coming right out of college. Will I still be quizzed on data structures and algorithms? Or will it be more on-topic subjects like frameworks, patterns, architectures, etc?
mathattack 8y ago
You can’t gain the knowledge of a CS degree in a week, but you can calm your nerves. Have some friends conduct a few mock interviews every day, giving you some questions you don’t know the answer to. Then have them give feedback on your poise, especially with difficult questions. You will be calmer and more confident in the rough patches of the interview.
mateo411 8y ago
I would postpone the interview. Give yourself at least 2 months to study this stuff. If you can't postpone it, then I would go ahead and do the interview anyway. There are some good suggestions below, try to spend at least a few hours each day. Hopefully a few hours in the morning, then a break, and then a few more hours. Get plenty of sleep. When you do the interview, do your best and try not to care about the outcome. If you don't care about the outcome, you won't be nervous and you'll likely do better.
Anayapatra 8y ago
You can opt for some mock interview practice app such as MockRabbit which I generally use

arenaninja 8y ago
An honest question for HN: has anyone really been in a project whose primary reason for failure was the lack of engineering talent? I have worked in micro/small businesses and large enterprise environments, and this has never been the case. The projects I have seen fail usually do so due to poor management, poor performers are typically fired unless they can pull one over management to make themselves seem more competent than they really are (not that difficult with bad management)

shaftway 8y ago

I can't speak to other companies, but I do know my [unofficial] experience interviewing (on both sides) at Google. As an interviewee, you know that you're going to have a handful of different interviewers. What you don't know is how much of an effect each of those interviewers is going to have on the hire/no hire decision. Is one bad interviewer enough to torpedo you? Two? And you have no idea what kind of questions each interviewer will ask. So, let's say only 10% of interviewers ask these kinds of questions (I'm guessing that's low). That's a ~41% chance that you're going to have to answer this, and if one bad interviewer is all you need, then you'd be foolish not to prepare just in case. As an interviewer, we're given surprisingly few guidelines on how to interview. You take a one day class, then shadow half a dozen interviews, and that's it. We aren't given specific questions to ask, and specific questions get banned all the time (any time they're "leaked" as a Google interview question). Once someone is hired it's really hard to force them out, so approving someone who talks a smooth game but can't back it up is extremely costly. I've seen teams get stuck with multiple people for well over a year because it takes a long time to get them out, they won't leave willingly. Meanwhile they're taking up headcount and letting them actually touch code is dangerous. In fact, I've seen teams spend an additional engineer training them to the point where they are productive, just because that's cheaper. So you want people to actually prove themselves with some kind of an algorithm question, but you get no real guidance on how to provide these and you constantly have to come up with new ones, but they have to be the kind of question that take less than 45 minutes to explain and solve. I have no doubt that some people fall back on these kinds of questions. Yeah, I get that these questions suck, and I try not to be that interviewer. But as an interviewee I would consider it extremely foolish to not brush up on it, just in case.

SZJX 8y ago
Just wondering, do you mean the range of questions covered is too narrow? If "10% of interviewers" ask these kinds of questions, what would the other 90% of interviewers do. Other types of common data structures/algorithms, DS/A questions thought up by themselves, or something in entirely different directions?
bsvalley 8y ago
You said it yourself "they're taking up headcount and letting them actually touch code is dangerous". My question is, how did they managed to get into Google if they apparently don't know how to write code? The only way to get into google is to go through a huge set of 45-min whiteborad crap. Not once, not twice, we're talking about 7-8 times! Going over the same stupid 45-min "technical screen" where only the original question varies. You need to know all the CS basic stuff + ability to scale (if possible). Like they all say in Silicon Valley - the only way for us to know if you're a rockstar is if you manage to crack a few meaningless problems on a whiteboard. Oh... and make sure to pick your favorite language. Your Resume tells us you have a MS in CS but we don't believe it. So we're gonna put you back into a college-like exam to make sure your degree isn't fake. To me, that's step zero. I still can't believe companies like Google, etc get stuck at step 0. They don't seem to care about step 1, 2, 3, 4. It doesn't matter if you have 1 year or 10 years of experience, we all go through step zero (again, even though we got an MS in CS a few years back). So, if Google ends up in a situation where "teams get stuck with multiple people for well over a year because it takes a long time to get them out", it's because the hiring process at Google sucks. If it is that costly and painful to hire the wrong people, then why Google hasn't put more resources to actually innovate and think beyond college-like evaluations. It is OK for people with zero experience, it is not OK for people with at least one work experience (which I call step 1). Of course, if you have 10 years of experience they need to use a different language in order to interact with you. So, unless someone just graduated from college looking for a job, you can't hire someone exclusively based on step 0 because it simply doesn't tell you if a candidate knows how to write code, build features, work in a collaborative environment, deal with requirements from product team, reuse exiting code, handle code reviews and feedback from peers, create frameworks or adopt new frameworks. All it tells you is if your CS degree is fake or not...
- shaftway 8y ago
  > The only way to get into google is to go through a huge set of 45-min whiteborad crap. This is not the only way to get into Google. > Not once, not twice, we're talking about 7-8 times! When I interviewed I had one 15 minute phone screen, and one round of in-person interviews. The in-person set was 5 people. Of those I think I cratered on one of them, did adequate on two, and stellar on the last two. > Like they all say in Silicon Valley - the only way for us to know if you're a rockstar is if you manage to crack a few meaningless problems on a whiteboard. Very few people get hired as a "rockstar", and the ones that do tend to be hired for non-coding roles. > Oh... and make sure to pick your favorite language. Yeah, the point is for you to answer the question and not get hung up on language semantics that you aren't comfortable with. I interviewed in C# despite ~0.1% of code at Google being C#. I had a very in depth conversation about contract differences between C# and Java that I think impressed the interviewer, despite me not knowing a single line of Java and him not knowing a single line of C#. If you pick the language and still struggle with the semantics of it, that's a huge red flag. > Your Resume tells us you have a MS in CS but we don't believe it. So we're gonna put you back into a college-like exam to make sure your degree isn't fake. An MS in CS doesn't, by itself, qualify you for a role at Google. I have plenty of friends who have the degree who I like very much, but I wouldn't want them on my team. > I still can't believe companies like Google, etc get stuck at step 0. They don't seem to care about step 1, 2, 3, 4. It doesn't matter if you have 1 year or 10 years of experience Yeah, I came in with 15 years of experience across 7 different firms. And I went through the same thing. I've also worked with people who have been in the industry for all kinds of timeframes, up to 35 years, and I've seen little to no correlation between "experience" and ability. A higher-touch process with more "describe what you did at company X" would be nice. But it also feels easier to game. I read design docs for projects at all levels at prior roles, including rationale, alternatives, etc. If I wanted to pass one of those project off as my own through an interview I don't think it'd be very hard. I also don't see any other companies that hire at the rate that Google does (well over 100 software engineers per week) that manages to do that. > So, if Google ends up in a situation where "teams get stuck with multiple people for well over a year because it takes a long time to get them out", it's because the hiring process at Google sucks. So now you're arguing for a more stringent review process, but one that doesn't require actually demonstrating any abilities? Also, this is less of an issue with hiring, and more of an issue with staff management. > you can't hire someone exclusively based on step 0 I'm not sure why you think that Google is "stuck" at step 0, or that we stop there. There is generally no feedback to a candidate about why an offer isn't extended. You're assuming that it's because of a whiteboard coding issue when it might be that your experience doesn't really mesh with what's needed. There are a wide variety of factors that candidates are scored on, and there are plenty of them that have nothing to do with the code that's written on the board. I've had plenty of candidates that have gotten a "hire" recommendation despite not having an optimal, or even a correct answer on the board. I was confident in their abilities because they demonstrated that they recognized there was a problem, usually due to running through test cases, and that given enough time they would solve it. I've had candidates that have gotten a "no hire" because, despite have a correct and nearly optimal answer, they refused to listen when told that "result &= true;" is a no-op in Java. Is the interview process perfect? Of course not. Perfection isn't achievable. And I'm happy to listen to suggestions on how to improve the process. But your suggestions seem to be: 1.) Don't ask whiteboard questions at all (which I have yet to be convinced of), 2.) Don't stop at asking whiteboard questions (which we don't).

shaftway 8y ago

I think it's worth including a bit on disjoint sets. I've managed to pull that solution on interviewers a couple times and they end up fairly impressed when you beat their best solution which is O(n) storage O(log n) time, with one that's O(n) storage O(1) time after amortization.

fspear 8y ago
can you elaborate?
- netgusto 8y ago
  Some material here: https://www.geeksforgeeks.org/union-find/ https://www.geeksforgeeks.org/union-find/ A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure: Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset. Union: Join two subsets into a single subset.
  - shaftway 8y ago
    Sorry, I should have com back, but yeah, this is a good summary. When done properly both Find and Union can be done in amortized inverse-Ackerman time, which is for all intents and purposes constant. It can pop up as a solution for a surprising number of questions. An old, common, (banned) interview question goes something like this: > Imagine you have a grid of squares, represented however you want, describing an ocean. I'm going to give you coordinates one by one that indicate land being created. You need to tell me in total how many islands exist after each coordinate, where an island is defined as a contiguous block of land connected horizontally or vertically, but not diagonally (or include diagonals if you want; it makes some parts of the answer messier). The disjoint-set answer to this question is that you look at the coordinate's neighbors. If there are none, this is a new island. Create the node as part of a new set where the node is the "representative" of that set. If there is one neighbor, create node but make its representative the same as the neighbor's representative. If there are more than one neighbors then you have to do a union; create your node and make its representative one of the neighbors' representatives. Then go to all of the other neighbors and find their representatives (make take a couple hops). Then make their final representatives use the first neighbor as their representative. At this point you have kind of a directed acyclic graph where each node has exactly one edge (maybe pointing to itself). The last improvement is to update each node's representative as you travel to be the final one. This amortizes out to a single hop for each node, after enough find or union operations. Then you can start adding more data to the representative and dealing with merging that to solve some pretty complex problems in a shockingly low runtime.