Интервью с Acing Software Engineering

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

Хорошо, давайте сразу перейдем к простым вопросам. Это простые вопросы с короткими ответами, которые может задать интервьюер, которые помогут ему быстро узнать о вас.

  • В чем разница между GET и POST?
  • Объясните архитектуру REST.
  • Зачем кому-то нужно перезаписывать метод .equals () в классе Java?
  • Объясните все, что происходит, когда вы вводите URL-адрес в свой веб-браузер.
  • В чем основное различие между HTTP 1.0 и 1.1?
  • Что такое полиморфизм?
  • Реализуйте функцию подкачки без использования временной переменной.
  • В чем разница между интерфейсом и абстрактным методом?
  • Как обычно реализуется хеш-таблица?
  • Опишите двоичную древовидную структуру и ее варианты.
  • Что такое поздняя статическая привязка?
  • Как каждый метод реализован в Ruby? Как бы ты это сделал?

Далее, вот некоторые из наиболее сложных вопросов, связанных с программированием, которые вы можете получить:

Вопрос первый

Мы начнем со старой доброй задачи FizzBuzz, которую популяризировал Джефф Этвуд в этом сообщении в блоге.

По сути, идея состоит в том, чтобы печатать каждое число от 1 до n, однако печатать 'fizz' каждый раз, когда число делится на 3, чтобы печатать 'buzz' каждый раз, когда число делится на 5, и печатать 'fizzbuzz' каждый раз число делится как на 3, так и на 5 (15). Эти числа могут измениться на два разных простых числа. Это не меняет способа решения проблемы.

Одно из моих любимых решений:

def fizzbuzz(n):
  print “\n”.join([(‘Fizz’*(not i%3) + ‘Buzz’*(not i%5)) if ((not i%3) or (not i%5)) else str(i) for i in xrange(1, n+1)])

Еще один замечательный:

def fizzbuzz(n):
 for i in xrange(1, n+1): print [i, ‘Fizz’, ‘Buzz’, ‘FizzBuzz’][(i%3 == 0) + 2 * (i % 5 == 0)]

Что-то еще, что я видел, строится на этом для проблемы FizzBuzzBazz. Это просто добавляет фразу «Bazz», связанную со следующим простым числом, скажем 7. Все остальное остается прежним. Обычно это используется, чтобы показать, почему некоторые решения могут быть неправильными или как их можно упростить.

Вопрос второй

Один из самых простых и распространенных вопросов - «Покажите мне метод, который проверяет, есть ли в строке какие-либо дубликаты».

public boolean inUnique(string str) {
 boolean[] chars = new boolean[256]; // Only works with ASCII
 for(int i=0; i<str.size(); i++) {
   if(chars[str.charAt(i)]) return false;
   chars[str.charAt(i)] = true;
 }
 return true;
}

Этот подход прост и требует времени O (n). Если пробел более важен, лучше всего протестировать каждый символ по сравнению с любым другим:

public boolean isUnique(string str) {
 for(int i=0; i<str.size(); i++){
   for(int j=0; j<str.size(); j++) {
     if(i==j) continue;
     else if(str.charAt(j) == str.charAt(i)) return false;
   }
 }
 return true;
}

И еще один способ с использованием хеша:

from collections import defaultdict
 
def isUnique(string):
 seen = defaultdict(lambda: False)
 for x in string:
   if not seen[x]: seen[x] = True
   else: return False
 return True

Вы также можете использовать битовый вектор, чтобы использовать еще меньше места.

Вопрос третий

Другой распространенный способ - найти n-е число Фибоначчи.

def fib(n):
 return reduce(lambda x, y: [x[1], x[0] + x[1]], xrange(n-2), [0, 1])[1]

Вопрос четвертый

Далее проблема со скобками. Один из моих любимых, просто спросите у людей в SendGrid. В этом основная идея состоит в том, чтобы создать метод, который принимает на вход строку и возвращает логическое значение. Истина, если скобки в строке допустимы, ложь, если нет. Например. () является действительным. ) (нет. Есть много решений этой проблемы. Следует иметь в виду одну вещь: стек идеально подходит для этой проблемы. Вот решение, использующее единицу:

def validParentheses? str
 a = []
 str.each_char do |x|
   if x == ‘(‘
     a.push x
   elsif x == ‘)’
     return false if a.pop == nil 
   end
 end
 a.empty?
end

Альтернативное соло, данное мне @Sirupsen:

def balanced?(string)
 string.each_char.inject(0) { |open, char|
 return false if open < 0
 char == ‘(‘ ? open + 1 : open — 1
 } == 0
end

Было бы довольно легко расширить это для работы со многими видами скобок. Что-то вроде этого подойдет:

def balancedParens(s):
 stack, opens, closes = [], [‘(‘, ‘[‘, ‘{‘], [‘)’, ‘]’, ‘}’]
 for c in s:
   if c in opens:
     stack.append(c)
   elif c in closes:
     try:
       if opens.index(stack.pop()) != closes.index(c):
         return False
     except (ValueError, IndexError):
       return False
  return not stack

Также вот такая же проблема.

Вопрос пятый

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

num_map = {‘0’: ‘0’, ‘1’: ‘1’, ‘2’: ‘ABC’, ‘3’: ‘DEF’, ‘4’: ‘GHI’, ‘5’: ‘JKL’, ‘6’: ‘MNO’, ‘7’: ‘PQRS’, ‘8’: ‘TUV’, ‘9’: ‘WXYZ’}
 
def get_number_representations(n):
 return itertools.product(*[num_map[x] for x in n])

Вопрос шестой

Напишите способ перетасовки колоды карт. Тасование должно быть идеальным - иными словами, каждая по 52! перестановки колоды должны быть одинаково вероятными. Вы можете предположить, что у вас есть настоящий генератор случайных чисел.

public void shuffleCards (int[] cards){ 
 int temp, index;
 for (int i = 0; i < cards.length; i++){
   index = (int) (Math.random() * (cards.length — i)) + i;
   temp = cards[i];
   cards[i] = cards[index];
   cards[index] = temp;
 }
}

Вопрос седьмой

Наконец, в этом разделе есть классический вопрос "это двоичное дерево поиска". Достаточно простое решение:

def isBST(node, minVal, maxVal):
 if node is None: return True
 if not minVal <= node.val <= maxVal: return False
 return isBST(node.left, minVal, node.val) and isBST(node.right, node.val, maxVal)

Вопрос восьмой

Бутылка одна. У вас есть кувшин на пять литров и кувшин на три литра, неограниченный запас воды и ничего больше. Как бы вы получили *** ровно *** четыре литра воды?

Нравится:

  • Заливка 5
  • Разлить в 3
  • Вылить 3
  • Налейте 2 из 5 в 3
  • Заливка 5
  • Вылейте 1 из 5 в 3

Или вот так:

  • Заливка 3
  • Разлить на пять
  • Заливка 3
  • Налейте 2 в 5 из 3
  • Вылить 5
  • Налейте 1 в 5
  • Заливка 3
  • Налейте 3 в 5

Ответ на этот вопрос может также доказать, что вы смотрели «Крепкий орешек». 😏

Вопрос девятый

Группа людей на острове. Волшебный джинн спускается, собирает всех вместе и надевает волшебную шляпу хотя бы на голову одного человека. Шляпа видна другим людям, но не человеку, который ее носит. Чтобы снять шляпу, те (и только те, у кого есть шляпа) должны окунуться под воду ровно в полночь. Если есть x человек и y головных уборов, сколько времени нужно людям, чтобы снять шляпы? Эти люди не могут разговаривать друг с другом.

Отвечать:

у-1 ночи. Все просто, не правда ли? Это потому, что если есть один парень в шляпе, он не увидит никого вокруг себя в шляпе, это должен быть он, поэтому в полночь он окунет голову в воду. Затем, если два человека носят шляпы, каждый увидит кого-то в шляпе, подождет ночь, а затем увидит, что другой не обмакнул голову, значит, это должны быть они и другой человек в шляпе. И так далее.

Вопрос десять

Вот что я услышал в колледже от одного из моих любимых профессоров: это здание в 100 этажей. У яиц есть определенная сила, и они пробиваются через этаж x. Найдите минимальное n с двумя яйцами. К концу можно разбить оба яйца.

Отвечать:

Самая простая попытка проста: сбросить первое яйцо с sqrt (этажи), а затем увеличить. Итак, 10, затем 20, затем 30 и т. Д. Затем, как только он сломается на полу x, сбросьте его с пола (x * 10) -9, затем (x * 10) -8 и так далее. Это ставит минимум наихудшего случая на 19.

В этом случае мы бросали каждое яйцо одинаковое количество раз, независимо от того, на каком этаже было разбито первое, лучший способ сделать это - попытаться получить каждую попытку первого яйца, чтобы уменьшить количество, которое вы должны бросить вторым яйцом. приводя к истинному минимуму. Это означает решение для: (x) + (x-1) + (x-2) + (x-3)… + 1 = 100 → x = 14. Итак, мы бросаем первое яйцо в 14, затем в 27, 39 и т. Д. Наш худший минимум - 14.

А также динамическое программирование.

Я не говорю, что это лучшие типы вопросов, которые нужно задавать кандидатам (это не так), но именно такие вопросы я получаю на собеседовании. Для любой причины. На самом деле это не имеет значения, ваша работа прямо сейчас - добиться успеха в том, что они вам бросят, и, по крайней мере, для вакансий разработчика программного обеспечения, которые только что закончили колледж, это, как правило, вопросы, которые задают кандидатам.

Цель этого поста - направить ваш ум в правильном направлении; что вам нужно знать, чтобы пройти собеседование, или, по крайней мере, техническую часть. Это не единственный документ, который вы читаете. Отсюда еще один хороший следующий шаг - это посмотреть на предыдущие Google Code Jams, Top Coder или (мой любимый) Project Euler. Еще одна методика собеседования, которую я видел, - это когда интервьюер уже написал файл спецификаций, и ваша работа - сделать все, чтобы все прошло успешно. Убедитесь, что вы знаете, что такое TDD / BDD.

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

И последнее, но не менее важное: получайте удовольствие! Собеседования могут быть интересными, если вы им позволите. Не переживайте, наслаждайтесь знакомствами с новыми людьми и разговорами о технологиях. Удачного интервью!