результат интервью
Резюме последних интервью:
- Задняя часть Toutiao: 3-сторонняя техническая боковая подвеска
- Ant Alipay Marketing-Machine Learning Platform Development: технически принят, и через год уведомлен, что есть только P7 hc
- Ant Zhongtai-Machine Learning Platform Development: технически пройдена, но Ant HR зависла (многие люди сталкивались с этой ситуацией, одна из них заключается в том, что общая обстановка в этом году не очень хорошая, а другая - постарайтесь не догнать конец Али) фискальный год для интервью, это маленькая подсказка)
- Серверная часть Kuaishou: получить предложение
- Серверная часть Baidu: получить предложение
В конце концов я отказался от Байду и поехал на Куайшоу.Я хотел пойти на Али.Лично у меня есть немного сюжета Али,и моя судьба почти. Подведите итог недавней ситуации с интервью.Поскольку интервью более 20, я дам вам резюме в соответствии с типом вопросов. Всем рекомендуется выделять время на встречи каждый год, не обязательно для смены работы, но вам нужно знать свои собственные недостатки, и ваши трудовые годы должны соответствовать вашим способностям. Например, лично из интервью я знаю, что мало что знаю о базах данных.Кроме того, поскольку моя группа меньше контактирует с базами данных, это недостаток.Как back-end инженеру стыдно говорить что я мало разбираюсь в базах данных. , вы можете быть предвзятым при выборе предложения. Следующие подтемы обобщают недавнее резюме интервью и всех. Я не буду говорить о чрезмерно простых, таких как печать графика или что-то еще, и я не очень хорошо помню.Например, Kuaishou кажется задачей динамического программирования. Конечно, могут быть некоторые решения, которые не очень хороши, вы можете обсудить их в группе по разборке кода. В последней статье я расскажу о некоторых навыках собеседования. Пожалуйста, лайкните, перешлите и поддержите~
Торговля акциями (заголовок)
На Leetcode есть три вопроса по торговле акциями.Во время интервью тестировались только два вопроса, которые были легкой и средней сложности.
Leetcode 121. Лучшее время для покупки и продажи акций
Дан массив, i-й элемент которого представляет собой цену данной акции в i-й день.
Если вам разрешено совершить не более одной сделки (т. е. купить и продать одну акцию), разработайте алгоритм для расчета максимальной прибыли, которую вы можете получить.
Обратите внимание, что вы не можете продать акцию до ее покупки.
Пример 1:
输入: [7,1,5,3,6,4]
输出: 5
Объяснение: покупка на 2-й день (цена акции = 1), продажа на 5-й день (цена акции = 6), максимальная прибыль = 6-1 = 5. Обратите внимание, что прибыль не может быть 7-1 = 6, потому что цена продажи должна быть больше, чем цена покупки. Пример 2:
输入: [7,6,4,3,1]
输出: 0
Объяснение: В этом случае сделка не завершена, поэтому максимальная прибыль равна 0.
отвечать
Записываются два состояния, одно — максимальная прибыль, а другое — минимальное значение пройденной подпоследовательности. Зная предыдущее минимальное значение, мы можем рассчитать максимально возможную прибыль на текущий день.
class Solution {
public int maxProfit(int[] prices) {
// 7,1,5,3,6,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];
}
}
return maxProfit;
}
}
Leetcode 122. Лучшее время для покупки и продажи акций II
На этот раз вы можете покупать и продавать акции несколько раз, но вы должны продать акции, которые у вас есть, прежде чем продавать акции. Пример 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
Пример 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
Пример 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
отвечать
Так как его можно покупать и продавать неограниченное количество раз. Все мы знаем, что если вы хотите заработать на акциях, конечно, вам нужно покупать по низкой цене и продавать по высокой цене, поэтому здесь нам нужно только начать со следующего дня.Если текущая цена выше, чем предыдущей цене, добавьте разницу к прибыли, потому что мы можем купить вчера. , продать сегодня, если цена будет выше завтра, вы можете купить сегодня и продать завтра. По аналогии максимальную прибыль можно получить после обхода всего массива.
class Solution {
public int maxProfit(int[] prices) {
// 7,1,5,3,6,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];
}
}
return maxProfit;
}
}
Кэш LRU (Toutiao, Ant)
Эта тема очень часто встречается в Toutiao, и я даже подозреваю, что Toutiao является обязательным вопросом в банке вопросов. Взгляд на пульс также встречается у многих людей. Первый раз написал, не очень хорошо написал, может из-за этого и завис.
Из Чжиху:zhuanlan.zhihu.com/p/34133067
тема
Используя известные вам структуры данных, спроектируйте и внедрите механизм кэширования LRU (наименее использовавшийся). Он должен поддерживать следующие операции: получить данные, получить и записать данные, положить.
Получить данные get(key) — Получить значение ключа (всегда положительное число), если ключ (ключ) существует в кеше, иначе вернуть -1. Записать данные put(key, value) — если ключ не существует, записать его значение данных. Когда емкость кэш-памяти достигает верхнего предела, он должен удалить последнее использованное значение данных перед записью новых данных, чтобы освободить место для нового значения данных.
Передовой:
Можете ли вы выполнить обе операции с временной сложностью O(1)?
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
отвечать
Этот вопрос относительно распространен в компаниях Toutiao, Kuaishou или Силиконовой долины, так как еще нужно написать много кода, и сложность тоже высока.
Самое главное, как реализовать стратегию LRU, Легко думать об использовании связанного списка, чтобы поместить самые последние использовавшиеся в начало связанного списка. Например, получение элемента эквивалентно тому, что оно было использовано, в это время его нужно разместить на переднем плане, а затем вернуть значение. То же верно и для множества. Итак, как быстро поместить средний элемент связанного списка в начало связанного списка? Естественно, мы подумали о двусторонних связных списках.
Реализация LRU на основе HashMap и двусвязного списка
Общая идея дизайна заключается в том, что вы можете использовать HashMap для хранения ключа, так что время сохранения и получения ключа составляет O (1), а значение HashMap указывает на узел узла LRU, реализованный двусвязным списком. , как показано на рисунке.
Хранилище LRU реализовано на основе двусвязного списка, и следующая диаграмма демонстрирует его принцип. Голова представляет собой голову двусвязного списка, а хвост — хвост. Сначала установите емкость LRU заранее.Если хранилище заполнено, хвост двусвязного списка может быть устранен за время O(1).Каждый раз, когда данные добавляются и к ним осуществляется доступ, новые узлы могут добавляться в O( 1) оперативность.В голову, или переместить существующий узел в голову очереди.
Ниже показано, предустановленный размер 3, изменение хранения LRU во время хранения и доступа. Чтобы упростить график, на рисунке не показаны изменения в части HashMap, а показаны только изменения в двусвязном списке LRU на приведенном выше рисунке. Наша последовательность операций с этим кэшем LRU выглядит следующим образом:
save("key1", 7)
save("key2", 0)
save("key3", 1)
save("key4", 2)
get("key2")
save("key5", 3)
get("key2")
save("key6", 4)
Соответствующая часть двусвязного списка LRU изменяется следующим образом:
Обобщите этапы основной операции:
save(key, value), сначала найдите узел, соответствующий ключу в HashMap, если узел существует, обновите значение узла и переместите узел в начало очереди. Если его нет, необходимо построить новый узел и попытаться поставить узел в начало очереди.Если места LRU недостаточно, узел в хвосте очереди устраняется через хвост, а ключ удаляется из HashMap.
get(key), найти узел связанного списка LRU через HashMap, так как по принципу LRU этот узел является последним посещением, поэтому узел нужно вставить в начало очереди, а затем вернуть закешированное значение.
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);
}
/**
* 弹出最尾巴节点
*/
private DLinkedNode popTail() {
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; // cache里面没有
}
// cache 命中,挪到开头
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命中,更新cache.
node.value = value;
this.moveToHead(node);
}
}
Обход уровня двоичного дерева (заголовок)
Эта тема также упоминалась ранее, вопросы Leetcode 102.
тема
Учитывая бинарное дерево, возвращайте его значения узлов, пройденные иерархически. (т.е. слой за слоем, посещая все узлы слева направо).
Например: Учитывая бинарное дерево: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
Вернуть результат его иерархического обхода:
[
[3],
[9,20],
[15,7]
]
отвечать
Обход по уровням, описанный в нашей книге по структуре данных, заключается в использовании очереди для непрерывной постановки в очередь левого и правого поддеревьев. Но эта проблема также требует вывода по слою. Итак, ключевой вопрос:Как определить, находятся ли они на одном уровне. Мы естественно думаем: Если все узлы на предыдущем уровне исключены из очереди перед помещением в очередь, то исключенные из очереди узлы представляют собой список предыдущего уровня. Поскольку очередь является структурой данных «первым пришел — первым обслужен», этот список ведется слева направо.
/**
* 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<>();
// 当前队列的大小就是上一层的节点个数, 依次出队
while (size > 0) {
TreeNode current = queue.poll();
if (current == null) {
continue;
}
currentRes.add(current.val);
// 左子树和右子树入队.
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
size--;
}
res.add(currentRes);
}
return res;
}
}
Можно ли решить эту задачу нерекурсивно?
Рекурсивная подзадача: пройти текущий узел, для текущего слоя пройти следующий слой левого поддерева, пройти следующий слой правого поддерева
Условие окончания рекурсии: текущий слой, текущий узел поддерева равен нулю
/**
* 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);
return res;
}
/**
* @param depth 二叉树的深度
*/
private void levelOrderHelper(List<List<Integer>> res, TreeNode root, int depth) {
if (root == null) {
return;
}
if (res.size() <= depth) {
// 当前层的第一个节点,需要new 一个list来存当前层.
res.add(new LinkedList<>());
}
// depth 层,把当前节点加入
res.get(depth).add(root.val);
// 递归的遍历下一层.
levelOrderHelper(res, root.left, depth + 1);
levelOrderHelper(res, root.right, depth + 1);
}
}
Бинарное дерево в связанный список (быстрая рука)
Это вопрос Leetcode 104. Имея двоичное дерево, разверните его в связанный список на месте.
Например, для бинарного дерева
1
/ \
2 5
/ \ \
3 4 6
Расширьте его до:
1
\
2
\
3
\
4
\
5
\
6
Ключ к этой проблеме заключается в том, что при рекурсивном преобразовании не забудьте сначала преобразовать правое поддерево, а затем левое. Поэтому вам нужно записать, где находится головной узел связанного списка после преобразования правого поддерева. Обратите внимание, что нет нового определения следующего указателя, но правый непосредственно используется в качестве следующего указателя, тогда мы можем присвоить левому указателю значение null.
class Solution {
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null) return;
flatten(root.right); // 先转换右子树
flatten(root.left);
root.right = prev; // 右子树指向链表的头
root.left = null; // 把左子树置空
prev = root; // 当前结点为链表头
}
}
Используя рекурсивное решение, используйте стек для записи узла, правое поддерево помещается в стек первым, а левое поддерево помещается в стек позже.
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;
}
}
}
Двоичное дерево для поиска ближайшего общего родительского узла (быстрая рука)
Leetcode 236 ближайший общий родительский узел бинарного дерева
отвечать
Переходя от корневого узла, если какой-либо из узлов node1 и node2 соответствует root, то root является младшим общим предком. Если совпадений нет, выполните рекурсию для левого и правого поддеревьев соответственно. Если один узел появляется в левом поддереве, а другой узел появляется в правом поддереве, корень является младшим общим предком. Если оба узла появляются в левом поддереве, тогда младший общий предок находится в левом поддереве, в противном случае он находится в правом поддереве.
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//发现目标节点则通过返回值标记该子树发现了某个目标结点
if(root == null || root == p || root == q) return root;
//查看左子树中是否有目标结点，没有为null
TreeNode left = lowestCommonAncestor(root.left, p, q);
//查看右子树是否有目标节点，没有为null
TreeNode right = lowestCommonAncestor(root.right, p, q);
//都不为空，说明做右子树都有目标结点，则公共祖先就是本身
if(left!=null&&right!=null) return root;
//如果发现了目标节点，则继续向上标记为该目标节点
return left == null ? right : left;
}
}
Поток данных для поиска медианы (муравей)
В интервью с командой Ant Zhongtai интервьюер во втором интервью предположил, что по уровню репортажа это должен быть уровень P9 и выше.В США стиль интервью больше похож на Силиконовую долину. Вопросы сложной сложности, leetcode 295 вопросов. Этот вопрос является исходным вопросом высокой сложности Leetcode. Учитывая поток данных, чтобы найти медиану потока данных, мы обычно хотим использовать кучу для решения проблемы нахождения медианы или topK. Однако интервьюер еще больше усложнил задачу: он потребовал небольшого использования памяти и отсутствия диска, но может выдержать определенную потерю времени при сжатии места. И интервьюер попросил не только высказать идеи, но и написать полный производственный код, который можно протестировать на больших данных.
Забудьте о памяти
Способ игнорировать память — это решение на форуме Leetcode. Основная идея состоит в том, чтобы построить две кучи. Слева большая куча корней, а справа маленькая куча корней. Если это нечетно, то вершина большой корневой кучи является медианой.
Например: [1,2,3,4,5] Большая корневая куча строится следующим образом:
3
/ \
1 2
Корневая куча создается следующим образом:
4
/
5
Когда он четный, это среднее значение максимальной и минимальной вершин кучи.
Пример: [1, 2, 3, 4]
Большая корневая куча строится следующим образом:
2
/
1
Корневая куча создается следующим образом:
3
/
4
Затем поддерживайте нечетно-четное состояние, чтобы найти медиану.
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;
}
}
сжимать память
Но проблема с этим в том, что память может взорваться. Если ваш поток бесконечно велик, это означает, что данные должны храниться в памяти, а куча должна иметь возможность построения бесконечно больших размеров. Если памяти должно быть мало, обменяйте время на пространство.
- Потоки можно читать повторно, используя время вместо пространства;
- Можно использовать идею «разделяй и властвуй», сначала прочитай поток, а количество данных в потоке раздели на ведра;
- После обхода сегментов можно узнать, в какой сегмент попадает медиана, что сужает масштаб проблемы.
public class Median {
private static int BUCKET_SIZE = 1000;
private int left = 0;
private int right = Integer.MAX_VALUE;
// 流这里用int[] 代替
public double findMedian(int[] nums) {
// 第一遍读取stream 将问题复杂度转化为内存可接受的量级.
int[] bucket = new 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;
}
// 如果是偶数,那么就需要计算第topK 个数
// 如果是奇数, 那么需要计算第 topK和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) {
// 当前bucket 就是中位数的bucket.
break;
}
topK -= indexBucketCount;
}
// 划分到这里其实转化为一个topK的问题, 再读一遍流.
if (even && indexBucketCount == topK) {
left = index * step;
right = (index + 2) * step;
return helperEven(nums, topK);
// 偶数的时候, 恰好划分到在左右两个子段中.
// 左右两段中 [topIndex-K + (topIndex-K + 1)] / 2.
} else if (even) {
left = index * step;
right = (index + 1) * step;
return helperEven(nums, topK);
// 左边 [topIndex-K + (topIndex-K + 1)] / 2
} else {
left = index * step;
right = (index + 1) * step;
return helperOdd(nums, topK);
// 奇数, 左边topIndex-K
}
}
}
После того, как мы разберемся с граничными условиями здесь, ключ в том, как найти topK для двух функций helperOdd и helperEven, Мы по-прежнему преобразуем его в задачу topK, тогда проблема нахождения top-K и top(K+1) здесь .Можно ли использовать кучу для ее решения Ответ - нет, рассмотрим крайние случаи.Среднее количество повторений очень велико
eg:
[100,100,100,100,100...] (1000亿个100)
Ваш раздел случайно упадет в это ведро, и память тоже взорвется.
обмен времени на пространство
Если размер корзины нашего раздела равен 10000, то максимальный временной интервал равен 20000. (соответствует приведенному выше четному числу и попадает в два ведра) Затем, поскольку он разделен на определенное ведро, мы можем напрямую использовать числовой метод для нахождения topK, а также можно использовать метод кучи, который более эффективен.На самом деле масштаб проблемы был разделен на небольшие, как можно использовать методы.. Мы используем структуру данных TreeMap для подсчета. Затем разделите нечетные и четные числа, чтобы решить.
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;
}
Пока что я думаю, что это хорошее решение.В сообществе leetcode нет соответствующих ответов и исследований.Приветствую всех к общению.
Популярное чтение
- Резюме технических статей
- 【Leetcode】101. Симметричное двоичное дерево
- 【Leetcode】100. То самое дерево
- 【Leetcode】98. Проверка двоичного дерева поиска