Most Comprehensive Coding Interview Cheat Sheet

Did you know that only 20% of candidates pass the coding interview stage at top tech companies? That's right—80% of even highly skilled developers get stuck.

It’s not that they lack talent or potential—it's usually because they focus too much on learning the "tricks" and not enough on truly understanding the fundamentals.

During my 15+ years of experience, both as a FAANG engineer and as someone who has sat on numerous coding interview panels, I have noticed that candidates who succeed are those who master the core principles of coding and problem-solving.

That’s why we have put together a list of top problems and coding concepts that you need to understand deeply.

This technical interview cheat sheet will help you build a problem-solving mindset and tackle possibly any question you encounter during the technical interviews.

Let's get started!

Data Structure Concepts for Coding Interviews

1. Array

An array is the fundamental data structure that stores a collection of elements, typically of the same data type, in a specific order. Each item can be accessed directly by its position number, called an index.

You can store a list of items, like numbers or names, and easily find any item by knowing its position in the array.

Types of Arrays

1. One-Dimensional Arrays: These are the most basic type of arrays also called linear arrays, where elements are stored in a single row.

2. Dynamic Arrays: Dynamic array can grow or shrink as needed. Moreover, dynamic array offers fast access and good performance on average.

Array Operations

• Accessing Elements
• Insertion
• Deletion
• Traversal
• Searching
• Updating

Key Points to Remember for Technical Interview

1. Arrays have a fixed size once they are created, meaning you can’t add or remove elements without creating a new array.

2. You can directly access any element from the input array using its index which starts from 0.

3. Arrays store elements in contiguous memory locations.

Important Interview Questions

• Roman to Integer (View Solution)

• Find Minimum in Rotated Sorted Array (View Solution)

2. Linked lists

A linked list is a data structure where each element (node) contains data and a reference (pointer) to the next element in the sequence.

In technical terms:

• Head: The first node in the linked list. This is where the list starts.

• Null: The last node in the list, points to null, indicating the end of the list.

Singly Linked Lists

In singly linked lists, each node points only to the next node in the sequence.

Doubly Linked Lists

In a doubly linked list, each node contains two pointers: one pointing to the next node and one pointing to the previous node.

Linked lists Operations

• Insertion
• Deletion
• Traversal
• Searching
• Updating

Key Points to Remember for Technical Interview

1. Linked lists do not have a fixed size, so you can easily add or remove nodes.

2. Unlike arrays, you cannot directly access an element in linked lists using an index.

3. Each node contains the data and the address of the next node.

Important Interview Questions

• Remove Duplicates from Sorted List (View Solution)

• Detect Cycle in Linked lists (View Solution)

• Number of Islands (View Solution)

3. Stacks and Queues

A stack is a simple data structure that works under the concept called LIFO—Last In, First Out.

In the stack, the most recent item added (the last one in) is the first one that gets removed (the first one out).

Principles of a Stack

• Push: Adding an item to the top of the stack.

• Pop: Removing the item from the top of the stack.

A queue, on the other hand, works under the concept called FIFO—First In, First Out.

In a queue, the first item added (the first one in line) is the first one that gets removed (the first one out).

Principles of a Queue

• Enqueue: Adding an item to the end of the queue.

• Dequeue: Removing the item from the front of the queue.

Stack Operations

• Push
• Pop
• Peek (or Top)
• IsEmpty
• IsFull

Queue Operations

• Enqueue
• Dequeue
• Front (or Peek)
• Rear (or Back)
• IsEmpty
• IsFull

Key Points to Remember for Technical Interview

1. Stacks are important for function call management.

2. Queues are essential in BFS algorithms.

Important Interview Questions

• Valid Parentheses (View Solution)
• Reverse a String (View Solution)

4. Tree

When it comes to coding interviews, trees are a common topic.

A tree is a data structure that organizes data hierarchically.

It consists of nodes connected by edges, forming a structure that resembles a branching tree.

Each node holds a value and can have multiple child nodes, but each node only has one parent, except for the root, which has no parent.

Components of a Tree

• Root: top node in the tree

• Leaf: the nodes at the bottom with no children

• Internal Nodes: the nodes between the root and leaves

• Height of a Tree: The height of a tree is the length of the longest path from the root node to any leaf node.

• Subtree: A subtree is any node in a tree along with all of its descendants.

Trees are inherently recursive data structures. Each subtree of a tree is itself a tree, which makes many tree operations naturally recursive.

Types of Trees

1. Binary Tree: A tree where each node has at most two children, typically referred to as the left and right child.

2. Binary Search Tree (BST): A tree where the left child of a node contains a value less than its parent node, and the right child contains a value greater than its parent.

3. Balanced Tree: A tree where the height difference between the left and right subtrees of any node is minimal, ensuring that operations like search, insertion, and deletion remain efficient.

Tree Operations

• Insertion
• Deletion
• Traversal (Pre-order, In-order, Post-order)
• Searching
• Finding Minimum
• Finding Maximum
• Finding Height (or Depth)
• Checking if the Tree is Balanced
• Finding Successor
• Finding Predecessor

Key Points to Remember for Technical Interview

1. A Full Binary Tree is a tree where every node has 0 or 2 children.

2. A Complete Binary Tree is a tree where all levels are fully filled except possibly the last, which is filled from left to right.

Important Interview Questions

• Validate Binary Search Tree (View Solution)

• Binary Tree Maximum Path Sum (View Solution)

• Same Tree (View Solution)

5. Graph

A graph is a collection of points (nodes) connected by lines (edges) that show relationships between those points.

Imagine you have a group of people, and you want to show who knows who. Each person is a node, and a line connecting two people shows that they know each other—this line is called an edge.

You can use graphs to represent all sorts of networks, like social circles, maps, or even how different tasks depend on each other in a project.

Types of Graphs

• Directed vs. Undirected: In a directed graph, the edges have a direction, like a one-way street. In an undirected graph, the edges don’t have a direction, like a two-way street.

• Weighted vs. Unweighted: In a weighted graph, edges have a value (or weight), representing something like distance or cost. In an unweighted graph, all edges are equal, and there’s no specific value associated with them.

• Cyclic vs. Acyclic: A cyclic graph has at least one loop or cycle (a path that starts and ends at the same node). An acyclic graph doesn’t have any cycles.

Important Graph Concepts

• Traversal: Just like with trees, traversal is key in graphs. The two most common methods are:

  • Breadth-First Search (BFS): Explores all the neighbors of a node before moving on to their neighbors.

  • Depth-First Search (DFS): Goes as deep as possible down one path before backtracking.

Graph Operations

• Add Node (Vertex)
• Add Edge
• Remove Node (Vertex)
• Remove Edge
• Search/Traversal
• Check for Edge
• Find Neighbors
• Pathfinding
• Cycle Detection
• Connected Components

Key Points to Remember for Technical Interview

1. Sparse Graph has relatively few edges compared to the number of nodes.

2. Dense Graph has the number of edges close to the maximum possible, where most nodes are connected.

Important Interview Questions

• Clone Graph (View Solution)

• Alien Dictionary (View Solution)

6. Hash Table

A hash table is a data structure that lets you store and retrieve data quickly using keys. Each piece of data (or value) is stored in a specific spot based on a key.

How It Works

When you want to store something in a hash table, you give it a key.

The hash table uses a function, called a hash function, to turn that key into an index, which tells it where to store the data in an array.

Later, when you need to retrieve that data, you just use the same key, and the hash function will tell you where to find it.

For example, if you wanted to store information about a student using their ID number, the function would take that ID and quickly find the right spot in the array where the student’s information is stored.

How to Prepare Hash Table for Technical Interviews

For coding interviews, make sure you understand how hash tables work using key-value pairs and can explain how collisions are handled.

Additionally, try to practice problems that involve using hash tables to solve real-world challenges, like counting the frequency of elements, finding pairs in an array, or implementing a simple caching system.

Hash Table Operations

• Insertion (Put/Set)
• Deletion (Remove)
• Search (Get/Lookup)
• Update
• Check for Existence (Contains/Has)
• Traversal

Key Points to Remember for Technical Interview

1. The load factor is a measure of how full the hash table is.

2. A hash map is a type of hash table with specific characteristics defined by the language or library implementing it.

3. Hash tables typically require more memory than other data structures due to the need to handle collisions and maintain efficiency.

Important Interview Questions

• Maximum Number of Balloons (View Solution)

• Longest Palindrome (View Solution)

Review your concepts with our course on Data Structures and Algorithms

Time and Space Complexity in Data Structures and Algorithms

Understanding the concept of time and space complexity is essential for your technical interviews. You will often be asked to evaluate the efficiency of your solution during the algorithm interviews.

Additionally, time and space complexity helps you choose the best algorithm for a problem, especially when working with a large data set.

Time Complexity

Time complexity is a way to describe how the time needed to run an algorithm increases as the size of the input grows. It gives you an idea of how efficiently an algorithm performs as you scale up the problem.

In coding interviews, you’ll often see time complexity expressed using Big O notation.

This notation describes the worst-case scenario, or how the algorithm behaves when it has to deal with the most challenging input.

Some common Big O notations are:

• O(1): Constant time. The algorithm takes the same amount of time, no matter how big the input is.

• O(n): Linear time. The time increases directly in proportion to the input size. If you double the input, the time doubles.

• O(n^2): Quadratic time. The time increases by the square of the input size. This usually happens in algorithms with nested loops.

Space Complexity

Space complexity, on the other hand, measures how much memory an algorithm needs as the input size grows. Just like with time complexity, space complexity is often expressed in Big O notation.

Moreover, it includes the memory used by the input data, the memory required for variables, and any additional space the algorithm uses during execution.

For example:

• O(1): Constant space. The algorithm uses a fixed amount of memory, no matter the input size.

• O(n): Linear space. The memory usage grows directly in proportion to the input size. For a detailed explanation, check out the ultimate guide on big-o.

Algorithms to Prepare for Technical Interviews

We suggest preparing core algorithms in this technical interview cheat sheet.

Let's discuss them one by one.

1. Sorting Algorithms

Sorting is the process of arranging data in a specific order, usually ascending or descending.

Here are the basic types of sorting algorithms:

• Bubble Sort: Compares and swaps adjacent elements, repeatedly passing through the list until it's sorted.

• Selection Sort: Finds the smallest (or largest) element and moves it to its correct position, one at a time.

• Insertion Sort: Builds a sorted list one element at a time by inserting each element into its correct position.

• Merge Sort: Merge sort divides the list into smaller parts, sorts them, and then merges them back together. By understanding merge sort, you can handle edge cases efficiently.

• Quick Sort: Picks a pivot element and partitions the list into smaller and larger elements, then sorts the partitions recursively.

Important Interview Questions

• Top 'K' Frequent Numbers (View Solution)

• Meeting Rooms (View Solution)

2. Searching

Searching algorithms are methods used to find an element in a list or data structure.

Here are the basic types:

1. Linear Search: This method checks each element in the list one by one until it finds the target. It’s simple but can be slow for large lists.

2. Binary Search: This method works on sorted lists. It repeatedly divides the list in half, checking the middle element to see if it’s the target.

Important Interview Questions

• Minimum Common Value (View Solution)

• Search a 2D Matrix (View Solution)

3. Dynamic Programming

Dynamic programming is a technique used to solve complex problems by breaking them down into simpler subproblems.

The idea is to store the results of these subproblems so that you don’t have to solve the same problem more than once, saving time.

Key Concepts

1. Overlapping Subproblems: Problems where the same smaller problem is solved multiple times.

2. Memoization: Storing the results of subproblems to avoid recomputation.

3. Tabulation: Building up a solution iteratively using a table, typically starting from the simplest subproblem.

Important Interview Questions

• Coin Change (View Solution)

• Subset Sum (View Solution)

• Fibonacci numbers (View Solution)

For more information, check out our course on Dynamic Programming.

4. Greedy Algorithm

A greedy algorithm is a method for solving problems by making the best choice possible at each step, without worrying about the bigger picture.

Key Concepts

• Local Best: At each step, you make the choice that seems best right now.

• No Backtracking: Once you make a choice, you don’t go back to change it.

• Not Always Optimal: Greedy algorithms are simple and fast, but they don’t always give the best overall solution.

Important Questions for Interview

• Valid Palindrome (View Solution)

• Remove Duplicate Letters (View Solution)

5. Recursive Algorithms

A recursive algorithm is a method where the solution to a problem depends on solving smaller instances of the same problem.

The algorithm calls itself with a smaller input until it reaches a base case, which is a simple, known solution that doesn’t require further recursion.

How It Works

1. Base Case: The simplest instance of the problem, where the answer is known and can be returned directly. This stops the recursion.

2. Recursive Case: The function calls itself with a smaller or simpler version of the original problem, gradually working towards the base case.

These algorithms are powerful for problems that can naturally be divided into similar subproblems, like tree traversal, searching through combinations, or solving puzzles like the Tower of Hanoi.

Important Questions for Interview

• BST Inorder Traversal (View Solution)

• Converting Decimal to Binary (View Solution)

For more details, check out our Art of Recursion course or read about the concept of recursion.

6. Backtracking

Backtracking is a problem-solving technique where you explore all possible options to find a solution, but "backtrack" and undo steps when you hit a dead end or when an option doesn’t lead to a solution.

It’s like trying different paths in a maze: you go forward until you can’t, then you back up and try a different route.

Backtracking is useful for problems that involve making a series of decisions, especially when you need to explore all possible combinations, like in puzzles, permutations, or combinations.

How It Works

1. Choose: Pick an option or make a decision.

2. Explore: Move forward with that choice, continuing to make decisions.

3. Backtrack: If you reach a point where the current path doesn’t work, go back to the previous decision and try a different option.

Important Questions for Interview

• Word Search (View Solution)

• Factor Combinations (View Solution)

7. Divide and Conquer

Dynamic programming is a technique used to solve problems by breaking them down into smaller, overlapping problems and solving each of those smaller problems just once.

The idea is to store the results of these smaller problems so that when the same problem comes up again, you don't need to solve it again—you just reuse the stored result.

It’s especially useful in coding assessments for problems involving optimization, such as finding the best way to do something or counting the number of ways to achieve a goal.

Important Questions for Interview

• Majority Elements (View Solution)

• Longest Nice Substring (View Solution)

Top Coding Patterns for the Interview

Coding patterns are common techniques or strategies used to solve specific types of problems in programming.

Here is a quick revision of the 20 common coding patterns often encountered in programming:

1. Sliding Window

A pattern that creates a window and moves it to process a subset of data efficiently.

Application: use it when you need to calculate or track data set within a moving range.

Practice Problems

• Maximum Sum Subarray of Size K (Solution)

• Fruits into Baskets (Solution)

• Longest Substring with Same Letters after Replacement (Solution)

2. Two Pointers

Involves using two pointers to traverse and compare elements in a list or array

Application: Use it for problems like finding pairs or reversing arrays.

Practice Problems

• Pair with Target Sum(Solution)

• Find Duplicate(Solution)

3. Fast and Slow Pointers

Utilizes two pointers moving at different speeds to detect cycles in linked lists or find the middle element.

Application: problems related to linked lists and cycles

Practice Problems

• Linkedlist Cycle(Solution)

• Happy Number(Solution)

4. Merge Intervals

Merges overlapping intervals into one.

Application: ranges or time schedules.

Practice Problems

• Merge Intervals (Solution)

• Insert Interval (Solution)

5. Cyclic Sort

Sorts numbers by placing each element in its correct position

Application: use it when dealing with consecutive numbers in a fixed range.

Practice Problems

• Cyclic Sort (Solution)

• Find Missing Number (Solution)

6. In-place Reversal of a Linked List

Reverses a linked list or a part of it without using extra space.

Application: use it for reversing sequence.

Practice Problems

• Reverse a sublist (Solution)

• Reverse Linkedlist (Solution)

7. Top K Elements

Finds the top K largest or smallest elements in a collection.

Application: use it in ranking or priority-based problems.

Practice Problems

• Top K Elements (Solution)

• Frequency Sort (Solution)

8. K-way Merge

Merges K sorted arrays or lists into one sorted list.

Application: use it when combining multiple sorted datasets.

Practice Problems

• Merge K Sorted Lists (Solution)

• Smallest Number in Sorted Matrix (Solution)

9. Knapsack (0/1)

Solves optimization problems by deciding which items to include in a limited capacity knapsack.

Application: use it in resource allocation problems.

Practice Problems

• 0/1 Knapsack (Solution)

• Subset Sum (Solution)

10. Depth-First Search (DFS)

Traverses a graph or tree by exploring as far as possible along each branch before backtracking.

Application: use it in pathfinding and connectivity problems

Practice Problems

• Sum of Path Numbers (Solution)

• Path with Given Sequence (Solution)

11. Breadth-First Search (BFS)

Traverses a graph or tree level by level.

Application: use it for shortest path and level-order traversal problems.

Practice Problems

• Zigzag Traversal (Solution)

• Level Order Successor (Solution)

12. Modified Binary Search

Adjusts the standard binary search to handle variations, like searching in a rotated or shifted sorted array.

Application: used when the simple binary search isn't enough.

Practice Problems

• Ceiling of a Number (Solution)

• Number Range (Solution)

13. Bitwise XOR

Involves using the XOR operation to solve problems.

Application: used to find the single non-repeated number in a list or to swap values.

Practice Problems

• Single Number (Solution)

• Complement of Base 10 (Solution)

14. Palindromic Subsequence

Finds the longest sequence within a string that reads the same forward and backward

Application: problems where you need to identify or count palindromic sequences within a string

Practice Problems

• Palindromic Substrings (Solution)

15. Subsets

Involves generating all possible combinations or groups from a given set of elements.

Application: used in problems where you need to explore all possible selections or combinations

Practice Problems

• Subsets (Solution)

• Permutations (Solution)

16. K-way merge

Combines multiple sorted lists into one sorted list by merging them efficiently.

Application: used in problems like merging data from several sorted sources.

Practice Problems

• Merge K Sorted Lists (Solution)

• Smallest Number Range (Solution)

17. Topological sort

Arranges nodes in a directed graph in a sequence where each node comes before the nodes it points to.

Application: used in scheduling tasks or resolving dependencies.

Practice Problems

• Topological Sort (Solution)

• Task Scheduling (Solution)

18. Two heaps

Uses two heaps to efficiently keep track of the median in a stream of numbers.

Application: used in problems where you need to quickly find or maintain the median of a dynamically changing dataset.

Practice Problems

• Find Median (Solution)

• Maximize Capital (Solution)

19. Fibonacci numbers

Generates a sequence where each number is the sum of the two preceding ones.

Application: used in problems involving series, dynamic programming, or where a sequence depends on previous results.

Practice Problems

• House Robber (Solution)

• Staircase (Solution)

20. Longest Common Substring

Finds the longest string of characters that appears in the same order in two different strings.

Application: used in problems where you need to compare and match similar parts of two strings.

Practice Problems

• Longest Increasing Subsequence (Solution)

• Longest Common Subsequence (Solution)

• Edit Distance (Solution)

For more details, review the coding lessons or read about the top 20 coding patterns.

Frequently Asked Questions - Technical interview cheat sheet

1. Which programming language to use in a tech interview?

Use the programming language you are most comfortable with and can code efficiently in. Most interviews allow you to choose your preferred language, as long as it is supported by the company. Ensure you understand the language's syntax and libraries well.

2. What are the Do’s and Dont’s of a Coding Interview?

Do’s:

• Clarify the problem before you start coding problems.
• Plan your strategy and ensure you’re on the same page.
• Explain your thought process and approach.
• Write clean code and handle coding challenges effectively.
• Test your code within the time constraints.

Don'ts:

• Don’t be defensive about mistakes.
• Don’t forget to communicate your progress and decisions.
• Don't rush to produce the same output without considering edge cases.

3. What Should I Do After a Coding Interview?

After a coding interview, send a thank-you email to the interviewer, expressing appreciation for the opportunity. Reflect on the interview by reviewing your performance, including what went well and what could be improved. If feedback is provided, take it constructively.

4. How to End the Coding Interviews?

End the interview on a positive note by thanking the interviewer for their time. If appropriate, ask about the next steps in the interview process and when you might expect to hear back. This also works for non-technical interviews.

5. How important are mock interviews in my preparation?

Mock interviews simulate real interview conditions by providing a platform to receive feedback. They help you improve your technical knowledge, enhance your interpersonal skills, practice behavioral questions, and refine your thought process. DesignGurus.io offers specialized mock interview sessions for coding and system design.

Wrapping Up - Coding Interview Cheat Sheet

Mastering the coding interview for software engineers takes more than just knowing how to code—it's a blend of practice and problem-solving.

When preparing for your coding interview, ensure you have a stable internet connection and enough reserved space on your device to handle additional elements in your data set during practice.

This coding interview cheatsheet is a go-to guide for software engineers covering key patterns and tips that will help tackle even the toughest coding interview questions.

But don’t stop here—use this cheatsheet as a launchpad to start practicing and refining your skills in the right direction with DesignGurus.io.