Comments 45
Он выиграл спор, написав: "We were impressed with your skills and experience, however, the team has decided not to move forward with your candidacy for this role."
Это шутка такая?..
А куда в итоге получили оффер, если конечно не секрет?
По поводу собеседования на MLщика, на мой взгляд это одни из самых сложных собесов, просто потому что есть слишком большое число вещей, по которым можно спросить, начиная от разработческого собеседования, вплоть до университетской математики и всё это довольно релевантные друг другу вопросы...
Мне попалась задача применить функцию ax^2 + bx + c к некоторому массиву. Массив, a, b и c даны. Ограничение было таким, что a > 0. Суть простая: найти минимум функции и потом двумя указателями сформировать результат.
Непонятно. Зачем для применения функции к массиву искать минимум? И зачем тут два указателя?
Я пропустил важную часть условия, спасибо, что указали на это. Результат должен был быть отсортированным. Оригинал задачи: https://leetcode.com/problems/sort-transformed-array/
Спасибо! Чтоб посмотреть условие по ссылке нужно логиниться, похоже, поэтому скопирую условие сюда для других:
Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax*x + bx + c to each element x in the array. The returned array must be in sorted order. Expected time complexity: O(n)
После того как я предложил решение меня попросили рассказать про то, можем ли мы как-то его ускорить. Учитывая, сколько до этого меня мучили вопросами про многопоточность, я предложил именно этот способ. Но интервьюер ожидал ответ намного проще - мы можем использовать numpy. Я примерно помнил, какой метод мог мне тут помочь, но немного натупил с reshape. В итоге пришел отказ, в котором интервьюер написал, что был крайне недоволен, что я не предложил использовать numpy сразу и что я написал класс, а не функцию для решения задачи.
Если речь про Python, то обрабатывать массив питоновскими циклами — это плохая идея. Они очень медленные.
Многотопоточность скорости не добавит из-за GIL. А если использовать многопроцессность, то будут большие накладные расходы на IPC, да внутри всё равно же те же питоновские циклы.
Так что вариантов немного:
Написать бинарное расширение. Это, очевидно, не для интервью.
Использовать Numba. Проще, но тоже есть нюансы.
Использовать Numpy, который очень сильно оптимизирован. Это вариант для решения лучший.
Я думаю, что основная претензия была всё же к многопоточности, а не к классу.
Насчёт класса тоже понятна претензия. От кандидата часто ждут, что он будет писать код, как в продакшн. А там на такую простую задачу смысла заводить класс нет. Python — это же не Java. То, что в LeetCode везде классы, — это не аргумент. Там они просто для упрощения запуска сделаны и смотрятся инородно.
Да, речь шла про python.
Я вот как раз и подумал, какой хороший вопрос, чтобы рассказать про GIL. Конкретно я предложил написать код на плюсах и завернуть его в python модуль. Ну и тут как бы само собой напрашивается numpy, но для меня тогда вариант с использованием дополнительной библиотеки как-то вообще в голове не укладывался
С точки зрения интервьюера это, видимо, был признак того, что кандидат плохо знаком с Numpy. Всё же в реальном коде для такой задачи скорее всего никто расширение на плюсах писать не будет.
Да и для собеседования это уже перебор писать на плюсах расширение (пусть даже и с помощью pybind11, что намного проще). Если не делаешь это каждый день, то попробуй ещё вспомни, как там GIL отпускается и как массив Numpy через buffer protocol туда-сюда гонять (ещё и выделять память под него). И это ещё надо распараллелить поиск уникальных элементов (не то, чтоб это было сложно, но время-то не резиновое).
Насчёт Snap интересно. Так и написали, что overqualified?
Воронка в 60+ отказов и игноров, конечно, поражает. Особенно с учетом того, что алгозадачи в подавляющем большинстве решались. Так понимаю, конторы с визой заморачиваться не хотят, а у остальных и так очередь на собеседование.
Все-таки в РФ с поиском работы сильно проще, даже с учетом всех нюансов.
раз вы сравниваете рационалки через каст к float-у, то и всю задачу можно было во float-ах решать, результат бы, я думаю, не изменился.
А зачем касты к float на операциях сравнения? На координаты ограничения от -10^4 до 10^4, тут можно обойтись одними умножениями в целых числах.
А ещё у вас, кажется, оператора разыменования в val_max не хватает, ибо std::max_element возвращает итератор, а не сам элемент.
Хэш от рационального числа a / b часто считают так:
hash(a / b) = hash(a * inv(b))где inv — это обратный элемент по модулю. Если в качестве модуля берём простое число, там достаточно быстро считается и асимптотика зависит только от самого модуля, а это константа. Да, тяжелее умножения, но зато мы асимптотику улучшаем переходом на хэш-таблицу. Впрочем, для ограничений задачи на практике в этом большого смысла и нет, константа под асимптотикой съест всё преимущество, наверное.
Про float уже сказали, что можно заменить на умножения. Или наоборот. Несмотря на то, что я числам с плавающей точкой не доверяю, при ограничениях задачи, наверное, всё можно было бы на них сделать и работало бы.
Если вдруг хочется полностью от float избавиться, то можно и корень выкинуть. Можно счётчик сделать хитрее. Надо будет хранить пару: (число точек на прямой, число встреченных пар). Изначально там (1, 0). Каждый раз когда добавляем пару, увеличиваем второе число на 1. Если оно стало равно первому, то увеличиваем уже его, а счётчик пар сбрасываем в 0. На асимптотику не влияет, просто на каждой итерации добавляется проверка и иногда ещё одно сложение и присваиванием.
Нет, для 1/1 и 2/2 хэши будут одинаковыми.
inv(b) — это такое (уникальное) число, a inv(b) = 1 (mod m).
Из малой теоремы Ферма следует, что inv(b) = b^(phi(m) - 1) (mod m). То есть, переходим от инверсии к обычной степени, а там можно раскрыть скобки и перегруппировать множители. И получаем, что inv(k b) = inv(k) inv(b) (mod m).
Соответственно, для несокращённой дроби ka / kb получаем k a inv(k b) = (k inv(k)) (a inv(b)) = a inv(b) (mod m), а это то же, что и для дроби a / b.
То есть, можно не сокращать.
Кстати, в Python легко обратный элемент считать, там это функция pow умеет:
pow(b, -1, m) # inv(b)Так что можно убедиться:
>>> a, b, m = 15, 33, 17389
>>> inv = lambda x: pow(x, -1, m)
>>> (a * inv(b)) % m
12647
>>> k = 30
>>> (k * a * inv(k * b)) % m
12647Но и на C++ это легко реализуется через быстрое возведение в степень.
Правда, надо сделать замечание, что числа должны быть взаимно простыми с m. Но можно взять простое m, большее, чем верхняя граница из условия задачи, тогда и GCD считать не нужно.
На самом деле можно даже брать m, не большее, чем граница, а большее, чем корень из границы. Этого достаточно, чтоб m не был множителем чисел из указанного диапазона. Если в задаче до 10^4 числа, то можно взять какое-то простое, большее 100. Это произвольные числа, так что можно вообще выбрать то, которое удобнее.
Если взять m=131, то возводить надо в степень 129 = 2^7 + 1. Тогда получается такой код:
>>> def inv(a):
... r = a
... for _ in range(7):
... r = (r * r) % 131
... return (r * a) % 131
...
>>> inv(1234)
81
>>> pow(1234, -1, 131)
81
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int res = 1;
int size = points.size();
for(int i = 0; i < size; i++)
{
for(int j = i + 1; j < size; j++)
{
int dx = points[j][0] - points[i][0];
int dy = points[j][1] - points[i][1];
int sum = 2;
for(int n = j + 1; n < size; n++)
{
sum += Belongs(points[i], dx, dy, points[n]) ? 1 : 0;
}
res = max(res, sum);
}
}
return res;
}
bool Belongs(vector<int>& p, int dx, int dy, vector<int>& q)
{
int dxq = q[0] - p[0];
int dyq = q[1] - p[1];
return dx * dyq == dy * dxq;
}
};
Иными словами, для человека с гражданством РФ двери в Майкрософт фактически закрыты (и похоже, навсегда)?
Искусство войны ML инженера с FAANG