4 ms·

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 * T

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 :-)
  - rimliu 8y ago
    Seems plausible. Big five stopped to look attractive to me few years ago (Microsoft and Amazon never were, tbh) but I get that people have different opinions. What I do not get is why do big five think this kinds of interview are effective. Or are they?
- 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...
nwbrown 8y ago
You are unlikely to get asked any of these things during the interview, and if you are it will be obvious that you just crammed for them (much like if just brush your teeth the day before your dental appointment and then arrive at the dentist with bleeding gums). If JavaScript is your language then you are likely looking at front end development, in which case it will be much more useful to know about frameworks and testing strategies than CS theory.
- sciencewolf 8y ago
  Yes, you are unlikely to get asked any of these _specific_ questions-- however, the point of study isn't to memorize any answers. Rather, it's to familiarize yourself with the patterns of CS solutions so that you're able to replicate it in a brand new problem. Also, JS isn't just for front-end development. Aside from Node.js, which is increasingly a larger player server-side, it's also used in a bunch of desktop apps.
  - nwbrown 8y ago
    Again, you aren't going to get familiar with the patterns in computer science in one week. That requires years of practice. Most likely you will just hit a Dunning-Kruger peak and try to shoehorn in a pattern where it doesn't belong. And yes, js is used in other contexts as well, but it is primarily used in front end developer. Which is why I used the word 'likely'.
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.
itronitron 8y ago
This begs the question >> if you can teach yourself any of these things in a day then why would you need to know it before working there?

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 :-)
- rimliu 8y ago
  Seems plausible. Big five stopped to look attractive to me few years ago (Microsoft and Amazon never were, tbh) but I get that people have different opinions. What I do not get is why do big five think this kinds of interview are effective. Or are they?
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...

nwbrown 8y ago

You are unlikely to get asked any of these things during the interview, and if you are it will be obvious that you just crammed for them (much like if just brush your teeth the day before your dental appointment and then arrive at the dentist with bleeding gums). If JavaScript is your language then you are likely looking at front end development, in which case it will be much more useful to know about frameworks and testing strategies than CS theory.

sciencewolf 8y ago
Yes, you are unlikely to get asked any of these _specific_ questions-- however, the point of study isn't to memorize any answers. Rather, it's to familiarize yourself with the patterns of CS solutions so that you're able to replicate it in a brand new problem. Also, JS isn't just for front-end development. Aside from Node.js, which is increasingly a larger player server-side, it's also used in a bunch of desktop apps.
- nwbrown 8y ago
  Again, you aren't going to get familiar with the patterns in computer science in one week. That requires years of practice. Most likely you will just hit a Dunning-Kruger peak and try to shoehorn in a pattern where it doesn't belong. And yes, js is used in other contexts as well, but it is primarily used in front end developer. Which is why I used the word 'likely'.

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.

itronitron 8y ago

This begs the question >> if you can teach yourself any of these things in a day then why would you need to know it before working there?