Обложка: Технические задачи для интервью на должность веб-разработчика

Технические задачи для интервью на должность веб-разработчика

9
Александр Бунтов
Александр Бунтов

Senior Software Engineer компании СберМаркет

Отведите для технического интервью не более 50 минут.

Задачи на создание или отладку кода

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

1. Найдите ошибку в коде

def resolve(owner_id:)
  obj = Form.find_by!(owner_id)
  if obj.delete
    { ok: true }
  else
    { errors: obj.errors }
  end
rescue StandardError => e
  GraphQL::ExecutionError.new("Error: #{e}. Form not remove.")
end

Решение задачи

Здесь приведены методы ActiveRecord. Метод .find_by! вернёт первый объект из базы без ключа. Так как бесключевой метод не экранирует SQL-запрос, появляется возможность сделать sql инъекцию. Это делает код небезопасным и уязвимым. Подробнее можно узнать про SQL Injection в Ruby on Rails на этой странице.

Вторая ошибка в применении метода .delete, он удаляет запись без вызова коллбеков. Здесь необходимо заменить его на метод .destroy, чтобы вновь включить работу коллбеков.

2. Опишите, как работает этот код

-> (a) {p a}["Lambda worked"]

Решение задачи

Cоздается Lambda, которая принимает единственный параметр a. Этот параметр выводится с помощью команды p, которая вызывает и передает атрибут строку "Lambda worked" с помощью [], где [] — это сокращённый вариант метода call.

3. В чём разница между двумя нижеприведёнными методами?

string = 'hello'
Разница между string += ' World'и string << ' World'

Решение задачи

Оператор += повторно инициализирует переменную новым значением, поэтому a += b эквивалентно a = a + b. Может показаться, что += изменяет значение, на самом деле, он создает новый объект и указывает старую переменную на вновь созданный объект. Разница имеет значение для производительности.

Задачи по структурам данных и алгоритмам

Для потенциального сотрудника в компании крупного бизнеса подойдут задачи по структурам данных и алгоритмам. Если кандидат умеет преобразовать алгоритм в чистый и структурированный код в хорошем стиле программирования, то, скорее всего, он будет успешно решать несколько задач одновременно. Проще говоря, он умён. А умные люди создают качественные и сложные продукты.

1. Реализуйте алгоритм игры «Тайный Санта (Secret Santa)»

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

Решение

Стоит отметить, что у этой задачи есть несколько решений. Рассмотрим один из вариантов.

Для начала представим, что жеребьёвка — это рандомный список дарителей и получателей. Отобразим его в виде Hash, где ключи — это дарители, а значения — это получатели.

Возникает вопрос: как распределить участников игры, чтобы они не смогли выбрать самих себя? Для этого нужно взять список дарителей и сместить на один шаг, то есть тот, кто в списке был первым дарителем, станет последним получателем.

Так выглядит готовый список. Мы также решили проблему с нечётным и четным количеством участников, чтобы все смогли получить свой подарок.

list = {
	'alex1' => 'alex2',
	'alex2' => 'alex3',
	'alex3' => 'alex4',
	'alex4' => 'alex5',
	'alex5' => 'alex1'
    }

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

class Player
  attr_accessor :recipient

  attr_reader :email, :name
  def initialize(email)
    @email = email
    @recipient = recipient
  end
end

class Draw
  def initialize(players)
    @players = players
  end
end

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

RSpec.describe Draw do
  it 'make a list' do
    players = (1..5).map { |i| Player.new("alex#{i}@mail.com") }

    draw = Draw.new(players)
	expected_list = { 
	                  'alex1@mail.com' => 'alex2@mail.com',
					  'alex2@mail.com' => 'alex3@mail.com',
   					  'alex3@mail.com' => 'alex4@mail.com',
					  'alex4@mail.com' => 'alex5@mail.com',
					  'alex5@mail.com' => 'alex1@mail.com'
					}
	expect(draw.assign_recipients).to eq(expected_list)
  end
end

Теперь мы можем реализовать логику методом assign_recipients :

class Draw
  attr_accessor :list
  def initialize(players)
  	@players = players.shuffle!
  	@list = {}
  end

  def assign_recipients
    # Пройдемся по всем участникам и назначим им получателей подарка
    0..@players.length.times do |i|
      if @players[i+1] # Если есть следующий участник
        # то назначаем дарителю следующего из списка получателем
        @players[i].recipient = @players[i+1] 
      else
        # Если список закончился назначаем получателя
        # первого из списка дарителей. 
        @players[i].recipient = @players[0]
      end
  	  list[@players[i].email] = @players[i].recipient.email
    end
  	# возвращаем список
  	list
  end
end

Теперь следует подумать, как реализовать рандомайзер, то есть как «встряхнуть шляпу» и применить логику привязки даритель-получатель. Для этого возьмём массив участников и применим к нему метод .shuffle!, после чего назначим получателей.

class Draw
  attr_accessor :list
  def initialize(players)
    @players = players.shuffle! # встряхнуть шляпу
	@list = {}
  end
...

Теперь запущенный тест упадёт с ошибкой. Чтобы это исправить, применим mock для метода .shuffle! и озеленим тест.

RSpec.describe Draw do
  it 'make a list' do
    players = (1..5).map { |i| Player.new("alex#{i}@mail.com") }
    # Мок для метода shuffle!
	allow(players).to receive(:shuffle!).and_return(players)

    draw = Draw.new(players)
	expected_list = { 'alex1@mail.com' => 'alex2@mail.com',
					  'alex2@mail.com' => 'alex3@mail.com',
					  'alex3@mail.com' => 'alex4@mail.com',
					  'alex4@mail.com' => 'alex5@mail.com',
					  'alex5@mail.com' => 'alex1@mail.com'
				     }
    expect(draw.assign_recipients).to eq(expected_list)
  end
end

В итоге мы получим такой код:

require 'rspec/autorun'

class Player
  attr_accessor :recipient
  attr_reader :email

  def initialize(email)
    @email = email
    @recipient = recipient
  end
end

class Draw
  attr_accessor :list
  def initialize(players)
    @players = players.shuffle!
    @list = {}
  end
	
  def assign_recipients
    # Пройдемся по всем участникам и назначим им получателей подарка
    0..@players.length.times do |i|
      if @players[i+1] # Если есть следующий участник
        # то назначаем дарителю следующего из списка получателем
        @players[i].recipient = @players[i+1] 
      else
        # Если список закончился назначаем получателя
        # первого из списка дарителей. 
        @players[i].recipient = @players[0]
      end
  	  list[@players[i].email] = @players[i].recipient.email
    end
  	# возвращаем список
  	list
  end
end

RSpec.describe Draw do
  it 'make a list' do
    players = (1..5).map { |i| Player.new("alex#{i}@mail.com") }
		# Мок для метода shuffle!
		allow(players).to receive(:shuffle!).and_return(players)

    draw = Draw.new(players)
    expected_list = { 'alex1@mail.com' => 'alex2@mail.com',
				      'alex2@mail.com' => 'alex3@mail.com',
					  'alex3@mail.com' => 'alex4@mail.com',
					  'alex4@mail.com' => 'alex5@mail.com',
					  'alex5@mail.com' => 'alex1@mail.com'
					}
    expect(draw.assign_recipients).to eq(expected_list)
  end
end

Анализ сложности алгоритма

Метод shuffle! реализует генерацию случайной перестановки, применяя алгоритм Фишера-Йетса. Он имеет временную сложность равную O(n) и константную пространственную сложность.

Также в решении задачи использовался один цикл, который проходит по всему списку участников. В этом же цикле мы заполняли Hash дарителей и получателей. Отсюда следует, что временная сложность и пространственная сложность равно O(n) ,где n — это количество участников игры.

2. Проверьте сортировку слов по заданному алфавиту

Предположим, что в других языках также используются строчные английские буквы, но, возможно, в другом порядке. Порядок алфавита — это некая система расположения строчных букв. Учитывая последовательность слов, написанных на чужом языке, и порядок в алфавите, нужно вернуть true, когда данные слова лексикографически отсортированы на этом языке.

Примеры:

# Input: words = ["hello","diary"], order = "hdabcefgijlkmnopqrstuvwxyz"
# Output: true

Поскольку в этом языке перед буквой d стоит буква h, последовательность букв в заданном алфавите уже отсортирована.

# Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
# Output: false

Поскольку в этом языке d стоит после l , то words[0]> words[1], следовательно последовательность не отсортирована.

# Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
# Output: false

Первые три символа «app» совпадают, а второе слово короче по количеству символов. Согласно лексикографическим правилам, «apple» больше «app», потому что l больше , где определяется как пробел, который меньше любого другого символа.

Решение

Хорошим тоном считается, если кандидат напишет тесты в первую очередь:

require 'rspec/autorun'

def is_alien_sorted(words, order)
end

RSpec.describe self do
  context 'is alien sorted' do
    it 'return true' do
      words, order = [["hello","diary"], "hdabcefgijlkmnopqrstuvwxyz"]
      expect(is_alien_sorted(words, order)).to be true
    end

    it 'return true' do
      words, order = [["app","apple"], "abcdefghijklmnopqrstuvwxyz"]
      expect(is_alien_sorted(words, order)).to be true
    end

    context 'return false' do
      it 'when sequence is unsorted' do
        words, order = [["word","world","row"],"worldabcefghijkmnpqstuvxyz"]
        expect(is_alien_sorted(words, order)).to be false
      end
      it 'when matching first chars' do 
        words, order = [["apple","app"], "abcdefghijklmnopqrstuvwxyz"]
        expect(is_alien_sorted(words, order)).to be false
      end
    end
  end
end

Далее необходимо создать словарь с помощью ассоциативного массива Hash или просто массива:

require 'rspec/autorun'

def is_alien_sorted(words, order)
  # Создание словаря с помощью Hash
  dic = {}
  order.chars.each_with_index do |ch,i|
	dic[ch] = i
  end
end
  
# Создание словаря с помощью метода chars, возвращает массив с символами

#def is_alien_sorted(words, order)
#  dic = order.chars
#end

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

(0...words.length - 1).each do |i| # проход по словам в цикле
  next if words[i] == words[i + 1] # закрываем edge case если слова
                                   # рядом дублируются
    (0...words[i].length).each do |j| # проход по буквам в слове
    
      return false if j >= words[i + 1].length # мы не находим несоответствия, 
      # мы проверяем лексикографический кейс (apple > app)

      if words[i][j] != words[i + 1][j]
        if dic[words[i][j]] > dic[words[i + 1][j]]
          return false
        else
          # Если мы найдем первую отличающуюся букву и 
          # условия сортировки между двумя буквами будут правильными
          #	Мы выйдем из текущего цикла и проверим слудующую пару слов.
          break
        end
      end
    end
  end

После этого кандидат должен ответить с какой сложностью выполняется алгоритм.

Анализ сложности выполнения алгоритма

Временная сложность:

  1. Создание словаря для сохранения порядка каждой буквы занимает O(n) времени.
  2. В первом цикле мы сначала перебираем слова, а во вложенном — проверяем буквы этого слова. Временная сложность займет O(m), где m — это количество всех букв в словах. Таким образом, временная сложность составляет O (m+n). Но в словаре всегда 26 букв, в примерах меняется лишь порядок. Следовательно, временная сложность O(m), где m — это количество всех букв в словах.

Пространственная сложность:

Мы используем только одну дополнительную структуру данных — это Hash или массив, где хранится порядок букв. Поскольку в словаре только 26 букв и их длина неизменна, мы имеем константную пространственную сложность.

Итоговый вид решения задачи:

require 'rspec/autorun'

def is_alien_sorted(words, order)
  # Создание словаря с помощью Hash
  dic = {}
  order.chars.each_with_index do |ch, i|
    dic[ch] = i
  end

  (0...words.length - 1).each do |i| # проход по словам в цикле
    next if words[i] == words[i + 1] # закрываем edge case если слова
                                     # рядом дублируются

    (0...words[i].length).each do |j| # проход по буквам в слове
      return false if j >= words[i + 1].length # мы не находим несоответствия,
      # мы только проверяем лексикографический кейс (apple > app)

      if words[i][j] != words[i + 1][j]
        if dic[words[i][j]] > dic[words[i + 1][j]]
          return false
        else
          # Если мы найдем первую отличающуюся букву и 
          # условия сортировки между двумя буквами будет правильной
          #	Мы выйдем из текущего цикла и проверим слудующую пару слов.
          break
        end
      end
    end
  end
  true
end

RSpec.describe self do
  context 'is alien sorted' do
    it 'return true' do
      words, order = [["hello", "diary"], "hdabcefgijlkmnopqrstuvwxyz"]
      expect(is_alien_sorted(words, order)).to be true
    end

    it 'return true' do
      words, order = [["app", "apple"], "abcdefghijklmnopqrstuvwxyz"]
      expect(is_alien_sorted(words, order)).to be true
    end

    context 'return false' do
      it 'when sequence is unsorted' do
        words, order = [["word", "world", "row"], "worldabcefghijkmnpqstuvxyz"]
        expect(is_alien_sorted(words, order)).to be false
      end
      it 'when matching first chars, ' do
        words, order = [["apple", "app"], "abcdefghijklmnopqrstuvwxyz"]
        expect(is_alien_sorted(words, order)).to be false
      end
    end
  end
end

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

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации

Что думаете?