https://habrahabr.ru/company/ruvds/blog/334538/

• Разработка веб-сайтов
• JavaScript
• Блог компании RUVDS.com

Недавно мне довелось побывать на встрече участников проекта FreeCodeCamp в Сан-Франциско. Если кто не знает, Free Code Camp — это сообщество, нацеленное на изучение JavaScript и веб-программирования. Там один человек, который готовился к собеседованиям на позицию фронтенд-разработчика, попросил меня подсказать, какие вопросы по JavaScript стоит проработать. Я немного погуглил, но не смог найти подходящего списка вопросов, на который я бы мог дать ссылку и сказать: «Разбери эти вопросы и работа твоя». Некоторые списки были близки к тому, что мне хотелось найти, некоторые выглядели очень уж простыми, но все они были либо неполными, либо содержали вопросы, которые вряд ли кто станет задавать на реальном собеседовании.

В итоге я решил составить собственный список. В него входят и те вопросы, которые задавали мне, когда я искал работу, и те, которые задавал я, когда искал сотрудников на позиции фронтенд-разработчиков. Обратите внимание на то, что некоторые компании (вроде Google) уделяют особое внимание таким вещам, как проектирование эффективных алгоритмов. Поэтому, если вы хотите в подобной компании работать, в дополнение к приведённым тут вопросам, порешайте задачки с соревнований CodeJam.

Я буду добавлять и редактировать ответы на эти вопросы здесь. Если у вас возникнет желание что-нибудь дополнить или улучшить — буду рад вашим пулл-реквестам.

Вопросы разбиты на несколько разделов:

• Теория.
• Программирование.
• Отладка.
• Проектирование систем.

Итак, вот мои вопросы.

Теория

Интервьюируемый должен обладать чётким пониманием концепций, которые затрагивают вопросы из этого раздела, должен уметь всё это объяснить. Программирование тут не требуется.

1. Что такое нотация «О-большое» и как ей пользоваться?
2. Что такое DOM?
3. Что такое цикл событий?
4. Что такое замыкание?
5. Как работает прототипное наследование и чем оно отличается от классической модели наследования? (По моему мнению, это не особенно полезный вопрос, но многим нравится его задавать.)
6. Как работает ключевое слово this?
7. Что такое всплытие событий и как работает этот механизм? (Мне этот вопрос тоже не нравится, но его часто задают на собеседованиях.)
8. Опишите несколько способов обмена данными между клиентом и сервером. Расскажите, не вдаваясь в подробности, о том, как работают несколько сетевых протоколов (IP, TCP, HTTP/S/2, UDP, RTC, DNS, и так далее).
9. Что такое REST и почему эта технология популярна?
10. Мой сайт тормозит. Расскажите о шагах по его диагностированию и исправлению. Опишите популярные подходы к оптимизации, и расскажите о том, когда их следует использовать.
11. Какими фреймворками вы пользовались? Каковы их сильные и слабые стороны? Почему программисты пользуются фреймворками? Проблемы какого рода решают фреймворки?

Программирование

Ответы на эти вопросы предполагают реализацию функций на JavaScript. За каждым вопросом следуют тесты, которые должно успешно проходить решение.

▍Простые задания

1. Реализуйте функцию isPrime(), которая возвращает true или false, указывая, является ли переданное ей число простым.
   
   

   isPrime(0)                          // false
   isPrime(1)                          // false
   isPrime(17)                         // true
   isPrime(10000000000000)             // false

   
   
2. Реализуйте функцию factorial(), которая возвращает факториал переданного ей числа.
   
   

   factorial(0)                        // 1
   factorial(1)                        // 1
   factorial(6)                        // 720

   
   
3. Реализуйте функцию fib(), возвращающую n-ное число Фибоначчи.
   
   

   fib(0)                              // 0
   fib(1)                              // 1
   fib(10)                             // 55
   fib(20)                             // 6765

   
   
4. Реализуйте функцию isSorted(), которая возвращает true или false в зависимости о того, отсортирован ли переданный ей числовой массив.
   
   

   isSorted([])                        // true
   isSorted([-Infinity, -5, 0, 3, 9])  // true
   isSorted([3, 9, -3, 10])            // false

   
   
5. Создайте собственную реализацию функции filter().
   
   

   filter([1, 2, 3, 4], n => n < 3)    // [1, 2]

   
   
6. Создайте собственную реализацию функции reduce().
   
   

   reduce([1, 2, 3, 4], (a, b) => a + b, 0) // 10

   
   
7. Реализуйте функцию reverse(), которая обращает порядок следования символов переданной ей строки. Не пользуйтесь встроенной функцией reverse().
   
   

   reverse('')                         // ''
   reverse('abcdef')                   // 'fedcba'

   
   
8. Создайте собственную реализацию функции indexOf() для массивов.
   
   

   indexOf([1, 2, 3], 1)               // 0
   indexOf([1, 2, 3], 4)               // -1

   
   
9. Реализуйте функцию isPalindrome(), которая возвращает true или false в зависимости от того, является ли переданная ей строка палиндромом (функция нечувствительна к регистру и к наличию в строке пробелов).
   
   

   isPalindrome('')                                // true
   isPalindrome('abcdcba')                         // true
   isPalindrome('abcd')                            // false
   isPalindrome('A man a plan a canal Panama')     // true

   
   
10. Реализуйте функцию missing(), которая принимает неотсортированный массив уникальных чисел (то есть, числа в нём не повторяются) от 1 до некоего числа n, и возвращает число, отсутствующее в последовательности. Там может быть либо одно отсутствующее число, либо их может не быть вовсе.
    
    Способны ли вы добиться того, чтобы функция решала задачу за время O(N)? Подсказка: есть одна хорошая формула, которой вы можете воспользоваться.
    
    

    missing([])                         // undefined
    missing([1, 4, 3])                  // 2
    missing([2, 3, 4])                  // 1
    missing([5, 1, 4, 2])               // 3
    missing([1, 2, 3, 4])               // undefined

    
    
11. Реализуйте функцию isBalanced() которая принимает строку и возвращает true или false, указывая на то, сбалансированы ли фигурные скобки, находящиеся в строке.
    
    

    isBalanced('}{')                      // false
    isBalanced('{{}')                     // false
    isBalanced('{}{}')                    // true
    isBalanced('foo { bar { baz } boo }') // true
    isBalanced('foo { bar { baz }')       // false
    isBalanced('foo { bar } }')           // false

▍Задания средней сложности

1. Реализуйте функцию fib2(). Она похожа на функцию fib() из предыдущей группы заданий, но поддерживает числа вплоть до 50. Подсказка: используйте мемоизацию.
   
   

   fib2(0)                               // 0
   fib2(1)                               // 1
   fib2(10)                              // 55
   fib2(50)                              // 12586269025

   
   
2. Реализуйте функцию isBalanced2(). Она похожа на функцию isBalanced() из предыдущей группы заданий, но поддерживает три типа скобок: фигурные {}, квадратные [], и круглые (). При передаче функции строки, в которой имеются неправильные скобочные последовательности, функция должна возвращать false.
   
   

   isBalanced2('(foo { bar (baz) [boo] })') // true
   isBalanced2('foo { bar { baz }')         // false
   isBalanced2('foo { (bar [baz] } )')      // false

   
   
3. Реализуйте функцию uniq(), которая принимает массив чисел и возвращает уникальные числа, найденные в нём. Может ли функция решить эту задачу за время O(N)?
   
   

   uniq([])                              // []
   uniq([1, 4, 2, 2, 3, 4, 8])           // [1, 4, 2, 3, 8]

   
   
4. Реализуйте функцию intersection(), которая принимает два массива и возвращает их пересечение. Можете ли вы добиться того, чтобы функция решала эту задачу за время O(M+N), где M и N — длины массивов?
   
   

   intersection([1, 5, 4, 2], [8, 91, 4, 1, 3])    // [4, 1]
   intersection([1, 5, 4, 2], [7, 12])             // []

   
   
5. Создайте реализацию функции sort(), которая сортирует числовой массив за время O(N×log(N)).
   
   

   sort([])                              // []
   sort([-4, 1, Infinity, 3, 3, 0])      // [-4, 0, 1, 3, 3, Infinity]

   
   
6. Реализуйте функцию includes(), которая возвращает true или false в зависимости от того, встречается ли переданное ей число в переданном ей отсортированном массиве. Может ли функция решить эту задачу за время O(log(N))?
   
   

   includes([1, 3, 8, 10], 8)            // true
   includes([1, 3, 8, 8, 15], 15)        // true
   includes([1, 3, 8, 10, 15], 9)        // false

   
   
7. Реализуйте функцию assignDeep(), которая похожа на Object.assign(), но выполняет глубокое объединение объектов. Для того, чтобы не усложнять задачу, можно исходить из допущения, что объекты могут содержать только числа и другие объекты (в них не может быть массивов, строк, и так далее).
   
   

   assignDeep({ a: 1 }, {})              // { a: 1 }
   assignDeep({ a: 1 }, { a: 2 })        // { a: 2 }
   assignDeep({ a: 1 }, { a: { b: 2 } }) // { a: { b: 2 } }
   assignDeep({ a: { b: { c: 1 }}}, { a: { b: { d: 2 }}, e: 3 })
   // { a: { b: { c: 1, d: 2 }}, e: 3 }

   
   
8. Реализуйте функцию reduceAsync(), которая похожа на функцию reduce() из группы простых заданий, но работает с функциями, возвращающими promise-объекты, каждый из которых должен быть разрешён до перехода к следующему.
   
   

   let a = () => Promise.resolve('a')
   let b = () => Promise.resolve('b')
   let c = () => new Promise(resolve => setTimeout(() => resolve('c'), 100))
   await reduceAsync([a, b, c], (acc, value) => [...acc, value], [])
   // ['a', 'b', 'c']
   await reduceAsync([a, c, b], (acc, value) => [...acc, value], ['d'])
   // ['d', 'a', 'c', 'b']

   
   
9. Реализуйте функцию seq(), пользуясь тем же подходом, что и при работе над функцией reduceAsync(). Эта функция должна принимать массив функций, которые возвращают promise-объекты, и разрешать их один за другим.
   
   

   let a = () => Promise.resolve('a')
   let b = () => Promise.resolve('b')
   let c = () => Promise.resolve('c')
   await seq([a, b, c])                  // ['a', 'b', 'c']
   await seq([a, c, b])                  // ['a', 'c', 'b']

▍Сложные задания

Некоторые задания из этой группы связаны с созданием структур данных. Не нужно запоминать все тонкости их функционирования, достаточно понимания их устройство, при этом сведения о предоставляемом ими интерфейсе можно найти в интернете. Далее, нужно знать, для чего эти структуры данных используются, каковы их ограничения в сравнении с другими структурами данных.

1. Реализуйте функцию permute(), которая возвращает массив строк, содержащий все пермутации заданной строки.
   
   

   permute('')             // []
   permute('abc')          // ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

   
   
2. Создайте самостоятельную реализацию функции debounce().
   
   

   let a = () => console.log('foo')
   let b = debounce(a, 100)
   b()
   b()
   b() // только этот вызов должен вызывать a()

   
   
3. Реализуйте класс LinkedList, не используя встроенные массивы JavaScript ( [] ). Ваш LinkedList должен поддерживать лишь 2 метода: add() и has().
   
   

   class LinkedList {...}
   let list = new LinkedList(1, 2, 3)
   list.add(4)                           // undefined
   list.add(5)                           // undefined
   list.has(1)                           // true
   list.has(4)                           // true
   list.has(6)                           // false

   
   
4. Реализуйте класс HashMap, не используя встроенные объекты JavaScript ( {} ) или функцию map(). Вам дана функция hash(), которая принимает строку и возвращает некое число. Эти числа, в основном, уникальны, но возможна и ситуация, когда двум разным строкам соответствуют одинаковые числа.
   
   

   function hash (string) {
     return string
       .split('')
       .reduce((a, b) => ((a << 5) + a) + b.charCodeAt(0), 5381)
   }

   
   Ваша реализация HashMap должна поддерживать лишь 2 метода: get() и set().
   
   

   let map = new HashMap
   map.set('abc', 123)                   // undefined
   map.set('foo', 'bar')                 // undefined
   map.set('foo', 'baz')                 // undefined
   map.get('abc')                        // 123
   map.get('foo')                        // 'baz'
   map.get('def')                        // undefined

   
   
5. Реализуйте класс BinarySearchTree. Он должен поддерживать 4 метода: add(), has(), remove(), и size().
   
   

   let tree = new BinarySearchTree
   tree.add(1, 2, 3, 4)
   tree.add(5)
   tree.has(2)                           // true
   tree.has(5)                           // true
   tree.remove(3)                        // undefined
   tree.size()                           // 4

   
   
6. Реализуйте класс BinaryTree, который поддерживает поиск в ширину, а также функции симметричного, прямого и обратного поиска в глубину.
   
   

   let tree = new BinaryTree
   let fn = value => console.log(value)
   tree.add(1, 2, 3, 4)
   tree.bfs(fn)                          // undefined
   tree.inorder(fn)                      // undefined
   tree.preorder(fn)                     // undefined
   tree.postorder(fn)                    // undefined

Отладка

При ответе на следующие вопросы сначала постарайтесь понять, почему представленный код не работает. Объясните причину ошибки. Затем предложите пару вариантов исправления проблемы и перепишите код, реализуя один из предложенных вариантов. В итоге программа должна работать правильно.

1. Необходимо, чтобы этот код выводил в лог hey amy, но он выводит hey arnold. Почему?
   
   

   function greet(person) {
     if (person == { name: 'amy' }) {
       return 'hey amy'
     } else {
       return 'hey arnold'
     }
   }
   greet({ name: 'amy' })

   
   
2. Необходимо, чтобы этот код выводил в лог числа 0, 1, 2, 3 в указанном порядке, но он этого не делает (Однажды вы столкнётесь с этой ошибкой. Некоторые люди любят задавать этот вопрос на собеседованиях).
   
   

   for (var i = 0; i < 4; i++) {
     setTimeout(() => console.log(i), 0)
   }

   
   
3. Необходимо, чтобы этот код выводил в лог doggo, но он выводит лишь undefined.
   
   

   let dog = {
     name: 'doggo',
     sayName() {
       console.log(this.name)
     }
   }
   let sayName = dog.sayName
   sayName()

   
   
4. Попытка вызова метода bark() объекта Dog вызывает ошибку. Почему?
   
   

   function Dog(name) {
     this.name = name
   }
   Dog.bark = function() {
     console.log(this.name + ' says woof')
   }
   let fido = new Dog('fido')
   fido.bark()

   
   
5. Почему функция isBig() возвращает именно такой результат?
   
   

   function isBig(thing) {
     if (thing == 0 || thing == 1 || thing == 2) {
       return false
     }
     return true
   }
   isBig(1)    // false
   isBig([2])  // false
   isBig([3])  // true

Проектирование систем

Если вы не уверены, что знаете, что такое «проектирование систем», сначала почитайте это.

1. Расскажите о реализации виджета автозавершения вводимого пользователем текста. Данные для автозавершения загружаются с сервера. Рассмотрите клиентскую и серверную части системы.

• Как бы вы спроектировали клиентскую часть системы, которая поддерживает следующие возможности:
  
  
  • Получение данных с применением серверного API.
  • Вывод результатов в виде дерева, когда у элементов могут быть родительские и дочерние элементы, то есть, подсказки автозаполнения — это не обычный плоский список.
  • Поддержка, помимо обычных текстовых фрагментов, элементов разных типов: флажков, радиокнопок, иконок.
  
  
• Как выглядит API компонента?
• Как выглядит серверное API?
• Какие соображения, касающиеся производительности, нужно учитывать для того, чтобы виджет работал в режиме реального времени, выводя подсказки по мере ввода данных пользователем? Есть ли здесь какие-нибудь пограничные случаи (например, когда пользователь вводит текст быстро при медленном сетевом соединении)?
• Как бы вы спроектировали сетевую подсистему и серверную часть высокопроизводительного решения такого рода? Как организовали бы взаимодействие клиента и сервера? Как данные хранятся на сервере? Как всё это масштабируется для поддержки больших объёмов данных и большого количества клиентов?

2. Расскажите о реализации сервиса, подобного Twitter, описав клиентскую и серверную части (этот вопрос бессовестно украден у моего друга Майкла Ву).

• Как твиты загружаются с сервера и выводятся в пользовательском интерфейсе?
• Как, при обновлении твитов, обновляется лента? Как клиентская часть приложения узнаёт о появлении новых твитов?
• Как выполняется поиск по твитам? Как организован поиск по автору? Расскажите о том, как спроектирована база данных, серверная часть приложения и API.

Итоги

Надеемся, эти вопросы пригодятся и тем, кто собирается на собеседования, и тем, кто их проводит. А если вы не относитесь ни к тем, ни к другим, полагаем, вопросы помогут вам поддерживать себя в хорошей программистской форме.

Вот, кстати, ещё несколько мест, куда можно заглянуть, если вам хочется попрактиковаться: The Algorithm Design Manual, задачи с соревнований CodeJam, репозиторий keon/algorithms. А вот — несколько ресурсов, которые будут полезны JS-разработчикам: JavaScript Allonge, You Don’t Know JS, Effective JavaScript.

Уважаемые читатели! Если у вас есть на примете вопросы, которые, по вашему мнению, стоит добавить в этот список (или если вы обнаружите ошибку) — расскажите нам и напишите автору этого материала.