Зачем я всё это написал? Дело в том, что я давно уже работаю программистом. Прошёл множество собеседований и сам провёл не мало. Видел самых разных разработчиков, наблюдал за ними… И сделал для себя некоторые выводы.
Так как многие спрашивают моего мнения, я решил написать его. Не чтобы кому-то навязать, просто, чтобы не рассказывать много раз.
Конечно, задачи сильно зависят от того, на какую ставку вы идёте и чем предполагаете заниматься. Но поверьте, если вашему работодателю достаточно того, что вы умеете плести цепочки вызовов на jQuery, знаете HTML, или SQL, то задумайтесь, — возможно, вас ждёт скучноватая работёнка.
Если же вашему работодателю не так уж важно на каком языке вам удобней выражать свои мысли. Если он больше обращает внимание на вашу эрудицию, — старайтесь получить эту работу. Вас, скорее всего, ждут разнообразные и интересные задачи.
Ладно, оставим разговоры. Сперва приведу задачи, а потом решения. Вы можете не проматывать до них и решить задачки самостоятельно. Если вы уложитесь в час, то ждём вас не собеседование ,-) Приступим.
У вас есть массив чисел. Напишите три функции, которые вычисляют сумму этих чисел: с for-циклом, с while-циклом, с рекурсией.
Напишите функцию, которая создаёт комбинацию двух списков таким образом:
[1, 2, 3] (+) [11, 22, 33] -> [1, 11, 2, 22, 3, 33]
Вычислите первые 100 чисел Фибоначчи. (Напишите код.)
У вас есть массив чисел, составьте из них максимальное число. Например:
[61, 228, 9] -> 961228
У вас есть девять цифр: 1, 2, …, 9. Именно в таком
порядке. Вы можете вставлять между ними знаки «+»,
«-» или ничего. У вас будут получаться
выражения вида 123+45-6+7+89. Найдите все
из них, которые равны 100.
Постарайтесь решить эти задачи за час.
А теперь ответы
Я буду приводить решения на Python3. Кроме того, это те решения, которые можно написать за час. В чём-то они не идеальны, это повод поговорить и, возможно, взять дополнительное время.
Код:
def sum_for_loop(a):
s = 0
for x in a:
s += x
return s
def sum_while_loop(a):
s = 0
n = len(a)
while n:
n -= 1
s += a[n]
return s
def sum_recursive(a):
if len(a) == 0:
return 0
return a[0] + sum_recursive(a[1:])
if __name__ == '__main__':
t = [5, 3, 4, 1, 7]
for f in (sum_for_loop, sum_while_loop, sum_recursive):
print(f(t))
Конечно, если вы рассказывайте про Python, то
имеет смысл сказать и про функцию sum или reduce.
Если речь идёт о других языках, будет не лишним
упоминать возможности их библиотек. Но здесь
интересно ваше решение.
В первой функции говорить особо не о чем. Спасибо Python.
Во втором случае уже можно порассуждать надо ли разрушать массив (вынимая из него элементы). Или пойти по тому пути, который выбрал я. Тут тоже можно обратить внимание на то, как эта функция невыгодно выглядит по сравнению с рекурсивной. Есть множество мест, где можно допустить ошибки.
Рекурсивная функция прекрасна.
Код:
def combine_lists(a, b):
len_a = len(a)
len_b = len(b)
if len_a < len_b:
limit = len_a
else:
limit = len_b
i = 0
r = []
while i < limit:
r.append(a[i])
r.append(b[i])
i += 1
return r
if __name__ == '__main__':
a = ['a', 'b', 'c']
b = ['A', 'B', 'C', 'D']
print(repr(combine_lists(a, b)))
Тут нет ничего необычного, но можно порассуждать
о библиотеках. Если речь про Python можно
предложить решение типа sum(zip(a, b), ()).
Код:
def fibonacci(n=10, a=0, b=1):
yield a
yield b
n -= 2
while n > 0:
c = a + b
a = b
b = c
yield c
n -= 1
if __name__ == '__main__':
for n in fibonacci(100):
print(n)
Я реализовал итератор. Этим можно было бы показать, что вы про них знаете и здесь их использование уместно.
Тут уже можно поговорить и о языке. Если ваш язык не Python, то, возможно, вам следует задуматься о типе и битности чисел, так как сотое число содержит 68 бит.
Кроме того, есть способ расчёта чисел Фибоначчи путём возведения в степень матриц. Он позволяет не рассчитывать все числа последовательности. Возможно, от вас хотят именно его.
Код (не правильный):
join_to_biggest = lambda a: int(''.join(sorted(map(str, a), reverse=True)))
if __name__ == '__main__':
print(join_to_biggest([501, 2, 1, 80, 9]))
Эта задача больше всего зависит от языка. Я её решил, используя возможности Python.
upd:
Этот код провисел на сайте года три, пока, некто Роман Парпалак не указал мне на ошибку.
Я сохраню интригу и не буду говорить в чём ошибка. Но код, дающий правильный результат я всё же приведу:
join_to_biggest = lambda x: ''.join(sorted(
map(str, x),
cmp=lambda x, y: cmp(y + x, x + y)
))
Да, тут Python2. В Python3 придётся сделать что-то вроде этого:
class smart_key(object):
def __init__(self, obj):
self.obj = obj
def __lt__(self, other):
return (other.obj + self.obj) < (self.obj + other.obj)
join_to_biggest = lambda x: ''.join(sorted(
map(str, x),
key=smart_key
))
Зачем я сохранил неправильный код? По нескольким причинам.
Во-первых, удалить его было бы не честно с моей стороны. Я же декларировал, что решу задачи за час. За указанное время я дал именно это решение.
Во-вторых, чтобы читатель мог поискать ошибку, подумать, нет ли ошибок в его решении…
В-третьих, чтобы подчеркнуть, что все могут ошибаться. Решение задач на время всегда будет сопровождаться ошибками. Недавно я проходил очень интересное интервью. Будет время, — напишу про него отдельно. Но меня в нём поразило то, что олимпиадных задач не было, и спешки тоже не было. И мне кажется, что эти люди действительно хорошо понимают, кого ищут, и выстраивают интервью адекватно своему пониманию. Но это отдельная интересное история.
А тут я лишь скажу: спасибо, Роман. Интересно было бы узнать ваш вариант решения.
Тут есть простор для творчества. Мой код таков:
def all_combinations(a):
if len(a) <= 1:
yield a
else:
head = ''
tail = list(a)
while len(tail) > 0:
head += tail.pop(0)
for s in all_combinations(tail):
yield [head] + s
def all_signs(n):
if n == 0:
yield ()
else:
for tail in all_signs(n-1):
for s in '+-':
yield (s,) + tail
def perform_operations(nums, signs):
nums = list(map(int, nums))
result = nums.pop(0)
n = 1
for s in signs:
if s == '+':
result += nums.pop(0)
if s == '-':
result -= nums.pop(0)
n += 1
return result
for numbers in all_combinations(tuple(map(str, range(1, 10)))):
#print(numbers)
for signs in all_signs(len(numbers) - 1):
#print(signs)
summ = perform_operations(numbers, signs)
if summ == 100:
print(
''.join(map(
lambda x: ''.join(x),
zip(numbers, signs)))
+ numbers[-1])
Мне кажется, в таком виде его проще всего и
писать и читать и тестировать. Тут у меня три функции:
all_combinations — итератор, который выдает все
числа для операций (в терминах задачи: вставляет пустые места);
all_signs — выдаёт все возможные сочетания знаков
+ и - заданной длинны (для единообразия, это тоже
итератор с рекурсией);
perform_operations — выполняет операции.
Тут, конечно, просится решение, избавленное от if-ов и кодирования операций с помощью символов. Но это решение будет более громоздким, о нём можно рассказать, но и писать, и читать его дольше. Лично я вышел бы за рамки отведённого часа.
Наверняка вам по душе будет какое-то иное решение. Мой пример — лишь одна из возможных реализаций.
Где можно взять таких задачек? Можно начать с Project Euler. Там, правда, немного более математизированные задачки, но это и не плохо. И сложность задач расчёт очень быстро. Я решил восемьдесят.
Если вы знаете ресурсы с хорошими задачками — пожалуйста напишите мне.
upd: В моём решении пятой задачи Мерзляков Александр из Уфы нашел неточность. Спасибо! Я поправил. Получается, что я на эти решения потратил больше часа.
