CTCI

A repository containing my C++ solutions for various Cracking the Coding Interview (6th ed) problems. You can find other suggested solutions on CareerCup's GitHub page.

Problem Table

• _ unsolved
• V solved, pen and paper (no code) (✓)
• V+ solved, code available (C++) (✓+)
• X try again (✗)
• - (code improvable)

Note: Not all of the solved problems have accompanying code, depending on the exercise. Solutions are not heavility tested and might contain errors. Usually, one or multiple functions solve the problem, whereas the main() function builds one or more testcases to show that the function works.

	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1. Arr	V+	V+	V+	V+	V+	V+	V+	V+	V+
2. LL	_	_	_	_	_	_	_	_
3. S,Q	_	_	_	_	_	_
4. T,G	_	_	_	_	_	_	_	_	_	_	_	_
5. Bit	V+	V+	V+	X	V	V+	V+	X+
6. Math	V	V	V	V	V	V	V+	V	V	_
7. OO	V	V	V	_	_	_	_	_	_	_	_	_
8. R,DP	V+	V+	V-	V+	V+	V+	V+	V+	V+	_	V+	_	_	_
9. Sca	_	_	_	_	_	_	_	_
10. S,S	_	_	_	_	_	_	_	_	_	_	_
11. Test	V	V	V	V	_	_
12. C++	V	V	V	V	V	V	V	_	_	_	_
13. Java	_	_	_	_	_	_	_	_
14. DB	V-	V-	V-	V	V	V	V-
15. Thr	_	_	_	_	_	_	_
16. Med	V+	X+	_	V+	V+	V+	V+	V+	V+	V+	V+	_	_
	_	V+	_	_	_	_	V+	V+	_	V+	V+	_	V+
17. Hard	V+	V+	V+	V-	V+	V+	V+	V-	V+	V	_	_	_
	_	_	V+	_	V+	V+	V+	V+	V+	_	_	_	_

Progress:

(86/189) [#########-----------] 45%

Problem List

1. Arrays and Strings

• 1.1 Is Unique
• 1.2 Check Permuation
• 1.3 URLify
• 1.4 Palindrome Permutation
• 1.5 One Away
• 1.6 String Compression
• 1.7 Rotate Matrix
• 1.8 Zero Matrix
• 1.9 String Rotation

2. Linked Lists

• 2.1 Remove Dups
• 2.2 Return Kth to Last
• 2.3 Delete Middle Node
• 2.4 Partition
• 2.5 Sum Lists
• 2.6 Palindrome
• 2.7 Intersection
• 2.8 Loop Detection

3. Stacks and Queues

• 3.1 Three in One
• 3.2 Stack Min
• 3.3. Stack of Plates
• 3.4 Queue via Stacks
• 3.5 Sort Stack
• 3.6 Animal Shelter

4. Trees and Graphs

• 4.1 Route Between Nodes
• 4.2 Minimal Tree
• 4.3 List of Depths
• 4.4 Check Balanced
• 4.5 Validate BST
• 4.6 Successor
• 4.7 Build Order
• 4.8 First Common Ancestor
• 4.9 BST Sequences
• 4.10 Check Subtree
• 4.11 Random Node
• 4.12 Paths with Sum

5. Bit Manipulation

• 5.1 Insertion
• 5.2 Binary to String
• 5.3 Flip Bit to Win
• 5.4 Next Number
• 5.5 Debugger
• 5.6 Conversion
• 5.7 Pairwise Swap
• 5.8 Draw Line

6. Math and Logic Puzzles

• 6.1 The Heavy Pill
• 6.2 Basketball
• 6.3 Dominos
• 6.4 Ants on a Triangle
• 6.5 Jugs of Water
• 6.6 Blue-Eyed Island
• 6.7 The Apocalypse
• 6.8 The Egg Drop Problem
• 6.9 100 Lockers
• 6.10 Poison

7. Object-Oriented Design

• 7.1 Deck of Cards
• 7.2 Call Center
• 7.3 Jukebox
• 7.4 Parking Lot
• 7.5 Online Book Reader
• 7.6 Jigsaw
• 7.7 Chat Server
• 7.8 Othello
• 7.9 Circular Array
• 7.10 Minesweeper
• 7.11 File System
• 7.12 Hash Table

8. Recursion and Dynamic Programming

• 8.1 Triple Step
• 8.2 Robot in a Grid
• 8.3 Magic Index
• 8.4 Power Set
• 8.5 Recursive Multiply
• 8.6 Towers of Hanoi
• 8.7 Permutations without Dups
• 8.8 Permutations with Dups
• 8.9 Parens
• 8.10 Paint Fill
• 8.11 Coins
• 8.12 Eight Queens
• 8.13 Stack of Boxes
• 8.14 Boolean Evaluation

9. System Design and Scalability

• 9.1 Stock Data
• 9.2 Social Network
• 9.3 Web Crawler
• 9.4 Duplicate URLs
• 9.5 Cache
• 9.6 Sales Rank
• 9.7 Personal Financial Manager
• 9.8 Pastebin

10. Sorting and Searching

• 10.1 Sorted Merge
• 10.2 Group Anagrams
• 10.3 Search in Rotated Array
• 10.4 Sorted Search, No Size
• 10.5 Sparse Search
• 10.6 Sort Big File
• 10.7 Missing Int
• 10.8 Find Duplicates
• 10.9 Sorted Matrix Search
• 10.10 Rank from Stream
• 10.11 Peaks and Valleys

11. Testing

• 11.1 Mistake
• 11.2 Random Crashes
• 11.3 ChessTest
• 11.4 No Test Tools
• 11.5 Test a Pen
• 11.6 Test an ATM

12. C and C++

• 12.1 Last K Lines
• 12.2 Reverse String
• 12.3 Hash Table vs. STL Map
• 12.4 Virtual Functions
• 12.5 Shallow vs. Deep Copy
• 12.6 Volatile
• 12.7 Virtual Base Class
• 12.8 Copy Node
• 12.9 Smart Pointer
• 12.10 Malloc
• 12.11 20 Alloc

13. Java

• 13.1 Private Constructor
• 13.2 Return from Finally
• 13.3 Final, etc.
• 13.4 Generics vs. Templates
• 13.5 TreeMap, HashMap, LinkedHashMap
• 13.6 Object Reflection
• 13.7 Lambda Expressions
• 13.8 Lambda Random

14. Databases

• 14.1 Multiple Apartments
• 14.2 Open Requests
• 14.3 Close All Requests
• 14.4 Joins
• 14.5 Denormalization
• 14.6 Entity-Relationship Diagram
• 14.7 Design Grade Database

15. Threads and Locks

• 15.1 Thread vs. Process
• 15.2 Context Switch
• 15.3 Dining Philosophers
• 15.4 Deadlock-Free Class
• 15.5 Call In Order
• 15.6 Synchronized Methods
• 15.7 FizzBuzz

16. Moderate

• 16.1 Number Swapper
• 16.2 Word Frequencies
• 16.3 Intersection
• 16.4 Tic Tac Win
• 16.5 Factorial Zeros
• 16.6 Smallest Difference
• 16.7 Number Max
• 16.8 English Int
• 16.9 Operations
• 16.10 Living People
• 16.11 Diving Board
• 16.12 XML Encoding
• 16.13 Bisect Squares
• 16.14 Best Line
• 16.15 Master Mind
• 16.16 Sub Sort
• 16.17 Contiguous Sequence
• 16.18 Pattern Matching
• 16.19 Pond Sizes
• 16.20 T9
• 16.21 Sum Swap
• 16.22 Langton's Ant
• 16.23 Rand7 from Rands
• 16.24 Pairs with Sum
• 16.25 LRU Cache
• 16.26 Calculator

17. Hard

• 17.1 Add Without Plus
• 17.2 Shuffle
• 17.3 Random Set
• 17.4 Missing Number
• 17.5 Letters and Numbers
• 17.6 Count of 2s
• 17.7 Baby Names
• 17.8 Circus Tower
• 17.9 Kth Multiple
• 17.10 Majority Element
• 17.11 Word Distance
• 17.12 BiNode
• 17.13 Re-Space
• 17.14 Smallest K
• 17.15 Longest Word
• 17.16 The Masseuse
• 17.17 Multi Search
• 17.18 Shortest Supersequence
• 17.19 Missing Two
• 17.20 Continuous Median
• 17.21 Volume of Histogram
• 17.22 Word Transformer
• 17.23 Max Black Square
• 17.24 Max Submatrix
• 17.25 Word Rectangle
• 17.26 Sparse Similarity