Re: Зачем просят перевернуть строку на интервью?
От: sergey2b ЮАР  
Дата: 11.10.18 14:54
Оценка:
Здравствуйте, Тёмчик, Вы писали:

Тё>Условие было такое: строка «один два три». Написать функцию на доске, чтобы поменять порядок символов внутри этой строки, не выделяя новой памяти (кроме временных переменных). Принимается ли решение через 15 минут?


в MS давали задание поменять порядок слов а не символов без дополнительной памяти
три два один
Re[3]: Зачем просят перевернуть строку на интервью?
От: anton_t Россия  
Дата: 11.10.18 15:02
Оценка:
Здравствуйте, Vladek, Вы писали:

V>Здравствуйте, Nuzhny, Вы писали:


N>>Здравствуйте, Тёмчик, Вы писали:


Тё>>>и сколько времени можно на это потратить у доски?


N>>Просто проверить, что человек может писать код.


V>Любой дурак может написать код для изолированной технической задачи. Это самая лёгкая часть работы.


Есть исследования, которые говорят об обратном: https://developers.slashdot.org/story/17/05/09/2019222/only-36-percent-of-indian-engineers-can-write-compilable-code-says-study
Не думаю, что у нас сильно лучше.
Re[4]: Зачем просят перевернуть строку на интервью?
От: anton_t Россия  
Дата: 11.10.18 15:09
Оценка: +1
Здравствуйте, IID, Вы писали:

IID>Здравствуйте, Тёмчик, Вы писали:


Тё>>без выделения новой строки


IID>и тут жаба с г-шарпом пошли горько рыдать в уголок к питону.


Не знаю кто куда пошел и зачем, но в Java изменяемая строка — это java.lang.StringBuilder, спокойно берешь и разворачиваешь Надо язык узнать, прежде чем бездарно хейтить.
Re[6]: Зачем просят перевернуть строку на интервью?
От: VVV Россия  
Дата: 11.10.18 15:21
Оценка:
Здравствуйте, B0FEE664, Вы писали:

BFE>Здравствуйте, VVV, Вы писали:


VVV>>А как рекурсивно?


BFE>Я не знаю, что там в жемчужинах, но элементарно же:


BFE>
BFE>void reverse(char* first, char* last)
BFE>{
BFE>  if ( first < last )
BFE>  {
BFE>    reverse(first + 1, last - 1);
BFE>    std::swap(*first, *last);
BFE>  }
BFE>}
BFE>


Не, не, не. В этой подветке речь уже идёт о другом алгоритме:

Прошу пардону.
Там реверс строки используется для реализации циклического сдвига строки на n позиций за О(n).

Re[6]: Зачем просят перевернуть строку на интервью?
От: VVV Россия  
Дата: 11.10.18 15:26
Оценка:
Здравствуйте, Тёмчик, Вы писали:


VVV>>Знаю как не рекурсивно (и очень элегантно) : http://rsdn.org/forum/other/124244.1
Автор: VVV
Дата: 01.11.02

Тё>Там в коде ошибка.
Там не код, а псевдокод. Но всё же, где там ошибка?

VVV>>А как рекурсивно?

Тё>Вместо for-loop впихнуть tail recursion. Imho это изврат- но возможно, для проверки умения кандидата в рекурсию подойдёт, хотя лучше эту проверку отдельной простой задачей сделать.

Речь всё ещё о циклическом сдвиге строки?
Re[14]: Зачем просят перевернуть строку на интервью?
От: 0xCAFEDEAD  
Дата: 11.10.18 15:29
Оценка:
Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, 0xCAFEDEAD, Вы писали:


CAF>>А какое решение быстрее (я слабо знаком с оптимизациями компиляторов, поэтому любые комменты от опытных тов приветствуются)

CC>Как правило компилятор всё равно преобразует кашу с индексами в адресную арифметику.

с одним итератором, а на двумя


CC>Ради интереса скормил код онлайн компилеру https://godbolt.org/ x86-64 gcc (trunk) -O3

CC>1.Nuzhny
Автор: Nuzhny
Дата: 10.10.18
, малость адаптирован чтоб таки скомпилить


CC>
CC>#include <algorithm>

CC>void revert(char* first, char* last)
CC>{
CC>    while ((first != last) && (first != --last)) {
CC>        std::iter_swap (first++, last);
CC>    }
CC>}
CC>


CC>2.RussianFellow
Автор: RussianFellow
Дата: 10.10.18
, для честности вынес strlen наружу как параметр


CC>
CC>#include <stddef.h>

CC>void revert(char* s, size_t n)
CC>{
CC>    for (auto i=0; i<n/2; i++)
CC>    {
CC>        auto c = s[i];
CC>        s[i] = s[n-1-i];
CC>        s[n-1-i] = c;
CC>    }
CC>}
CC>


CC>Итого:


CC>1.

CC>
CC>revert(char*, char*):
CC>        cmp     rdi, rsi
CC>        jne     .L3
CC>        jmp     .L1
CC>.L6:
CC>        add     rdi, 1
CC>        movzx   edx, BYTE PTR [rsi]
CC>        movzx   eax, BYTE PTR [rdi-1]
CC>        mov     BYTE PTR [rdi-1], dl
CC>        mov     BYTE PTR [rsi], al
CC>        cmp     rsi, rdi
CC>        je      .L1
CC>.L3:
CC>        sub     rsi, 1
CC>        cmp     rsi, rdi
CC>        jne     .L6
CC>.L1:
CC>        ret
CC>


CC>2.

CC>
CC>revert(char*, unsigned long):
CC>        mov     rdx, rsi
CC>        shr     rdx
CC>        je      .L1
CC>        lea     rax, [rdi-1+rsi]
CC>        lea     rsi, [rdi+rdx]
CC>.L4:
CC>        movzx   ecx, BYTE PTR [rax]
CC>        movzx   edx, BYTE PTR [rdi]
CC>        add     rdi, 1
CC>        sub     rax, 1
CC>        mov     BYTE PTR [rdi-1], cl
CC>        mov     BYTE PTR [rax+1], dl
CC>        cmp     rdi, rsi
CC>        jne     .L4
CC>.L1:
CC>        ret
CC>


CC>Забавно что если взять другие компиляторы то 1й вариант меняется незначительно, а вот второй генерит вот такой вот пц:


CC>Clang (trunk) -O3

CC>
CC>revert(char*, unsigned long):                           # @revert(char*, unsigned long)
CC>        mov     rcx, rsi
CC>        shr     rcx
CC>        je      .LBB0_6
CC>        mov     r8d, ecx
CC>        and     r8d, 1
CC>        cmp     rcx, 1
CC>        jne     .LBB0_7
CC>        xor     ecx, ecx
CC>        test    r8, r8
CC>        jne     .LBB0_5
CC>        jmp     .LBB0_6
CC>.LBB0_7:
CC>        lea     rdx, [rdi + 1]
CC>        lea     r11, [rdi + rsi]
CC>        add     r11, -1
CC>        mov     r9, r8
CC>        sub     r9, rcx
CC>        xor     ecx, ecx
CC>.LBB0_8:                                # =>This Inner Loop Header: Depth=1
CC>        movzx   r10d, byte ptr [rdx - 1]
CC>        movzx   eax, byte ptr [r11 + rcx]
CC>        mov     byte ptr [rdx - 1], al
CC>        mov     byte ptr [r11 + rcx], r10b
CC>        movzx   r10d, byte ptr [rdx]
CC>        movzx   eax, byte ptr [r11 + rcx - 1]
CC>        mov     byte ptr [rdx], al
CC>        mov     byte ptr [r11 + rcx - 1], r10b
CC>        add     rdx, 2
CC>        add     rcx, -2
CC>        cmp     r9, rcx
CC>        jne     .LBB0_8
CC>        neg     rcx
CC>        test    r8, r8
CC>        je      .LBB0_6
CC>.LBB0_5:
CC>        mov     r8b, byte ptr [rdi + rcx]
CC>        mov     rdx, rcx
CC>        not     rdx
CC>        add     rdx, rsi
CC>        mov     al, byte ptr [rdi + rdx]
CC>        mov     byte ptr [rdi + rcx], al
CC>        mov     byte ptr [rdi + rdx], r8b
CC>.LBB0_6:
CC>        ret
CC>


CAF>>Ну и конечно на десерт, можно ли еще быстрее?

CC>Тут скорее не про быстрее стоит вести речь а про вменяемее.
Я имел ввиду именно быстрее. Допустим — это критичная функция для приложения (ну так надо этому злобному бизнесу).
т.е. не до красоты — пиши что хочешь, но выдай результат

CC>>>Из моего опыта — любители индексов в массе пишут спагетти код.

CAF>>Это мнение субъективное Спорить с таким утверждением бессмысленно.
CC>Ну так там так и написано "Лично я увидев в этой задаче индексы..."
Re: Зачем просят перевернуть строку на интервью?
От: 0xCAFEDEAD  
Дата: 11.10.18 15:32
Оценка:
Здравствуйте, Тёмчик, Вы писали:

Тё>и сколько времени можно на это потратить у доски?


Тё>Условие было такое: строка «один два три». Написать функцию на доске, чтобы поменять порядок символов внутри этой строки, не выделяя новой памяти (кроме временных переменных). Принимается ли решение через 15 минут?


Так что же с тобой случилось? От волнения ты забыл как мел в руках держать или тебе доску мылом намазали?
Или это были злобные знакомые Де-Билла ("даст же бог фаимилию") и они тебя замучали?
Мне кажется в любом другом случае, ты бы забыл об этом вопросе к концу собеседования
Re[6]: Зачем просят перевернуть строку на интервью?
От: IID Россия  
Дата: 11.10.18 16:15
Оценка:
Здравствуйте, Ikemefula, Вы писали:

I>Непонятно. Знает tensorflow это как понять ?


Это один из баззвордов, на которые Тёмчик делает стойку.
kalsarikännit
Re[5]: Зачем просят перевернуть строку на интервью?
От: IID Россия  
Дата: 11.10.18 16:19
Оценка:
Здравствуйте, anton_t, Вы писали:

IID>>и тут жаба с г-шарпом пошли горько рыдать в уголок к питону.


_>Не знаю кто куда пошел и зачем, но в Java изменяемая строка — это java.lang.StringBuilder, спокойно берешь и разворачиваешь Надо язык узнать, прежде чем бездарно хейтить.


Ты точно программист ?
StringBuilder это совсем не строка
И когда он в строку преобразуется (методом ToString) — строка порождается новая.
kalsarikännit
Re[10]: Зачем просят перевернуть строку на интервью?
От: IID Россия  
Дата: 11.10.18 16:32
Оценка:
Здравствуйте, Michael7, Вы писали:

M>А если строка в utf8?


а тогда это задание половина отметившихся не осилит
kalsarikännit
Re[5]: Зачем просят перевернуть строку на интервью?
От: LaptevVV Россия  
Дата: 11.10.18 17:02
Оценка:
LVV>>Прошу пардону.
LVV>>Там реверс строки используется для реализации циклического сдвига строки на n позиций за О(n).
VVV>Знаю как не рекурсивно (и очень элегантно) : http://rsdn.org/forum/other/124244.1
Автор: VVV
Дата: 01.11.02

VVV>А как рекурсивно?
Да, циклический сдвиг — нерекурсивно делается с помощью реверса строки.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[15]: Зачем просят перевернуть строку на интервью?
От: CreatorCray  
Дата: 11.10.18 17:18
Оценка:
Здравствуйте, 0xCAFEDEAD, Вы писали:

CAF>с одним итератором, а на двумя

Ты асм читал?

2.
    movzx   ecx, BYTE PTR [rax]
    movzx   edx, BYTE PTR [rdi]
...
    mov     BYTE PTR [rdi-1], cl
    mov     BYTE PTR [rax+1], dl


Я вижу два.

CAF>Я имел ввиду именно быстрее. Допустим — это критичная функция для приложения (ну так надо этому злобному бизнесу).

Крайне странный критерий. Я не знаю ни одного собеседования где бы искали по критерию "умеет быстро говнокодить".

PS. Письма с From: Аноним <forum@rsdn.org> я удаляю не читая — анонимная кукушка может отдыхать.
Хочешь пообщаться — зарегайся, я не собираюсь даже читать сообщения на которые нельзя адресно ответить.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[6]: Зачем просят перевернуть строку на интервью?
От: CreatorCray  
Дата: 11.10.18 17:18
Оценка: +2
Здравствуйте, IID, Вы писали:

IID>StringBuilder это совсем не строка

И почему я не удивлён что дохрена народа не понимает вообще сути задачи а доколупываются к словам?
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[6]: Зачем просят перевернуть строку на интервью?
От: Don Reba Канада https://stackoverflow.com/users/49329/don-reba
Дата: 11.10.18 17:52
Оценка: +2
Здравствуйте, IID, Вы писали:

IID>StringBuilder это совсем не строка

IID>И когда он в строку преобразуется (методом ToString) — строка порождается новая.

StringBuilder — это не строка, а один из многих классов для работы со строками. String тоже один из них. Строка — это последовательность символов.
Ce n'est que pour vous dire ce que je vous dis.
Отредактировано 11.10.2018 17:53 Don Reba . Предыдущая версия .
Re[16]: Зачем просят перевернуть строку на интервью?
От: 0xCAFEDEAD  
Дата: 11.10.18 17:52
Оценка:
Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, 0xCAFEDEAD, Вы писали:


CAF>>с одним итератором, а на двумя

CC>Ты асм читал?

CC>2.

CC>
CC>    movzx   ecx, BYTE PTR [rax]
CC>    movzx   edx, BYTE PTR [rdi]
CC>...
CC>    mov     BYTE PTR [rdi-1], cl
CC>    mov     BYTE PTR [rax+1], dl
CC>


CC>Я вижу два.

Сорри, как-то я пропустил выкладки, не внимателен был. Т.е компилятор тоже за пару итераторов...

CAF>>Я имел ввиду именно быстрее. Допустим — это критичная функция для приложения (ну так надо этому злобному бизнесу).

CC>Крайне странный критерий. Я не знаю ни одного собеседования где бы искали по критерию "умеет быстро говнокодить".
Я имел ввиду скорость реализации, а не написания.

CC>PS. Письма с From: Аноним <forum@rsdn.org> я удаляю не читая — анонимная кукушка может отдыхать.

CC>Хочешь пообщаться — зарегайся, я не собираюсь даже читать сообщения на которые нельзя адресно ответить.
Я не очень понимаю, о чем ты. Я писем не писал, если оно пустое или с белибердой — то может по-ошибке с телефона?
Re[4]: Зачем просят перевернуть строку на интервью?
От: Vladek Россия Github
Дата: 11.10.18 18:32
Оценка:
Здравствуйте, anton_t, Вы писали:

_>Здравствуйте, Vladek, Вы писали:


V>>Здравствуйте, Nuzhny, Вы писали:


N>>>Здравствуйте, Тёмчик, Вы писали:


Тё>>>>и сколько времени можно на это потратить у доски?


N>>>Просто проверить, что человек может писать код.


V>>Любой дурак может написать код для изолированной технической задачи. Это самая лёгкая часть работы.


_>Есть исследования, которые говорят об обратном: https://developers.slashdot.org/story/17/05/09/2019222/only-36-percent-of-indian-engineers-can-write-compilable-code-says-study

_>Не думаю, что у нас сильно лучше.

Я говорил о тех, кто может пройти тест Fizz Buzz — то есть тест, который отсеивает левых людей. На вакансию программиста может откликнуться кто угодно.

Вообще научить программировать мелкие задачи можно кого угодно — люди будут вполне успешно писать скрипты, автоматизирующие что-то. Это банальный ликбез. Но настоящую программу нельзя склеить из отдельных скриптов или писать как большой скрипт, рано или поздно зайдёшь в тупик — нужны другие способности, способность к выведению абстракций и структурированию связей между ними, это уже не программирование с использованием готовых абстракций, это их изобретение. И тут выясняется, кто-то способен это делать, а кто-то нет и весь код их похож на бесконечные скрипты и они жутко не любят решать задачи иначе.
Re[2]: Зачем просят перевернуть строку на интервью?
От: Тёмчик Австралия жж
Дата: 11.10.18 19:35
Оценка:
Здравствуйте, a_g_99, Вы писали:

__>Я приму такое решение через 15 мин без всяких проблем. Вообще время это что то малокритичное на собеседовании в пределах получаса.

Т.е. то, что кандидат морозит чушь на доске и «справился» с подсказками «тянем за уши» на половине от изначальной проблемы за 15 минут- это засчитываем? Вообще-то мы не школьника собеседовали- а чела с весьма крутым резюме и с бакалавром + мастером в компьютерных науках, и с знанием нейросетей, тензорфло. Читая его резюме, сразу хочется взять такого крутого перца.
Re[7]: Зачем просят перевернуть строку на интервью?
От: Тёмчик Австралия жж
Дата: 11.10.18 19:38
Оценка:
Здравствуйте, VVV, Вы писали:

VVV>>>Знаю как не рекурсивно (и очень элегантно) : http://rsdn.org/forum/other/124244.1
Автор: VVV
Дата: 01.11.02

Тё>>Там в коде ошибка.
VVV>Там не код, а псевдокод. Но всё же, где там ошибка?
В индексах.

VVV>>>А как рекурсивно?

Тё>>Вместо for-loop впихнуть tail recursion. Imho это изврат- но возможно, для проверки умения кандидата в рекурсию подойдёт, хотя лучше эту проверку отдельной простой задачей сделать.

VVV>Речь всё ещё о циклическом сдвиге строки?

«псевдокод» использует reverse строки. Речь об имплементации reverse без for-loop.
Re[17]: Зачем просят перевернуть строку на интервью?
От: CreatorCray  
Дата: 11.10.18 20:26
Оценка: :)
Здравствуйте, 0xCAFEDEAD, Вы писали:

CAF>Я не очень понимаю, о чем ты.

Это не тебе.
Тут есть анонимная кукушка, которая ходит и подкладывает своё "ценное мнение" приватными мессагами от анонима.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[8]: Зачем просят перевернуть строку на интервью?
От: Lexey Россия  
Дата: 11.10.18 22:18
Оценка:
Здравствуйте, Тёмчик, Вы писали:

Тё>Ну разве про swap без временной переменной


Што?

Тё>и вообще без индексов.


Што?
Маразм крепчал?
"Будь достоин победы" (c) 8th Wizard's rule.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.