Last modified: December 05, 2024

This article is written in: 🇺🇸

Solving Programming Brain Teasers

Programming puzzles and brain teasers are excellent tools for testing and enhancing your coding abilities and problem-solving skills. They are frequently used in technical interviews to evaluate a candidate's logical thinking, analytical prowess, and ability to devise efficient algorithms. To excel in these scenarios, it is recommended to master effective strategies for approaching and solving these problems.

General Strategies

When tackling programming puzzles, consider the following strategies:

Data Structures

Understanding and effectively using data structures is fundamental in programming. Below are detailed strategies and tips for working with various data structures.

Working with Arrays

Arrays are fundamental data structures that store elements in contiguous memory locations, allowing efficient random access. Here are strategies for working with arrays:

Working with Strings

Strings, as sequences of characters, often require special handling due to their immutable nature in some languages and the variety of operations performed on them.

Working with Linked Lists

Linked lists are dynamic data structures consisting of nodes that contain data and references to the next (and possibly previous) nodes.

Working with Trees and Binary Trees

Trees are hierarchical data structures with a root node and child nodes. Binary trees are a specific type where each node has at most two children.

Working with Graphs

Graphs consist of vertices (nodes) and edges connecting them, used to represent complex relationships.

I. Graph Representations:

II. Graph Traversal Algorithms:

III. Cycle Detection:

IV. Shortest Path Algorithms:

V. Minimum Spanning Trees (MST):

VI. Network Flow Algorithms:

VII. Other Important Concepts:

Working with Hash Tables

Hash tables store key-value pairs for efficient lookup, insertion, and deletion.

Algorithms

Mastering algorithms is helpful for solving programming problems more efficiently by understanding patterns and techniques that reduce time and space usage.

Two-Pointer Technique

I. The two-pointer technique is ideal when working with sorted arrays or when the task involves finding pairs or triplets that meet a certain condition, such as summing to a target value.

II. Implementation tips for the two-pointer technique include:

III. An example of this technique is finding all pairs in a sorted array that sum to a given value.

Step 1: Start with two pointers, left at the beginning and right at the end of the array.

  Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
          ↑                       ↑
        left                   right
  Check: arr[left] + arr[right] = 1 + 9 = 10 (Target Found!)

Step 2: If arr[left] + arr[right] equals the target, you’re done!
If the sum is less than the target, move left right.
If the sum is greater than the target, move right left.

Example when the sum is too small:
  Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
             ↑                  ↑
           left              right
  Check: arr[left] + arr[right] = 2 + 9 = 11 (Too Large, move right left)

Example when the sum is too large:
  Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]
          ↑                    ↑
        left                 right
  Check: arr[left] + arr[right] = 1 + 8 = 9 (Too Small, move left right)

Recursion

I. Recursion works by breaking a problem into smaller instances of itself, with each call reducing the size of the problem.

II. Key principles of recursion include:

III. Consider stack overflow when recursion depth is too great. You can either switch to an iterative approach or use tail recursion optimization (if supported by the language). Memoization is another technique to improve efficiency by caching results of recursive calls to avoid redundant computations.

factorial(4)
|
|---> 4 * factorial(3)
           |
           |---> 3 * factorial(2)
                      |
                      |---> 2 * factorial(1)
                                 |
                                 |---> 1 * factorial(0)
                                            |
                                            |---> Base case: 1

Backtracking

I. Backtracking is well-suited for problems that require exploring all potential configurations, such as puzzles like Sudoku, the N-Queens problem, or combinatorial tasks.

II. Implementation tips for backtracking include:

III. A classic example is solving the N-Queens problem, where queens are placed row by row, and conflicts are resolved by backtracking when necessary.

Step 1: Start with an empty board.

+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Step 2: Move to Row 2.

+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   | Q |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Step 3: Move to Row 3.

+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   | Q |   |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Step 4: Move to Row 4.

Step 5: Try other possibilities in Row 3.

Step 6: Try other possibilities in Row 2.

+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   | Q |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Step 7: Move to Row 3.

+---+---+---+---+
| Q |   |   |   |
+---+---+---+---+
|   |   |   | Q |
+---+---+---+---+
|   | Q |   |   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Continue exploring alternatives and backtracking as necessary until all solutions are found.

Dynamic Programming

I. Dynamic programming is used to solve optimization problems by breaking them down into overlapping subproblems with an optimal substructure, meaning solutions to smaller subproblems can be reused to solve larger problems.

II. There are two primary approaches to dynamic programming:

III. The key steps in dynamic programming include:

IV. Space optimization is often possible by realizing that only a few recent states are needed, reducing space complexity.

V. Classic examples include problems like the Fibonacci sequence, the Knapsack problem, or calculating the minimum edit distance between two strings.

DP Table (Rows = Items, Columns = Knapsack Capacities):

  Capacity ->  0   1   2   3   4   5   6   7
  Item 0     [ 0   0   0   0   0   0   0   0 ]  (Base case: No items)
  Item 1     [ 0   1   1   1   1   1   1   1 ]  (Include Item 1)
  Item 2     [ 0   1   1   4   5   5   5   5 ]  (Include Item 2)
  Item 3     [ 0   1   1   4   5   6   6   9 ]  (Include Item 3)
  Item 4     [ 0   1   1   4   5   7   8  11 ]  (Include Item 4)

How the Table Is Filled

For each cell $DP[i][w]$ if the weight of the item $i$ is less than or equal to the current capacity $w$, choose the maximum of:

Visualization of Choices

I. For Item 1 (Weight = 1, Value = 1):

Capacity = 0 → Can't include Item 1 → DP[1][0] = 0
Capacity = 1 → Include Item 1 → DP[1][1] = 1
Capacity = 2 → Include Item 1 → DP[1][2] = 1
...
Capacity = 7 → Include Item 1 → DP[1][7] = 1

II. For Item 2 (Weight = 3, Value = 4):

Capacity = 0 → Can't include Item 2 → DP[2][0] = 0
Capacity = 3 → Include Item 2 → DP[2][3] = 4
Capacity = 4 → Include Item 2 → DP[2][4] = 5
...
Capacity = 7 → Include Item 2 → DP[2][7] = 5

III. Continue for all items, progressively updating the table.

Extract the Solution

To find the maximum value look at the last cell: $DP[4][7] = 11$.

To find the items included trace back from $DP[4][7]$, checking where values changed:

Final Knapsack Contents:

Greedy Algorithms

I. Greedy algorithms are used when making a locally optimal choice at each step leads to a globally optimal solution.

II. The two key characteristics of greedy algorithms are:

III. Common implementation tips for greedy algorithms include:

IV. Examples of greedy algorithms include the activity selection problem, Huffman coding, and algorithms for finding minimum spanning trees (Prim's and Kruskal's).

Example Huffman coding Input:

Characters: $[A, B, C, D, E, F]$

Frequencies: $[5, 9, 12, 13, 16, 45]$

Build a Min-Heap

Create a priority queue (min-heap) with the characters and their frequencies.

Initial Min-Heap:
    5(A)  9(B)  12(C)  13(D)  16(E)  45(F)

Build the Huffman Tree

Combine the two smallest frequency nodes into a new node. Repeat until there is one tree.

I. Combine 5(A) and 9(B):

(14)
 /  \
5(A) 9(B)

Updated Heap: $[12(C), 13(D), 14(AB), 16(E), 45(F)]$

II. Combine 12(C) and 13(D):

(25)
 /  \
12(C) 13(D)

Updated Heap: $[14(AB), 16(E), 25(CD), 45(F)]$

III. Combine 14(AB) and 16(E):

(30)
 /  \
14(AB) 16(E)

Updated Heap: $[25(CD), 30(ABE), 45(F)]$

IV. Combine 25(CD) and 30(ABE):

(55)
 /  \
25(CD) 30(ABE)

Updated Heap: $[45(F), 55(CDABE)]$

V. Combine 45(F) and 55(CDABE):

Tree:
         (100)
         /    \
      45(F)  55(CDABE)
       /      \
    25(CD)   30(ABE)
    /   \     /    \
 12(C) 13(D) 14(AB) 16(E)
                  /   \
               5(A)   9(B)

Assign Binary Codes

Traverse the tree to assign codes:

Codes:
A = 000
B = 001
C = 100
D = 101
E = 01
F = 11

Final Huffman Tree Diagram:

Tree:
                        (100)
                       /     \
                    (45)     (55)
                   /         /    \
                (F)      (25)    (30)
                        /   \     /   \
                     (C)   (D) (14)  (E)
                                 /  \
                              (A)  (B)

Divide and Conquer

I. The divide and conquer strategy solves problems by dividing them into smaller subproblems, solving those independently, and then combining their solutions.

II. Implementation tips for divide and conquer:

III. Examples of divide and conquer algorithms include Merge Sort, Quick Sort, and Binary Search.

Graph Algorithms

Below is a detailed comparison of commonly used graph algorithms:

Algorithm/Technique Uses Implementation
Breadth-First Search (BFS) Finding the shortest path in unweighted graphs, level-order traversal. Use a queue to process nodes in a First In, First Out (FIFO) manner.
Depth-First Search (DFS) Topological sorting, cycle detection, pathfinding. Use recursion or a stack to explore as deep as possible before backtracking.
Dijkstra's Algorithm Shortest path in weighted graphs with non-negative weights. Use a min-heap (priority queue) to select the next node with the smallest tentative distance.
Bellman-Ford Algorithm Shortest path in graphs with negative weights, detecting negative cycles. Relax all edges V-1 times, where V is the number of vertices.
Floyd-Warshall Algorithm All pairs shortest paths. Use a 2D matrix to store distances, updating distances by considering each vertex as an intermediate point.
Union-Find Data Structure Keeping track of disjoint sets, cycle detection in Kruskal's algorithm. Optimize with path compression and union by rank for efficient merging of sets and lookups.

Sorting Algorithms

Sorting algorithms are fundamental to computer science and programming. They are used to rearrange elements in a list or array so that they follow a specific order (ascending or descending). Efficient sorting is a first step for optimizing other algorithms (like search and merge algorithms) that require input data to be in sorted lists. Understanding the different sorting algorithms, their time and space complexities, stability, and suitable use cases is essential for problem-solving and technical interviews.

Overview of Common Sorting Algorithms

Below is a detailed comparison of commonly used sorting algorithms:

Algorithm Average Time Complexity Worst-Case Time Complexity Space Complexity Stability Best Use Case Notes
Bubble Sort $O(n^2)$ $O(n^2)$ $O(1)$ Stable Educational purposes, small datasets Simple but inefficient for large datasets
Insertion Sort $O(n^2)$ $O(n^2)$ $O(1)$ Stable Nearly sorted or small datasets Efficient for small or nearly sorted datasets
Selection Sort $O(n^2)$ $O(n^2)$ $O(1)$ Unstable Small datasets, when memory is limited Inefficient for large datasets
Merge Sort $O(n \log n)$ $O(n \log n)$ $O(n)$ Stable Large datasets, linked lists Requires additional memory for merging
Quick Sort $O(n \log n)$ $O(n^2)$ $O(\log n)$ Unstable Large datasets, general-purpose sorting Pivot selection strategy affects performance
Heap Sort $O(n \log n)$ $O(n \log n)$ $O(1)$ Unstable Large datasets, in-place sorting Efficient with minimal memory usage
Radix Sort $O(nk)$ $O(nk)$ $O(n + k)$ Stable Large datasets with integer keys Non-comparative sorting algorithm
Counting Sort $O(n + k)$ $O(n + k)$ $O(k)$ Stable Small range of integer keys Efficient when range $k$ is small
Tim Sort $O(n \log n)$ $O(n \log n)$ $O(n)$ Stable Real-world data, hybrid sorting Default sorting algorithm in Python
Bucket Sort $O(n + k)$ $O(n^2)$ $O(n)$ Stable Uniformly distributed data Divides elements into buckets
Shell Sort $O(n \log n)$ to $O(n^2)$ $O(n^2)$ $O(1)$ Unstable Medium-sized datasets Improves upon Insertion Sort

General Tips for Sorting Algorithms

Practical Applications

Bit Manipulation

Bit manipulation involves algorithms that operate directly on bits, the basic units of data in computing. By leveraging bit-level operations, you can achieve performance optimizations, reduce memory usage, and solve certain problems more elegantly. Bit manipulation is particularly useful in systems programming, cryptography, graphics, and competitive programming.

Fundamental Concepts

Bit Manipulation Techniques

int count = 0;
while (number) {
    number &= (number - 1);
    count++;
}

This works by repeatedly clearing the LSB and incrementing the count.

a ^= b;
b ^= a;
a ^= b;

This sequence of XOR operations swaps the values of a and b without needing extra space.

Bit Masks

Bit Shifting Tricks

Cautions and Best Practices

List of problems

Minimum deletions to make valid parentheses

Given a string of parentheses, determine the minimum number of parentheses that need to be removed to make the string valid. This can be solved using a stack data structure to track the open parentheses as we iterate through the string. If we encounter an open parenthesis, we add it to the stack. If we encounter a closing parenthesis, we check if there is a matching open parenthesis on the top of the stack. If there is, we pop the open parenthesis from the stack. If there is not, we add the closing parenthesis to a list of characters to remove. After we have processed the entire string, we remove the remaining open parentheses from the stack.

Is palindrome after at most one char delete?

Determinine whether a string can be transformed into a palindrome by deleting at most one character. This can be solved using a two pointer approach, where we start from both ends of the string and move towards the middle. If we encounter a pair of characters that are not equal, we have three options: delete the character at the left pointer, delete the character at the right pointer, or delete both characters. We check if any of these options results in a palindrome and return the result.

K closest points to origin

Find the K points in a list of points that are closest to the origin (0, 0). This can be solved using a min heap data structure, where we store the K closest points so far. As we iterate through the list of points, we compute the distance from each point to the origin and add it to the heap if it is among the K closest points so far.

Subarray sum equals K

Find a contiguous subarray of an array that has a sum of K. This can be solved using a sliding window approach, where we maintain a running sum of the elements in the window and move the window through the array until we find a subarray with the desired sum.

Add numbers given as strings

Add two numbers represented as strings. This can be solved by treating the strings as arrays of digits and using a carry variable to keep track of the carryover from one place value to the next.

Dot product of two sparse vectors

Compute the dot product of two sparse vectors, where a vector is represented as a list of (index, value) pairs. This can be solved by iterating through both vectors and adding up the products of the values at the same index.

Range sum of BST

Compute the sum of the values of all the nodes in a binary search tree within a given range. This can be solved using a recursive in-order traversal of the tree, where we add the value of each node to the sum if it is within the range.

Product of array except self

Compute an array where each element is the product of all the other elements in the input array. This can be solved using two pass approach, where we first compute the product of all the elements before each index and then compute the product of all the elements after each index.

Convert BST to sorted doubly linked list

Convert a binary search tree to a sorted doubly linked list. This can be solved using a recursive in-order traversal of the tree, where we build the linked list by adding each node to the end of the list as we visit it.

Lowest common ancestor of a binary tree

Find the lowest common ancestor (LCA) of two nodes in a binary tree. The LCA is the node in the tree that is the ancestor of both nodes and is the deepest node in the tree. To solve this problem, you can use a variety of techniques such as traversing the tree in a depth-first or breadth-first manner, or using a recursive approach to traverse the tree and find the LCA. You can also use a divide and conquer approach, where you split the tree into left and right subtrees and find the LCA in each subtree. Another approach is to use a hash table or a map to store the ancestors of each node and then use this information to find the LCA.

LRU Cache

Designing a cache data structure that stores a limited number of items and removes the least recently used items when the capacity is reached. This can be solved using a doubly linked list and a hash table. The doubly linked list is used to store the items in the cache in the order in which they were accessed, with the most recently accessed item at the front of the list and the least recently accessed item at the back. The hash table is used to store the keys and values of the items in the cache and to quickly retrieve items from the cache based on their keys.

Randomize An Array

Shuffle the elements of an array randomly. This can be solved using a random number generator and a Fisher-Yates shuffle algorithm. The Fisher-Yates shuffle algorithm works by starting at the end of the array and randomly swapping each element with an element preceding it. This results in a randomly shuffled array.

Binary Tree Right Side View

Given a binary tree, return an array containing the values of the nodes on the right side of the tree, when viewed from the right. One way to solve this problem might be to perform a breadth-first search on the tree, keeping track of the maximum depth of each node as it is visited. When visiting a node at a particular depth for the first time, add its value to the result array.

Design Browser History

Implement a browser history system that supports the following operations: visit a URL, go back to the previous URL, and go forward to the next URL. One potential approach to this problem could involve using a doubly-linked list to store the URLs visited, with a pointer to the current URL. Going back or forward would simply involve moving the pointer to the previous or next URL in the list.

Score After Flipping Matrix

Given a matrix of 0s and 1s, flip the rows and columns of the matrix such that the maximum possible score is achieved. The score is calculated as the number of 1s in the matrix. One way to solve this problem might be to use dynamic programming to compute the maximum score for each submatrix of the original matrix, taking into account whether the rows and columns of the submatrix should be flipped.

Table of Contents

    Solving Programming Brain Teasers
    1. General Strategies
    2. Data Structures
      1. Working with Arrays
      2. Working with Strings
      3. Working with Linked Lists
      4. Working with Trees and Binary Trees
      5. Working with Graphs
      6. Working with Hash Tables
    3. Algorithms
      1. Two-Pointer Technique
      2. Recursion
      3. Backtracking
      4. Dynamic Programming
    4. Greedy Algorithms
      1. Divide and Conquer
      2. Graph Algorithms
    5. Sorting Algorithms
      1. Overview of Common Sorting Algorithms
      2. General Tips for Sorting Algorithms
      3. Practical Applications
    6. Bit Manipulation
      1. Fundamental Concepts
      2. Bit Manipulation Techniques
      3. Bit Masks
      4. Bit Shifting Tricks
      5. Cautions and Best Practices
    7. List of problems
      1. Minimum deletions to make valid parentheses
      2. Is palindrome after at most one char delete?
      3. K closest points to origin
      4. Subarray sum equals K
      5. Add numbers given as strings
      6. Dot product of two sparse vectors
      7. Range sum of BST
      8. Product of array except self
      9. Convert BST to sorted doubly linked list
      10. Lowest common ancestor of a binary tree
      11. LRU Cache
      12. Randomize An Array
      13. Binary Tree Right Side View
      14. Design Browser History
      15. Score After Flipping Matrix