Essential Coding and System Design Problems
These problems help building foundation for solving difficult problems
"Cracking the Coding Interview" by Gayle Laakmann McDowell is a comprehensive resource for preparing for technical interviews, particularly for software engineering roles. The book covers a wide range of topics, including data structures, algorithms, system design, and more. Below is a list of the **technical questions** categorized by chapter.
Note that this is a high-level overview, and the book contains detailed explanations, solutions, and variations for each question.
Chapter 1: Arrays and Strings
Is Unique: Implement an algorithm to determine if a string has all unique characters (e.g., "abcdef" → true, "hello" → false).
Check Permutation: Given two strings, decide if one is a permutation of the other (e.g., "abc" and "bca" → true, "abc" and "def" → false).
URLify: Replace all spaces in a string with '%20' (e.g., "Mr John Smith" → "Mr%20John%20Smith").
Palindrome Permutation: Check if a string is a permutation of a palindrome (e.g., "taco cat" → true, "hello" → false).
One Away: Check if two strings are one edit (or zero edits) away (e.g., "pale", "ple" → true; "pale", "bake" → false).
String Compression: Compress a string using counts of repeated characters (e.g., "aabcccccaaa" → "a2b1c5a3").
Rotate Matrix: Rotate an NxN matrix by 90 degrees (e.g., input matrix [[1,2], [3,4]] → [[3,1], [4,2]]).
Zero Matrix: Write an algorithm to set entire rows and columns to zero if an element is zero (e.g., input [[1,0,3],[4,5,6]] → output [[0,0,0],[4,0,6]]).
String Rotation: Check if one string is a rotation of another using only one call to a substring function (e.g., "waterbottle" and "erbottlewat" → true).
Chapter 2: Linked Lists
Remove Dups: Remove duplicates from an unsorted linked list (e.g., 1 → 2 → 2 → 3 → 4 → 4 → 5 → 1 → 2 → 3 becomes 1 → 2 → 3 → 4 → 5).
Return Kth to Last: Find the kth to last element of a singly linked list (e.g., for list 1 → 2 → 3 → 4 → 5, k=2 returns 4).
Delete Middle Node: Delete a node in the middle of a singly linked list (e.g., deleting 'c' from a → b → c → d → e results in a → b → d → e).
Partition: Partition a linked list around a value x (e.g., input 3 → 5 → 8 → 5 → 10 → 2 → 1 with x=5 becomes 3 → 2 → 1 → 5 → 8 → 5 → 10).
Sum Lists: Add two numbers represented by linked lists (e.g., (7 → 1 → 6) + (5 → 9 → 2) represents 617 + 295 = 912 → (2 → 1 → 9)).
Palindrome: Check if a linked list is a palindrome (e.g., 1 → 2 → 3 → 2 → 1 → true, 1 → 2 → 3 → false).
Intersection: Find the intersection point of two linked lists.
Loop Detection: Detect if a linked list has a loop and return the node at the start of the loop.
Chapter 3: Stacks and Queues
Three in One: Implement three stacks using a single array.
Stack Min: Design a stack that supports push, pop, and min operations in O(1) time.
Stack of Plates: Implement a data structure that mimics a stack of plates.
Queue via Stacks: Implement a queue using two stacks.
Sort Stack: Sort a stack using only one additional stack (e.g., input [3,1,4,2] → output [1,2,3,4]).
Animal Shelter: Design a queue system for an animal shelter, where adoption is FIFO by species.
Chapter 4: Trees and Graphs
Route Between Nodes: Determine if there is a path between two nodes in a directed graph.
Minimal Tree: Create a binary search tree with minimal height from a sorted array.
List of Depths: Create a linked list of all nodes at each depth of a binary tree.
Check Balanced: Check if a binary tree is balanced.
Validate BST: Check if a binary tree is a valid binary search tree.
Successor: Find the "next" node of a given node in a binary search tree.
Build Order: Determine a build order for projects with dependencies.
First Common Ancestor: Find the first common ancestor of two nodes in a binary tree.
Chapter 5: Bit Manipulation
Insertion: Insert one number into another at a specific bit position.
Binary to String: Convert a real number between 0 and 1 to a binary string.
Flip Bit to Win: Find the longest sequence of 1s you can create by flipping one bit (e.g., "11011101111" → 8 by flipping one 0).
Next Number: Find the next smallest and largest numbers with the same number of 1s in binary.
Debugger: Explain what the code
((n & (n-1)) == 0)does (checks if n is a power of 2).Conversion: Determine the number of bits you need to flip to convert one integer to another (e.g., 29 → 15 (11101 → 01111), output: 2 bits).
Chapter 6: Math and Logic Puzzles
The Heavy Pill: Identify the bottle with heavy pills using a scale once (e.g., weigh pills strategically to find the heavier one).
Basketball: Calculate the probability of winning a game of basketball (e.g., given probabilities of making shots, determine win chances).
Dominos: Determine if a chessboard with two corners removed can be covered with dominos (e.g., prove why it's impossible).
Ants on a Triangle: Calculate the probability of ants colliding on a triangle (e.g., ants randomly moving along edges).
Jugs of Water: Measure a specific amount of water using jugs of different sizes (e.g., 3L and 5L jugs to get 4L).
Blue-Eyed Island: Determine when all blue-eyed people will leave the island (e.g., logical deduction of observations).
The Apocalypse: Calculate the gender ratio of a post-apocalyptic world (e.g., families keep having kids until a boy is born).
The Egg Drop Problem: Determine the highest floor an egg can be dropped from without breaking (e.g., minimize worst-case drops).
100 Lockers: Determine how many lockers remain open after toggling (e.g., lockers toggled in a perfect square pattern stay open).
Poison: Identify the poisoned bottle using test strips (e.g., use binary representation for efficient testing).
Chapter 7: Object-Oriented Design
Deck of Cards: Design a deck of cards (e.g., classes for Card, Deck, and Suit).
Call Center: Design a call center system (e.g., employee levels with escalating call handling).
Jukebox: Design a jukebox (e.g., classes for Song, Playlist, and User interactions).
Parking Lot: Design a parking lot (e.g., manage vehicle types, availability, and fees).
Online Book Reader: Design an online book reader (e.g., track users, bookmarks, and book availability).
Jigsaw: Design a jigsaw puzzle (e.g., piece placement logic and edge matching).
Chat Server: Design a chat server (e.g., user authentication, messaging, and groups).
Othello: Design the game Othello (e.g., implement game rules and board mechanics).
Circular Array: Implement a circular array class (e.g., wrap-around indexing for efficiency).
Minesweeper: Design the game Minesweeper (e.g., board generation and reveal logic).
File System: Design a file system (e.g., directories, files, and permissions structure).
Hash Table: Design a hash table (e.g., implement collision handling strategies like chaining).
Chapter 8: Recursion and Dynamic Programming
Triple Step: Count the number of ways to climb stairs (e.g., 1, 2, or 3 steps at a time).
Robot in a Grid: Find a path for a robot in a grid (e.g., avoiding obstacles using recursion).
Magic Index: Find a magic index in a sorted array (e.g., A[i] == i).
Power Set: Generate all subsets of a set (e.g., recursively add elements).
Recursive Multiply: Multiply two numbers without using the * operator (e.g., repeated addition).
Towers of Hanoi: Solve the Towers of Hanoi problem (e.g., recursive disk movement strategy).
Permutations without Dups: Generate all permutations of a string with unique characters (e.g., swap characters recursively).
Permutations with Dups: Generate all permutations of a string with duplicate characters (e.g., track used elements to avoid duplicates).
Parens: Generate all valid combinations of n pairs of parentheses (e.g., backtracking approach).
Paint Fill: Implement a paint fill function (e.g., similar to the bucket tool in MS Paint).
Coins: Calculate the number of ways to represent n cents using coins (e.g., dynamic programming solution).
Eight Queens: Place eight queens on a chessboard without them attacking each other (e.g., backtracking approach).
Stack of Boxes: Calculate the tallest stack of boxes (e.g., sort by base area and apply dynamic programming).
Boolean Evaluation: Count the number of ways to parenthesize a boolean expression to evaluate to true (e.g., dynamic programming with memoization).
Chapter 9: System Design and Scalability
Stock Data: Design a system to store and retrieve stock data (e.g., optimize for fast queries).
Social Network: Design a social network (e.g., friend relationships, news feed, and messaging).
Web Crawler: Design a web crawler (e.g., efficiently explore and store web pages).
Duplicate URLs: Design a system to detect duplicate URLs (e.g., hashing for quick lookup).
Cache: Design a cache system (e.g., implement LRU cache for efficiency).
Sales Rank: Design a system to track sales ranks (e.g., maintain product popularity rankings in real-time).
Personal Financial Manager: Design a personal financial manager (e.g., budget tracking, transactions, and reports).
Pastebin: Design a pastebin-like system (e.g., store and retrieve text snippets with expiration support).
Chapter 10: Sorting and Searching
Sorted Merge: Merge two sorted arrays into a single sorted array.
Group Anagrams: Sort an array of strings such that anagrams are grouped together.
Search in Rotated Array: Search for an element in a rotated sorted array.
Sorted Search, No Size: How would you search for an element in a sorted array with unknown size?
Sparse Search: Search for a string in an array with sparse (missing) values.
Sort Big File: Sort a large file containing integers that can’t fit into memory.
Missing Int: Find the smallest missing integer in a file of 4 billion non-negative integers.
Find Duplicates: How can you find duplicates in an unsorted array of integers?
Sorted Matrix Search: Search for a target value in a sorted MxN matrix.
Rank from Stream: Track the rank of each number as it appears in a stream of numbers.
Peaks and Valleys: Reorganize an array into peaks and valleys (higher values between lower ones).
Chapter 11: Testing
Mistake: Identify and fix the error in a provided piece of code.
Random Crashes: How would you debug a system that crashes randomly?
Chess Test: How would you test the functionality of a chess game?
No Test Tools: Test a pen without using any external testing tools.
Test an ATM: How would you design tests for an ATM machine?
Chapter 12: C and C++
Private Constructor: What is the purpose of a private constructor in C++?
Virtual Functions: Explain how virtual functions enable dynamic method dispatch in C++.
Shallow vs Deep Copy: What is the difference between a shallow and a deep copy?
Volatile Keyword: What does the
volatilekeyword do in C, and why is it used?Virtual Base Class: Why would you use a virtual base class in C++?
Copy Node: Write a function to create a deep copy of a node in a linked list.
Template vs Generics: How do C++ templates differ from Java generics?
Chapter 14: Databases
Denormalization: What is denormalization, and when is it useful?
Joins: Explain the different types of SQL joins and when to use each.
Denormalized vs Normalized: What are the advantages and disadvantages of denormalized versus normalized databases?
Draw an E-R Diagram: Design an Entity-Relationship diagram for a given scenario (e.g., university database).
Design a Grade Database: Design a database schema to store student grades and course information.
Write a Query: Write SQL queries to solve common database problems (e.g., find top 10 students).
Chapter 15: Threads and Locks
Thread vs Process: What is the difference between a thread and a process?
Context Switching: What is context switching, and why is it important in multi-threading?
Dining Philosophers: How would you solve the dining philosophers problem using synchronization?
Deadlock-Free Class: Design a class that guarantees no deadlock while using locks.
Call In Order: How would you ensure that three threads call methods in a specific order?
Synchronized Methods: Explain how synchronized methods work in multi-threaded programming (e.g., Java, Python).
FizzBuzz: Implement the FizzBuzz problem using threads for concurrent processing.
This list provides a comprehensive overview of the technical questions in "Cracking the Coding Interview." For detailed solutions and explanations, refer to the book itself.