Interview knowledge collection series
The interview tips series has always received feedback from everyone, including the success of internal promotion in the background, the success of my friend’s colleague from a small start-up company to Huawei and so on. I am very glad that the sorting and sharing of xiaofang can really help everyone
The topic of today’s article is to share 14 kinds of ideas to solve the interview algorithm programming problems (from educative[1]). Through my previous written test interview experience, it is indeed very high frequency, and must be very familiar with it. I’ll give you for each of these ideas
- “Basic Principles (with drawings)”
- Application Scenarios
- “Leetcode or sword refers to offer specific chestnut”
Enjoy!
1. Sliding Windows
The sliding window pattern is used to perform the desired action on a particular window size for a given array or list, such as finding the oldest sequence containing all 1s. The sliding window starts with the first element, moves one element to the right at a time and adjusts the length of the window depending on the problem to be solved. In some cases, the size of the window stays the same, while in other cases, the size increases or decreases.
Application scenarios
Okay, now that we understand the principle of sliding Windows, when do we need it?
- The problem input is a linear data structure, such as a linked list, array, or string
- Find the longest/shortest substring, subarray, or desired value
Take a chestnut
Let’s take a look at the problem that sliding Windows solves in practice
- Maximum number of sliding Windows (pointing to offer) [2]
- Sliding window median (LEETCODE) [3]
- Minimum Coverage substring (LEETCODE) [4]
- A subarray of K distinct integers (LEETCODE) [5]
2. Dual Pointers
The basic idea of double-pointers is to iterate over a data structure in series with two Pointers until one or both of them reach a certain condition. Two Pointers are often useful when searching pairs of elements in sorted arrays or linked lists, such as when comparing each element of an array with other elements.
We usually need two Pointers because if we only have a single pointer, we have to loop through the array to find the answer. This solution, while feasible, is obviously inefficient for time and space complexity. In many cases, using dual Pointers can help you find a solution with better spatial or temporal complexity.
Application scenarios
- The problem is a set of elements that sort an array or a linked list and need to satisfy certain constraints
- The set of elements in an array is a pair, a triple, or even a subarray
Take a chestnut
- N-sum problem (LEETCODE)
- Longest creation without repeating characters (LEETCODE) [6]
- Rainwater harvesting (LEETCODE) [7]
- Minimum length subarray (LEETCODE) [8]
3. Fast and slow pointer
Also known as the tortoise-rabbit algorithm, the basic idea is to use two Pointers to move through an array or linked list at different speeds. This method is useful when dealing with circularly linked lists or arrays. By moving at different speeds (for example, in a circular linked list), the algorithm proves that two Pointers must meet. Once both Pointers are in a loop, the fast pointer should capture the slow pointer.
Application scenarios
- Linked list or array loop
- Used to find intermediate elements
- You need to know the position of an element or the total length of the list
Take a chestnut
- Circular linked List (LEETCODE) [9]
- Intersecting Linked Lists (LEETCODE) [10]
- Circular list entry node (LEETCODE) [11]
4. Merge interval
Merge interval pattern is an effective technique to deal with overlapping interval. Among many problems involving intervals, you may need to find overlapping intervals or merging intervals if they overlap. Given two intervals and, there can be six different interval interactions:
Application scenarios
- Requires a list to be generated with only mutex intervals
- The word “intervals” appears
Take a chestnut
- Merge interval (LEETCODE) [12]
- Conference Room (LEETCODE) [13]
- Range module (LEETCODE) [14]
- Intersection of interval lists (LEETCODE) [15]
5, Tree width first search (Tree BFS)
This pattern is based on breadth-first search (BFS) techniques to traverse the tree and use queues to record all nodes in that layer before jumping to the next layer. Using this approach, you can effectively solve any problem that involves traversing the tree in a hierarchical order. The basic idea of the Tree BFS pattern is to push the root node to the queue and iterate until the queue is empty. For each iteration, the node at the head of the queue is removed and “accessed”. After each node is removed from the queue, we also push all of its children into the queue.
Application scenarios
- It involves a sequence traversal tree
Take a chestnut
- Sequence traversal of n-tree (LEETCODE) [16]
- Sequence traversal of binary tree (LEETCODE) [17]
- Zigzag level traversal of binary tree [18]
6, Tree depth first search (Tree DFS)
Tree DFS is based on depth-first search (DFS) technology to traverse the tree. The basic idea of Tree DFS is to trace all previous (parent) nodes through a traverse using recursion (or stack of iterative methods). Starting at the root of the tree, if the node is not a leaf, three things need to be done:
- Decide whether to process the current node immediately (sequential traversal), two child nodes in between (mid-sequential traversal), or two child nodes after (sequential traversal).
- Make two recursive calls to the two children of the current node to process them.
Application scenarios
- It deals with tree preordering, middle ordering, or subsequent traversal
- If the problem involves searching for objects closer to the leaf
Take a chestnut
- Find the sum of numbers from root to leaf (LEETCODE) [19]
- Maximum depth of binary tree (LEETCODE) [20]
- Constructing a binary tree (LEETCODE) by traversing sequences in middle and rear order [21]
- Path Summation Series (LEETCODE) [22]
7, Subset
A large number of programming interview questions involve dealing with permutations and combinations of a given set of elements. The Subsets pattern describes an efficient breadth-first search (BFS) approach to all of these problems. For example, given an array [1, 5, 3]
- First initialize an empty array:
[[]] - Add the first number (1) to all existing subsets to create new subsets:
[[], [1]] - Continue to add
[1], [5], [1, 5] [[], [1], [5], [1, 5], [3], [1, 3], [5, 3], [1, 5, 3]]
Application scenarios
- Problems that require finding combinations or permutations of a given set
Take a chestnut
- Subset Series (LEETCODE) [23]
- All case and upper case arrangement (LEETCODE) [24]
- List all abbreviations of words (LEETCODE) [25]
- Word subset (LEETCODE) [26]
References for this article
[1]
Educative: hackernoon.com/14-patterns…
[2]
A maximum of sliding window (sword offer) : www.nowcoder.com/practice/16…
[3]
Sliding window median (LEETCODE) : leetcode-cn.com/problems/sl…
[4]
Minimum coverage substring (LEETCODE) : leetcode-cn.com/problems/mi…
[5]
A subarray of K distinct integers (LEETCODE) : leetcode-cn.com/problems/su…
[6]
The longest creation without repeating characters (LEETCODE) : leetcode-cn.com/problems/lo…
[7]
Rainwater harvesting (LEETCODE) : leetcode-cn.com/problems/tr…
[8]
Minimum length subarray (LEETCODE) : leetcode-cn.com/problems/mi…
[9]
Circular linked Lists (LEETCODE) : leetcode-cn.com/problems/li…
[10]
Intersecting Linked Lists (LEETCODE) : leetcode-cn.com/problems/in…
[11]
Circular list entry node (LEETCODE) : leetcode-cn.com/problems/li…
[12]
Merge interval (LEETCODE) : leetcode-cn.com/problems/me…
[13]
Conference room (LEETCODE) : leetcode-cn.com/problems/me…
[14]
Range module (LEETCODE) : leetcode-cn.com/problems/ra…
[15]
Intersection of interval lists (LEETCODE) : leetcode-cn.com/problems/in…
[16]
Order traversal of N tree (LEETCODE) : leetcode-cn.com/problems/n-…
[17]
Sequential traversal of binary trees (LEETCODE) : leetcode-cn.com/problems/bi…
[18]
Zigzag level traversal of binary trees: leetcode-cn.com/problems/bi…
[19]
Find the sum of numbers from root to leaf (LEETCODE) : leetcode-cn.com/problems/su…
[20]
Maximum depth of binary tree (LEETCODE) : leetcode-cn.com/problems/ma…
[21]
Constructing a binary tree (LEETCODE) by traversing sequences in middle and rear order: leetcode-cn.com/problems/co…
[22]
Path Summation Series (LEETCODE) : leetcode-cn.com/problems/pa…
[23]
Subset series (LEETCODE) : leetcode-cn.com/problems/su…
[24]
All case and upper case (LEETCODE) : leetcode-cn.com/problems/le…
[25]
List all the abbreviations of the words (LEETCODE) : leetcode-cn.com/problems/ge…
[26]
Word subset (LEETCODE) : leetcode-cn.com/problems/wo…
– END –
Machine Learning Online Manual Deep Learning online Manual AI Basics download (PDF updated to25Set) site QQ group1003271085To join the wechat group, please reply to "add group" to get a discount station knowledge planet coupon, please reply to "knowledge planet" like the article, click on itCopy the code