This blog post is a coding and system design interview cookbook/cheatsheet compiled by me with code pieces written by me as well. There is no particular structure nor do I pretend this to be a comprehensive guide. Also there are no explanations as the purpose is just to list important things. Moreover, this blog post is work-in-progress as I’m planning to add more things to it.
As always, opinions are mine.
Just replace the queue in BFS with stack and you are done:
Generally a recursive algorithm attempting candidates and either accepting them or rejecting (“backtracking”) based on some condition. Below is an example of permutations generation using backtracking:
Technique to determine result using previous results. You should be able to reason about your solution recursively and be able to deduce dp[i] using dp[i-1]. Generally you would have something like this:
When you need to figure out if something belongs to the same set you can use the following:
Below are recursive and iterative versions of inorder traversal
Simplest way to remember Djikstra is to imagine it as BFS over PriorityQueue instead of normal Queue, where values in queue are best distances to nodes pending processing.
Hopefully no one asks you this one. It would be too much code here, but the idea is not that difficult: build LPS (example “AAABAAA” -> [0,1,2,0,1,2,3]); use LPS to skip when comparing as if you were doing it in brute-force.
Let’s imagine we have window of length k and string s, then the hash for the first window will be:
H(k) = s[0]*P^(k-1) + s[1]*P^(k-2) + … + s[k]*P^0
Moving the window by one, would be O(1) operation:
H(k+1) = (H(k) – s[0]*P^(k-1)) * P + s[k+1]*P^0
Here is some sample code:
JUnit User guide: https://junit.org/junit5/docs/current/user-guide/
Many interview problems can be solved by using right data structure.
These are notes I took while reading “System Design Interview – An insider’s guide”:
Well, internet is just full of all kinds of resources and blog posts on how to prepare for the technical interview plus there are numerous books and websites available. LeetCode is probably the most known of practicing websites. “Cracking The Coding Interview” is probably the most known book. I can also recommend “Guide to Competitive Programming”. As of system design, preparation resources are not so readily available. One good resource is “Grokking System Design Interview”, but it would be more valuable to practice designing large distributed systems. I also found the book “Designing Data-Intensive Applications” to be extremely helpful.
What are other “must know” algorithms and important system design topics to be listed in this post?
December 12, 2019 Interview No comments
Disclaimer: anything you read in this blog post is my own opinion and doesn’t represent opinion of my current or past employers in any way.
For those of you who are looking for landing a Software Development Engineer job at a large tech company being able to crack the coding interview is essential.
You might be a reader from outside North America and are not really used to the kind of software interviews common here, but the harsh truth is that you have to grind college/university kind of coding problems before the interview.
Of course, the argument always goes that you should be a problem solver and that interviewer is accessing your approach to tackling a problem as well as your comprehension and communication skills. My counter argument is that preparation matters a big deal and even people with enormous experience and track record of deliveries would have difficulties if they haven’t brushed on algorithms in a long while.
Let’s do a thought experiment: let’s imagine there are two deep copies of you. By “deep copy” I mean that you both have absolutely identical personalities, knowledge, background, experience. Now you are both to be interviewed in one month at a big company. Copy One doesn’t have time to prepare and just looks up what are the main types of questions. Copy Two takes a month of vacation and sits at TopCoder / LeetCode / HackerRank / GeeksForGeeks solving, say 300-500 problems. Copy One is also capable of doing it as both of you did well in university XX years ago. Now when the interview comes, copy Two just shines and cracks all questions. Copy One struggles with solving problems but manages them somehow. Both do almost equally well on behavioral and design questions, though copy Two still has an edge as all of her/his stories are pre-prepared. So when the performance of these two copies is compared copy Two wins even it appeared both had similar cognitive and communication skills. What hiring company gets is almost identically same employee with a difference of 1 month of intensive practice, which has 0 effect on day-to-day job or quality of work.
Nevertheless there are some positive sides to these kind of interviews. One of them is that they are somewhat standardized and candidates are generally judged against the same bar. Another very obvious aspect is that these problems require writing code. If you go to an interview for a software engineer role and the main skill of your job isn’t accessed then there is something wrong with that interview. Here is the quote for this:
Talk is cheap. Show me the code.
Torvalds, Linus (2000-08-25)
My favorite types of questions for interviews are those (a) that could be solved in multiple different ways from least efficient to most efficient; even better are those (b) that start very simple but allow interviewer to make the problem ever more difficult, say by increasing the limits or converting input to a stream instead of an array, or by adding complication that requires alternative approach. Though an ideal problem, in my opinion, would be a problem that satisfies both conditions (a) and (b) and also is close to potential real-world task (c).
Problems at interview preparation websites, such as LeetCode, might satisfy the condition (a) from above, but rarely satisfy (b) or (c). I almost never see problems that would be (a), (b), and (c) – those would be fantastic.
Some example of a set of problems that satisfy (a) and (b) at LeetCode is classical easy problem “Best Time to Buy and Sell Stock” that can be solved with brute force O(N²) or more efficient O(N), but then there is a twist by adding transaction fee, when you would need to come up with a dynamic programming solution, there are many other twists. Here are variations: 1, 2, 3, 4, 5, 6. Some example of a problem that matches condition (c) would be implementation of an iterator interface, like “Flatten Nested List Iterator“.
Personally I’m not good at solving coding problems. I did participate in ACM competitions back in the university days, but I was always 3rd person on a team – kind of banging my head against the wall on a single problem while the other two guys were bashing the keyboard or coming up with magical math formulas.
I keep practicing on LeetCode mostly to keep myself in a good form. At the moment I have 407 out of 1285 problems solved. I bought myself premium subscription as it unlocks some problems and makes submission process faster. It also unlocks some of the mock interview functionality. Again I suck, but this kind of stats please my eyes (previously solved problems appear in mocks at times so I just know how to solve them).
Another fun activity you can do at LeetCode (without premium subscription) is to take part in Weekly Contests. Please let me know if you are competing as well and want to chat (my contacts are always easy to find andriybuday everywhere or leave a comment).
This post wasn’t much about how to prepare to the interview nor an overview of coding practicing resources, though if you are interested, read about the interview process online, consider buying yourself the book “Cracking the Coding Interview” or other top resources. Remember that big companies often have the information on their process public, for example facebook on their interview process. Make sure you prepare for system design interview as well. But most importantly of all: practice, practice, practice!
October 7, 2019 Design, Interview, Opinion No comments
Designing something like Dropbox or other well known service is one of the standard System Design Interview (SDI) questions at FAANG companies. This post is for self-educational purposes focused on how to approach SDI question. Also this does not represent how any tech company is designing their software or is interviewing candidates. Though, feel free to use it as a guide for your SDI if you find it useful.
I like to break SDI into four phases. You want to get to the last phase when interviewer is making the problem harder by asking you follow up questions.
The most important part that sets the tone for the entire interview is to clarify requirements with your interviewer. Try to understand what functional and non-functional scope of the problem they expect you to cover.
Functionally Dropbox “offers cloud storage, file synchronization, personal cloud, and client software”. You can list these as bullet points during the interview (any device accessibility, automatic file synchronization, file sharing, file storing, backups, team collaboration, security, etc).
Something like Dropbox will have to handle millions of users, have scalable, available, and performant backend. Ask for number of users, active users, devices, etc to be able to estimate required storage, network capacity and understand if partitioning and how much of replication of data is required. This can be used in calculations later on. Something like: 2K (avg. files) * 500Kb (avg. file size) * 1B (tot. users) ~= 1PB (file storage).
It is always a good idea to define interfaces of your system. APIs exposed by server are usually a great way to start. Define interfaces like list of REST calls or just names of APIs.
After gathering the requirements and documenting main interfaces proceed to listing major components of the system. You might not be able to list everything, so mentioning that there are other aspects that you not fully covering, but can get back to them when required (examples could be: authentication, payment system, integration with external systems, etc).
At this stage you should arrive at key ideas to solving the design. Key ideas for designing Dropbox could be: split large files into multiple chunks; keep chunk metadata in database locally and sync to server; receive and upload files via synchronization queues.
Once key solution ideas are clear, draw some boxes. It is best to start from top and proceed to details. In our Dropbox example it could be Backend and Frontend. Backend could consist of File Storage, Metadata Database, App Servers and Queues. Our Client could be split into logical parts. Many similar posts (not sure about origin) suggest to split client into Chunker (split files into multiple), Watcher (watches local folders and server for updates), Indexer (processes watcher events), InternalDb (stores metadata).
Obviously, it is impossible to cover gigantic system, like Dropbox, in 45 minutes, so you have to focus on few aspects that are important. For instance, you can focus on database design for metadata by drawing tables and their relations, or instead you can focus on how updates will be sent to other devices by drawing sequence diagram, etc.
This could be the best stage to show your depth of the knowledge in one or the other area. More often then not interviewer would be happy to focus on area you are comfortable with and then would ask you follow-up questions to understand the depth of your knowledge and whether you really know what you are talking about or just making things up while throwing buzz-words. It should go without saying that you should not be doing this.
It is a very good sign when interviewer starts to make the problem harder as it means you are doing really good. At this stage the interview can go into any direction depending on the interviewer, but often you would need to solve scalability problems (queues, caches, load balancers), availability (replications), or you could be asked to increase the scope of functionality that would make you add new components, etc.
This is my concise view on the parts of SDI, though your experience could be totally different depending on the interviewer, company, level targeted and specifics of a question (like, say, designing fridge controller).
I recommend reading the book “Designing Data Intensive Applications” as it is absolutely great resource to train yourself whether you are preparing yourself for interview or just trying to solidify design skills. You can also try watching youtube videos and googling articles like this.