/leetcode-python

Leetcode Python Solution and Explanation. Also a Guide to Prepare for Software Engineer Interview.

Primary LanguagePython

Overview

  1. This is my Python (2.7) Leetcode solution. As time grows, this also become a guide to prepare for software engineer interview.

  2. I really take time tried to make the best solution and collect the best resource that I found.
    Because I wanted to help others like me. If you like my answer, a star on GitHub means a lot to me. https://github.com/wuduhren/leetcode-python

  3. The solution is at problems/the-file-name/. For example, merge-sorted-array.py's solution is at https://leetcode.com/problems/merge-sorted-array/.

Leetcode Similar Problems

I found it makes sense to solve similar problems together, so that we can recognize the problem faster when we encounter a new one. My suggestion is to skip the HARD problems when you first go through these list.

Two Pointers

Id Name Difficulty Comments
11 Container With Most Water ★★
167 Two Sum II - Input array is sorted ★★
977 Squares of a Sorted Array ★★ merge sort

Recursion

Id Name Difficulty
726 Number of Atoms ★★★ 736 394
856 Score of Parentheses ★★★

Divide and Conquer

Id Name Difficulty Comments
169 Majority Element ★★
315 Count of Smaller Numbers After Self ★★★★ merge sort / BIT

Search

Id Name Difficulty Comments
17 Letter Combinations of a Phone Number ★★ 39 40 77 78 90 216 Combination
46 Permutations ★★ 47 784 943 996 Permutation
22 Generate Parentheses ★★★ 301 DFS
37 Sudoku Solver ★★★ 51 52 DFS
79 Word Search ★★★ 212 DFS
127 Word Ladder ★★★★ 126 752 BFS
542 01 Matrix ★★★ 675 934 BFS
698 Partition to K Equal Sum Subsets ★★★ 93 131 241 282 842 Partition

Hash Table

Id Name Difficulty
1 Two Sum ★★ 560

List

Id Name Difficulty Comments
2 Add Two Numbers ★★ 445
24 Swap Nodes in Pairs ★★
206 Reverse Linked List ★★
141 Linked List Cycle ★★ 142 fast/slow
23 Merge k Sorted Lists ★★★ 21 priority_queue
147 Insertion Sort List ★★★ insertion sort
148 Sort List ★★★★ merge sort O(1) space
707 Design Linked List ★★★★

Tree

Id Name Difficulty Comments
94 Binary Tree Inorder Traversal ★ 589 590 traversal
100 Same Tree ★★ 101 104 110 111 572 965
102 Binary Tree Level Order Traversal ★★ 107 429 872 987 collecting nodes
814 Binary Tree Pruning ★★ 669
112 Path Sum ★★★ 113 437
124 Binary Tree Maximum Path Sum ★★★ 543 687 Use both children, return one
129 Sum Root to Leaf Numbers ★★★ 257
236 Lowest Common Ancestor of a Binary Tree ★★★ 235
297 Serialize and Deserialize Binary Tree ★★★ 449
508 Most Frequent Subtree Sum ★★★
968 Binary Tree Cameras ★★★★ 337 979

Binary Search

Id Name Difficulty Comments
35 Search Insert Position ★★ 34 704 981 upper_bound
33 Search in Rotated Sorted Array ★★★ 81 153 154 162 852 rotated / peak
69 Sqrt(x) ★★★ upper_bound
74 Search a 2D Matrix ★★★ treat 2d as 1d
875 Koko Eating Bananas ★★★ 1011 guess ans and check
378 Kth Smallest Element in a Sorted Matrix ★★★ 668 kth + matrix
778 Swim in Rising Water ★★★ 174 875 guess ans and check
4 Median of Two Sorted Arrays ★★★★
719 Find K-th Smallest Pair Distance ★★★★ 786 kth + two pointers

Binary Search Tree

Id Name Difficulty Comments
98 Validate Binary Search Tree ★★ 530 inorder
700 Search in a Binary Search Tree ★★ 701 binary search
230 Kth Smallest Element in a BST ★★★ inorder
99 Recover Binary Search Tree ★★★ inorder
108 Convert Sorted Array to Binary Search Tree ★★★
501 Find Mode in Binary Search Tree ★★★ inorder
450 Delete Node in a BST ★★★★ binary search

Graph

Id Name Difficulty Comments
133 Clone Graph ★★ 138 queue + hashtable
200 Number of Islands ★★ 547 695 733 827 grid + connected components
841 Keys and Rooms ★★ connected components
207 Course Schedule ★★★ 210 802 topology sorting
399 Evaluate Division ★★★ 839 952 990 721 union find
785 Is Graph Bipartite? ★★★ bipartition
684 Redundant Connection ★★★★ 685 787 cycle, union find
743 Network Delay Time ★★★★ 882 shortest path
847 Shortest Path Visiting All Nodes ★★★★ 815 864 924 BFS
943 Find the Shortest Superstring ★★★★ 980 996 Hamiltonian path (DFS / DP)
959 Regions Cut By Slashes ★★★★ union find / grid + connected component
332 Reconstruct Itinerary ★★★★ Eulerian path
1192 Critical Connections in a Network ★★★★ Tarjan

Dynamic Programming

Id Name Difficulty Comments
70 Climbing Stairs ★ 746 I: O(n), S = O(n), T = O(n)
303 Range Sum Query - Immutable ★
53 Maximum Subarray ★★ 121
198 House Robber ★★★ 213 309 740 790 801 I: O(n), S = O(3n), T = O(3n)
139 Word Break ★★★ 140 818 I: O(n), S = O(n), T = O(n^2)
300 Longest Increasing Subsequence ★★★ 673
72 Edit Distance ★★★ 10 44 97 115 583 712 I: O(m+n), S = O(mn), T = O(mn)
322 Coin Change ★★★ 377 416 494 I: O(n) + k, S = O(n), T = O(kn)
813 Largest Sum of Averages ★★★ I: O(n) + k, S = O(n), T = O(kn^2)
312 Burst Balloons ★★★★ 664 1024 1039 I: O(n), S = O(n^2), T = O(n^3)
741 Cherry Pickup ★★★★ I: O(n^2), S = O(n^3), T = O(n^3)
546 Remove Boxes ★★★★★ I: O(n), S = O(n^3), T = O(n^4)
943 Find the Shortest Superstring ★★★★ 980 996 I: O(n), S = O(n2^n), T = (n^22^n)
62 Unique Paths ★★ 63 64 120 174 931 I: O(mn), S = O(mn), T = O(mn)
85 Maximal Rectangle ★★★ 221 304
688 Knight Probability in Chessboard ★★★ 576 935 I: O(mn) + k, S = O(kmn) T = O(kmn)
322 Coin Change ★★★ 377 416 494 1043 1049 I: O(n) + k, S = O(n), T = O(kn)
1220 1230 1262 1269
813 Largest Sum of Averages ★★★★ 1278 1335 410 I: O(n) + k
S = O(n*k), T = O(kn^2)
1223 Dice Roll Simulation ★★★★ I: O(n) + k + p
S = O(k*p), T = O(n^2kp)
312 Burst Balloons ★★★★ 664 1024 1039 1140 1130 I: O(n), S = O(n^2), T = O(n^3)
741 Cherry Pickup ★★★★ I: O(n^2), S = O(n^3), T = O(n^3)
546 Remove Boxes ★★★★★ I: O(n), S = O(n^3), T = O(n^4)
943 Find the Shortest Superstring ★★★★★ 980 996 1125 I: O(n)
S = O(n2^n), T = (n^22^n)

Advanced

Id Name Difficulty Comments
208 Implement Trie (Prefix Tree) ★★★ 648 676 677 720 745 Trie
307 Range Sum Query - Mutable ★★★ BIT/Segment Tree
901 Online Stock Span ★★★ 907 1019 Monotonic Stack
239 Sliding Window Maximum ★★★ Monotonic Queue

This list is made by huahua, I found this on his youtube. Please visit his website for more.

Software Engineer Interview

Overall Mindset

  1. Having a right mindset is the most important one. It keeps you going when you are tired after work. Studying when everyone else are out having fun. Reminding you that your goals are not going to come easy, it takes time, self-discipline, mental and physical toughness...

  2. How to Get a Job at the Big 4.

  3. How I Got a Job at Google as a Software Engineer.

  4. The #1 Daily Habit of Those Who Dominate with Andy Frisella. It is also avaliable on Spotify or Youtube, just google it.

Prepare in a Structural Way

  1. How should I prepare for my Google interview if I have 1 month left and I’m applying for a software engineer role?

  2. How can I get a job at Facebook or Google in 6 months?

  3. What should I know from the CLRS 3rd edition book if my aim is to get into Google?

Data Structures and Algorithms for beginners

If you are new or know nothing about data structures and algorithms, I recommend this course. This course is taught in Python and design to help you find job and do well in the interview.

System Design

  1. More resource

  2. Architecture 101

  3. Systems Design Interview Concepts. There are also lots of tech interview related topic in his channel.

  4. Narendra's Youtube Channel

Knowledge Base Question

  1. Session vs Cookie
  2. Token Authentication
  3. TCP/UDP
    • Transport Layer
      • Application Layer (HTTP, FTP)
      • Transport Layer (UDP/TCP, Slice data to small packages)
      • Network Layer (IP)
      • Link Layer (Wifi)
      • Physical Layer (Coaxial Ethernet Cable)
    • UDP has smaller package size (8 bytes), while TCP needs 20 bytes due to it has larger header.
    • UDP are not order guaranteed. TCP are in order.
    • They both have error messages, but TCP will resent it again, UDP does not.
    • TCP needs a three-way handshake to initiate a connection between ports. It’s like a phone call. While UDP is like a mail.
    • In short, UDP is smaller and faster while TCP is reliable and ordered.
    • UDP example, video streaming, DNS lookups.
  4. HTTPS, CA, PKI
  5. HTTP, HTTP Code, Socket, WebSocket, HTTP KeepAlive, HTTP2
  6. DNS, CNAME, NS, A, AAAA, IPv4, IPv6
  7. Code, Process, Thread
  8. Stack memory vs Heap memory

    • Stack memory

      • Stores temporary variable created by functions.
      • Memory is managed by CPU for you. No need to allocate and free it by hand.
      • L.I.F.O.
      • Stacks has limit (That is why we seldom use recursion real life)
      • Stacks variable are local variable in nature.

    • Heap memory

      • Larger.
      • Slightly slower. Because we has to use "pointers" to access.
      • We are responsible to free() the memory.
      • Heap variable is global variable in nature.
  9. GET vs POST
  10. CORS
    ...

Others

Resume

https://drive.google.com/file/d/10b9NZDhPbUOW_C7108IKe9ev6Ed2UG7F/view

Interview Question Survey

https://www.glassdoor.com/index.htm
https://www.careercup.com/

Offer Negotiation

https://haseebq.com/my-ten-rules-for-negotiating-a-job-offer/