Overview

This is my Python (2.7) Leetcode solution. As time grows, this also become a guide to prepare for software engineer interview.
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
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
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

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)

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

This list is made by huahua, I found this on his youtube.

Software Engineer Interview

Overall Mindset

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...
How to Get a Job at the Big 4.
How I Got a Job at Google as a Software Engineer.
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

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

More resource
Architecture 101
Systems Design Interview Concepts. There are also lots of tech interview related topic in his channel.
Narendra's Youtube Channel

Knowledge Base Question

Session vs Cookie
Token Authentication
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.
HTTPS, CA, PKI
HTTP, HTTP Code, Socket, WebSocket, HTTP KeepAlive, HTTP2
DNS, CNAME, NS, A, AAAA, IPv4, IPv6
Code, Process, Thread
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.
GET vs POST
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/

tauka / leetcode-python Goto Github PK

leetcode-python's Introduction