rigwild/code-challenges

Cracking The Coding Interview - Book progress

rigwild opened this issue · 1 comments

rigwild commented

  • I. The Interview Process .......................... 4

    • Why? .......................... 4
    • How Questions are Selected .......................... 6
    • It's All Relative .......................... 7
    • Frequently Asked Questions .......................... 7

  • II. Behind the Scenes .......................... 8

    • The Microsoft Interview .......................... 9
    • The Amazon Intervie .......................... 10
    • The Google Interview .......................... 10
    • The Apple Interview .......................... 11
    • The Facebook Interview .......................... 12
    • The Palantir Interview .......................... 13

  • III. Special Situations .......................... 15

    • Experienced Candidates.......................... 15
    • Testers and SDETs .......................... 15
    • Product (and Program) Management .......................... 16
    • Dev Lead and Managers .......................... 17
    • Startups .......................... 18
    • Acquisitions and Acquihires .......................... 19
    • For Interviewers .......................... 21

  • IV. Before the Interview .......................... 26

    • Getting the Right Experience .......................... 26
    • Writing a Great Resum .......................... 27
    • Preparation Map .......................... 30

  • V. Behavioral Questions .......................... 32

    • Interview Preparation Grid .......................... 32
    • Know Your Technical Project .......................... 33
    • Responding to Behavioral Question .......................... 34
    • So, tell me about yourself.......................... 36

  • VI. BigO .......................... 38

    • An Analog .......................... 38
    • Time Complexit .......................... 38
    • Space Complexit .......................... 40
    • Drop the Constants .......................... 41
    • Drop the Non-Dominant Terms .......................... 42
    • Multi-Part Algorithms: Add vs. Multiply .......................... 42
    • Amortized Time .......................... 43
    • Log N Runtimes 0 .......................... 44
    • Recursive Runtimes .......................... 44
    • Examples and Exercises .......................... 45

  • VII. Technical Questions .......................... 60

    • How to Prepare .......................... 60
    • What You Need To Know .......................... 60
    • Walking Through a Problem .......................... 62
    • Optimize & Solve Technique # 1 : Look for BUD .......................... 67
    • Optimize & Solve Technique # 2: DIY (Do It Yourself) .......................... 69
    • Optimize & Solve Technique # 3: Simplify and Generalize .......................... 71
    • Optimize & Solve Technique # 4: Base Case and Build .......................... 71
    • Optimize & Solve Technique # 5: Data Structure Brainstorm .......................... 72
    • Best Conceivable Runtime (BCR) 0 .......................... 72
    • Handling Incorrect Answers .......................... 76
    • When You've Heard a Question Before .......................... 76
    • The "Perfect" Language for Interviews .......................... 76
    • What Good Coding Looks Like .......................... 77
    • Don't Give Up! .......................... 81

  • VIII. The Offer and Beyond .......................... 82

    • Handling Offers and Rejection .......................... 82
    • Evaluating the Offer .......................... 83
    • Negotiation .......................... 84
    • On the Job .......................... 85

  • IX. Interview Questions .......................... 87

  • Chapter 1 | Arrays and Strings .......................... 88

    • Hash Tables .......................... 88
    • ArrayList & Resizable Arrays .......................... 89
    • String Builder .......................... 89
    • 1.1 Is Unique
    • 1.2 Check Permutation
    • 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

  • Chapter 2 | Linked Lists .......................... 92

    • Creating a Linked List .......................... 92
    • Deleting a Node from a Singly Linked List .......................... 93
    • The "Runner" Technique .......................... 93
    • Recursive Problems .......................... 93
    • 2.1 Remove Dups
    • 2.2 Return Kth to Last
    • 2.3 Delete Middle Node
    • 2.4 Partition
    • 2.S Sum Lists
    • 2.6 Palindrome
    • 2.7 Intersection
    • 2.8 Loop Detection

  • Chapter 3 | Stacks and Queue .......................... 96

    • Implementing a Stack .......................... 96
    • Implementing a Queue .......................... 97
    • 3.1 Three in One
    • 3.2 Stack Min
    • 3.3 Stack of Plates
    • 3.4 Queue via Stacks
    • 3.S Sort Stack
    • 3.6 Animal Shelter

  • Chapter 4 | Trees and Graphs .......................... 100

    • Types of Trees .......................... 100
    • Binary Tree Traversal .......................... 103
    • Binary Heaps (Min-Heaps and Max-Heaps) .......................... 103
    • Tries (Prefix Trees) .......................... 105
    • Graphs .......................... 105
    • Graph Search .......................... 107
    • Concepts and Algorithms .......................... 112
    • 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

  • Chapter 5 | Bit Manipulation .......................... 112

    • Bit Manipulation By Hand .......................... 112
    • Bit Facts and Tricks .......................... 112
    • Two's Complement and Negative Numbers .......................... 113
    • Arithmetic vs. Logical Right Shift.......................... 113
    • Common Bit Tasks: Getting and Setting .......................... 114
    • 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

  • Chapter 6 | Math and Logic Puzzles .......................... 117

    • Prime Numbers .......................... 117
    • Probability .......................... 119
    • Start Talking .......................... 121
    • Develop Rules and Patterns .......................... 121
    • Worst Case Shifting .......................... 122
    • Algorithm Approaches .......................... 122
    • 6.1 The Heavy Pill
    • 6.2 Basketball
    • 6.3 Dominos
    • 6.4 Ants on a Triangle
    • 6.6 Blue-Eyed Island
    • 6.7 The Apocalypse
    • 6.8 The Egg Drop Problem
    • 6.9 100 Lockers
    • 6.10 Poison

  • Chapter 7 | Object-Oriented Design .......................... 125

    • How to Approach .......................... 125
    • Design Patterns .......................... 126
    • 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

  • Chapter 8 | Recursion and Dynamic Programming .......................... 130

    • How to Approach .......................... 130
    • Recursive vs. lterative Solutions .......................... 131
    • Dynamic Programming & Memoization .......................... 131
    • 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

  • Chapter 9 | System Design and Scalability .......................... 137

    • Handling the Questions .......................... 137
    • Design: Step-By-Step .......................... 138
    • Algorithms that Scale: Step-By-Step .......................... 139
    • Key Concepts .......................... 140
    • Considerations .......................... 142
    • There is no "perfect" system .......................... 143
    • Example Problem .......................... 143
    • 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

  • Chapter 10 | Sorting and Searching .......................... 146

    • Common Sorting Algorithms .......................... 146
    • Searching Algorithms .......................... 149
    • 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

  • Chapter 11 | Testing .......................... 152

    • What the Interviewer Is Looking For .......................... 152
    • Testing a Real World Object .......................... 153
    • Testing a Piece of Software .......................... 154
    • Testing a Function .......................... 155
    • Troubleshooting Questions .......................... 156
    • Knowledge Based .......................... 158
    • 11.1 Mistake
    • 11.2 Random Crashes
    • 11.3 Chess Test
    • 11.4 No Test Tools
    • 11.5 Test a Pen
    • 11.6 Test an ATM

  • Chapter 12 | C and C++ .......................... 158

    • Classes and Inheritance .......................... 58
    • Constructors and Destructors .......................... 159
    • Virtual Functions .......................... 159
    • Virtual Destructor .......................... 160
    • Default Values .......................... 161
    • Operator Overloading .......................... 161
    • Pointers and References .......................... 162
    • Templates .......................... 163
    • 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

  • Chapter 13 | Java .......................... 165

    • How to Approach .......................... 165
    • Overloading vs. Overriding .......................... 165
    • Collection Framework .......................... 166
    • 13.1 Private Constructor
    • 13.2 Return from Finally
    • 13.3 Final, etc.
    • 13.4 Generics vs. Templates
    • 13.6 Object Reflection
    • 13.7 Lambda Expressions
    • 13.8 Lambda Random

  • Chapter 14 | Databases .......................... 169

    • SQL Syntax and Variations .......................... 169
    • Denormalized vs. Normalized Databases .......................... 169
    • SQL Statements .......................... 169
    • Small Database Design .......................... 171
    • Large Database Design .......................... 172
    • 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

  • Chapter 15 | Threads and Locks .......................... 174

    • Threads in Java .......................... 174
    • Synchronization and Locks .......................... 176
    • Deadlocks and Deadlock Prevention .......................... 179
    • 15.3 Dining Philosophers
    • 15.4 Deadlock-Free Class
    • 15.5 Call In Order
    • 15.6 Synchronized Methods
    • 15.7 FizzBuzz

  • Additional Review Problems .......................... 181

    • Chapter 16 | Moderate .......................... 181
      • 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.26 Calculator
    • Chapter 17 | Hard .......................... 186
      • 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 25
      • 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

  • XI. Advanced Topics .......................... 628

    • Useful Math .......................... 629
    • Topological Sort .......................... 632
    • Dijkstra's Algorithm .......................... 633
    • Hash Table Collision Resolution .......................... 636
    • Rabin-Karp Substring Search .......................... 636
    • AVL Trees .......................... 637
    • Red-Black Trees .......................... 639
    • MapReduce .......................... 642
    • Additional Studying .......................... 644

  • XII. Code Library .......................... 645

    • HashMapList<T. E> .......................... 646
    • TreeNode (Binary Search Tree) .......................... 647
    • LinkedListNode (Linked List) .......................... 649
    • Trie & TrieNode .......................... 649