The interview results
Summary of recent interviews:
- Headline back end: 3 technical side hangings
- Ant Alipay marketing – machine learning platform development: technical side passed, after the year was informed only P7 HC
- Ant Zhongtai – Machine learning platform development: Passed the technical aspect, but was failed by Ant HR (many people have encountered this situation, one is that the environment is not good this year, the other is that the interview should not catch up with the end of Ali’s fiscal year, this is a bit of tips)
- Quick end: Get the offer
- Baidu backend: get the offer
Finally rejected Baidu, go quick hand, a wish to go to Ali, personal a little ali plot, fate almost. Summarize the recent interview situation, because the face of more than 20, according to the classification of the question to everyone a summary. It is recommended that you take time to meet each year, not necessarily to change jobs, but to know your weaknesses, and make sure that your length of service matches your ability. For example, THROUGH the interview, I know that I don’t know much about database. In addition, my team has little contact with database, which is my weakness. As a back-end engineer, it is shameful to say that I don’t know much about database. The following points the topic of the recent interview summary and everyone summary. Too simple will not say, such as printing a graphic what, and I do not remember clearly, such as quick hand side seems to be a dynamic planning topic. Of course, there may be some solutions that are not very good, you can discuss in the hand rip code group. In the last article, I will talk about some interview skills and so on. Please like to forward support ~
Stock buying and selling (Headline)
There were three questions about stock trading in Leetcode, and only two questions were tested in the interview, which were the difficulty of Easy and medium
Leetcode 121. The best time to buy and sell stocks
Given an array, its ith element is the price of a given stock on the ith day.
If you only allow one trade (buy and sell one stock), design an algorithm to calculate the maximum profit you can make.
Note that you can’t sell a stock before you buy it.
Example 1:
Input: [7,1,5,3,6,4] output: 5Copy the codeExplanation: Buy on day 2 (stock price = 1), sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be greater than the buying price. Example 2:
Input: [7,6,4,3,1] output: 0Copy the codeExplanation: In this case, no transaction is completed, so the maximum profit is 0.
Answer key
Record two states, one is the maximum profit, the other is the minimum value of the traversed subsequence. Knowing the previous minimum we can figure out what the maximum possible profit is today
Class Solution {public int maxProfit(int[] prices) {// 7,1, 2,3, 4 int maxProfit = 0; int minNum = Integer.MAX_VALUE;for (int i = 0; i < prices.length; i++) {
if(Integer.MAX_VALUE ! = minNum && prices[i] - minNum > maxProfit) { maxProfit = prices[i] - minNum; }if(prices[i] < minNum) { minNum = prices[i]; }}returnmaxProfit; }}Copy the codeLeetcode 122. The best time to Buy and sell stocks II
This time the stock can be traded multiple times, but you must hold the stock before selling the stock. Example 1:
Input: [7,1,5,3,6,4] Output: 7 Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.Copy the codeExample 2:
Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the codeExample 3:
Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the codeAnswer key
Because you can buy and sell an infinite number of times. We all know that the way to make money in the stock market is to buy low and sell high, so all we have to do here is start the next day, and if the current price is higher than the previous price, we add the difference to the profit, because we can buy yesterday and sell today, and if the price is higher tomorrow, we can buy today and sell tomorrow. And so on, iterating through the entire array to get the maximum profit.
Class Solution {public int maxProfit(int[] prices) {// 7,1, 2,3, 4 int maxProfit = 0;for (int i = 0; i < prices.length; i++) {
if (i != 0 && prices[i] - prices[i-1] > 0) {
maxProfit += prices[i] - prices[i-1];
}
}
returnmaxProfit; }}Copy the codeLRU cache (Headlines, ants)
This is a headline question, and I suspect the headline interview question is a must-have question in the question bank. Look at the pulse is also a lot of people encountered. I didn’t get it right the first time I wrote it, so MAYBE I died because of that.
Turn self-knowledge on: zhuanlan.zhihu.com/p/34133067
The title
Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. It should support the following operations: get for data and PUT for writing data.
Get (key) – Gets the value of the key if it exists in the cache (always positive), otherwise -1 is returned. Write data PUT (key, value) – Writes the data value of the key if it does not exist. When the cache reaches its maximum capacity, it should remove the least-recently used data values before writing new data to make room for new data values.
Advanced:
Can you do both in O(1) time?
LRUCache cache = new LRUCache(2 /* Cache capacity */); cache.put(1, 1); cache.put(2, 2); cache.get(1); // return 1 cache. Put (3, 3); Cache.get (2); // This operation invalidates key 2. // return -1 (not found) cache.put(4, 4); Cache.get (1); // This operation invalidates key 1. // return -1 (not found) cache.get(3); // return 3 cache.get(4); / / return 4Copy the codeAnswer key
This problem is very common in toutiao, Kuaishou or silicon Valley companies.
The most important thing is how the LRU strategy is implemented, and it’s easy to think of implementing it with a linked list of the most recently used ones at the top of the list. For example, if you get an element, it’s used, it needs to be put first, and then return the value, same with set. So how do you quickly put the middle element of a list at the beginning of the list? It’s natural to think of a double-entailed list.
LRU based on HashMap and bidirectional linked list
The overall design idea is that you can use HashMap to store keys, so that the time of save and get keys is O(1), and the Value of HashMap points to the Node Node of LRU implemented by bidirectional linked list, as shown in the figure.
LRU storage is implemented based on a bidirectional linked list, which is illustrated in the figure below. Head represents the head of a bidirectional list, and tail represents the tail. First, the capacity of LRU is set in advance. If the storage is full, the tail of the bidirectional linked list can be eliminated by O(1) time. Every time data is added and accessed, new nodes can be added to the head by O(1) efficiency, or existing nodes can be moved to the head of the queue.
The following shows how LRU storage, with a default size of 3, changes during storage and access. To simplify the diagram, the changes in the HashMap part are not shown, only the changes in the LRU bidirectional list shown above. Our sequence of operations on the LRU cache is as follows:
save("key1", 7)
save("key2", 0)
save("key3", 1)
save("key4", 2)
get("key2")
save("key5", 3)
get("key2")
save("key6", 4)
Copy the codeThe corresponding LRU bidirectional linked list changes as follows:
To summarize the steps of the core operation:
Save (key, value), first find the node corresponding to the key in the HashMap, update the value of the node if it exists, and move the node to the queue head. If they don’t exist, a new node needs to be constructed and tried to squeeze the node into the head of the queue. If the LRU runs out of space, the node at the end of the queue is eliminated by tail and the Key is removed from the HashMap.
Get (key), using the HashMap to find the LRU linked list node, because according to LRU principle, this node is the most recently accessed, so the node is inserted into the queue head, and then returns the cached value.
private static class DLinkedNode { int key; int value; DLinkedNode pre; DLinkedNode post; */ private void addNode(DLinkedNode node) {node.pre = head; node.post = head.post; head.post.pre = node; head.post = node; */ private void removeNode(DLinkedNode node) {DLinkedNode pre = node.pre; DLinkedNode post = node.post; pre.post = post; post.pre = pre; } private void moveToHead(DLinkedNode node) {this.removenode (node); this.addNode(node); } /** * popup the tail node */ private DLinkedNodepopTail() {
DLinkedNode res = tail.pre;
this.removeNode(res);
return res;
}
private HashMap<Integer, DLinkedNode>
cache = new HashMap<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;
head = new DLinkedNode();
head.pre = null;
tail = new DLinkedNode();
tail.post = null;
head.post = tail;
tail.pre = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return- 1; This.movetohead (node); this.moveTohead (node);return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
this.cache.put(key, newNode);
this.addNode(newNode);
++count;
if(count > capacity) {// DLinkedNode tail = this.poptail (); this.cache.remove(tail.key); count--; }}else{// Cache hit, update cache.node. value = value; this.moveToHead(node); }}Copy the codeBinary tree traversal (headline)
We’ve seen this before, Leetcode 102.
The title
Given a binary tree, return the value of the nodes traversed hierarchically. (That is, layer by layer, all nodes are accessed from left to right).
For example, given a binary tree: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Copy the codeReturns the result of its hierarchical traversal:
[[3], [9,20], [15,7]Copy the codeAnswer key
The way we teach in our data structure book is to use a queue to continuously queue up the left and right subtrees. But this problem also requires layer output. So the key question is: how do you make sure they’re on the same floor? It is natural to think that if all the nodes in the previous tier are removed from the queue before joining the queue, then the nodes that are removed from the queue are the list of the previous tier. Since queues are a first-in, first-out data structure, the list is left to right.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(! queue.isEmpty()) { int size = queue.size(); List<Integer> currentRes = new LinkedList<>(); // The size of the current queue is the number of nodes in the upper layerwhile (size > 0) {
TreeNode current = queue.poll();
if (current == null) {
continue; } currentRes.add(current.val); // The left and right subtrees join the team.if(current.left ! = null) { queue.add(current.left); }if(current.right ! = null) { queue.add(current.right); } size--; } res.add(currentRes); }returnres; }}Copy the codeCan we solve this problem nonrecursively?
Recursive subproblem: traverse the current node, for the current level, traverse the next level of the left subtree, and traverse the next level of the right subtree
End of recursion condition: current level, current subtree node is null
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
levelOrderHelper(res, root, 0);
returnres; } private void levelOrderHelper(List<List<Integer>> res, TreeNode root, int depth) {if (root == null) {
return;
}
ifRes.add (new LinkedList<>()); res.add(new LinkedList<>()); res.add(new LinkedList<>()); } // depth layer, add the current node to res.get(depth).add(root.val); LevelOrderHelper (res, root.left, depth + 1); levelOrderHelper(res, root.left, depth + 1); levelOrderHelper(res, root.right, depth + 1); }}Copy the codeBinary tree turntable (Kuaishou)
This is Leetcode problem 104. Given a binary tree, expand it in place as a linked list.
For example, given a binary tree
1 / \ 2 5 / \ 3 4 6Copy the codeExpand it as:
1\2\3\4\5\6Copy the codeAnd the key thing about this problem is that when you recurse remember to transform the right subtree first, and then the left subtree. So we need to keep track of where the head of the list is after the right subtree is converted. Note that we did not define a new pointer to next. Instead, we set right as next and Left as null.
class Solution {
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null) return; flatten(root.right); // Convert right subtree flatten(root.left); root.right = prev; Root. left = null; root.left = null; Prev = root; // The current node is the link header}}Copy the codeIn a recursive solution, a stack is used to record nodes, with the right subtree pushed first and the left subtree pushed last.
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(! stack.isEmpty()) { TreeNode current = stack.pop();if(current.right ! = null) stack.push(current.right);if(current.left ! = null) stack.push(current.left);if(! stack.isEmpty()) current.right = stack.peek(); current.left = null; }}}Copy the codeBinary tree to find the nearest common parent node (Quick hand)
The nearest common parent node of the Leetcode 236 binary tree
Answer key
The loop starts at the root, and if either node1 or node2 matches root, then root is the lowest common ancestor. If neither match, the left and right subtrees are recursed separately. If one node appears in the left subtree and the other in the right subtree, root is the lowest common ancestor. If both nodes appear in the left subtree, the lowest common ancestor is in the left subtree; otherwise, it is in the right subtree.
public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)if(root == null || root == p || root == q) returnroot; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); // All subtrees have target nodes, so the common ancestor is itselfif(left! =null&&right! =null)returnroot; // If the target node is found, continue to mark up as the target nodereturnleft == null ? right : left; }}Copy the codeFinding the median of data stream (ant)
I met the team of Ant Zhongtai, and the second interview was assumed to be P9 level or above according to the reporting level. When I met me in the United States, the interview style was more like silicon Valley. Leetcode 295. This problem is the source of Leetcode’s hard difficulty. Given a data stream, finding the median of the data stream, finding the median or topK is a problem that we usually want to solve with the heap. But the interviewer took it a step further by asking for minimal memory use, no disks, and a time waster to squeeze space. Besides, the interviewer is required not only to express his thoughts, but also to write a complete production code that can be tested by big data.
Forget about memory
The memory-free approach is solved on the Leetcode forum. The basic idea is to build two heaps. On the left is the big pile, on the right is the small pile. If it’s odd, the top of the big root heap is the median.
For example: [1,2,3,4,5] the big root heap is built as follows:
3
/ \
1 2
Copy the codeThe small root heap is established as follows:
4/5Copy the codeEven numbers are the average of the maximum heap and the minimum heap top.
For example: [1, 2, 3, 4]
The big root heap is built as follows:
2/1Copy the codeThe small root heap is established as follows:
Three quarters ofCopy the codeAnd then maintain an odd or even state to find the median.
public class MedianStream {
private PriorityQueue<Integer> leftHeap = new PriorityQueue<>(5, Collections.reverseOrder());
private PriorityQueue<Integer> rightHeap = new PriorityQueue<>(5);
private boolean even = true;
public double getMedian() {
if (even) {
return(leftheap.peek () + rightheap.peek ()) / 2.0; }else {
return leftHeap.peek();
}
}
public void addNum(int num) {
if (even) {
rightHeap.offer(num);
int rightMin = rightHeap.poll();
leftHeap.offer(rightMin);
} else{ leftHeap.offer(num); int leftMax = leftHeap.poll(); rightHeap.offer(leftMax); } System.out.println(leftHeap); System.out.println(rightHeap); // even =! even; }}Copy the codeSqueeze the memory
The problem with this is that memory may explode. If your stream is infinitely large, then that means that the data has to be in memory, and the heap has to be able to be built infinitely large. If memory must be small, use time for space.
- Flow is repeatable, time for space;
- You can use the idea of divide-and-conquer to read the stream first and divide the number of data in the stream into buckets.
- Then you can walk through the buckets to find which bucket the median number falls in, which Narrows the problem down.
public class Median { private static int BUCKET_SIZE = 1000; private int left = 0; private int right = Integer.MAX_VALUE; Public double findMedian(int[] nums) {// The first read of the stream converts the complexity of the problem to an acceptable level of memory int[BUCKET_SIZE]; int step = (right - left) / BUCKET_SIZE; boolean even =true;
int sumCount = 0;
for(int i = 0; i < nums.length; i++) { int index = nums[i] / step; bucket[index] = bucket[index] + 1; sumCount++; even = ! even; } // If it is even, then we need to count topK and topK+1. Int topK = even? sumCount / 2 : sumCount / 2 + 1; int index = 0; int indexBucketCount = 0;for (index = 0; index < bucket.length; index++) {
indexBucketCount = bucket[index];
if(indexBucketCount >= topK) {// The current bucket is the median bucket.break; } topK -= indexBucketCount; } // The partition turns into a topK problem, read the stream again.if (even && indexBucketCount == topK) {
left = index * step;
right = (index + 2) * step;
returnhelperEven(nums, topK); [topIndex -k + (topIndex -k + 1)] / 2.}else if (even) {
left = index * step;
right = (index + 1) * step;
returnhelperEven(nums, topK); [topIndex -k + (topIndex -k + 1)] / 2}else {
left = index * step;
right = (index + 1) * step;
returnhelperOdd(nums, topK); // topIndex -k}}}Copy the codeSo once we’ve dealt with the boundary conditions here, the question is how do we solve for topK with helperOdd and helperEven. So let’s turn this into a topK problem, so top minus K and top of K plus 1, can we just use the heap here? The answer is no, consider the extreme case. The median number of repetitions is very high
Eg: [100100100100100]... (100 billion - 100).Copy the codeIf your partition falls into the bucket, the memory will also burst.
Time for space
If our partition bucket size is 10000, the maximum time range is 20000. (corresponding to the above even number and falling into two buckets) Now that we are divided into a bucket, we can directly use the way of number to calculate topK, or we can use the way of heap, which is more efficient. In fact, the problem size here has been divided into small, both methods can be used. We use TreeMap data structure to count. And then we divide it into odd and even numbers.
private double helperEven(int[] nums, int topK) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= left && nums[i] <= right) {
if(! map.containsKey(nums[i])) { map.put(nums[i], 1); }else {
map.put(nums[i], map.get(nums[i]) + 1);
}
}
}
int count = 0;
int kNum = Integer.MIN_VALUE;
int kNextNum = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int currentCountIndex = entry.getValue();
if(kNum ! = Integer.MIN_VALUE) { kNextNum = entry.getKey();break;
}
if (count + currentCountIndex == topK) {
kNum = entry.getKey();
} else if (count + currentCountIndex > topK) {
kNum = entry.getKey();
kNextNum = entry.getKey();
break;
} else{ count += currentCountIndex; }}return (kNum + kNextNum) / 2.0;
}
private double helperOdd(int[] nums, int topK) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= left && nums[i] <= right) {
if(! map.containsKey(nums[i])) { map.put(nums[i], 1); }else {
map.put(nums[i], map.get(nums[i]) + 1);
}
}
}
int count = 0;
int kNum = Integer.MIN_VALUE;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int currentCountIndex = entry.getValue();
if (currentCountIndex + count >= topK) {
kNum = entry.getKey();
break;
} else{ count += currentCountIndex; }}return kNum;
}
Copy the codeSo far, I think it is a good solution. There is no relevant solution or exploration in leetcode community, welcome everyone to communicate.
Popular reading
- Summary of technical articles
- 101. Symmetric binary trees
- [Leetcode] 100. Same tree
- [Leetcode] 98. Validate binary search trees
