Skip to content

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

Notifications You must be signed in to change notification settings

tingjunye/leetcode-python

Folders and files

NameName
Last commit message
Last commit date

Latest commit

History

105 Commits

Repository files navigation

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

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

Recursion

IdNameDifficulty
726Number of Atoms★★★736394
856Score of Parentheses★★★

Divide and Conquer

IdNameDifficultyComments
169Majority Element★★
315Count of Smaller Numbers After Self★★★★merge sort / BIT

Search

IdNameDifficultyComments
17Letter Combinations of a Phone Number★★3940777890216Combination
46Permutations★★47784943996Permutation
22Generate Parentheses★★★301DFS
37Sudoku Solver★★★5152DFS
79Word Search★★★212DFS
127Word Ladder★★★★126752BFS
54201 Matrix★★★675934BFS
698Partition to K Equal Sum Subsets★★★93131241282842Partition

Hash Table

IdNameDifficulty
1Two Sum★★560

List

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

Tree

IdNameDifficultyComments
94Binary Tree Inorder Traversal589590traversal
100Same Tree★★101104110111572965
102Binary Tree Level Order Traversal★★107429872987collecting nodes
814Binary Tree Pruning★★669
112Path Sum★★★113437
124Binary Tree Maximum Path Sum★★★543687Use both children, return one
129Sum Root to Leaf Numbers★★★257
236Lowest Common Ancestor of a Binary Tree★★★235
297Serialize and Deserialize Binary Tree★★★449
508Most Frequent Subtree Sum★★★
968Binary Tree Cameras★★★★337979

Binary Search

IdNameDifficultyComments
35Search Insert Position★★34704981upper_bound
33Search in Rotated Sorted Array★★★81153154162852rotated / peak
69Sqrt(x)★★★upper_bound
74Search a 2D Matrix★★★treat 2d as 1d
378Kth Smallest Element in a Sorted Matrix★★★668kth + matrix
778Swim in Rising Water★★★174875guess ans and check
4Median of Two Sorted Arrays★★★★
719Find K-th Smallest Pair Distance★★★★786kth + two pointers

Binary Search Tree

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

Graph

IdNameDifficultyComments
133Clone Graph★★138queue + hashtable
200Number of Islands★★547695733827grid + connected components
841Keys and Rooms★★connected components
207Course Schedule★★★210802topology sorting
399Evaluate Division★★★839952990721union find
785Is Graph Bipartite?★★★bipartition
684Redundant Connection★★★★685787cycle, union find
743Network Delay Time★★★★882shortest path
847Shortest Path Visiting All Nodes★★★★815864924BFS
943Find the Shortest Superstring★★★★980996Hamiltonian path (DFS / DP)
959Regions Cut By Slashes★★★★union find / grid + connected component

Dynamic Programming

IdNameDifficultyComments
70Climbing Stairs746I: O(n), S = O(n), T = O(n)
303Range Sum Query - Immutable
53Maximum Subarray★★121
198House Robber★★★213309740790801I: O(n), S = O(3n), T = O(3n)
139Word Break★★★140818I: O(n), S = O(n), T = O(n^2)
300Longest Increasing Subsequence★★★673
72Edit Distance★★★104497115583712I: O(m+n), S = O(mn), T = O(mn)
322Coin Change★★★377416494I: O(n) + k, S = O(n), T = O(kn)
813Largest Sum of Averages★★★I: O(n) + k, S = O(n), T = O(kn^2)
312Burst Balloons★★★★66410241039I: O(n), S = O(n^2), T = O(n^3)
741Cherry Pickup★★★★I: O(n^2), S = O(n^3), T = O(n^3)
546Remove Boxes★★★★★I: O(n), S = O(n^3), T = O(n^4)
943Find the Shortest Superstring★★★★980996I: O(n), S = O(n2^n), T = (n^22^n)
62Unique Paths★★6364120174931I: O(mn), S = O(mn), T = O(mn)
85Maximal Rectangle★★★221304
688Knight Probability in Chessboard★★★576935I: O(mn) + k, S = O(kmn) T = O(kmn)

Advanced

IdNameDifficultyComments
208Implement Trie (Prefix Tree)★★★648676677720745Trie
307Range Sum Query - Mutable★★★BIT/Segment Tree
901Online Stock Span★★★9071019monotonic stack

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

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/

About

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

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python100.0%