Поиск работы в Америке
Должность Город, Штат
job title, keywords or company
city, state or zip jobs by job search
Страница 29 из 47 Первая ... 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ... Последняя
Показано с 281 по 290 из 464
Like Tree244Likes

Тема: Короче, ничего индусы не знают

  1. #281
    Гражданин Аватар для TemporaryGhost
    Регистрация
    23.10.2015
    Адрес
    Destination anywhere - Left or right, I don't care
    Возраст
    35
    Сообщений
    1,021
    Спасибо
    21
    Сказали 122 раз в 99 постах

    Re: Короче, ничего индусы не знают




    Цитата Сообщение от L0K1 Посмотреть сообщение
    Однажды кандидат расстроился, когда его попросили это сделать без использования дополнительной памяти (индекс не считается).
    Это в принципе не возможно. Для обмена двух переменных(элементов массива) нужна одна переменная. Я бы сделал примерно так:
    void reverseString(char * str)
    {
    int i, len;
    char tmp;
    len = strlen(str);

    for(i = 0; i < len/2; i++)
    {
    tmp = str[i];
    str[i] = str[len-1-i];
    str[len-i] = tmp;
    }
    }
    Кстати, получается не за O(n), а за O(n/2), если я правильно понял Big O notation.

    Кстати, правильно заданный вопрос - половина ответа. Когда вопрос зашел за O(n) первое что пришло в голову - второй массив равный длине строки и бежать с конца строки к началу, записывая во второй массив в начала в конец
    ☑ DV-2016 -> ☑ DS-260 -> ☑ Мед.комиссия -> ☑ Интервью -> ☑ Визы -> ☑ USA, MN

  2. Бронирование Отелей в США
    Circuit advertisement
    Регистрация
    Always
    Адрес
    Advertising world
    Возраст
    2010
    Сообщений
    Many




     

  3. #282
    Гражданин Аватар для Partner
    Регистрация
    15.01.2007
    Адрес
    California
    Сообщений
    20,317
    Спасибо
    592
    Сказали 8,018 раз в 4,710 постах

    Re: Короче, ничего индусы не знают

    Цитата Сообщение от TemporaryGhost Посмотреть сообщение
    Это в принципе не возможно.
    Возможно. Hint - XOR

  4. #283
    Гражданин Аватар для TemporaryGhost
    Регистрация
    23.10.2015
    Адрес
    Destination anywhere - Left or right, I don't care
    Возраст
    35
    Сообщений
    1,021
    Спасибо
    21
    Сказали 122 раз в 99 постах

    Re: Короче, ничего индусы не знают

    Цитата Сообщение от Partner Посмотреть сообщение
    Возможно. Hint - XOR
    Хотите выкручусь? XOR, на сколько я помню, не работает с памятью напрямую для двух аргументов. Т.е. сначала один из них надо поместить в регистр. А это тоже память. Кроме того, результат тоже будет в регистре и его еще надо записать в память. А это все машинные команды.
    Меняем в моем примере "char tmp" на "register char tmp" и получаем переменную размещенную в регистре(есть нюансы, но рассматривать не будем). И такой код будет работать быстрее чем ваши XOR'ы.
    ☑ DV-2016 -> ☑ DS-260 -> ☑ Мед.комиссия -> ☑ Интервью -> ☑ Визы -> ☑ USA, MN

  5. #284
    Гражданин Аватар для Partner
    Регистрация
    15.01.2007
    Адрес
    California
    Сообщений
    20,317
    Спасибо
    592
    Сказали 8,018 раз в 4,710 постах

    Re: Короче, ничего индусы не знают

    Цитата Сообщение от TemporaryGhost Посмотреть сообщение
    Хотите выкручусь?
    Не защитано. Задача на неиспользование памяти (точнее - переменных) на уровне абстракций языка, а не на уровне машинных команд.

    Цитата Сообщение от TemporaryGhost Посмотреть сообщение
    такой код будет работать быстрее чем ваши XOR'ы.
    Согласен, будет быстрее. В любом случае, с переменной или без, время будет O(n)
    Замечу, что не стояла задача написать самый быстрый код.

  6. #285
    Гражданин Аватар для TemporaryGhost
    Регистрация
    23.10.2015
    Адрес
    Destination anywhere - Left or right, I don't care
    Возраст
    35
    Сообщений
    1,021
    Спасибо
    21
    Сказали 122 раз в 99 постах

    Re: Короче, ничего индусы не знают

    Цитата Сообщение от Partner Посмотреть сообщение
    адача на неиспользование памяти (точнее - переменных) на уровне абстракций языка, а не на уровне машинных команд.
    Вопрос надо задавать правильно. Про переменные вопроса не было, был вопрос про память.
    ИМХО: когда задается вопрос про переменные - тут абстракция на уровне языка. Когда про память - тут уже идет привязка к железу.
    ☑ DV-2016 -> ☑ DS-260 -> ☑ Мед.комиссия -> ☑ Интервью -> ☑ Визы -> ☑ USA, MN

  7. #286
    Модератор
    Регистрация
    18.03.2006
    Сообщений
    37,258
    Спасибо
    38
    Сказали 14,659 раз в 8,847 постах

    Re: Короче, ничего индусы не знают

    Цитата Сообщение от TemporaryGhost Посмотреть сообщение
    Кстати, получается не за O(n), а за O(n/2), если я правильно понял Big O notation.
    Vot reshil posmotret' o chem vy pishete v ETOI teme. O(n) i O(n/2) - eto odno i to je, raznicy net.
    +Den and MishkaMishka like this.
    Ты не несешь ответственности за то, чего ждут от тебя другие люди. Если от тебя ждут слишком многого, то это их ошибка, а не твоя вина.
    Ричард Ф. Фейнман

  8. #287
    Гражданин Аватар для TemporaryGhost
    Регистрация
    23.10.2015
    Адрес
    Destination anywhere - Left or right, I don't care
    Возраст
    35
    Сообщений
    1,021
    Спасибо
    21
    Сказали 122 раз в 99 постах

    Re: Короче, ничего индусы не знают

    Цитата Сообщение от raevsky Посмотреть сообщение
    Vot reshil posmotret' o chem vy pishete v ETOI teme. O(n) i O(n/2) - eto odno i to je, raznicy net.
    Я уже понял. Смысл в том, что время выполнения зависит от количество элементов(n), и не важно, что в одном случае количество итераций будет равно n, а во втором случае равно n/2. Верно?
    ☑ DV-2016 -> ☑ DS-260 -> ☑ Мед.комиссия -> ☑ Интервью -> ☑ Визы -> ☑ USA, MN

  9. #288
    Модератор
    Регистрация
    18.03.2006
    Сообщений
    37,258
    Спасибо
    38
    Сказали 14,659 раз в 8,847 постах

    Re: Короче, ничего индусы не знают

    Цитата Сообщение от TemporaryGhost Посмотреть сообщение
    Я уже понял. Смысл в том, что время выполнения зависит от количество элементов(n), и не важно, что в одном случае количество итераций будет равно n, а во втором случае равно n/2. Верно?
    O(n) oznachaet chto ogranicheno sverhu C*n dlia nekotorogo C. Togda dlia n/2 budet 2C*n/2 = C*n
    +Den likes this.
    Ты не несешь ответственности за то, чего ждут от тебя другие люди. Если от тебя ждут слишком многого, то это их ошибка, а не твоя вина.
    Ричард Ф. Фейнман

  10. #289
    Гражданин Аватар для TemporaryGhost
    Регистрация
    23.10.2015
    Адрес
    Destination anywhere - Left or right, I don't care
    Возраст
    35
    Сообщений
    1,021
    Спасибо
    21
    Сказали 122 раз в 99 постах

    Re: Короче, ничего индусы не знают

    Цитата Сообщение от Partner Посмотреть сообщение
    Не защитано. Задача на неиспользование памяти (точнее - переменных)
    Придумал еще один вариант, правда так же зависим от реализации строк в языке:
    void reverseString(char * str)
    {
    int i, len = strlen(str);

    for(i = 0; i < len/2; i++)
    {
    str[len]= str[i];
    str[i] = str[len-1-i];
    str[len-i] = str[len];
    }
    str[len] = 0;
    }
    Можно и len не использовать, но компилятор с оптимизацией создаст его сам, а без оптимизации будет дергать strlen на каждой итерации.

    Цитата Сообщение от raevsky Посмотреть сообщение
    O(n) oznachaet chto ogranicheno sverhu C*n dlia nekotorogo C. Togda dlia n/2 budet 2C*n/2 = C*n
    А откуда взялось 2 перед С?
    Короче читать мне еще и читать...
    ☑ DV-2016 -> ☑ DS-260 -> ☑ Мед.комиссия -> ☑ Интервью -> ☑ Визы -> ☑ USA, MN

  11. #290
    Гражданин Аватар для koshix
    Регистрация
    02.05.2011
    Адрес
    Boston
    Сообщений
    1,937
    Спасибо
    107
    Сказали 490 раз в 357 постах

    Re: Короче, ничего индусы не знают

    Booking.com
    Цитата Сообщение от TemporaryGhost Посмотреть сообщение
    Это в принципе не возможно. Для обмена двух переменных(элементов массива) нужна одна переменная. Я бы сделал примерно так:
    Кстати, получается не за O(n), а за O(n/2), если я правильно понял Big O notation.

    Кстати, правильно заданный вопрос - половина ответа. Когда вопрос зашел за O(n) первое что пришло в голову - второй массив равный длине строки и бежать с конца строки к началу, записывая во второй массив в начала в конец
    Три раза XOR

    update: Сорри, не дочитала, что уже обсудили.
    Последний раз редактировалось koshix; 07.01.2016 в 09:22.
    Life doesn't give you seat belts! (c) LEGO Batman

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Visitors found this page by searching for:

индусы

индус

Я полтора года в ITaccentureBlACKED ALEKXXXX

Социальные закладки

Социальные закладки

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •  

Форум "Говорим про Америку"
Форум "Говорим про Америку" Facebook