Whats the fastest way to sort an array on disk thats too large to fit into memory?

Dorsum in 2017, I went through some coding interviews and got offers from several large tech companies. So at that bespeak, I decided to share what I'd learned in this article.

And I've simply updated it for 2022 so it'll exist super useful and relevant if you're chore hunting now.

Despite scoring decent grades in both my CS101 Algorithm class and my Information Structures class in university, I shudder at the thought of going through a coding interview that focuses on algorithms.

Hence I spent the last three months figuring out how to improve my coding interview skills and eventually received offers from big tech companies like Google, Facebook, Airbnb, Lyft, Dropbox and more.

In this post, I'll be sharing the insights and tips I gained along the way. Experienced candidates can too expect System Design questions, only that is out of the scope of this post.

Many of the algorithmic concepts tested in coding interviews are not what I usually employ at piece of work, where I am a Forepart Stop Engineer (spider web). Naturally, I have forgotten quite a bit almost these algorithms and information structures, which I learned more often than not during my freshmen and sophomore years of college.

Information technology's stressful to have to produce (working) code in an interview, while someone scrutinizes every keystroke that yous make. What'south worse is that as an interviewee, you're encouraged to communicate your thought process out loud to the interviewer.

I used to retrieve that being able to think, lawmaking, and communicate simultaneously was an incommunicable feat, until I realized that most people are only not expert at coding interviews when they first start out. Interviewing is a skill that yous can go better at by studying, preparing, and practicing for it.

My recent task search has led me on a journey to improve my coding interview skills. Front end Engineers like to rant about how the current hiring process is broken because technical interviews can include skills not related to front end-stop evolution. For case, writing a maze solving algorithm and merging two sorted lists of numbers. Every bit a Front End Engineer myself, I tin understand with them.

Forepart cease is a specialized domain where engineers take to care about many issues related to browser compatibilities, the Document Object Model, JavaScript performance, CSS layouts, and so on. Information technology is uncommon for forepart-end engineers to implement some of the complex algorithms tested in interviews.

At companies similar Facebook and Google, the people are software engineers commencement, domain experts 2nd.

Unfortunately, rules are set up by the companies, not the candidates. There is a high accent on full general information science concepts like algorithms, design patterns, information structures; core skills that a good software engineer should possess. If you desire the job, y'all have to play by the rules gear up by the game masters — improve your coding interview skills!

This post is structured into the post-obit two sections. Experience free to skip ahead to the section that interests you lot.

• The breakdown of coding interviews, and how to fix for them.
• Helpful tips and hints for each algorithm topic (arrays, trees, dynamic programming, etc.), forth with recommended LeetCode practise questions to review core concepts and to amend on those topics.

The content for this mail tin exist constitute here. I'll make updates there when necessary.

If y'all are interested in Front Terminate content, check out my front end interview handbook here.

Picking a programming linguistic communication

Earlier anything else, you need to choice a programming language for your algorithmic coding interview.

Most companies will permit yous to lawmaking in the language of your option. The but exception I know is Google. They allow their candidates to pick from just Java, C++, Python, Become or JavaScript.

For the most role, I recommend using a linguistic communication that you are extremely familiar with, rather than one that is new to y'all but that the company uses widely.

There are some languages that are more suitable than others for coding interviews. Then there are some that you lot absolutely want to avert.

From my feel every bit an interviewer, most candidates choice Python or Coffee. Other languages ordinarily selected include JavaScript, Ruby, and C++. I would absolutely avert lower-level languages like C or Go, only because they lack standard library functions and data structures.

Personally, Python is my de facto choice for coding algorithms during interviews. It is succinct and has a huge library of functions and data structures.

One of the top reasons I recommend Python is that it uses consistent APIs that operate on different data structures, such as len(), for ... in ... and slicing notation on sequences (strings, lists, and tuples). Getting the last element in a sequence is arr[-1] , and reversing it is simply arr[::-1]. You can achieve a lot with minimal syntax in Python.

Java is a decent choice too. Simply considering you will accept to constantly declare types in your code, information technology means entering extra keystrokes. This will dull downward the speed at which you lot code and type. This consequence will be more credible when you have to write on a whiteboard during on-site interviews.

The reasons for choosing or non choosing C++ are similar to Java. Ultimately, Python, Coffee, and C++ are decent choices. If you lot take been using Java for a while, and do not have time to become familiar with some other linguistic communication, I recommend sticking to Java instead of picking upward Python from scratch. This helps you to avoid having to use one language for work and some other one for interviews. Most of the time, the bottleneck is in the thinking and not the writing.

One exception to the convention of allowing the candidate to "pick any programming linguistic communication they desire" is when the interview is for a domain-specific position, such as front-end, iOS, or Android engineer roles. You need to be familiar with coding algorithms in JavaScript, Objective-C, Swift, and Coffee, respectively.

If y'all need to use a information structure that the language does not support, such as a queue or heap in JavaScript, inquire the interviewer if you tin assume that you have a data structure that implements certain methods with specified fourth dimension complexities. If the implementation of that information structure is non crucial to solving the problem, the interviewer will usually permit it.

In reality, being aware of existing data structures and selecting the appropriate ones to tackle the problem at hand is more of import than knowing the intricate implementation details.

Review your CS101

If you have been out of college for some fourth dimension, it is highly advisable to review the CS fundamentals. I prefer to review it as I practice. I scan through my notes from college and revise the various algorithms equally I work on the algorithm problems from LeetCode and Peachy the Coding Interview.

If yous are interested in how information structures are implemented, bank check out Lago, a GitHub repository containing Data Structures and Algorithms examples in JavaScript.

GitHub - yangshun/lago: 📕 Data Structures and Algorithms library in TypeScript

📕 Data Structures and Algorithms library in TypeScript - GitHub - yangshun/lago: 📕 Information Structures and Algorithms library in TypeScript

yangshun GitHub

Mastery through exercise

Next, proceeds familiarity and mastery of the algorithms and information structures in your called programming language.

Practise and solve algorithm questions in your chosen language. While Cracking the Coding Interview is a good resource, I prefer solving bug by typing code, letting it run, and getting instant feedback.

There are various Online Judges, such as LeetCode, HackerRank, and CodeForces for you to exercise questions online and to get used to the language. From my experience, LeetCode questions are nigh similar to the questions asked in interviews. HackerRank and CodeForces questions are more similar to questions in competitive programming.

If you practice enough LeetCode questions, there is a good hazard that you volition either see or complete i of your actual interview questions (or some variant of it).

Larn and sympathise the time and infinite complexities of the common operations in your chosen language. For Python, this page will come in handy. Also, learn nearly the underlying sorting algorithm existence used in the linguistic communication's sort() function and its time and space complexities (in Python information technology'south Timsort, which is a hybrid).

After completing a question on LeetCode, I commonly add together the fourth dimension and space complexities of the written code every bit comments above the function body. I use the comments to remind myself to communicate the assay of the algorithm after I have completed the implementation.

Read up on the recommended coding way for your language and stick to it. If you choose Python, refer to the PEP 8 Style Guide. If you lot cull Java, refer to Google's Coffee Style Guide.

Acquire well-nigh and be familiar with the common pitfalls and caveats of the linguistic communication. If you point them out during the interview and avert falling into them, you will earn bonus points and impress the interviewer, regardless of whether the interviewer is familiar with the language or non.

Gain a broad exposure to questions from various topics. In the second one-half of the article, I mention algorithm topics and the useful questions for each topic to practise. Do around 100 to 200 LeetCode questions, and you should be good.

If you prefer courses where the learning is more structured, hither are a few recommendations. In no way is taking online courses a must in order to pass interviews.

• AlgoMonster aims to help you ace the technical interview in the shortest time possible. Past Google engineers, AlgoMonster uses a data-driven approach to teach you the nearly useful key question patterns and has contents to help you quickly revise basic data structures and algorithms. Best of all, AlgoMonster is not subscription-based - pay a one-time fee and become lifetime admission.
• Grokking the Coding Interview: Patterns for Coding Questions by Educative expands on the recommended practice questions in this article merely approaches the practicing from a questions pattern perspective, which is an arroyo I likewise concord with for learning and have personally used to get improve at coding interviews. The course allows yous to exercise selected questions in Coffee, Python, C++, JavaScript and also provides sample solutions in those languages. Learn and empathise patterns, not memorize answers.

And of course, practice, practice, and more practice!

Phases of a coding interview

Congratulations, you are ready to put your skills to practise! In a coding interview, you will be given a technical question by the interviewer. You will write the lawmaking in a real-fourth dimension, collaborative editor (phone screen) or on a whiteboard (on-site), and accept thirty to 45 minutes to solve the problem. This is where the real fun begins!

Your interviewer will be looking to see that you meet the requirements of the role. It is upward to you to testify them that you have the skills. Initially, information technology may experience weird to talk while you code, every bit most programmers exercise non make a habit of explaining out loud their thoughts while they are typing code.

Yet, information technology is hard for the interviewer to know what y'all are thinking by just looking at your code. If yous communicate your approach to the interviewer even before you first to lawmaking, y'all tin validate your approach with them. This manner, the ii of you can agree on an acceptable arroyo.

Preparing for a remote interview

For phone screens and remote interviews, have a paper and pen or pencil to jot downwards any notes or diagrams. If y'all are given a question about trees and graphs, it usually helps if you draw examples of the information structure.

Use earphones. Make certain you are in a quiet environment. You do not want to exist holding a phone in one manus and typing with the other. Endeavor to avoid using speakers. If the feedback is bad, advice is made harder. Having to repeat yourself volition just result in the loss of valuable time.

What to do when you get the question

Many candidates beginning coding as soon equally they hear the question. That is usually a big mistake. Get-go, have a moment and repeat the question back to the interviewer to make sure that you understand the question. If you misunderstand the question, so the interviewer can clarify.

E'er seek clarification about the question upon hearing information technology, even if y'all think it is clear. You lot might discover that you lot have missed something. Information technology as well lets the interviewer know that y'all are attentive to details.

Consider asking the following questions.

• How big is the size of the input?
• How big is the range of values?
• What kind of values are there? Are there negative numbers? Floating points? Volition there be empty inputs?
• Are at that place duplicates within the input?
• What are some extreme cases of the input?
• How is the input stored? If you lot are given a dictionary of words, is it a list of strings or a trie?

After yous have sufficiently antiseptic the scope and intention of the trouble, explain your loftier-level arroyo to the interviewer, even if it is a naive solution. If you lot are stuck, consider diverse approaches and explain out loud why it may or may non piece of work. Sometimes your interviewer might drop hints and lead you toward the right path.

Beginning with a brute-force approach. Communicate it to the interviewer. Explain the time and space complexities and clarify why information technology is bad. It is unlikely that the brute-forcefulness approach will be the one that you lot will be coding. At this indicate, the interviewer will usually popular the dreaded, "Can we practice amend?" question. This means they are looking for a more optimal approach.

This is usually the hardest part of the interview. In general, look for repeated work and try to optimize them by potentially caching the calculated result somewhere. Reference it afterwards, rather than computing information technology all over once more. I provide some tips on tackling topic-specific questions in item beneath.

Only showtime coding later you and your interviewer have agreed on an approach and you have been given the light-green light.

Starting to code

Use a skilful way to write your code. Reading code written by others is normally not an enjoyable task. Reading horribly formatted lawmaking written by others is even worse. Your goal is to make your interviewer empathise your code then that they tin quickly evaluate if your code does what it is suppose to and if it solves a given problem.

Use clear variable names and avoid names that are unmarried letters, unless they are for iteration. However, if you are coding on a whiteboard, avoid using verbose variable names. This reduces the corporeality of writing you will take to do.

Always explain to the interviewer what you lot are writing or typing. This is non almost reading, verbatim, to the interviewer the code you lot are producing. Talk well-nigh the section of the code y'all are currently implementing at a higher level. Explain why it is written as such, and what information technology is trying to achieve.

When you re-create and paste in code, consider whether it is necessary. Sometimes it is, sometimes it is not. If you find yourself copying and pasting a big chunk of code spanning multiple lines, it is probably an indicator that you can restructure the lawmaking by extracting those lines into a role. If it is just a unmarried line you copied, usually information technology is fine.

Notwithstanding, remember to change the corresponding variables in your copied line of lawmaking where relevant. Copying and pasting errors are a mutual source of bugs, fifty-fifty in 24-hour interval-to-mean solar day coding!

Later on coding

Afterward y'all have finished coding, do not immediately denote to the interviewer that you are done. In most cases, your lawmaking is usually not perfect. Information technology may contain bugs or syntax errors. What you demand to do is review your code.

First, look through your code from start to stop. Look at it every bit if it were written by someone else, and you are seeing it for the first time and trying to spot bugs in it. That'due south exactly what your interviewer will exist doing. Review and gear up any bug you may find.

Side by side, come with modest examination cases and pace through the lawmaking (non your algorithm) with those sample input.

Interviewers similar it when you read their minds. What they ordinarily practise afterwards you have finished coding is get you to write tests. It is a huge plus if you write tests for your lawmaking even before they prompt you to do so. You should be emulating a debugger when stepping through your code. Jot down or tell them the values of certain variables as y'all walk the interviewer through the lines of code.

If there are large duplicated chunks of code in your solution, restructure the code to show the interviewer that yous value quality coding. Likewise, wait out for places where y'all tin can do brusk-circuit evaluation.

Lastly, give the fourth dimension and space complexities of your lawmaking, and explain why it is such. You can annotate chunks of your code with their various fourth dimension and space complexities to demonstrate your agreement of the code. You can even provide the APIs of your called programming language. Explain any trade-offs in your current approach versus alternative approaches, possibly in terms of time and space.

If your interviewer is happy with the solution, the interview normally ends hither. It is besides common that the interviewer asks you extension questions, such as how you would handle the problem if the whole input is too large to fit into memory, or if the input arrives as a stream. This is a common follow-up question at Google, where they care a lot nearly scale.

The answer is usually a separate-and-conquer approach — perform distributed processing of the data and simply read certain chunks of the input from deejay into retentiveness, write the output back to deejay and combine them later.

Practice with mock interviews

The steps mentioned higher up can be apposite over and over again until y'all have fully internalized them and they become second nature to you. A skilful way to exercise is by partnering with a friend and taking turns to interview each other.

A great resource for preparing for coding interviews is interviewing.io. This platform provides free and bearding practice interviews with Google and Facebook engineers, which tin can lead to real jobs and internships.

By virtue of existence anonymous during the interview, the inclusive interview process is unbiased and low take chances. At the end of the interview, both the interviewer and interviewee tin can provide feedback to each other for the purpose of helping i another improve.

Doing well in mock interviews volition unlock the jobs page for candidates, and allow them to book interviews (as well anonymously) with tiptop companies like Uber, Lyft, Quora, Asana, and more. For those who are new to coding interviews, a demo interview can be viewed on this site. Note that this site requires users to sign in.

I have used interviewing.io, both every bit an interviewer and an interviewee. The experience was great. Aline Lerner, the CEO and co-founder of interviewing.io, and her team are passionate about revolutionizing the process for coding interviews and helping candidates better their interview skills.

She has besides published a number of coding interview-related articles on the interviewing.io blog. I recommend signing up equally early on as possible with interviewing.io, fifty-fifty though it's in beta, to increment the likelihood of receiving an invite.

Another platform that allows y'all to practise coding interviews is Pramp. Where interviewing.io matches potential job seekers with seasoned coding interviewers, Pramp takes a unlike approach. Pramp pairs yous up with another peer who is besides a job seeker. The ii of you have turns assuming the roles of interviewer and interviewee. Pramp also prepares questions, and provides solutions and prompts to guide the interviewee.

Go forth and conquer

After doing a fair corporeality of questions on LeetCode and having enough practise doing mock interviews, go along and put your new-constitute interviewing skills to the examination.

Utilise to your favorite companies or, amend nonetheless, get referrals from your friends working for those companies. Referrals tend to become noticed earlier and have a faster response rate than applying without a referral. Adept luck!

Applied tips for coding questions

This section dives deep into applied tips for specific topics of algorithms and information structures, which announced frequently in coding questions. Many algorithm questions involve techniques that can be practical to questions of a similar nature.

The more techniques you have in your arsenal, the greater your chances of passing the interview. For each topic, there is also a list of recommended questions, which is valuable for mastering the cadre concepts. Some of the questions are only available with a paid subscription to LeetCode, which in my opinion is absolutely worth the coin if it lands you a task.

General tips

Always validate input commencement. Check for inputs that are invalid, empty, negative, or different. Never assume yous are given the valid parameters. Alternatively, clarify with the interviewer whether you can presume valid input (normally yes), which tin can save yous fourth dimension from writing code that does input validation.

Are there any time and infinite complexities requirements or constraints?

Check for off-past-one errors.

In languages where there are no automated blazon coercion, check that chain of values are of the same type: int,str, and listing.

Later you lot finish your code, use a few example inputs to test your solution.

Is the algorithm supposed to run multiple times, possibly on a web server? If yes, the input can likely be pre-processed to better the efficiency in each API call.

Use a mix of functional and imperative programming paradigms:

• Write pure functions equally often as possible.
• Apply pure functions because they are easier to reason with and can assistance reduce bugs in your implementation.
• Avoid mutating the parameters passed into your role, especially if they are passed by reference, unless you are certain of what yous are doing.
• Achieve a balance betwixt accurateness and efficiency. Use the right amount of functional and imperative lawmaking where appropriate. Functional programming is unremarkably expensive in terms of space complexity because of non-mutation and the repeated resource allotment of new objects. On the other hand, imperative lawmaking is faster considering you operate on existing objects.
• Avert relying on mutating global variables. Global variables introduce state.
• Make sure that you lot practice not accidentally mutate global variables, especially if you have to rely on them.

By and large, to amend the speed of a program, we can choose to either employ an advisable data structure or algorithm, or to use more memory. Information technology'southward a classic space and time trade off.

Information structures are your weapons. Choosing the right weapon for the correct boxing is the central to victory. Know the strengths of each data structure and the time complexity for its various operations.

Information structures can be augmented to attain efficient time complexity across different operations. For example, a HashMap can be used together with a doubly-linked listing to accomplish O(1) time complexity for both the get and put performance in an LRU enshroud.

HashMaps are probably the nearly commonly used information structure for algorithm questions. If you are stuck on a question, your last resort tin can be to enumerate through the possible data structures (thankfully there aren't that many) and consider whether each of them can exist applied to the problem. This has worked for me at times.

If you are cutting corners in your lawmaking, state that out loud to your interviewer, and explain to them what you would do outside of an interview setting (no time constraints). For instance, explain that y'all would write a regex to parse a cord rather than using split , which does non cover all cases.

Sequence

Notes

Arrays and strings are considered sequences (a cord is a sequence of characters). There are tips for dealing with both arrays and strings, which volition be covered here.

Are there duplicate values in the sequence? Would they impact the answer?

Bank check for sequence out of premises.

Be mindful about slicing or concatenating sequences in your code. Typically, slicing and concatenating sequences crave O(n) time. Utilise beginning and stop indices to demarcate a subarray or substring where possible.

Sometimes you lot traverse the sequence from the right side rather than from the left.

Master the sliding window technique that applies to many substring or subarray bug.

When you are given 2 sequences to process, it is common to have 1 index per sequence to traverse. For case, we use the aforementioned approach to merge two sorted arrays.

Corner Cases

• Empty sequence
• Sequence with 1 or 2 elements
• Sequence with repeated elements

Assortment

Notes

Is the array sorted or partially sorted? If it is either, some course of binary search should be possible. This usually means that the interviewer is looking for a solution that is faster than O(n).

Can you sort the array? Sometimes sorting the array first may significantly simplify the problem. Brand sure that the order of assortment elements do not need to be preserved before attempting to sort information technology.

For questions where summation or multiplication of a subarray is involved, pre-computation using hashing or a prefix, suffix sum, or product might be useful.

If you are given a sequence and the interviewer asks for O(i) space, it might exist possible to utilize the array itself equally a hash tabular array. For example, if the array has values only from 1 to Due north, where N is the length of the array, negate the value at that index (minus i) to indicate the presence of that number.

Practice Questions

• Two Sum
• Best Fourth dimension to Buy and Sell Stock
• Contains Duplicate
• Product of Array Except Self
• Maximum Subarray
• Maximum Product Subarray
• Observe Minimum in Rotated Sorted Array
• Search in Rotated Sorted Array
• 3Sum
• Container With About Water

Binary

Study Links

• Bits, Bytes, Building With Binary

Notes

Questions involving binary representations and bitwise operations are asked sometimes. Y'all must know how to catechumen a number from decimal grade into binary form, and vice versa, in your chosen programming language.

Some helpful utility snippets:

• Test kth bit is prepare: num & (1 << m) != 0
• Set kth flake: num |= (i << k)
• Turn off kth flake: num &= ~(1 << k)
• Toggle the kth bit: num ^= (i << m)
• To check if a number is a ability of ii: num & num - i == 0.

Corner Cases

• Cheque for overflow/underflow
• Negative numbers

Practice Questions

• Sum of Two Integers
• Number of one $.25
• Counting Bits
• Missing Number
• Reverse Bits

Dynamic Programming

Study Links

• Demystifying Dynamic Programming

Notes

Dynamic Programming (DP) is normally used to solve optimization problems. Alaina Kafkes has written an awesome post on tackling DP problems. You lot should read information technology.

The only fashion to get better at DP is with exercise. It takes lots of practice to recognize that a problem can be solved by DP.

To optimize infinite, sometimes yous do non take to store the entire DP table in retention. The terminal two values or the last two rows of the matrix will suffice.

Practice Questions

• 0/i Knapsack
• Climbing Stairs
• Coin Alter
• Longest Increasing Subsequence
• Longest Common Subsequence
• Word Break Problem
• Combination Sum
• House Robber and Firm Robber 2
• Decode Ways
• Unique Paths
• Jump Game

Geometry

Notes

When comparing Euclidean distance between two pairs of points, using dx² + dy² is sufficient. Information technology is unnecessary to foursquare root the value.

To observe out if two circles overlap, bank check that the altitude between the two centers of the circles is less than the sum of their radii.

Graph

Study Links

• From Theory To Practice: Representing Graphs
• Deep Dive Through A Graph: DFS Traversal
• Going Broad In A Graph: BFS Traversal

Notes

Be familiar with the various graph representations and graph search algorithms, and with their time and space complexities.

Yous can be given a list of edges and tasked to build your ain graph from the edges to perform a traversal on. The common graph representations are

• Adjacency matrix
• Adjacency list
• HashMap of HashMaps

Some inputs wait like they are trees, but they are actually graphs. Clarify this with your interviewer. In that example, you will take to handle cycles and keep a gear up of visited nodes when traversing.

Graph search algorithms

• Common: Breadth first search (BFS), Depth first search (DFS)
• Uncommon: Topological sort, Dijkstra's algorithm
• Rare: Bellman-Ford algorithm, Floyd-Warshall algorithm, Prim's algorithm, and Kruskal's algorithm

In coding interviews, graphs are commonly represented every bit 2-D matrices, where cells are the nodes and each cell can traverse to its next cells (up, down, left, and right). Hence information technology is important to be familiar with traversing a 2-D matrix.

When recursively traversing the matrix, always ensure that your next position is within the boundary of the matrix. More than tips for doing DFS on a matrix can be institute here. A simple template for doing DFS on a matrix appears something like this:

                def traverse(matrix):   rows, cols = len(matrix), len(matrix[0])   visited = set up()   directions = ((0, ane), (0, -i), (one, 0), (-1, 0))   def dfs(i, j):     if (i, j) in visited:       return     visited.add((i, j))     # Traverse neighbors     for management in directions:       next_i, next_j = i + direction[0], j + direction[1]       if 0 <= next_i < rows and 0 <= next_j < cols: # Check boundary         # Add whatsoever other checking here ^         dfs(next_i, next_j)   for i in range(rows):     for j in range(cols):       dfs(i, j)              

Corner Cases

• Empty graph
• Graph with ane or two nodes
• Disjoint graphs
• Graph with cycles

Practice Questions

• Clone Graph
• Course Schedule
• Alien Dictionary
• Pacific Atlantic Water Flow
• Number of Islands
• Graph Valid Tree
• Number of Continued Components in an Undirected Graph
• Longest Consecutive Sequence

Interval

Notes

Interval questions are questions that requite an array of two-element arrays (an interval). The two values represent a start and an end value. Interval questions are considered to be part of the assortment family, just they involve some common techniques. Hence, they have their own special section.

An example of an interval array: [[ane, ii], [four, 7]].

Interval questions can be tricky for those who do not accept experience with them. This is considering of the sheer number of cases to consider when interval arrays overlap.

Clarify with the interviewer whether [one, two] and [two, iii] are considered overlapping intervals, because information technology affects how you will write your equality checks.

A common routine for interval questions is to sort the array of intervals by the starting time value of each interval.

Be familiar with writing code to check if two intervals overlap and to merge two overlapping intervals:

                def is_overlap(a, b):   return a[0] < b[1] and b[0] < a[1]    def merge_overlapping_intervals(a, b):   return [min(a[0], b[0]), max(a[ane], b[1])]              

Corner Cases

• Single interval
• Non-overlapping intervals
• An interval totally consumed within another interval
• Duplicate intervals

Exercise Questions

• Insert Interval
• Merge Intervals
• Coming together Rooms and Meeting Rooms II
• Non-overlapping Intervals

Linked List

Notes

Like arrays, linked lists are used to represent sequential data. The benefit of linked lists is that insertion and deletion of code from anywhere in the listing is O(ane), whereas in arrays, the elements have to exist shifted.

Calculation a dummy node at the head and /or tail might assist to handle many border cases where operations have to exist performed at the head or the tail. The presence of dummy nodes ensures that operations will never have be executed on the head or the tail. Dummy nodes remove the headache of writing provisional checks to deal with nada pointers. Exist certain to remove them at the end of the operation.

Sometimes linked lists problem can exist solved without additional storage. Try to borrow ideas from the for contrary a linked list trouble.

For deletion in linked lists, y'all can either alter the node values or alter the node pointers. Y'all might need to keep a reference to the previous element.

For partitioning linked lists, create two dissever linked lists and bring together them back together.

Linked lists problems share similarities with assortment bug. Think nigh how you would solve an array problem and apply information technology to a linked list.

Two pointer approaches are also mutual for linked lists:

• Getting the kth from the last node: Have two pointers, where 1 is 1000 nodes alee of the other. When the node ahead reaches the end, the other node is k nodes behind.
• Detecting cycles: Have two pointers, where i arrow increments twice equally much equally the other. If the two pointers meet, it ways that there is a cycle.
• Getting the heart node: Have two pointers. One pointer increments twice as much as the other. When the faster node reaches the end of the list, the slower node will be at the middle.

Exist familiar with the following routines because many linked list questions brand utilize of one or more of these routines in their solution.

• Count the number of nodes in the linked list
• Contrary a linked list in identify
• Find the middle node of the linked list using fast or irksome pointers
• Merge two lists together

Corner Cases

• Single node
• Two nodes
• Linked list has cycle. Clarify with the interviewer whether there tin be a cycle in the listing. Commonly the answer is no.

Do Questions

• Reverse a Linked Listing
• Detect Wheel in a Linked Listing
• Merge Ii Sorted Lists
• Merge K Sorted Lists
• Remove Nth Node From End Of Listing
• Reorder List

Math

Notes

If the code involves sectionalization or modulo, recall to check for division or modulo by 0 example.

When a question involves "a multiple of a number", modulo might be useful.

Check for and handle overflow and underflow if yous are using a typed language like Java and C++. At the very least, mention that overflow or underflow is possible and ask whether you demand to handle it.

Consider negative numbers and floating point numbers. This may sound obvious, simply when you lot are nether pressure in an interview, many obvious points go unnoticed.

If the question asks to implement an operator such equally power, squareroot, or division, and it is to be faster than O(n), binary search is commonly the arroyo.

Some common formulas

• Sum of ane to N = (n+1) * n/two
• Sum of GP = 2⁰ + ii¹ + 2² + 2³ + … 2^n = 2^(n+ane)-1
• Permutations of Northward = N! / (Northward-G)!
• Combinations of N = N! / (Grand! * (Due north-Yard)!)

Corner Cases

• Division by 0
• Integer overflow and underflow

Practice Questions

• Pw(x, n)
• Sqrt(ten)
• Integer to English Words

Matrix

Notes

A matrix is a two-dimensional array. Questions involving matrices are usually related to dynamic programming or graph traversal.

For questions involving traversal or dynamic programming, brand a re-create of the matrix with the same dimensions that are initialized to empty values. Use these values to store the visited state or dynamic programming table. Be familiar with this routine:

                rows, cols = len(matrix), len(matrix[0]) copy = [[0 for _ in range(cols)] for _ in range(rows)              

• Many grid-based games can be modeled as a matrix. For example, Tic-Tac-Toe, Sudoku, Crossword, Connect iv, and Battleship. It is not uncommon to exist asked to verify the winning condition of the game. For games like Tic-Tac-Toe, Connect 4, and Crosswords, verification has to be washed vertically and horizontally. I trick is to write lawmaking to verify the matrix for the horizontal cells. Then transpose the matrix, reusing the logic used for horizontal verification to verify originally vertical cells (which are at present horizontal).
• Transposing a matrix in Python is just:

                transposed_matrix = nix(*matrix)              

Corner Cases

• Empty matrix. Bank check that none of the arrays are 0 length.
• 1 x 1 matrix.
• Matrix with simply 1 row or column.

Practise Questions

• Prepare Matrix Zeroes
• Spiral Matrix
• Rotate Prototype
• Word Search

Recursion

Notes

Recursion is useful for permutation, because it generates all combinations and tree-based questions. You should know how to generate all permutations of a sequence likewise as how to handle duplicates.

Remember to always define a base of operations case so that your recursion volition end.

Recursion implicitly uses a stack. Hence all recursive approaches tin can be rewritten iteratively using a stack.

Beware of cases where the recursion level goes besides deep and causes a stack overflow (the default limit in Python is chiliad). Yous may get bonus points for pointing this out to the interviewer.

Recursion will never be O(1) space complexity because a stack is involved, unless there is tail call optimization (TCO). Detect out if your chosen linguistic communication supports TCO.

Practise Questions

• Subsets and Subsets 2
• Strobogrammatic Number II

String

Notes

Please read the above tips on sequence. They apply to strings too.

Ask nigh input character set and case sensitivity. Normally the characters are express to lowercase Latin characters, for example a to z.

When you demand to compare strings where the society isn't important (like anagram), you may consider using a HashMap equally a counter. If your language has a built-in Counter class like Python, inquire to utilize that instead.

If you need to go along a counter of characters, a common mistake is to say that the infinite complexity required for the counter is O(due north). The space required for a counter is O(1) not O(n). This is because the upper jump is the range of characters, which is usually a fixed abiding of 26. The input set is just lowercase Latin characters.

Common information structures for looking upwards strings efficiently are

• Trie/Prefix Tree
• Suffix Tree

Common string algorithms are

• Rabin Karp, which conducts efficient searches of substrings, using a rolling hash
• KMP, which conducts efficient searches of substrings

Not-repeating characters

Use a 26-scrap bitmask to indicate which lower example Latin characters are inside the string.

                mask = 0 for c in prepare(discussion):   mask |= (ane << (ord(c) - ord('a')))              

To make up one's mind if two strings have common characters, perform & on the two bitmasks. If the upshot is not-zero, mask_a & mask_b > 0 , then the two strings have common characters.

Anagram

An anagram is word switch or word play. It is the result of re-arranging the letters of a word or phrase to produce a new word or phrase, while using all the original letters just once. In interviews, usually we are merely bothered with words without spaces in them.

To make up one's mind if two strings are anagrams, there are a few plausible approaches:

• Sorting both strings should produce the same resulting cord. This takes O(nlgn) time and O(lgn) space.
• If nosotros map each grapheme to a prime and nosotros multiply each mapped number together, anagrams should have the same multiple (prime gene decomposition). This takes O(due north) time and O(one) space.
• Frequency counting of characters volition help to determine if two strings are anagrams. This too takes O(northward) time and O(ane) infinite.

Palindrome

A palindrome is a word, phrase, number, or other sequence of characters that reads the same astern and forward, such equally madam or racecar .

Here are ways to make up one's mind if a cord is a palindrome:

• Reverse the string and it should exist equal to itself.
• Have two pointers at the start and end of the string. Move the pointers inward till they run into. At whatsoever point in time, the characters at both pointers should match.

The order of characters within the cord matters, then HashMaps are usually non helpful.

When a question is about counting the number of palindromes, a common play a trick on is to have two pointers that move outward, away from the middle. Annotation that palindromes can be even or odd length. For each middle pin position, yous need to check it twice: Once that includes the character and once without the character.

• For substrings, yous can terminate early once there is no lucifer.
• For subsequences, use dynamic programming every bit there are overlapping subproblems. Check out this question.

Corner Cases

• Empty string
• Single-character string
• Strings with merely one distinct character

Practice Questions

• Longest Substring Without Repeating Characters
• Longest Repeating Character Replacement
• Minimum Window Substring
• Encode and Decode Strings
• Valid Anagram
• Group Anagrams
• Valid Parentheses
• Valid Palindrome
• Longest Palindromic Substring
• Palindromic Substrings

Tree

Study Links

• Foliage It Up To Binary Trees

Notes

A tree is an undirected and continued acyclic graph.

Recursion is a common approach for trees. When y'all notice that the subtree problem tin be used to solve the entire problem, try using recursion.

When using recursion, always remember to check for the base case, normally where the node is null.

When you are asked to traverse a tree by level, use depth get-go search.

Sometimes it is possible that your recursive part needs to render two values.

If the question involves summation of nodes along the way, be sure to check whether nodes can exist negative.

Y'all should be very familiar with writing pre-lodge, in-order, and post-gild traversal recursively. As an extension, challenge yourself by writing them iteratively. Sometimes interviewers ask candidates for the iterative approach, especially if the candidate finishes writing the recursive approach also chop-chop.

Binary tree

In-order traversal of a binary tree is insufficient to uniquely serialize a tree. Pre-guild or mail-order traversal is also required.

Binary search tree (BST)

In-gild traversal of a BST will give you all elements in order.

Be very familiar with the properties of a BST. Validate that a binary tree is a BST. This comes upward more often than expected.

When a question involves a BST, the interviewer is usually looking for a solution which runs faster than O(n).

Corner Cases

• Empty tree
• Single node
• Two nodes
• Very skewed tree (like a linked list)

Practice Questions

• Maximum Depth of Binary Tree
• Aforementioned Tree
• Invert or Flip Binary Tree
• Binary Tree Maximum Path Sum
• Binary Tree Level Social club Traversal
• Serialize and Deserialize Binary Tree
• Subtree of Another Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Validate Binary Search Tree
• Kth Smallest Element in a BST
• Everyman Common Ancestor of BST

Tries

Study Links

• Trying to Understand Tries
• Implement Trie (Prefix Tree)

Notes

Tries are special trees (prefix trees) that make searching and storing strings more efficient. Tries have many practical applications, such as conducting searches and providing autocomplete. It is helpful to know these common applications so that you lot can easily identify when a trouble can be efficiently solved using a trie.

Sometimes preprocessing a dictionary of words (given in a list) into a trie, volition improve the efficiency of searching for a word of length thousand, among n words. Searching becomes O(thou) instead of O(northward).

Be familiar with implementing, from scratch, a Trie class and its add together, remove , and search methods.

Do Questions

• Implement Trie (Prefix Tree)
• Add and Search Word
• Give-and-take Search II

Heap

Study Links

• Learning to Honey Heaps

Notes

If y'all encounter a tiptop or everyman k mentioned in the question, information technology is unremarkably a sign that a heap can be used to solve the problem, such as in Top K Frequent Elements.

If you require the top k elements, apply a Min Heap of size grand . Iterate through each element, pushing it into the heap. Whenever the heap size exceeds k , remove the minimum element. That volition guarantee that you lot have the k largest elements.

Practice Questions

• Merge Chiliad Sorted Lists
• Top K Frequent Elements
• Discover Median from Data Stream

Conclusion

Coding interviews are tough. Only fortunately, you tin get amend at them past studying and practicing for them, and doing mock interviews.

To recap, to practice well in coding interviews:

1. Decide on a programming linguistic communication
2. Report CS fundamentals
3. Exercise solving algorithm questions
4. Internalize the Do'southward and Don'ts of interviews
5. Practice by doing mock technical interviews
6. Interview successfully to get the job

By following these steps, y'all volition improve your coding interview skills, and be one step closer (or probably more than) to landing your dream job.

All the all-time!

The content for this post tin be plant hither. Future updates volition be posted there. Pull requests for suggestions and corrections are welcome.

If yous enjoyed this article, share information technology with your friends!

You can too follow me on GitHub and Twitter.

---

---

Larn to code for costless. freeCodeCamp's open up source curriculum has helped more twoscore,000 people go jobs as developers. Become started

lebeauevering49.blogspot.com

Source: https://www.freecodecamp.org/news/coding-interviews-for-dummies-5e048933b82b/