Каждый год это пиковый сезон найма на золото, серебро и серебро. Мне повезло получить возможность пройти письменный тест Microsoft. Все программисты должны знать, что старые и красивые компании любят бороться со структурами данных и алгоритмами, и Microsoft определенно не является исключением. Все кандидаты честные.В этот раз я голосовал за Microsoft Research Institute.Письменный тест не сложный.Это самая распространенная задача алгоритма структуры данных.Я запишу ее здесь и дам решение.
1 Быстрая сортировка
Быстрый ряд должен быть самым популярным вопросом в Интернете, от школьного рекрутинга до социального рекрутинга, от бэкенда к фронтенду и к мобильному, но, по оценкам, из них можно выдрать не более половины, и не более половина может быть ясно объяснена. Фактически, это можно суммировать в двух словах, то есть двойной указатель + рекурсивный разделяй и властвуй. В каждом раунде рекурсии найдите отсортированную позицию каждого ссылочного числа и поместите все числа меньше этот ссылочный номер слева от него. , поместите все числа больше этого базового числа справа от него, а затем рекурсивно выполните рекурсию массива слева и справа от него соответственно. Например, массив [2,3,1,5,6,4]:
function quickSort(arr, begin, end) {
//递归出口
if(begin >= end)
return;
var l = begin; // 左指针
var r = end; //右指针
var temp = arr[begin]; //基准数，这里取数组第一个数
//左右指针相遇的时候退出扫描循环
while(l < r) {
//右指针从右向左扫描，碰到第一个小于基准数的时候停住
while(l < r && arr[r] >= temp)
r --;
//左指针从左向右扫描，碰到第一个大于基准数的时候停住
while(l < r && arr[l] <= temp)
l ++;
//交换左右指针所停位置的数
[arr[l], arr[r]] = [arr[r], arr[l]];
}
//最后交换基准数与指针相遇位置的数
[arr[begin], arr[l]] = [arr[l], arr[begin]];
//递归处理左右数组
quickSort(arr, begin, l - 1);
quickSort(arr, l + 1, end);
}
var arr = [2,3,4,1,5,6]
quickSort(arr, 0, 5);
console.log(arr)
Мысль: "Почему сначала перемещается правый указатель, а не левый? Давайте подумаем об этом сами, ха-ха, и вы узнаете это, смоделировав это".
дивергентное мышление
Выше я упомянул левый массив, правый массив и понятие эталонного числа, при котором все значения в левом массиве меньше эталонного числа, а все значения в правом массиве больше ссылочного номера, а быстрая сортировка является рекурсивным процессом. Если я проведу здесь аналогию, если я рассмотрю референсное число как корень дерева, левый массив как левый дочерний элемент корня, а правый массив как правый дочерний элемент корня, я полагаю, что дети, которые научились структуры данных это знают. Разве это не BST? Ха-ха, это правда, на самом деле вы обнаружите, что упорядоченный обход BST представляет собой упорядоченный массив, поэтому процесс быстрой сортировки выше — это процесс создания двоичного дерева поиска.
Двоичное дерево поиска (также: Двоичное дерево поиска, Двоичное дерево сортировки) Это либо пустое дерево, либо бинарное дерево со следующими свойствами: Если его левое поддерево не пусто, то левое значение всех узлов в поддереве меньше, чем значение его корневого узла; если его правое поддерево не пусто, значение всех узлов в правом поддереве больше, чем значение его корневого узла; его левое, правое поддерево также является бинарным отсортированным деревом, соответственно.
Так что если вы спросите, как создать BST, вы должны быть в состоянии сделать это на кончиках ваших пальцев.Давайте не будем говорить о коде:
function vNode(value) {
this.val = value;
this.left = this.right = null;
}
function createBST(arr) {
var len = arr.length;
if(len < 1)
return;
var l = 0;
var r = len - 1;
var temp = arr[0];
while(l < r) {
while(l < r && arr[r] >= temp)
r --;
while(l < r && arr[l] <= temp)
l ++;
[arr[l], arr[r]] = [arr[r], arr[l]];
}
[arr[0], arr[l]] = [arr[l], arr[0]];
var root = new vNode(arr[l]);
root.left = createBST(arr.slice(0, l));
root.right = createBST(arr.slice(l + 1));
return root;
}
Нерекурсивный обход двоичного дерева по порядку
Я считаю, что многие люди могут написать рекурсивный обход бинарных деревьев: рекурсивно пройти левое поддерево, вывести корневой узел, рекурсивно пройти правое поддерево, три строки кода, и все готово, но когда их спрашивают о нерекурсивном обходе, большинство людей вероятно ошарашены. , но люди должны проверить, что вы не можете. Нерекурсивный обход на самом деле делается с помощью стеков:
var inorderTraversal = function(root) {
const res = [];
const stack = [];
while(root||stack.length !== 0)
{
while(root)
{
stack.push(root);
root=root.left;
}
if(stack.length)
{
let p=stack[stack.length - 1];
res.push(p.val);
stack.pop();
root = p.right;
}
}
return res;
};
Для старой американской компании проверка алгоритма должна быть пройдена. Итак, предстоит пройти долгий путь, пожалуйста, отметьте вопросы и еще больше вопросов.