Опыт фронтенд-интервью в июне 2018 года (посередине)

интервью внешний интерфейс алгоритм
Опыт фронтенд-интервью в июне 2018 года (посередине)

предисловие

В прошлой статье я написал несколько письменных тестовых вопросов, которые будут проверены, когда я выйду на собеседование, они не очень полные (хахаха, в основном я помню их мозгом, а некоторые из них забываются~)

Портал здесь:Опыт фронтенд-интервью в июне 2018 года (часть 1)～～～

В этой статье я опишу некоторые проблемы с алгоритмами, с которыми я столкнулся.Решения не одинаковы.Я надеюсь, что вы можете предоставить больше своих собственных идей и кодов~

проблема алгоритма

1) Быстрая сортировка

思路:
- 随机选择数组中的一个数 A，以这个数为基准
- 其他数字跟这个数进行比较，比这个数小的放在其左边，大的放到其右边
- 经过一次循环之后，A 左边为小于 A 的，右边为大于 A 的
- 这时候将左边和右边的数再递归上面的过程

const Arr = [85, 24, 63, 45, 17, 31, 96, 50];
function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    // 递归
    return quickSort(left).concat([pivot], quickSort(right));
}

console.log(quickSort(Arr));

ps:
这是阮老师的一个快排写法，网上对于这个的争论很多，第一说了阮老师不应该用splice去取值，应该用下标，还有就是不应该每次都从新开俩个新数组。
其实我觉得算法题重要的是思路，实现的方式有很多，不一定说谁对谁错，效率越好的算法的确是我们想要的，但是更多的理解一些不同的实现思路，我觉得也是可以的～。

Вот разные голоса:Интервьюер: Версия быстрой сортировки Жуань Ифэн совершенно неверна

2) Бинарный метод сортировки

Метод бинарного поиска предназначен главным образом для решения задачи «найти указанное число в группе упорядоченных чисел». Независимо от того, являются ли эти числа одномерными массивами или многомерными массивами, пока они упорядочены, их можно оптимизирован бинарным поиском.

Бинарный поиск — это своего рода алгоритм «разделяй и властвуй», общий процесс выглядит следующим образом:

  • Среднее число А в массиве, сравните размер с искомым числом
  • Поскольку массив упорядочен, то: а) Больше означает, что искомое число должно быть найдено из первой половины б) А
  • Меньше означает, что поиск следует выполнять со второй половины искомого номера.
  • Это продолжает смотреть вниз по порядку величины (отбрасывая половину данных), пока не будет найден массив
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

function Find(target, array) {
    let i = 0;
    let j = array[i].length - 1;
    while (i < array.length && j >= 0) {
        if (array[i][j] < target) {
            i++;
        } else if (array[i][j] > target) {
            j--;
        } else {
            return true;
        }
    }
    return false;
}

//测试用例
console.log(Find(10, [
    [1, 2, 3, 4], 
    [5, 9, 10, 11], 
    [13, 20, 21, 23]
    ])
);

3) Параметры после разбора URL

function parseParam(url) {
  let obj = {};
  let arr = url.split("?");
  if (arr.length == 1) { //判断没有问号
    return "无参数"
  }
  let total = arr[1].split("&");
  for (let i = 0; i < total.length; i++) {
    let single = total[i].split("=");
    if (single[0] == '') { //判断有？但是没有参数
      return '无参数'
    }
    if (!single[1]) {
      obj[single[0]] = true;
    } else {
      if (obj[single[0]]) {
        let concat
        if (!Array.isArray(obj[single[0]])) { //判断是否数组
          concat = [obj[single[0]]]
        } else {
          concat = obj[single[0]];
        }
        concat.push(single[1]);
        concat = new Set(concat);
        concat = Array.from(concat) //数组去重
        obj[single[0]] = concat
      } else {
        obj[single[0]] = decodeURI(single[1]) //进行转码
      }
    }
  }
  return obj
}

var url = 'http://www.baidu.com/?user=huixin&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled';

var params = parseParam(url)

console.log(params)

4) Реализовать простой шаблонизатор:

Столбец: меня зовут, возраст B, пол C; Пусть данные = { Имя: «Сяо Мин», Возраст: 18, } Нет определенного возврата undefined


let template = '我是{name}，年龄{age}，性别{sex}';
    let data = {
        name: '小明',
        age: 18,
    }
    const  reg= /({([a-zA-Z]+)})/g;
    var r= '',regrounp={};
    while( r = reg.exec(template) ){
        Object.defineProperty(regrounp,r[2],{
            enumerable:true,
            value:r[2]
        })
    }

    var render = (template,regrounp)=>{
        var result='';
        for( key in regrounp){
            if(data[key] == undefined){
                result  = (result || template).replace(new RegExp(`{${regrounp[key]}}`,"g"),undefined);
            }else{		
                result  = (result || template).replace(new RegExp(`{${regrounp[key]}}`,"g"),data[key]);
            }
        }
        return result
    }
    let newtemple = render(template, regrounp);
    console.log(newtemple) // 结果： 我是小明，年龄18，性别undefined

Я не знаю, если я не попробую это здесь.Объекты, объявленные как {}, могут быть перечислены напрямую.Объекты, объявленные Object.defineProperty, не могут быть перечислены с помощью for-in, если они не определяют enumerable:true.

Здесь есть хорошая статья РекомендуемНаписание простого механизма шаблонов JavaScript

5) Как быстро превратить строку в число тысячной точности

function exchange(num) {
    num += ''; //转成字符串
    if (num.length <= 3) {
        return num;
    }

    num = num.replace(/\d{1,3}(?=(\d{3})+$)/g, (v) => {
        console.log(v)
        return v + ',';
    });
    return num;
}

console.log(exchange(1234567));

6) Реализовать глубокое копирование объектов JS

深拷贝То есть при копировании данных копируются все ссылочные структуры данных. Проще говоря, в памяти есть две структуры данных, идентичные и независимые друг от друга, и ссылочный тип копируется, а не просто копируется его ссылочное отношение.

как анализировать深拷贝:

  • Сначала предположим, что метод глубокого копирования завершен, для deepClone
  • Чтобы скопировать часть данных, мы должны пройти по его свойствам.Если свойства объекта все еще являются объектами, продолжайте использовать этот метод и так далее.
function deepClone(o1, o2) {
    for (let k in o2) {
        if (typeof o2[k] === 'object') {
            o1[k] = {};
            deepClone(o1[k], o2[k]);
        } else {
            o1[k] = o2[k];
        }
    }
}
// 测试用例
let obj = {
    a: 1,
    b: [1, 2, 3],
    c: {}
};
let emptyObj = Object.create(null);
deepClone(emptyObj, obj);
console.log(emptyObj.a == obj.a);
console.log(emptyObj.b == obj.b);

Рекурсия легко вызывает взрыв стека. Хвостовой вызов может решить эту проблему рекурсии. Движок Chrome V8 оптимизировал хвостовые вызовы. Мы также должны обращать внимание на запись хвостового вызова при написании кода. Проблема рекурсивного взрыва стека может быть решена путем перезаписи рекурсии в перечисление, т.е.forилиwhileвместо рекурсии.

7) Найдите элемент Фибоначчи числа n (количество столбцов кролика) ... в этом 1,1,2,3,5,8,13,21,34,55,89

 下面的代码中count记录递归的次数，我们看下两种差异性的代码中的count的值：
 let count = 0;
 function fn(n) {
    let cache = {};
    function _fn(n) {
        if (cache[n]) {
            return cache[n];
        }
        count++;
        if (n == 1 || n == 2) {
            return 1;
        }
        let prev = _fn(n - 1);
        cache[n - 1] = prev;
        let next = _fn(n - 2);
        cache[n - 2] = next;
        return prev + next;
    }
    return _fn(n);
}

let count2 = 0;
function fn2(n) {
    count2++;
    if (n == 1 || n == 2) {
        return 1;
    }
    return fn2(n - 1) + fn2(n - 2);
}

console.log(fn(20), count); // 6765 20
console.log(fn2(20), count2); // 6765 13529

8) Эффективность алгоритма

Качество алгоритма можно измерить сложностью алгоритма, которая включает временную и пространственную сложность. Временная сложность находится в центре внимания интервью из-за характеристик хорошей оценки и оценки. Сложность пространства мало рассматривается в интервью.

Общие временные сложности:

  • постоянный порядокO(1)
  • логарифмическийO(logN)
  • Линейный порядокO(n)
  • Линейный логарифмический порядокO(nlogN)
  • Квадратный порядокO(n^2)
  • кубический порядокO(n^3)
  • !k порядок мощностиO(n^k)
  • Экспоненциальный порядокO(2^n)

При постоянном увеличении размера задачи n вышеуказанная временная сложность продолжает расти, а эффективность выполнения алгоритма снижается.

Как правило, при анализе сложности алгоритма следуйте следующим методам:

  • Посмотрите, сколько циклов, вообще говоря, один O(n), два O(n^2) и так далее.
  • O(logN), если есть дихотомия
  • Сохранить верхний член, удалить постоянный член

Тема: Анализ алгоритмической сложности следующего кода

let i =0; // 语句执行一次 
while (i < n) { // 语句执行 n 次 
  console.log(`Current i is ${i}`); //语句执行 n 次
  i++; // 语句执行 n 次
}
根据注释可以得到，算法复杂度为1 + n + n + n = 1 + 3n，去除常数项，为O(n)。

На самом деле существует еще много алгоритмических проблем, таких как добавление, удаление, изменение и проверка бинарного дерева.

Расширенные ресурсы:

Изучите структуры данных и алгоритмы в JavaScript

Интерфейсные структуры данных и алгоритмы, с которыми я столкнулся

пасхальные яйца

часовое интервью

1) Каким человеком вы себя считаете?

2) Почему вы ушли с работы?

3) Что вам больше всего не нравилось в вашем предыдущем руководстве?

4) Что ты обычно делаешь по выходным?

5) Какой ваш любимый проект, над которым вы работали? Зачем?

6) Какая команда тебе нравится?

Примечание: я закончил эту статью с новым обновлением, а следующее - интервью с интервьюером. Поскольку мой стек технологий - реакция, следующая тема вокругreact~

Категории