Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 51
Саша, расскажите за бабосы? Сколько дали на старт… ну и прочие мелкие радости — какое меню в столовой как часто пользуетесь прачечной. Насколько ситуация описанная в сериале Silicon Valley соответствует реальности на местности.
Никто вам этого не расскажет, во всех крупных компаниях, насколько я знаю, такая информация относится к особо конфиденциальной и за её разглашение легко лишиться работы.
Все верно, но это касается точных деталей. Ориентировочно нормальные люди всегда говорят :)
Недавно смотрел Adam Ruins Everything про США, так там обсуждалось что-то вроде, что скрытие уровня зарплаты ведет к дискриминации и запрещать ее озвучивать — незаконно. Разве не так?
Ой, я вас умоляю.
j.mp/salaries-list
j.mp/salaries-list
Про деньги без проблем находится на GlassDoor, зарплаты в гугл. Моя позиция Resident Engineer, зп чуть выше потому что в Калифорнии, а там средняя по разным штатам.
Когда полный оффер получаешь, дополнительно стоки дают, об этом тоже на гласдоре есть.
Мелких радостей очень много: бесплатная хорошая еда, например, в столовых в любое время — для меня самое главное. Вообще про это я как нибудь отдельный пост напишу.
Когда полный оффер получаешь, дополнительно стоки дают, об этом тоже на гласдоре есть.
Мелких радостей очень много: бесплатная хорошая еда, например, в столовых в любое время — для меня самое главное. Вообще про это я как нибудь отдельный пост напишу.
Насчет первого не соглашусь. Тут я получаю BS Computer Science (бакалавр короче) и меня пригласили. Хотя интервью я завалил :) Подучу алгоритмы, и попробую ещё раз через годик.
Вопрос был таким:
Есть сортированный массив с цифрами, которые могут повторяться. Найти число которое повторяется N/4 (где N это размер массива) раз. Я довольно быстро дал решение в polynomial time (n^2). Но мне сказали это сделать в constant time. Там то я и не смог найти решение :)
А так, я их зацепил своим резюме. Довольно обычное резюме со всеми скилами и опытом, которыми я владею. Реферал не обязателен, но с ним 100% шанс получить интервью
Вопрос был таким:
Есть сортированный массив с цифрами, которые могут повторяться. Найти число которое повторяется N/4 (где N это размер массива) раз. Я довольно быстро дал решение в polynomial time (n^2). Но мне сказали это сделать в constant time. Там то я и не смог найти решение :)
А так, я их зацепил своим резюме. Довольно обычное резюме со всеми скилами и опытом, которыми я владею. Реферал не обязателен, но с ним 100% шанс получить интервью
Задачка довольно простецкая — делаете проход и складываете количество цифр листом в хешмеп все это делается за O(n) потом когда узнаете размер массива то вытягиваете свой лист одним заходом.
Я по приколу обычно для разогрева когда ищу новую работу прохожу интервью в Гугл всего получилось три раза.
Я по приколу обычно для разогрева когда ищу новую работу прохожу интервью в Гугл всего получилось три раза.
Решу быстрее Вас в три раза и без хешмапов. Ключевое слово в условии — Сортированный массив цифр…
Интересная задачка. По идее, зная длину массива, можно решить в один проход, но сложность алгоритма все равно не будет O(1)…
А хотите О(1)? Так как там одинаковых чисел четверть массива, то достаточно проверить всего 8 чисел — из них пару раз попадем в участок с одинаковыми.
Да, но я бы взял тысячу или десять тысяч, чтобы точно убедиться что одинаковых чисел не меньше и не больше N/4. Все равно же будет O(1), даже если проверим миллион, так как от N это не зависит.
То есть, мы разбиваем массив на 8 равных частей и смотрим, есть ли в парах соседних точек одинаковые элементы (и при этом следующие граничные точки не содержат это же значение)? Но при этом, если я правильно понимаю, мы можем только гарантировать, что найденная последовательность имеет длину >= N/8, но не можем гарантировать, что в найденной последовательности ровно N/4 чисел.
Возможно, я в чем-то ошибаюсь.
И даже если рассмотреть случай, когда точек разбиения можно взять больше (миллион! :), то, с одной стороны, это все равно только повышает вероятность нахождения правильного решения, а с другой стороны такая зависимость количества точек разбиения от возможной длины массива уже не может рассматриваться как решение с константной сложностью. То есть, грубо говоря, на каждый вариант разбиения на N точек можно найти массив с кол-вом элементов >= 8 * N.
Возможно, я в чем-то ошибаюсь.
И даже если рассмотреть случай, когда точек разбиения можно взять больше (миллион! :), то, с одной стороны, это все равно только повышает вероятность нахождения правильного решения, а с другой стороны такая зависимость количества точек разбиения от возможной длины массива уже не может рассматриваться как решение с константной сложностью. То есть, грубо говоря, на каждый вариант разбиения на N точек можно найти массив с кол-вом элементов >= 8 * N.
Чтобы найти абсолютно точно, можно использовать следующий алгоритм:
1. Разбиваем на N/1000 элементов, считаем кол-во одинаковых последовательностей так чтобы они были от 248 до 250, При 250 проверяем ещё два элемента с краев и заканчиваем алгоритм, O(1)
2. Бинарным поиском находим в отрезке N/1000 первый элемент перед последовательностью, O(logN/1000)
3. Проверяем один элемент с N/4 от найденного в (2), O(1)
Итого, получается пусть и не константное время, но очень близкое к нему O(log N).
1. Разбиваем на N/1000 элементов, считаем кол-во одинаковых последовательностей так чтобы они были от 248 до 250, При 250 проверяем ещё два элемента с краев и заканчиваем алгоритм, O(1)
2. Бинарным поиском находим в отрезке N/1000 первый элемент перед последовательностью, O(logN/1000)
3. Проверяем один элемент с N/4 от найденного в (2), O(1)
Итого, получается пусть и не константное время, но очень близкое к нему O(log N).
int findX(int[] A) {
int x, n = 0;
for(int i = 1; i < 8; ++i)
if(A[i*N/8] == A[(i-1)*N/8] && (i == 7 || A[i*N/8] != A[(i+1)*N/8]))
{
x = A[i*N/8]; n += 1;
}
if (n == 0) throw new Exception("No such element");
if (n > 1) throw new Exception(" Too many candidates");
return x;
}
Вот такой вот алгоритм за константу. Сначала ищем все подпоследовательности длиннее N/8 и короче 3N/8. Если такая всего одна, а мы знаем что точно есть одна подпоследовательность длинной точно N/4 — то это она и есть. А если похожих больше — ну не судьба значит за константу.
Если я правильно понимаю, данный алгоритм находит действительно одну последовательность, но не может гарантировать, что ее длина равна ровно N/4 элементов. Безусловно, мы можем дополнить условие задачи тем, что у нас имеется только один элемент в массиве, для которого выполняется условие, что он встречается от N/8 до 3N/8 раз, и других таких элементов в массиве нет. В этом случае согласен с вашим решением.
Вроде в условии не сказано, что число должно встречаться РОВНО N/4. Тогда за константу можно найти ВСЕ такие последовательности, сколько бы их не было. Максимум все 4 )
===
Найти число которое повторяется N/4 (где N это размер массива) раз.
===
Да, нет слова «РОВНО», но, по-моему, оно тут и не нужно, так как и без него условие очевидно.
Найти число которое повторяется N/4 (где N это размер массива) раз.
===
Да, нет слова «РОВНО», но, по-моему, оно тут и не нужно, так как и без него условие очевидно.
Условие не очевидно, есть два варианта: 1) известно что такое число точно существует в массиве 2) такое число может существовать, а может и не сушествовать. И решения будет различны в этих случаях, в первом варианте возможно решение за константное время в 99.9% случаев, во втором не сумел придумать решения быстрее чем O(log N)
=) Даже если есть хоть 1 возможный вариант из миллиарда, когда алгоритм будет работать не по «константной» схеме, значит, он «неконстантный». Потому что ты не можешь гарантировать константное время его работы для любых произвольных данных. Это как если бы ты в произвольном алгоритме сортировки сначала всегда проверял все пары соседних элементов, а не находится ли входной массив уже в отсортированном порядке. Такие случаи вполне могут быть. Но это не значит, что сложность алгоритма сортировки станет считаться как O(N), верно?
Совершенно не верно, есть такие понятие как вычисли́тельная сложность алгоритма в худшем, наилучшем и среднем случае. Если есть хоть 1 возможный вариант из миллиарда, когда алгоритм будет работать не по «константной» схеме, значит, он «неконстантный» в худшем случае, но константный в среднем.
Многие современные алгоритмы в худшем случае имеют очень высокую сложность, но зато в среднем вполне нормальную и учитывая редкость этого самого худшего случая, их активно используют. Банально большинство хештаблиц в худшем случае имеют дают доступ к элементу со сложностью N (полный перебор), но так как это очень редкий случай, а в среднем сложность около O(1) на них построены все базы данных.
Многие современные алгоритмы в худшем случае имеют очень высокую сложность, но зато в среднем вполне нормальную и учитывая редкость этого самого худшего случая, их активно используют. Банально большинство хештаблиц в худшем случае имеют дают доступ к элементу со сложностью N (полный перебор), но так как это очень редкий случай, а в среднем сложность около O(1) на них построены все базы данных.
Кстати, буду признателен, если вы приведете алгоритм, который в 99.9% будет иметь «константное» решение для случая, когда заранее известно, что некоторый элемент точно присутствует в массиве и встречается там N/4 раз. Просто почему я сомневаюсь в этом. Для того, чтобы алгоритм обеспечивал чаще константное решение, необходимо после разбиения на фиксированное кол-во точек и поиске цепочки подходящей длины, проверять только соседние точки (без переборов и двоичных поисков). Повысить вероятность этого можно только увеличением кол-ва точек разбиения (вырожденный случай, дающий 100% вероятность — когда количество точек разбиения равно размерности самого массива). В этом случае вероятность выше, но тогда нельзя сказать, что алгоритм «константен», потому как с увеличением размерности массива придется всегда увеличивать кол-во точек разбиения для получения высокой вероятности. А если число точек разбиения не увеличивать, то, соответствнно, и вероятность будет значительно ниже. Но я подожду вашего решения.
Смотрите, тут все зависит от распределения остальных чисел, но представим что оно более или менее случайно, то есть у нас есть один массив чисел N/4 и M массивов чисел со случайными длинами от 0 до 3N/4. Вероятность наличия последовательности M, которая больше или меньше N/4 на 1% длины пусть будет 1%, на 0.1% длины — 0.1% и т.д. (само значение вероятности не так важно, важен принцип). Тогда разделив все последовательность на 2000 точек по длине, мы сможем найти потенциальную последовательность и с вероятностью 0.1% она будет только одна. Разделив на 20 тыс — вероятность будет 0.01% и т.д. Само значение N тут роли не играет.
Проблема будет только в том что кто-то будет сознательно готовить плохие данные добавляя одну последовательность вроде N/4+1 или N/4-1, тогда придется один из концов искать быстрым поиском с log N. Но это уже из раздела обмануть алгоритм плохими данными. При любом относительно случайном распределении длин такое маловероятно.
Проблема будет только в том что кто-то будет сознательно готовить плохие данные добавляя одну последовательность вроде N/4+1 или N/4-1, тогда придется один из концов искать быстрым поиском с log N. Но это уже из раздела обмануть алгоритм плохими данными. При любом относительно случайном распределении длин такое маловероятно.
Честно говоря, не совсем понял, откуда вы взяли все эти цифры, в частности 2000 точек и связанные с ними 0.1%. Ну ладно, не суть. Давайте по-простому. У нас есть массив из 80 точек (цифра взята просто для удобства последующего деления). В нем есть некоторая последовательность из 20 одинаковых элементов. Предположим, мы решили взять шаг разбиения в 10 элементов. Таким образом, наш массив поделен на 8 равных частей, каждая часть состоит из 10 точек. Мы перебираем пары соседних точек и смотрим, чтобы элементы массива в них имели одинаковые значения, а соседние с ними элементы были не равны им. Найдя такую пару точек мы можем предположить, что в этом месте расположена последовательность нужной нам длины. Искать реальные концы последовательности мы не можем, так как в этом случае будет нарушено требование «константной» временной сложности. Фактически же длина найденной нами последовательности может быть в дианазоне от 10 до 30 точек (то есть, от N/8 до 3N/8). И вероятность нашего «угадывания» составляет 1/20 (1 вариант из 20 возможных) или 5%.
Конечно, мы можем разделить массив с шагом не 10, а, например, 5, получая не 8, а 16 точек разбиения. В этом случае, вероятность угадывания составит уже 10%. Таким образом, увеличивая количество точек разбиения мы повышаем вероятность правильного ответа. Но в этом случае, как я уже писал ранее, наш алгоритм приобретает все более «линейную» сложность., так как для получения требуемой вероятности правильного ответа нам нужно будет постоянно увеличивать количество точек разбиения при увеличении количества элементов входного массива.
Ну и по поводу «плохих» данных. Разумеется, во входном массиве могут быть как N/4+1, так и N/4-1, N/4-2 и прочие последовательности указанных длин. В общем, любые последовательности длины от N/8 до 3N/8 включительно. Ничего противоестественного в таких наборах нет и говорить об исключительности этой ситуации весьма странно, на мой взгляд.
Конечно, мы можем разделить массив с шагом не 10, а, например, 5, получая не 8, а 16 точек разбиения. В этом случае, вероятность угадывания составит уже 10%. Таким образом, увеличивая количество точек разбиения мы повышаем вероятность правильного ответа. Но в этом случае, как я уже писал ранее, наш алгоритм приобретает все более «линейную» сложность., так как для получения требуемой вероятности правильного ответа нам нужно будет постоянно увеличивать количество точек разбиения при увеличении количества элементов входного массива.
Ну и по поводу «плохих» данных. Разумеется, во входном массиве могут быть как N/4+1, так и N/4-1, N/4-2 и прочие последовательности указанных длин. В общем, любые последовательности длины от N/8 до 3N/8 включительно. Ничего противоестественного в таких наборах нет и говорить об исключительности этой ситуации весьма странно, на мой взгляд.
В любом случае это не const, а O(n). Что-то я не вижу решения за константу, даже у PapaBubaDiop оно линейное.
Оу оу оу. Извиняюсь, да я дал им linear time O(n) с hash tables. Довольно стыдно давать polynomial time в такой задаче для четверокурсника :D
Я потом у интервьювера спросил правильный ответ: Он быстро рассказал, что нужно модифицировать binary search, и оно каким-то образом будет показывать первую ячейку повторяющейся цифры и последнюю (и просто вычетаем последнюю от первой и сравниваем c N/4). Он не вдавался в детали, но примерно так. Это занимает constant time
Я потом у интервьювера спросил правильный ответ: Он быстро рассказал, что нужно модифицировать binary search, и оно каким-то образом будет показывать первую ячейку повторяющейся цифры и последнюю (и просто вычетаем последнюю от первой и сравниваем c N/4). Он не вдавался в детали, но примерно так. Это занимает constant time
За constant time — не получится (будет интересно, если переубедите). Можно сделать, чтоб было минимум O(log n) и максимум O(n), с константной дополнительной памятью.
Получится, ключевое слово число повторяется N/4 раз, то есть если размер массива 1 млн. элементов, то таких чисел 250 тыс. и они отсортированы. Алгоритм: делим массив на тысячу частей, считаем кол-во одинаковых чисел, то число которое повторится в нашем массиве от 248 до 250 раз и будет с большой вероятностью искомым. O(1).
Да, соглашусь. Вот почему я в гугле и не работаю. Можно, наверное, взять 8 равноудалённых индексов в массиве. Там где значения совпадают — там и ответ. Так что да, О(1).
если в массиве есть последовательности длиннее чем N/4, а нужно нейти именно N/4 — то примерные попадания в диапазон могут дать ложные срабатывания
Могут, возможно вопрос звучал как не менее чем N/4, тогда это решается за константное время в большинстве случаев. Тут я написал как найти точно за log N в худшем случае (чаще за константное время).
А зачем делить на тысячу-то? Если последовательность одинаковых чисел имеет длину N/4, то хватит и гораздо меньшего числа. Наверняка можно вывести минимальное количество таких проверок элементов в массиве, при последовательном попадании последовательности в которые можно 100% утверждать, что такая последовательность — имеется.
Смотрите, я вижу там три разных задачи (нужно уточнять у спрашивающего):
1. В массиве есть число, которое повторяется точно N/4 раз. Известно что оно точно есть и такое число только одно.
2. В массиве есть число, которое повторяется не менее чем N/4 раз, найти любое такое число.
3. В массиве может быть число, которое повторяется точно N/4 раз. Найти это число, либо доказать что такого числа в массиве нет.
Первые два решаются в большинстве случаев за константное время (взяв тысячу проверок можно найти эту последовательность с допуском 1% по длине, взяв 10 тыс — с допуском 0,1% и т.д. мало вероятно наличие нескольких подобных последовательностей), третий вариант за O(log N).
К сожалению, 100% точно решить в третьем случае можно только O(log N) вариантов, за константное количество проверок решить не получится (если я ошибаюсь, расскажите как).
1. В массиве есть число, которое повторяется точно N/4 раз. Известно что оно точно есть и такое число только одно.
2. В массиве есть число, которое повторяется не менее чем N/4 раз, найти любое такое число.
3. В массиве может быть число, которое повторяется точно N/4 раз. Найти это число, либо доказать что такого числа в массиве нет.
Первые два решаются в большинстве случаев за константное время (взяв тысячу проверок можно найти эту последовательность с допуском 1% по длине, взяв 10 тыс — с допуском 0,1% и т.д. мало вероятно наличие нескольких подобных последовательностей), третий вариант за O(log N).
Наверняка можно вывести минимальное количество таких проверок элементов в массиве, при последовательном попадании последовательности в которые можно 100% утверждать, что такая последовательность — имеется.
К сожалению, 100% точно решить в третьем случае можно только O(log N) вариантов, за константное количество проверок решить не получится (если я ошибаюсь, расскажите как).
Моя идея в основном заключалось в том, что:
1) надо пользоваться тем, что массив отсортирован
2) надо хочется проверить как можно меньше элементов
Я бы разбивал массив сначала на меньшее число частей (допустим, на 8) и проверял элементы на их краях — их будет ровно 9.
Если нашлись элементы с одинаковыми числами — значит есть вероятность, что искомая последовательность как раз их содержит
1) надо пользоваться тем, что массив отсортирован
2) надо хочется проверить как можно меньше элементов
Я бы разбивал массив сначала на меньшее число частей (допустим, на 8) и проверял элементы на их краях — их будет ровно 9.
Если нашлись элементы с одинаковыми числами — значит есть вероятность, что искомая последовательность как раз их содержит
> Насчет первого не соглашусь.
Я не имел ввиду обязательность маги; любая степень, конечно, сработает, но просто в магу гораздо проще поступить при отсутствии денег, чем на бакалавра.
> Реферал не обязателен, но с ним 100% шанс получить интервью
Вот тут не соглашусь — был у меня реферал в FB, и резюме же нормальное, но на интервью не пригласили.
Я не имел ввиду обязательность маги; любая степень, конечно, сработает, но просто в магу гораздо проще поступить при отсутствии денег, чем на бакалавра.
> Реферал не обязателен, но с ним 100% шанс получить интервью
Вот тут не соглашусь — был у меня реферал в FB, и резюме же нормальное, но на интервью не пригласили.
сортированный массив с цифрами
Найти число
Так в массиве цифры или числа? Если только цифры, то можно придумать за O(1), если числа, то вероятно всё-таки O(logN)
Вы не могли бы описать суть «константного» алгоритма, если массив состоит исключительно из цифр от 0 до 9? Я надеюсь, это будет интересно не только мне.
Гм, по ходу я заблуждался. Посидел расписал алгоритм, и понял, что найти ответ об индексе начала и конца числа (или цифры), встречающегося N/4 раз, за константу невозможно. В какой-то момент показалось, что как-то можно подшаманить, если будут только 10 различных значений в массиве. А так O(logN). Извините, кого обнадёжил.
Есть сортированный массив с цифрами, которые могут повторяться. Найти число которое повторяется N/4 (где N это размер массива) раз Цифры десятичные? То есть массив чисел [0..9]? Количество раз ровно N/4? N кратно 4?
>> Правила просты: никаких опечаток, грамотный… попросите знакомого [native speaker] проверить
…
>> инжинера
Да хватило бы и обычной автоматической проверки орфографии в редакторе.
А так — очередной «How to draw an owl».
…
>> инжинера
Да хватило бы и обычной автоматической проверки орфографии в редакторе.
А так — очередной «How to draw an owl».
Спасибо за ошибку.
Кстати, инженер — очень интересное слово: engineer — чтобы запомнить как писать его на английском, я пришел к проверочному — engine — и дальше просто добавляешь -er. На русском же оно «словарное», и почему пишется именно так, вопреки оригиналу, для меня загадка.
> How to draw an owl
Даже не знаю что ответить. Если какие то вопросы остались не отвеченными — задавайте, сделаю UPD.
Кстати, инженер — очень интересное слово: engineer — чтобы запомнить как писать его на английском, я пришел к проверочному — engine — и дальше просто добавляешь -er. На русском же оно «словарное», и почему пишется именно так, вопреки оригиналу, для меня загадка.
> How to draw an owl
Даже не знаю что ответить. Если какие то вопросы остались не отвеченными — задавайте, сделаю UPD.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как получить работу в Google?