A collection of coding challenges and their solutions from:
- LeetCode
- HackerRank
- Cracking the Coding Interview
Complexity | Name |
---|---|
O(1) | Constant |
O(log n) | Logarithmic |
O(n) | Linear |
O(n log n) | Linear-logarithmic |
O(n ^ 2) | Quadratic |
O(n ^ c) | Polynomial |
O(2 ^ n) | Exponential |
O(n!) | Factorial |
Keywords | Techniques |
---|---|
"Shortest path", "Minimum", "closest" | BFS , Dijkstra |
"Level-by-level", "Least number of moves", "Batch" | BFS |
"All paths", "Choices", "Branching" | BFS , DFS |
"Path exists" | BFS , DFS , Disjont sets |
"Path may not exist" | isolated vertices , cycles |
"Generate all", "All permutations", "All combinations", "All possible", "Choices", "Branching" | Backtracking (DFS) |
"Next Permutation" | pivot & sorting |
"Sorted", "Maximum", "Minimum" | Binary Search , Two pointers |
"Right-most", "Left-most" | Binary Search |
"Iterating array comparing elements" | Stack |
"Next greater element", "Next lesser element" | Monotonic stack |
"Longest subsequence", "Smallest subsequence", "Maximum", "Minimum", "Neighbors" | Sliding window |
"Subsequence in a graph" | Memoization , Backtracking (DFS) |
"In-place" | Swap |
"Loop/cycle in a linked list" | Slow and Fast pointers i.e. Hare and Tortoise |
"Loop/cycle in a graph" | Disjoint sets , Topological sort |
"Minimum cost" | MST , Kruskal , Prims |
"Compare neighbors in a string", "Comparing right to left elements" | Stack |
"Largest value", "Smallest value" | Heap |
"kth smallest", "kth largest", "kth frequent", "Top k", "k closet" | QuickSelect |
"Matrix diagonal" | r1 - c1 == r2 - c2 |
"Consecutive" | sort |
"Merge", "Intervals", "Neighbors" | sort |
"Rotate by k" | (i + k) % array.count |
Need to... | Technique | Example |
---|---|---|
Optimise graph traversal | Memoization |
LongestIncreasingSubsequence |
Generate all premutations of an array | Offset nested for loops with the inner starting at i+1 |
AdditiveNumber |
Find "x" from an infinite array | Treat array as a graph and perform a DFS, at each level include all elements in the array | CoinChanges |
Explore possible replacement values for a given element in an array/string | DFS , Memoization |
ValidParenthesisString |
Can't use additional memory when working with an array | Negative Marking |
FindAllNumbersDisappearedInAnArray |
Combine numbers together to form one number e.g. [5, 10] to 510 |
Convert the numbers to strings | LargestNumber |
Simulate time passing or different rounds | Batch up changes either using a Queue or caching state between rounds |
PushDominoes |
Count possible substrings | count * (count + 1) / 2 |
Substring |
Count possible subarrays | count * (count + 1) / 2 |
CountTheNumberOfIncremovableSubarraysI |
Count possible subsequences | (2 ^ count) - 1 |
Subsequence |
Repeatedly find the min and max value in subarrays | Sort the overall array and take the first and last element in the subarray | MinimumDifferenceBetweenHighestAndLowestOfKScore |
Find the end of duplicates in an array | Nest a while loop that only increments one of the pointers | RemoveDuplicatesFromSortedListII |
Find the minimum distance from one element to multiple elements in a graph | Multi-source BFS | AsFarFromLandAsPossible |
Traverse up a tree | Turn the tree into a directed graph with child -> parent and parent -> child |
ClosestLeafInABinaryTree |
Sort two "linked" arrays together | Merge the two array into one tuple array | MaximumCoinsHeroesCanCollect |
Work out the cost/total of all previous elements in sorted data | PrefixSum |
MaximumCoinsHeroesCanCollect |
Flip neighbors to find the maximum/minimum | Sliding window |
MaximizeTheConfusionOfAnExam |
A lot of problems can be treated as graph problems.
Technique | What is it? | Example |
---|---|---|
BFS | Breadth-first search involves searching a graph level by level - ensuring all vertices on a level have been searched before moving onto the next level. A level is all immediate vertices connected to a vertice from the previous level. | BFS |
DFS | Depth-first search involves searching a graph by fully exploring one path from root before searching any other other vertices from root. | DFS |
Binary search | Binary search works by selecting the middle index in the sorted array values and comparing its value against target . If values[mid] matches target then we have found our target and can return; if values[mid] does not match target then we half the search space by moving either left to the right (if values[mid] was smaller than target ) or moving right to the left (if values[mid] was larger than target ). We can reduce the search space like this because values sorted so we know that if values[mid] was smaller than target then any index less than mid will contain an even smaller value than values[mid] so searching those other indexes would be pointless (the opposite is true for reducing the search space to the right of mid ). |
BinarySearch |
Dynamic Programming | Dynamic programming is a technique for solving problems of recursive nature where we re-use work to speed up the process of solving the problem. It can look like dynamic programming solutions are brute force in nature. Dynamic programming can be implemented bottom-up or top-down: - Bottom-up is when we solve the easiest sub-problem first and use that solution directly to solve a "higher" problem. - Top-down is when we cache the solutions to sub-problems in the course of solving a "higher" problem. We can then access those cached solutions when attempting to solve other similar "higher" problems (not the original "higher problem"). |
HouseRobberIII |
- A tree has one root node
- Each node has only one parent node (apart from the root node which has none)
- Each node has a maximum of two child nodes - left and right
- A node without any child nodes is a leaf node
- Any subtree is also a valid independent binary Tree
- The depth of a node is the number of edges from the node to the tree's root node - a root node will have a depth of 0
- The height of a node is the number of edges on the longest path from the node to a leaf - a leaf node will have a height of 0
- Traversal:
- Preorder traversal involves traversing from the root to the left subtree then to the right subtree
- Inorder traversal involves traversing from the left subtree to the root then to the right subtree
- Postorder traversal involves traversing from the left subtree to the right subtree then to the root
- Searching:
- Breadth First Search (BFS) - queue based, level by level traversal
- Depth First Search (DFS) - stack based, go as deep as possible then backtrack
- A balanced binary tree is a tree in which the height of the left and right subtrees differ by no more than 1
- A complete binary tree is a tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are filled left to right
- A full/proper binary tree is a tree in which every node has either 0 or 2 children.
- A tree is special type of graph
- Doesn't contain cycles
Inherits the characteristics of a Binary Tree
- Nodes to the left of the root are less than or equal than that of the root
- Nodes to the right of the root are greater than that of the root
- Inorder traversal results in a sorted list of the nodes in a BST
- Searching takes O(log n) time as at each node it is possible to discard half of the remaining nodes (as being either too small of too large)
- Non-linear data structure consisting of nodes/vertices and edges
- Can be weighted or unweighted
- Weighted - each edge has a cost
- Unweighted - each edge is the same i.e. no cost
- Can be directed or undirected
- Directed - only allow travel down an edge in a certain direction,
- Undirected - edge can be used for travel both ways
- Each node has an
indegree
- this is the number of node connecting into that node - Each node has n
outdegree
- this is the number of nodes, this node is connecting to - A node can have any number of edges to other nodes
- Can contain unconnected nodes
- Adjacency list can be used to store the
outdegree
of each node in a graph - A matrix can be used to show edges between Nodes
- Wasteful spacewise
- A path is sequence of nodes that it takes to get from A -> Z
- Directed Acyclic Graph (DAG) is a directed graph with no directed cycles
- Topological sort only works on DAGs
- Searching:
- Breadth First Search (BFS) - queue based, level-by-level traversal
- Depth First Search (DFS) - stack (recursive) based, go as deep as possible then backtrack
- Can contain cycles
- Just a disguised graph
- Relative indexing allows for moving/search a matrix without going out of bounds by mapping the possible movements and determining if that movement is valid
- Visited arrays ensure that when search we don't get caught in an infinite loop
- Searching:
- Breadth First Search (BFS) - queue based, level by level traversal
- Depth First Search (DFS) - stack based, go as deep as possible then backtrack
- Backtracking involves exhaustively searching down one path before reversing back up that path to search down alternative paths at each branching point