rigwild / code-challenges Goto Github PK

Cracking The Coding Interview book: #2

Curated List of Top 75 LeetCode Questions progress
Link: https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-100-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

Array

• Two Sum - https://leetcode.com/problems/two-sum/
• Best Time to Buy and Sell Stock - https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
• Contains Duplicate - https://leetcode.com/problems/contains-duplicate/
• Product of Array Except Self - https://leetcode.com/problems/product-of-array-except-self/
• Maximum Subarray - https://leetcode.com/problems/maximum-subarray/
• Maximum Product Subarray - https://leetcode.com/problems/maximum-product-subarray/
• Find Minimum in Rotated Sorted Array - https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
• Search in Rotated Sorted Array - https://leetcode.com/problems/search-in-rotated-sorted-array/
• 3Sum - https://leetcode.com/problems/3sum/
• Container With Most Water - https://leetcode.com/problems/container-with-most-water/

Binary

• Sum of Two Integers - https://leetcode.com/problems/sum-of-two-integers/
• Number of 1 Bits - https://leetcode.com/problems/number-of-1-bits/
• Counting Bits - https://leetcode.com/problems/counting-bits/
• Missing Number - https://leetcode.com/problems/missing-number/
• Reverse Bits - https://leetcode.com/problems/reverse-bits/

Dynamic Programming

• Climbing Stairs - https://leetcode.com/problems/climbing-stairs/
• Coin Change - https://leetcode.com/problems/coin-change/
• Longest Increasing Subsequence - https://leetcode.com/problems/longest-increasing-subsequence/
• Longest Common Subsequence - https://leetcode.com/problems/longest-common-subsequence/
• Word Break Problem - https://leetcode.com/problems/word-break/
• Combination Sum - https://leetcode.com/problems/combination-sum-iv/
• House Robber - https://leetcode.com/problems/house-robber/
• House Robber II - https://leetcode.com/problems/house-robber-ii/
• Decode Ways - https://leetcode.com/problems/decode-ways/
• Unique Paths - https://leetcode.com/problems/unique-paths/
• Jump Game - https://leetcode.com/problems/jump-game/

Graph

• Clone Graph - https://leetcode.com/problems/clone-graph/
• Course Schedule - https://leetcode.com/problems/course-schedule/
• Pacific Atlantic Water Flow - https://leetcode.com/problems/pacific-atlantic-water-flow/
• Number of Islands - https://leetcode.com/problems/number-of-islands/
• Longest Consecutive Sequence - https://leetcode.com/problems/longest-consecutive-sequence/
• Alien Dictionary (Leetcode Premium) - https://leetcode.com/problems/alien-dictionary/
• Graph Valid Tree (Leetcode Premium) - https://leetcode.com/problems/graph-valid-tree/
• Number of Connected Components in an Undirected Graph (Leetcode Premium) - https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

Interval

• Insert Interval - https://leetcode.com/problems/insert-interval/
• Merge Intervals - https://leetcode.com/problems/merge-intervals/
• Non-overlapping Intervals - https://leetcode.com/problems/non-overlapping-intervals/
• Meeting Rooms (Leetcode Premium) - https://leetcode.com/problems/meeting-rooms/
• Meeting Rooms II (Leetcode Premium) - https://leetcode.com/problems/meeting-rooms-ii/

Linked List

• Reverse a Linked List - https://leetcode.com/problems/reverse-linked-list/
• Detect Cycle in a Linked List - https://leetcode.com/problems/linked-list-cycle/
• Merge Two Sorted Lists - https://leetcode.com/problems/merge-two-sorted-lists/
• Merge K Sorted Lists - https://leetcode.com/problems/merge-k-sorted-lists/
• Remove Nth Node From End Of List - https://leetcode.com/problems/remove-nth-node-from-end-of-list/
• Reorder List - https://leetcode.com/problems/reorder-list/

Matrix

• Set Matrix Zeroes - https://leetcode.com/problems/set-matrix-zeroes/
• Spiral Matrix - https://leetcode.com/problems/spiral-matrix/
• Rotate Image - https://leetcode.com/problems/rotate-image/
• Word Search - https://leetcode.com/problems/word-search/

String

• Longest Substring Without Repeating Characters - https://leetcode.com/problems/longest-substring-without-repeating-characters/
• [-] Longest Repeating Character Replacement - https://leetcode.com/problems/longest-repeating-character-replacement/
• Minimum Window Substring - https://leetcode.com/problems/minimum-window-substring/
• Valid Anagram - https://leetcode.com/problems/valid-anagram/
• Group Anagrams - https://leetcode.com/problems/group-anagrams/
• Valid Parentheses - https://leetcode.com/problems/valid-parentheses/
• Valid Palindrome - https://leetcode.com/problems/valid-palindrome/
• Longest Palindromic Substring - https://leetcode.com/problems/longest-palindromic-substring/
• Palindromic Substrings - https://leetcode.com/problems/palindromic-substrings/
• Encode and Decode Strings (Leetcode Premium) - https://leetcode.com/problems/encode-and-decode-strings/

Tree

• Maximum Depth of Binary Tree - https://leetcode.com/problems/maximum-depth-of-binary-tree/
• Same Tree - https://leetcode.com/problems/same-tree/
• Invert/Flip Binary Tree - https://leetcode.com/problems/invert-binary-tree/
• Binary Tree Maximum Path Sum - https://leetcode.com/problems/binary-tree-maximum-path-sum/
• Binary Tree Level Order Traversal - https://leetcode.com/problems/binary-tree-level-order-traversal/
• Serialize and Deserialize Binary Tree - https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
• Subtree of Another Tree - https://leetcode.com/problems/subtree-of-another-tree/
• Construct Binary Tree from Preorder and Inorder Traversal - https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
• Validate Binary Search Tree - https://leetcode.com/problems/validate-binary-search-tree/
• Kth Smallest Element in a BST - https://leetcode.com/problems/kth-smallest-element-in-a-bst/
• Lowest Common Ancestor of BST - https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
• Implement Trie (Prefix Tree) - https://leetcode.com/problems/implement-trie-prefix-tree/
• Add and Search Word - https://leetcode.com/problems/add-and-search-word-data-structure-design/
• Word Search II - https://leetcode.com/problems/word-search-ii/

Heap

• Merge K Sorted Lists - https://leetcode.com/problems/merge-k-sorted-lists/
• Top K Frequent Elements - https://leetcode.com/problems/top-k-frequent-elements/
• Find Median from Data Stream - https://leetcode.com/problems/find-median-from-data-stream/

• 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