Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Работа Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6   вперед  Ctrl      все
 Re: Собеседование в Тинкофф  [new]
bga83
Member

Откуда: Город герой Ленинград
Сообщений: 31634
Vyatich
TurboLizard
есть массив целых чисел и число k, нужно найти в массиве два таких числа, сумма которых равнялась бы k, но интервьюер сразу обозначил момент, что обычный брутфорс с O(n^2) его не устроит, нужно что-нибудь быстрее.

массив упорядочен?
что-то мне подсказывает что его можно упорядочитоь быстрее чем O(n^2)
10 июн 21, 11:21    [22333650]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Alex Le
Member

Откуда:
Сообщений: 63
Для решения задачи можно задуматься над задействованием дополнительной памяти.
10 июн 21, 11:29    [22333654]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Alex Le
Member

Откуда:
Сообщений: 63
TurboLizard
попросил обозначить проблемы, которые я вижу в этом коде.

Я не так близок Java, но тут вижу следующее:
1) Запрос курсов через Rest. Полагаю это внутренний сервис, но нам нужно каждый раз нужен курс по одной валюте.
2) Расчёт комиссии в сервисе жёстко зашит.
3) Комиссия никак не привязывается к платежу.
4) В классе Fee нет методов доступа к private значениям.

Кто-то поправит и дополнит меня?

Сообщение было отредактировано: 10 июн 21, 11:38
10 июн 21, 11:46    [22333665]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 65953
Блог
bga83
что-то мне подсказывает что его можно упорядочитоь быстрее чем O(n^2)

Мне не доводилось встречаться с таким на собеседованиях, но всегда была забавна мысль сказать интервьюеру про сортировку за O(n) и провалить собеседование, поскольку интервьюер таких алгоритмов не знает.
10 июн 21, 12:24    [22333693]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
forumtrol23
Member

Откуда:
Сообщений: 3
softwarer,

и что это за алгоритм?
10 июн 21, 12:26    [22333696]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
bga83
Member

Откуда: Город герой Ленинград
Сообщений: 31634
softwarer
bga83
что-то мне подсказывает что его можно упорядочитоь быстрее чем O(n^2)

Мне не доводилось встречаться с таким на собеседованиях, но всегда была забавна мысль сказать интервьюеру про сортировку за O(n) и провалить собеседование, поскольку интервьюер таких алгоритмов не знает.
O(n*log(n)) помню из универа такие алгоритмы, но чтобы в общем случае с линейной сложностью
10 июн 21, 12:37    [22333703]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Кесарь
Member

Откуда:
Сообщений: 653
У нас вообще любят экзамены мало связанные с реальной деятельностью. Например экзамен на права. Хотя даже там вроде есть подвижки.

А тут коммерческие предприятия, а ведут себя как заправские чиновники.



Вот на кой хрен вам нужно, чтобы кандидат знал алгоритмы поисков и обходов дерева? Вы их каждый день пишете и переписываете? И предполагается, что кандидат занимался ровно этим же на предыдущей работе, что их все знает и помнит?
10 июн 21, 12:43    [22333710]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Кесарь
Member

Откуда:
Сообщений: 653
adreaaeej
Меня тут как то попросили написать подсчет высоты дерева.

Написал - не устроило - дескать не самый прозрачный и ясный способ.


А сколько времени дали на это эпическое деяние, сверх полезное для их бизнеса?
10 июн 21, 12:57    [22333728]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Кесарь
Member

Откуда:
Сообщений: 653
adreaaeej
Кесарь
пропущено...


А сколько времени дали на это эпическое деяние, сверх полезное для их бизнеса?


Нисколько

Просто надо было написать


А-ха-ха. Классика можно сказать. Очевидно они все ищут людей для участия в олимпиадах. Всегда хочется спросить в ответ: вы на рабочие задачи тоже по 5 минут выделяете?


Я ввел флажок - глубина рекурсии и в MutableInt сохранял максимум

Не устроило - типа плохое решение и ожидали что напишу так

int height(Node root) {
if (root == null) {
return 0;
}

int left = height(root.left);
int right = height(root.right);
return max(left,right);
}


Так они хотели что ли услышать заветные слова "обход по Селко"? Если я правильно понял то, что вы написали.
10 июн 21, 13:13    [22333747]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Кесарь
Member

Откуда:
Сообщений: 653
adreaaeej
Кесарь

Так они хотели что ли услышать заветные слова "обход по Селко"? Если я правильно понял то, что вы написали.


Они хотели найти человека - который будет писать код и думать также как тот кто интервьюировал.


Ну так я и говорю. Ищут для чего угодно и как угодно, не не для того чтобы работу работать.
10 июн 21, 13:23    [22333760]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Vyatich
Member

Откуда:
Сообщений: 3869
bga83
Vyatich
пропущено...

массив упорядочен?
что-то мне подсказывает что его можно упорядочитоь быстрее чем O(n^2)

а мне подсказывает, что на упорядоченном наборе решается за O(n). Поэтому я бы уточнил что там за массив был.
10 июн 21, 14:11    [22333826]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Кесарь
Member

Откуда:
Сообщений: 653
adreaaeej
Кесарь
пропущено...


Ну так я и говорю. Ищут для чего угодно и как угодно, не не для того чтобы работу работать.

Предыдущего напарника выжили - потому что писал код так что с крутым постоянно были конфликты (ну типа крутой считал что тот пишет сложный непонятный код).

Ну вот таким способом ищут того кто будет писать ясный и понятный код - чтобы подобного не повторялось

То есть работу делать надо - но ожидают что ее будут делать качественно.


А дать тестовое задание (на дом, по объёму чтобы на один вечер) они не догадались? Там бы сразу и было видно, какой именно код пишет кандидат.

А качественно работы не проверит ничто кроме испытательного срока.


И эти люди считают себя шибко умными, гнут пальцы и руководят другими... мда.
10 июн 21, 17:40    [22333980]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Кесарь
Member

Откуда:
Сообщений: 653
adreaaeej
На тестовом задании не получилось бы проверить "прогибаемость" кандидата

А так сразу было видно что я не прогибаюсь и разговор закончился


Ч.т.д. Проверяют не умение работу работать, а другие вещи.
10 июн 21, 17:51    [22333987]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 65953
Блог
bga83
O(n*log(n)) помню из универа такие алгоритмы, но чтобы в общем случае с линейной сложностью

n * log n - это для алгоритмов, работающих на основании сравнения. То есть тех, в которых можно ввести (и, как правило, вводят) функцию сравнения, получающую два значения и возвращающую больше-меньше-равно. Для алгоритмов, учитывающих внутреннюю структуру сравниваемых значений, можно добиться O(n), самый популярный метод - radix sort.

Собственно, ответ на этот вопрос довольно ярко отличает тех, кто учился по хорошим книгам, от тех, кто учился по хелпу к JDK.
10 июн 21, 18:53    [22334049]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
Кесарь
Member

Откуда:
Сообщений: 653
softwarer
Собственно, ответ на этот вопрос довольно ярко отличает тех, кто учился по хорошим книгам, от тех, кто учился по хелпу к JDK.



А вот и представитель обсуждаемого ранее множества любителей отбирать "на олимпиады"
10 июн 21, 18:57    [22334053]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 65953
Блог
adreaaeej
Стесняюсь спросить почему radix sort не присутствует в качестве имплементации std::sort ?

Уверен, если Вы спросите у автора этой замечательной библиотеки, получите соответствующий ответ.
10 июн 21, 19:03    [22334060]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
love_bach
Member

Откуда:
Сообщений: 822
Alex Le
Для решения задачи можно задуматься над задействованием дополнительной памяти.


словарь D с разбиением k
словарь R с индексами элементов из исходного массива, для определения кто кому соответствует, чтобы в сумме было k

1 проход для определения min из исходного массива - сложность O(n)
1 проход (от min до k) для построения D - сложность сопоставима с O(n)
2 прохода (прямой и обратный) по исходному массиву для построения R - сложность 2* O(n)

и по R результат (берем первый элемент, у него первый соответствующий) - сложность 2=const

итого сложность немного более 4*O(n)

вроде так

Сообщение было отредактировано: 10 июн 21, 20:38
10 июн 21, 20:42    [22334094]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
love_bach
Member

Откуда:
Сообщений: 822
Vyatich
TurboLizard
есть массив целых чисел и число k, нужно найти в массиве два таких числа, сумма которых равнялась бы k, но интервьюер сразу обозначил момент, что обычный брутфорс с O(n^2) его не устроит, нужно что-нибудь быстрее.

массив упорядочен?


и как это поможет?
11 июн 21, 10:03    [22334192]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
love_bach
Member

Откуда:
Сообщений: 822
love_bach
Alex Le
Для решения задачи можно задуматься над задействованием дополнительной памяти.


словарь D с разбиением k
словарь R с индексами элементов из исходного массива, для определения кто кому соответствует, чтобы в сумме было k

1 проход для определения min из исходного массива - сложность O(n)
1 проход (от min до k) для построения D - сложность сопоставима с O(n)
2 прохода (прямой и обратный) по исходному массиву для построения R - сложность 2* O(n)

и по R результат (берем первый элемент, у него первый соответствующий) - сложность 2=const

итого сложность немного более 4*O(n)

вроде так


словарь D в этом частном случае можно убрать, эффективно вычислить пару можно без него (k=5, A[i] = 2, пара = 5 - 2).
2 прохода не равнозначны по сложности, и O(n) - грубая оценка. 2-й проход - меньше сложность, так как R уже построен, и только требует уточнения.
если добавить досрочный выход, т.к. надо только 2 числа найти, то сложность еще меньше становится, в среднем в 2 раза, хотя, она и так линейная, даже для поиска всех таких пар
11 июн 21, 10:11    [22334196]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
love_bach
Member

Откуда:
Сообщений: 822
я бы такую задачу на собеседовании и близко бы не решил. хотя она не сложная, но требует напрячь мозг. в стрессовой ситуации собеседования я бы даже пузырьковую сортировку не вспомнил
11 июн 21, 10:15    [22334198]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
bga83
Member

Откуда: Город герой Ленинград
Сообщений: 31634
love_bach
Vyatich
пропущено...

массив упорядочен?


и как это поможет?
снижение сложности до линейной
11 июн 21, 10:36    [22334216]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
love_bach
Member

Откуда:
Сообщений: 822
bga83
love_bach
пропущено...


и как это поможет?
снижение сложности до линейной


я показал выше, что сложность и так линейная, не зависит от упорядоченности (хотя, упорядоченность её, конечно, снизит еще)

Сообщение было отредактировано: 11 июн 21, 10:30
11 июн 21, 10:38    [22334220]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
love_bach
Member

Откуда:
Сообщений: 822
adreaaeej
love_bach
я бы такую задачу на собеседовании и близко бы не решил. хотя она не сложная, но требует напрячь мозг. в стрессовой ситуации собеседования я бы даже пузырьковую сортировку не вспомнил


Вот еще задачка

Есть массив пар, в каждой паре первая чиселка - номер дня пребывания в отель человека, вторая чиселка продолжительность пребывания в отеле

ну то есть типа: [(1,123),(2,10),(3,50),(7,90),(8,200) ]

Человек 1 прибывл в день 1 и пробыл 123 дня
Человек 2 прибыл в день 2 и пробыл 10 дней
...

требуется найти номер дня - в котором в отеле жило максимальное число людей.


в каком контексте: SQL? или просто решить (не важно как)?
11 июн 21, 10:44    [22334228]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
love_bach
Member

Откуда:
Сообщений: 822
adreaaeej
love_bach
пропущено...


в каком контексте: SQL? или просто решить (не важно как)?


C++


"требуется найти номер дня" - пн, вт... - ?
11 июн 21, 10:56    [22334241]     Ответить | Цитировать Сообщить модератору
 Re: Собеседование в Тинкофф  [new]
love_bach
Member

Откуда:
Сообщений: 822
adreaaeej
love_bach
пропущено...


"требуется найти номер дня" - пн, вт... - ?


Считаем что сегодня 11 июня 2021 года и счет номеров дней ведем с этой даты


это надо сначала подумать

Сообщение было отредактировано: 11 июн 21, 10:55
11 июн 21, 11:00    [22334243]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6   вперед  Ctrl      все
Все форумы / Работа Ответить