• lexszero
    lexszero
    тырпрайз Дали порешать задачки на всякие тонкости сишки и костылеалгоритмы. Дядька так яростно сыпал баззвордами, что за час собеседования мне несколько раз хотелось заорать BULLSHIT BINGO. Порассказывал, какой у них анальный ад, КУЧА ПЛАТФОРМ СКРУМ ПЫЩЬ 16 ЧАСОВ ПОЛНЫЙ ПРОГОН ТЕСТОВ СТЕНДАП МИТИНГИ В 10:30, сколько килострок написано на сишке, жаве и пейтоне. Сказал, что удивлен, что я так много знаю, и ВНЕЗАПНО нестудент, поэтому меня СЛОЖНЕЕ ПРОДАТЬ ЗАКАЗЧИКАМ ПЫЩЬ.
    И вообще, пришлось ставить байк более чем в 50 метрах от входа — отвратительно!

Replies (43)

  • Elemir
    Elemir
    @lexszero,
    ВНЕЗАПНО нестудент, поэтому меня СЛОЖНЕЕ ПРОДАТЬ ЗАКАЗЧИКАМ ПЫЩЬ.
    Без бумажки ты АНАЛЬНЫЙ РАБ КИТАЙЦЕВ.
    /2 ·
  • lexszero
    lexszero
    @Elemir, без бумажки я перспективный стартапер.
    /3 in reply to /2 ·
  • Elemir
    Elemir
    @lexszero,
    перспективный
    Ну-ну. Алсо да, дуров тут бабло веп-стартапам раздаёт. Может записать идею Usenet 2.0 и ему прислать? :3
    /4 in reply to /3 ·
  • lexszero
    lexszero
    @Elemir,
    веп
    не буду
    /5 in reply to /4 ·
  • Elemir
    Elemir
    @lexszero, ЕДРО ВЕППРОЕКТА НА ХАСКЕЛЕ. ДАВАЙ НЕ СЦЫ.
    /6 in reply to /5 ·
  • lexszero
    lexszero
    @Elemir, БУЭЭЭЭЭЭЭЭЭЭЭЭЭЭЭ
    /7 in reply to /6 ·
  • Elemir
    Elemir
    @lexszero, Алсо P.S. был из раздела *бред
    /8 in reply to /5 ·
  • L29Ah
    L29Ah
    @Elemir, Комментатор был из раздела *элемир
    /9 in reply to /8 ·
  • lexszero
    lexszero
    @Elemir, habrastorage.org
    гуглокартинки про "ядро на хаскеле"
    /10 in reply to /6 ·
  • Elemir
    Elemir
    @lexszero, kernel_on_haskell.jpg.to
    /11 in reply to /10 ·
  • Elemir
    Elemir
    @Elemir, =(
    /12 in reply to /11 ·
  • 4DA
    4DA
    @lexszero, чоза задачки? как поменять значения двух переменных без третьей?
    /13 ·
  • 4DA
    4DA
    @Elemir, ЕдРО на хаскеле? ЛЕНИВЫЕ ВЫЧИСЛЕНИЯ, НИКАКОГО БЭКГРАНДА, ТОЛЬКО ФОРЕГРАУНД, ТОЛЬКО ХАРДКОР, ТОЛЬКО МОНАДНЫЕ ТРАНСФОРМАТОРЫ.
    /14 in reply to /6 ·
  • lexszero
    lexszero
    @4DA, ну запомнились две:
    1) что выведет этот быдлокод:
    int a[] = {3,4,5,6,7};
    #define LEN (sizeof(a)/sizeof(a[0]))
    int d;
    for (d = -1; d < LEN-1; d++)
    printf("%i\n", a[d+1]);

    2) есть односвязный список. надо проверить, нет ли в нем цикла (т.е. например 1→2→3→4→2 — цикл есть)
    /15 in reply to /13 ·
  • lexszero
    lexszero
    @lexszero, а, дополнение ко второй: элементы списка как-либо изменять нельзя, алгоритм должен работать в константном количестве памяти, не зависящим от длины списка.
    /16 in reply to /15 ·
  • 4DA
    4DA
    @lexszero, 1) 3,4,5,6,7 ?
    2) какие ограничения на дополнительную память?
    /17 in reply to /15 ·
  • lexszero
    lexszero
    @4DA, 1) неправильно
    2) мне известно решение, которое требует очень мало памяти, но если скажу сколько именно — это сильно приблизит тебя к ответу :3
    намнооого меньше килобайта.
    /18 in reply to /17 ·
  • Elemir
    Elemir
    @lexszero, Какая-то нереалистичная вторая задача. Или люксофт изобрела многокубитовые квантовые компьютеры?
    /19 in reply to /18 ·
  • lexszero
    lexszero
    @Elemir, реалистичная. алгоритм на самом деле весьма простой и красивый и работает за O(n) времени. ну и самый тупой вариант за O(n²), думаю, уже все придумали.
    /20 in reply to /19 ·
  • Elemir
    Elemir
    @lexszero, А цикл по значениям или по указателям?
    /21 in reply to /20 ·
  • lexszero
    lexszero
    @Elemir, по указателям
    /22 in reply to /21 ·
  • 4DA
    4DA
    @lexszero, 1) блять, отрицательные числа, я мудак
    2) если числа не повторяются и среди них нет нуля, можно взять xor между текущим и следующим элементом и если он вдруг стал равным нулю, значит, повторяются.
    /23 in reply to /18 ·
  • 4DA
    4DA
    @4DA, 1) все-таки, я дважды мудак
    /24 in reply to /23 ·
  • lexszero
    lexszero
    @4DA, нихуя не распарсил. какие еще числа? нас волнуют указатели, а не содержимое, разумеется, в элементах списка может быть хоть черти лысые (в том числе одинаковые), а ксорить чертей — очень дорогая операция.
    вот есть связный список, в котором первый элемент указывает на второй, второй — на третий, третий — на четвертый, четвертый — на второй. в нем есть цикл.
    вот есть другой список, первый указывает на второй, второй на третий, третий на NULL. в нем цикла нет.
    /25 in reply to /23 ·
  • 4DA
    4DA
    @lexszero, ну, тогда давай xor-ить указатели (текущий адрес и следующий):
    Как только xor дал 0, значит есть цикл,
    либо пока не упремся в NULL указатель.
    прокатит?
    /26 in reply to /25 ·
  • L29Ah
    L29Ah
    @4DA, ШТО
    /27 in reply to /26 ·
  • Elemir
    Elemir
    @4DA, Ты утверждаешь, что a xor b xor c = 0 равносильно тому, что либо a = b, либо a = c, либо c = b? Херня. Возьми c = a xor b и всё.
    /28 in reply to /26 ·
  • lexszero
    lexszero
    @4DA, што. чем (x ^ x->next == 0) отличается от тупого (x == x->next)? алсо, циклы бывают любой длины.
    /29 in reply to /26 ·
  • 4DA
    4DA
    @Elemir, да верно, хоть и маловероятно.
    /30 in reply to /28 ·
  • 4DA
    4DA
    @lexszero, я предлагал так:
    xorval ^= x->next;

    но /28 заставил меня поверить, что может получится (маловеорятно), что xorval совпадет с очередным указателем.
    /31 in reply to /29 ·
  • 4DA
    4DA
    @4DA, s/x/p
    /32 in reply to /31 ·
  • lexszero
    lexszero
    @4DA, ээ, даже если забить на вероятностные штуки, то что ты будешь делать с наксоренными указателями на элементы, не входящие в цикл?
    /33 in reply to /31 ·
  • Elemir
    Elemir
    @lexszero, Они просто проигнорируются. xor коммутативен и ассоциативен.
    /34 in reply to /33 ·
  • 4DA
    4DA
    @lexszero, int xorval = head;
    p = head;
    while (p->next != NULL) {
    xorval ^= p->next;
    if (xorval == 0){
    //ЦЫКЛ
    p = p->next;
    }

    как-то так
    /35 in reply to /29 ·
  • 4DA
    4DA
    @4DA, после //ЦЫКЛ "}" забыл
    /36 in reply to /35 ·
  • lexszero
    lexszero
    @Elemir, пусть у нас список 1-2-4-8-2 (штоб не ксорилось поверх)
    0 ^ 1 = 1
    1 ^ 2 = 3
    3 ^ 4 = 7
    7 ^ 8 = 15
    15 ^ 2 = 13
    13 ^ 4 = 9
    9 ^ 8 = 1
    1 ^ 2 = 3
    3 ^ 4 = 7
    ....
    где ноль?
    /37 in reply to /34 ·
  • Elemir
    Elemir
    @lexszero, Не, бред. Нихуя не понял
    /40 ·
  • Elemir
    Elemir
    @Elemir, А, понял. Получается нуль, который съедается
    /41 in reply to /40 ·
  • lexszero
    lexszero
    @Elemir, што. я про то, что вклад начальной части списка, не входящей в цикл, не равен нулю, сколько не ксорь сам цикл, этот вклад все равно будет оставаться. энивей, слишком сложно. красивое решение пиздец простое.
    /42 in reply to /40 ·
  • Elemir
    Elemir
    @lexszero, Да-да, из-за того что ноль неконсервативен
    /43 in reply to /42 ·
  • lexszero
    lexszero
    @Elemir, даже лях придумал рабочее решение, а чертовы математики не могут
    !
    /44 in reply to /43 ·
  • 4DA
    4DA
    @4DA, фу, я идиот, можно же пустить два указателя прыгать по узлам (один — по два узла за раз), другой — по одному. и если получится, что они в одном узле, значит есть цикл. (то есть первый догонит второй).
    так ?
    /45 in reply to /36 ·
  • lexszero
    lexszero
    @4DA, ура.
    /46 in reply to /45 ·