Comments 22
к примеру, последние пол-года сижу на джине, работу искать — не ищу, есть чем заниматься, но из всей адской массы HR-ов и работодателей, только ОДИН задал технические вопросы, а тестового задания так и вовсе никто не прислал )… в осадок выпал недавно, получив предложение HRа на собеседование к компании в которой работаю много лет )…
не представляю, с какими сложностями и бредом сталкиваются ребята, которые действительно ищут сегодня хорошую, достойно оплачиваемую работу…
Вы про какую? Та, классическая, которая с парой — нормальная задача.
А про xor3 автор и не предлагает (это действительно была бы жесть).
А чего жесть? Задача интересная, если не извращаться как автор а решать в лоб — то решение в десяток строк:
uint_fast64_t xor3(uint_fast64_t a, uint_fast64_t b) {
uint_fast64_t c=0, m=1;
while (a>0 && b>0) {
c += m * ((a%3+b%3) % 3);
a /= 3;
b /= 3;
m *= 3;
}
c += m * (a + b);
return c;
}Хотя бы шанс что собеседуемый такую задачу не видел повыше :)
Я имел ввиду постановку задачи как классическую, только с заменой пар на тройки, без каких-либо уточнений. В условиях собеседования "с маркером у доски" не так-то просто быстро сообразить.
Хотя если собеседование в чем-то типа codility, тогда нормально, там хоть обстановка поспокойнее и можно минут 5 подумать. :-)
Лично меня волнует насколько хорошо человек понимает предметную область и общие подходы к разработке. Поэтому я например на собеседованиях задаю вопросы именно такого плана: «А почему в атомарном контексте в ядре нельзя использовать блокирующие вызовы? А что такое вообще блокирующий вызов, кстати? А как можно попасть в атомарный контекст? А как мне синхронизировать в атомарном контексте? У вас был принят code-review на прошлом проекте? А какие инструменты вы использовали? А как решали спорные ситуации?»
Это намного больше расскажет о том, подходит ли человек, чем умение отмерять время сжигая отрезки веревок разной длины.
Как раз понимание того как все работает, зачем было принято то или иное архитектурное решение и позволит решать нетривиальные задачи.
Мне не нужен человек, который просто умеет копировать код с SO и вызубрил решение тех двух десятков логических задач, которые спрашивают на каждом втором собеседовании. Мне нужен человек который может пояснить почему написанный код был написан именно так, сможет привести альтернативные решения и объяснить их достоинства и недостатки.
Меня такой код восхищает, потому что он наверняка супер оптимален и с первого взгляда совершенно непонятно, как работает. От подобных алгоритмов я получаю особое удовольствие.
А я ровно наоборот. Не скажу, что в данном случае это плохо, всё-таки, как я понял, библиотечная реализация, которая, вообще говоря, критична к производительности. Но хотелось бы комментарий «как» и «почему так», хотя бы название алгоритма/приёма, если это какая-то классика. Вот опечатается коллега на один символ в реализации, а мне придёт бага — и как мне понять, есть ли здесь ошибка, где конкретно и как проявляется?
Если посмотреть на подобный код в библиотечных реализациях в том же классе Long, то там каждый такой метод снабжён комментарием вида // HD, Figure 7-1 (согласно документации это ссылка на главу книги с подробным описанием).
Данный конкретный способ был взят из головы. Если и есть классическое название, то я с ним не знаком.
Имеется массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза, и только ДВА числа не имеют пары. Необходимо предложить алгоритм, который за ФИКСИРОВАННОЕ количество проходов по массиву и используемой памяти определяет оба этих числа, не имеющих пары.
Вариация действительно превосходная, пришлось хорошо подумать, чтобы решить. Я снова предполагаю, что массив заполнен 32-битными целыми числами, но решение масштабируется на числа любой длины. Исхожу из предположения, что "фиксированное количество памяти" в данном случае можно расценить как "могу позволить себе 33 переменных".
Для начала понадобится один проход по массиву:
- нужно посчитать
xorвсего массива; - вместе с ним нужно посчитать
xorвеличин, равных конъюнкции элементов массива с их циклическими сдвигами на 1 (т.е.x & ((x >>> 1) | (x << 31)), гдеx— элемент массива).
Дальше идёт хитрая часть вычислений. Раз неизвестных чисел два и они различны, то есть как минимум один бит, который у данных чисел будет разным (ну это очевидно).
Возьмём бит a1 для первого числа и b1 для второго (с той же позиции). Тогда наши два вычисления дают следующие результаты:
c1 = a1 XOR b1;c2 = a2 XOR b2(соседние биты дляa1иb1);d = (a1 & a2) XOR (b1 & b2).
Сразу стоит оговориться, что поменяв местами значения a и b, решением эта пара быть не перестанет. Значит в какой-то момент нам просто нужно будет случайным образом решить, что есть a, а что есть b. Так, для порядка.
Учитывая данную симметрию, проследим, какими могут быть значения c1, c2 и d:
a1 a2 b1 b2 | c1 c2 d
0 0 0 0 | 0 0 0
0 0 0 1 | 0 1 0
0 0 1 0 | 1 0 0
0 0 1 1 | 1 1 1
0 1 0 1 | 0 0 0
0 1 1 0 | 1 1 0
0 1 1 1 | 1 0 1
1 0 1 0 | 0 0 0
1 0 1 1 | 0 1 1
1 1 1 1 | 0 0 0В четырёх случаях из данного списка все значения c1, c2 и d оказались нулями — это именно те случаи, где a1 == b1 && a2 == b2, то есть нас они не интересуют. Для остальных случаев тройка {c1, c2, d} однозначно определяет значения {a1, a2, b1, b2}.
Дальше дело за малым — пара различных бит — это либо {a1, b1}, либо {a2, b2}. Без ограничения общности будем считать, что это {a1, b1}. Теперь мы в праве вычислить e = (a1 & a3) XOR (b1 & b3) (тут циклическое смещение на два) и т.д. для всех длин циклического смещения, достраивая полноценные значение a и b бит за битом.
Конечно, данное решение будет засчитано только если верно моё предположение о том, что разрядность чисел можно считать константой. Если это не так, то варианта получше у меня пока нет.
Используем 33 переменных и один проход по массиву.
В первую переменную вычисляем XOR элементов, где первый бит равен 1.
Во вторую переменную вычисляем XOR элементов, где второй бит равен 1.
… и так первые 32 переменные.
А в последнюю 33 переменную — общий XOR всех элементов.
По крайней мере одна из 32 переменных не будет равна общему XOR или нулю — это и есть одно из двух непарных чисел. Второе вычисляется по их общему XOR.
#include<stdio.h>
int main() {
int n;
int a[32];
for (int i = 0; i < 32; i++)
a[i] = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int x, j = 0;
scanf("%d", &x);
while (x) {
a[j++] += x % 2;
x >>= 1;
}
}
int s = 0;
for (int i = 31; i >=0; i--)
s = s*2 + a[i]%3;
printf("%d", s);
return 0;
}
Двоично-троичная битовая магия