Типовые задачи на собеседованиях по программированию с решениями
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 07.07.16 06:00
Оценка: :)
Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?
Желательно привести решения этих задач с комментариями или объяснениями. (Стандартный язык для ответов--C++, но можно использовать любой другой--Delphi, C#, Java и т.д.)
1613 г. = 2024 г.
Re: Типовые задачи на собеседованиях по программированию с решениями
От: Miroff Россия  
Дата: 07.07.16 06:07
Оценка:
Здравствуйте, RussianFellow, Вы писали:

RF>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?

RF>Желательно привести решения этих задач с комментариями или объяснениями. (Стандартный язык для ответов--C++, но можно использовать любой другой--Delphi, C#, Java и т.д.)

FizBuzz
Re[2]: Типовые задачи на собеседованиях по программированию
От: Arsen.Shnurkov  
Дата: 07.07.16 06:28
Оценка:
M> FizBuzz

хотел бы я посмотреть на решение этой задачи средствами GNU make (т.е. только мейк-файлом без GMSL и внешних вызовов)

У меня нет сомнений, что сделать это возможно (там же есть циклы, условия и $(word N))

У меня есть сомнения, что предложивший написать такого рода код, сможет сам написать сходу.
Отредактировано 07.07.2016 6:32 Arsen.Shnurkov . Предыдущая версия .
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 07.07.16 06:57
Оценка: :))) :)
Здравствуйте, Miroff, Вы писали:

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


RF>>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?

RF>>Желательно привести решения этих задач с комментариями или объяснениями. (Стандартный язык для ответов--C++, но можно использовать любой другой--Delphi, C#, Java и т.д.)

M>FizBuzz


"Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”."


Код на C++ :

#include <stdio.h>

for (int i=0; i<=100; i++)
{
    if (i==((i/15)*15))
    {
        printf("FizzBuzz\n");
    }
    else
    {
        if (i==((i/3)*3))
        {
            printf("Fizz\n");
        }
        else if (i==((i/5)*5))
        {
           printf("Buzz\n");
        }
        else
        {
            printf("%d\n",i);
        }
    }
}


Так, что ли?
1613 г. = 2024 г.
Re[3]: Типовые задачи на собеседованиях по программированию с решениями
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 07.07.16 07:00
Оценка:
Прошу прощения--числа от 1 до 100:

RF>
#include <stdio.h>

for (int i=1; i<=100; i++)
{
    if (i==((i/15)*15))
    {
        printf("FizzBuzz\n");
    }
    else
    {
        if (i==((i/3)*3))
        {
           printf("Fizz\n");
        }
        else if (i==((i/5)*5))
        {
           printf("Buzz\n");
        }
        else
        {
           printf("%d\n",i);
        }
    }
}
1613 г. = 2024 г.
Re[4]: Типовые задачи на собеседованиях по программированию с решениями
От: alzt  
Дата: 07.07.16 07:33
Оценка: +3
Здравствуйте, RussianFellow, Вы писали:

Я бы переписал сл. образом.

#include <stdio.h>

for (int i=1; i<=100; i++)
{
    bool mul3 = (i%3)==0;
    bool mul5 = (i%5)==0;

    if(mul3 && mul5) printf("FizzBuzz\n");
    else if(mul3) printf("Fizz\n");
    else if(mul5) printf("Buzz\n");
    else printf("%d\n",i);
}
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 07.07.16 07:57
Оценка:
Здравствуйте, Miroff, Вы писали:

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


RF>>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?

RF>>Желательно привести решения этих задач с комментариями или объяснениями. (Стандартный язык для ответов--C++, но можно использовать любой другой--Delphi, C#, Java и т.д.)

M>FizBuzz


Ясно.

А как с задачами создания стека, очереди, дека без использования STL, MFC и других библиотек?
А как с задачей создания и обхода бинарного дерева?
А как с задачами работы со списком--разворот, сортировка?
1613 г. = 2024 г.
Re: Типовые задачи на собеседованиях по программированию с решениями
От: 4Real Швеция  
Дата: 07.07.16 08:11
Оценка: +1 -1
Здравствуйте, RussianFellow, Вы писали:

hackerrank — там не дают примеров решения сразу, но дают достаточно информации чтоб добраться до ответа самостоятельно. После того как твое решение проходит нужные тесты можешь смотреть как эту задачу решают другие. В общем полезный ресурс, сам на нем практикуюсь.
Re: Типовые задачи на собеседованиях по программированию с решениями
От: strcpy Россия  
Дата: 07.07.16 16:20
Оценка:
Здравствуйте, RussianFellow, Вы писали:

RF>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?

RF>Желательно привести решения этих задач с комментариями или объяснениями. (Стандартный язык для ответов--C++, но можно использовать любой другой--Delphi, C#, Java и т.д.)
https://leetcode.com/
Удвой число ошибок, если не получается добиться цели.
Re: Типовые задачи на собеседованиях по программированию с решениями
От: nekocoder США  
Дата: 07.07.16 16:28
Оценка: +3 -1
Здравствуйте, RussianFellow, Вы писали:

RF>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?


Есть посвященная как раз этому книга Cracking the Coding Interview.
Re[3]: Типовые задачи на собеседованиях по программированию с решениями
От: b0r3d0m  
Дата: 07.07.16 17:50
Оценка: -2 :)
RF>Код на C++ :

RF>
RF>#include <stdio.h>

RF>for (int i=0; i<=100; i++)
RF>{
RF>    if (i==((i/15)*15))
RF>    {
RF>        printf("FizzBuzz\n");
RF>    }
RF>    else
RF>    {
RF>        if (i==((i/3)*3))
RF>        {
RF>            printf("Fizz\n");
RF>        }
RF>        else if (i==((i/5)*5))
RF>        {
RF>           printf("Buzz\n");
RF>        }
RF>        else
RF>        {
RF>            printf("%d\n",i);
RF>        }
RF>    }
RF>}
RF>


RF>Так, что ли?


Какой же ужас.

Даже если не брать в расчёт наличие в языке встроенного operator%, вы напрочь забыли о том, что 3/3*3 вовсе не обязательно равняется 3.
Re[4]: Типовые задачи на собеседованиях по программированию с решениями
От: nigh  
Дата: 07.07.16 21:00
Оценка:
Здравствуйте, b0r3d0m, Вы писали:

B>вы напрочь забыли о том, что 3/3*3 вовсе не обязательно равняется 3.

забывать там нечего. Деление целых чисел в C — всегда целочисленное
Re[5]: Типовые задачи на собеседованиях по программированию с решениями
От: b0r3d0m  
Дата: 07.07.16 21:02
Оценка:
B>>вы напрочь забыли о том, что 3/3*3 вовсе не обязательно равняется 3.
N>забывать там нечего. Деление целых чисел в C — всегда целочисленное
Тем более.
Re[6]: Типовые задачи на собеседованиях по программированию с решениями
От: nigh  
Дата: 07.07.16 21:08
Оценка:
Здравствуйте, b0r3d0m, Вы писали:

B>>>вы напрочь забыли о том, что 3/3*3 вовсе не обязательно равняется 3.

N>>забывать там нечего. Деление целых чисел в C — всегда целочисленное
B>Тем более.
поясните? для целей это задачи указанный способ подходит. (хотя, % конечно лучше и быстрее)
Re[7]: Типовые задачи на собеседованиях по программированию с решениями
От: b0r3d0m  
Дата: 07.07.16 21:12
Оценка:
N>поясните? для целей это задачи указанный способ подходит. (хотя, % конечно лучше и быстрее)
Лол. Что ж, это я задание неправильно прочитал, извиняюсь. Про operator% всё ещё актуально, а остальное нафиг.
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: De-Bill  
Дата: 08.07.16 03:05
Оценка:
M>FizBuzz
for i in range(1,101):print("Fizz"*(i%3==0)+"Buzz"*(i%5==0)+str(i)*(i%3!=0!=i%5))
Re[3]: Типовые задачи на собеседованиях по программированию с решениями
От: De-Bill  
Дата: 08.07.16 03:23
Оценка:
DB>
DB>for i in range(1,101):print("Fizz"*(i%3==0)+"Buzz"*(i%5==0)+str(i)*(i%3!=0!=i%5))
DB>

Или даже так
for i in range(100):print("Fizz"*(i%3==2)+"Buzz"*(i%5==4) or str(i+1))
Re[4]: Типовые задачи на собеседованиях по программированию с решениями
От: Miroff Россия  
Дата: 08.07.16 04:36
Оценка:
Здравствуйте, De-Bill, Вы писали:

DB>
for i in range(100):print("Fizz"*(i%3==2)+"Buzz"*(i%5==4) or str(i+1))


PEP8 соблюдать необязательно?
Re[5]: Типовые задачи на собеседованиях по программированию с решениями
От: De-Bill  
Дата: 08.07.16 06:14
Оценка:
DB>>
for i in range(100):print("Fizz"*(i%3==2)+"Buzz"*(i%5==4) or str(i+1))

M>PEP8 соблюдать необязательно?

Это же code golf. Вообще можно ничего не соблюдать. Лишь бы работало.
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: cures Россия cures.narod.ru
Дата: 10.07.16 22:38
Оценка:
Здравствуйте, strcpy, Вы писали:

S> le****de.com


Они там больные, требовать за доступ к задачам 25 баксов в месяц, когда есть десятки сайтов с тысячами таких же и гораздо лучших задач даром?
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: Arsen.Shnurkov  
Дата: 08.12.16 06:40
Оценка: :)))
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: ylem  
Дата: 08.12.16 07:27
Оценка:
N>Есть посвященная как раз этому книга Cracking the Coding Interview.

Там вот в оценках мнения разделились. Можно комментариев? Она не священная вообще? Священная, но с оговорками? Cвященная, только в определенных частях cвета?
Книгу читал и не осуждаю.
Re[8]: Типовые задачи на собеседованиях по программированию с решениями
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 08.12.16 08:01
Оценка:
Здравствуйте, b0r3d0m, Вы писали:

B>Про operator% всё ещё актуально, а остальное нафиг.


Кому как удобно.
1613 г. = 2024 г.
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: antonio_banderas Россия  
Дата: 08.12.16 08:06
Оценка:
Здравствуйте, Miroff, Вы писали:

M>FizBuzz


The "Fizz-Buzz test" is an interview question designed to help filter out the 99.5% of programming job candidates who can't seem to program their way out of a wet paper bag. The text of the programming assignment is as follows:


А как "to program their way out of a wet paper bag" переводится? Не могут запрограммировать выход из мокрого бумажного мешка?

Из этого перевода дальше будет следовать, кого она таки отсеивает.
Потому что не суметь решить её — я не знаю, как надо вообще не уметь программировать для этого. Её даже школьники решат, причем троечники тоже, имхо. ))

Может, это 99.5% индусов не могут её решить?
Re[5]: Типовые задачи на собеседованиях по программированию
От: antonio_banderas Россия  
Дата: 08.12.16 08:21
Оценка: -2
Здравствуйте, alzt, Вы писали:

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


A>Я бы переписал сл. образом.


A>
A>#include <stdio.h>

A>for (int i=1; i<=100; i++)
A>{
A>    bool mul3 = (i%3)==0;
A>    bool mul5 = (i%5)==0;

A>    if(mul3 && mul5) printf("FizzBuzz\n");
A>    else if(mul3) printf("Fizz\n");
A>    else if(mul5) printf("Buzz\n");
A>    else printf("%d\n",i);
A>}
A>


Если цели написать эффективный код нету, то всё нормально (только у нас во всех стайл-гайдах на всех работах инструкцию после условий надо с новой строки писать — иначе очень трудно отладчиком будет ходить; а чаще еще и со скобками).
Можно сэкономить на делениях (оно дорогое вообще-то):

    for (unsigned i = 1, counter3 = i, counter5 = i; i <= 100; ++i, ++counter3, ++counter5)
    {
        if (counter3 == 3)
        {
            counter3 = 0;
        }
        if (counter5 == 5)
        {
            counter5 = 0;
        }

        if (counter3 == 0 && counter5 == 0)
        {
            std::cout << "mod15" << std::endl;
        }
        else if (counter3 == 0)
        {
            std::cout << "mod3" << std::endl;
        }
        else if (counter5 == 0)
        {
            std::cout << "mod5" << std::endl;
        }
        else
        {
            std::cout << i << std::endl;
        }
    }
Отредактировано 08.12.2016 8:26 antonio_v_krasnom . Предыдущая версия .
Re[6]: Типовые задачи на собеседованиях по программированию с решениями
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 08.12.16 08:26
Оценка: -3
Здравствуйте, antonio_banderas, Вы писали:

_>Если цели написать эффективный код нету, то всё нормально (только у нас во всех стайл-гайдах на всех работах инструкцию после условий надо с новой строки писать — иначе очень трудно отладчиком будет ходить; а чаще еще и со скобками).

_>Можно сэкономить на делениях (оно дорогое вообще-то):

  спрятал кошмар
_>
_>    for (unsigned i = 1, counter3 = i, counter5 = i; i < 100; ++i, ++counter3, ++counter5)
_>    {
_>        if (counter3 == 3)
_>        {
_>            counter3 = 0;
_>        }
_>        if (counter5 == 5)
_>        {
_>            counter5 = 0;
_>        }

_>        if (counter3 == 0 && counter5 == 0)
_>        {
_>            std::cout << "mod15" << std::endl;
_>        }
_>        else if (counter3 == 0)
_>        {
_>            std::cout << "mod3" << std::endl;
_>        }
_>        else if (counter5 == 0)
_>        {
_>            std::cout << "mod5" << std::endl;
_>        }
_>        else
_>        {
_>            std::cout << i << std::endl;
_>        }
_>    }
_>


А где это такие дикие требования встречаются?! И вообще, зачем отладчик в 21 веке, всё легко и изящно решается юнит-тестами и логами
Re[7]: Типовые задачи на собеседованиях по программированию с решениями
От: El Camino Real США  
Дата: 08.12.16 10:14
Оценка:
Здравствуйте, kaa.python, Вы писали:

KP>А где это такие дикие требования встречаются?! И вообще, зачем отладчик в 21 веке, всё легко и изящно решается юнит-тестами и логами

Отладчиком может быть быстрее. Зависит от вариативности входных данных. Экспоненциальный рост количества юнит-тестов никто не отменял.
Re[6]: Типовые задачи на собеседованиях по программированию
От: alzt  
Дата: 09.12.16 20:43
Оценка:
Здравствуйте, antonio_banderas, Вы писали:

_>Если цели написать эффективный код нету, то всё нормально (только у нас во всех стайл-гайдах на всех работах инструкцию после условий надо с новой строки писать — иначе очень трудно отладчиком будет ходить; а чаще еще и со скобками).


Придирки к форматированию это почти как придирки к орфографии.

_>Можно сэкономить на делениях (оно дорогое вообще-то):

Оно вообще ничего не стоит. Пользователи не заметят, если ты этот цикл вообще уберёшь.
Этот пример преждевременной оптимизации, которую не надо делать.
Отредактировано 09.12.2016 20:44 alzt . Предыдущая версия .
Re[6]: Типовые задачи на собеседованиях по программированию
От: __kot2  
Дата: 09.12.16 21:27
Оценка:
Здравствуйте, antonio_banderas, Вы писали:
_>
_>    for (unsigned i = 1, counter3 = i, counter5 = i; i <= 100; ++i, ++counter3, ++counter5) 
_>    {
_>        if (counter3 == 3)
_>        { ну ладно с новой строки, но зачем скобочек-то поналеплено? знаете, что такое составной оператор? нет? :) а зачем тогда используете?
_>            counter3 = 0;
_>        }
_>        if (counter5 == 5) кстати, такая запись counter5 == 5 редко, но приводит к опечатке counter5 = 5 что тяжело найти, 
        особенно без тестов, которые, я так понимаю, не для вас и рекомундуется писать обратно 5 == counter5
_>        {
_>            counter5 = 0;
_>        }

_>        if (counter3 == 0 && counter5 == 0)
_>        {
_>            std::cout << "mod15" << std::endl; вообще обычно используют using namespace std, ну я думаю, вы в курсе
_>        }
_>
Отредактировано 09.12.2016 21:31 __kot2 . Предыдущая версия .
Re[3]: Типовые задачи на собеседованиях по программированию с решениями
От: std.denis Россия  
Дата: 09.12.16 23:20
Оценка:
_>А как "to program their way out of a wet paper bag" переводится? Не могут запрограммировать выход из мокрого бумажного мешка?

да
Re[6]: Типовые задачи на собеседованиях по программированию
От: mik1  
Дата: 09.12.16 23:44
Оценка: +1
Здравствуйте, antonio_banderas, Вы писали:

A>>Я бы переписал сл. образом.


Расскажите, как вы это будете тестировать
Re[5]: Типовые задачи на собеседованиях по программированию с решениями
От: Pzz Россия https://github.com/alexpevzner
Дата: 10.12.16 14:53
Оценка: 2 (1) +1
Здравствуйте, alzt, Вы писали:

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


A>Я бы переписал сл. образом.


А я бы так:

for (int i = 1; i <= 100; i ++) {
    printf("%s%s%d\n", (i % 3) ? "" : "Fizz", (i % 5) ? "" : "Buzz", i);
}
Re[7]: Типовые задачи на собеседованиях по программированию
От: antonio_banderas Россия  
Дата: 12.12.16 07:42
Оценка: +1
Здравствуйте, __kot2, Вы писали:

__>ну ладно с новой строки, но зачем скобочек-то поналеплено? знаете, что такое составной оператор?


Знаю.

__>нет? а зачем тогда используете?


Потому что так код удобней читать.
Если что, я поначалу (курсе на 2-3) тоже писал в стиле "письмо домой родителям" — много инструкций в 1 строчку.

__>if (counter5 == 5) кстати, такая запись counter5 == 5 редко, но приводит к опечатке counter5 = 5 что тяжело найти,

__>особенно без тестов, которые, я так понимаю, не для вас и рекомундуется писать обратно 5 == counter5

Можно я на ты буду?
Все современные компиляторы при присваивании в условии выдают варнинги.
Из выше написанной тобой фразы можно сделать вывод, что ты либо последний раз писал код давно, либо пользуешься древними компиляторами, либо глушишь все варнинги, либо оставляешь после себя простыню варнингов и их даже не читаешь.
Например, на большинстве работ, где я работал, в стайл-гайде запрещалось писать код с варнингами, а в теперешней и еще одной фирме даже более того — большинство проектов собирались с -Werror. Тут даже если и захочешь, в условии не получится присвоить. Так что (5 == counter5) это прошлый век.

__>std::cout << "mod15" << std::endl; вообще обычно используют using namespace std, ну я думаю, вы в курсе


Да, в курсе. Дело вкуса. Кто-то использует, кто-то явно пишет.
Когда в проекте несколько библиотек и у каждой есть похожие сущности, удобней явно писать, что откуда.

__>особенно без тестов, которые, я так понимаю, не для вас


Почему?
Отредактировано 12.12.2016 7:44 antonio_v_krasnom . Предыдущая версия .
Re[6]: Типовые задачи на собеседованиях по программированию с решениями
От: antonio_banderas Россия  
Дата: 12.12.16 07:48
Оценка:
Здравствуйте, Pzz, Вы писали:

Pzz>А я бы так:


Pzz>
Pzz>for (int i = 1; i <= 100; i ++) {
Pzz>    printf("%s%s%d\n", (i % 3) ? "" : "Fizz", (i % 5) ? "" : "Buzz", i);
Pzz>}
Pzz>


Одна неточность:

But for multiples of three print “Fizz” instead of the number ...

Re[7]: Типовые задачи на собеседованиях по программированию
От: antonio_banderas Россия  
Дата: 12.12.16 07:54
Оценка:
Здравствуйте, mik1, Вы писали:

M>Расскажите, как вы это будете тестировать


Есть много способов это тестировать.
А что?
Re: Типовые задачи на собеседованиях по программированию с решениями
От: Sharov Россия  
Дата: 12.12.16 10:59
Оценка:
Здравствуйте, RussianFellow, Вы писали:

RF>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?


Строку перевернуть за О(1) памяти.
Кодом людям нужно помогать!
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: playnext  
Дата: 12.12.16 13:38
Оценка:
Здравствуйте, Sharov, Вы писали:

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


RF>>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?


S>Строку перевернуть за О(1) памяти.


это очень легкая задача, такие редко задают.
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 12.12.16 13:47
Оценка: :)
Здравствуйте, Sharov, Вы писали:

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


RF>>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?


S>Строку перевернуть за О(1) памяти.


Я не знаю, что такое O(1), O(n), O(log n), но перевернуть строку (тип char* или char[]) без использования STL:

char *s; // или char s[80];
int  i, n;
char  c;

n = strlen(s);
for (i=0; i<n/2; i++)
{
    c = s[i];
    s[i] = s[n-1-i];
    s[n-1-i] = c;
}
1613 г. = 2024 г.
Re[3]: Типовые задачи на собеседованиях по программированию с решениями
От: Sharov Россия  
Дата: 12.12.16 14:08
Оценка:
Здравствуйте, RussianFellow, Вы писали:


S>>Строку перевернуть за О(1) памяти.


RF>Я не знаю, что такое O(1), O(n), O(log n), но перевернуть строку (тип char* или char[]) без использования STL:


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

RF>
RF>char *s; // или char s[80];
RF>int  i, n;
RF>char  c;

RF>n = strlen(s);
RF>for (i=0; i<n/2; i++)
RF>{
RF>    c = s[i];
RF>    s[i] = s[n-1-i];
RF>    s[n-1-i] = c;
RF>}
RF>


Похоже на правду.
Кодом людям нужно помогать!
Re[4]: Типовые задачи на собеседованиях по программированию с решениями
От: playnext  
Дата: 12.12.16 17:39
Оценка: +1
Здравствуйте, Sharov, Вы писали:

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



S>>>Строку перевернуть за О(1) памяти.


RF>>Я не знаю, что такое O(1), O(n), O(log n), но перевернуть строку (тип char* или char[]) без использования STL:


S>Это очень плохо. Это должно от зубов отскакивать, т.е. что значит O(1), O(n) и т.д. должно от зубов отскакивать. Можно не знать выч. сложность какого-нибудь алгоритма -- по расходуемой памяти или кол-ву операций, но определение знать необходимо. Мат. часть тут


RF>>
RF>>char *s; // или char s[80];
RF>>int  i, n;
RF>>char  c;

RF>>n = strlen(s);
RF>>for (i=0; i<n/2; i++)
RF>>{
RF>>    c = s[i];
RF>>    s[i] = s[n-1-i];
RF>>    s[n-1-i] = c;
RF>>}
RF>>


S>Похоже на правду.


Обычно задают список перевернуть односвязный. Это чаще встречается.
Re: Типовые задачи на собеседованиях по программированию с решениями
От: IT Россия linq2db.com
Дата: 12.12.16 20:15
Оценка:
Здравствуйте, RussianFellow, Вы писали:

RF>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?


http://problembook.net/
Если нам не помогут, то мы тоже никого не пощадим.
Re[8]: Типовые задачи на собеседованиях по программированию
От: __kot2  
Дата: 12.12.16 20:53
Оценка:
Здравствуйте, antonio_banderas, Вы писали:
_>Потому что так код удобней читать.
не только я один считаю, что твой код из-за кучи скобочек стал нечитаемым

_>Если что, я поначалу (курсе на 2-3) тоже писал в стиле "письмо домой родителям" — много инструкций в 1 строчку.

я не про это, я про ненужные скобочки

_>Все современные компиляторы при присваивании в условии выдают варнинги.

_>Из выше написанной тобой фразы можно сделать вывод, что ты либо последний раз писал код давно, либо пользуешься древними компиляторами, либо глушишь все варнинги, либо оставляешь после себя простыню варнингов и их даже не читаешь.
_>Например, на большинстве работ, где я работал, в стайл-гайде запрещалось писать код с варнингами, а в теперешней и еще одной фирме даже более того — большинство проектов собирались с -Werror. Тут даже если и захочешь, в условии не получится присвоить. Так что (5 == counter5) это прошлый век.
аркгументы, конечно, интересные. но вот мой gcc 4.9.3 — полтора года назад зарелизен варнинг не дает.

__>>особенно без тестов, которые, я так понимаю, не для вас

_>Почему?
попробуй, напиши тесты к своему коду
Отредактировано 12.12.2016 21:02 __kot2 . Предыдущая версия .
Re: Типовые задачи на собеседованиях по программированию с решениями
От: licedey  
Дата: 13.12.16 03:05
Оценка:
Здравствуйте, RussianFellow, Вы писали:

RF>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?

RF>Желательно привести решения этих задач с комментариями или объяснениями. (Стандартный язык для ответов--C++, но можно использовать любой другой--Delphi, C#, Java и т.д.)

Мне в жизни не приходилось передвинуть бит! (с)
Вариации: посчитать биты в числе, возвести 2 в степень N без циклов

На последних интервью надо было:
— Проверить правильно расставлены скобки ({<>}) в строке
— Перевернуть односвязный список

Если компания зарубежная, рекомендую этот ресурс.
Re[7]: Типовые задачи на собеседованиях по программированию с решениями
От: alzt  
Дата: 13.12.16 07:37
Оценка:
Здравствуйте, antonio_banderas, Вы писали:

Pzz>>
Pzz>>for (int i = 1; i <= 100; i ++) {
Pzz>>    printf("%s%s%d\n", (i % 3) ? "" : "Fizz", (i % 5) ? "" : "Buzz", i);
Pzz>>}
Pzz>>


_>Одна неточность:


_>

_>But for multiples of three print “Fizz” instead of the number ...



Подумалось — решение красиво, но вот менять код будет не так-то просто.
Re[3]: Типовые задачи на собеседованиях по программированию с решениями
От: alzt  
Дата: 13.12.16 07:44
Оценка:
Здравствуйте, RussianFellow, Вы писали:

RF>
RF>char *s; // или char s[80];
RF>int  i, n;
RF>char  c;

RF>n = strlen(s);
RF>for (i=0; i<n/2; i++)
RF>{
RF>    c = s[i];
RF>    s[i] = s[n-1-i];
RF>    s[n-1-i] = c;
RF>}
RF>


Задавая такие задачи ожидают что-то вроде использования двух указателей с инкрементом/декрементом.
Re[9]: Типовые задачи на собеседованиях по программированию
От: antonio_banderas Россия  
Дата: 13.12.16 11:43
Оценка:
Здравствуйте, __kot2, Вы писали:

_>>Все современные компиляторы при присваивании в условии выдают варнинги.

_>>Из выше написанной тобой фразы можно сделать вывод, что ты либо последний раз писал код давно, либо пользуешься древними компиляторами, либо глушишь все варнинги, либо оставляешь после себя простыню варнингов и их даже не читаешь.
_>>Например, на большинстве работ, где я работал, в стайл-гайде запрещалось писать код с варнингами, а в теперешней и еще одной фирме даже более того — большинство проектов собирались с -Werror. Тут даже если и захочешь, в условии не получится присвоить. Так что (5 == counter5) это прошлый век.
__>аркгументы, конечно, интересные. но вот мой gcc 4.9.3 — полтора года назад зарелизен варнинг не дает.

Нужно флажок -Wall дать, по умолчанию варнинги отключены.
Для гарантированного отсутствия варнингов можно -Werror. ))

__>>>особенно без тестов, которые, я так понимаю, не для вас

_>>Почему?
__>попробуй, напиши тесты к своему коду

Скорей всего можно тестами подцепиться к std::cout, ну или если нельзя, выход в другой стрим направить, к которому подцепиться тестами. Всё. Дальше читаем output функции и проверяем.
Re[3]: Типовые задачи на собеседованиях по программированию с решениями
От: Kernan Ниоткуда https://rsdn.ru/forum/flame.politics/
Дата: 13.12.16 12:38
Оценка: +1
Здравствуйте, playnext, Вы писали:

S>>Строку перевернуть за О(1) памяти.

P>это очень легкая задача, такие редко задают.
Тогда тебя не затруднит превести работающий код.
Sic luceat lux!
Re[4]: Типовые задачи на собеседованиях по программированию с решениями
От: GarryIV  
Дата: 13.12.16 13:16
Оценка:
Здравствуйте, Kernan, Вы писали:

S>>>Строку перевернуть за О(1) памяти.

P>>это очень легкая задача, такие редко задают.
K>Тогда тебя не затруднит превести работающий код.

Если в языке строки immutable то никак, тут O(N) без вариантов.
Если mutable то какие проблемы поменять символы k и lenght-k-1 местами в цикле?
WBR, Igor Evgrafov
Re[5]: Типовые задачи на собеседованиях по программированию с решениями
От: playnext  
Дата: 13.12.16 15:25
Оценка:
Здравствуйте, GarryIV, Вы писали:

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


S>>>>Строку перевернуть за О(1) памяти.

P>>>это очень легкая задача, такие редко задают.
K>>Тогда тебя не затруднит превести работающий код.

GIV>Если в языке строки immutable то никак, тут O(N) без вариантов.

GIV>Если mutable то какие проблемы поменять символы k и lenght-k-1 местами в цикле?

Если immutable то например:
const char* reverseString(char* s) {
  if (!s || !*s) {
    return s;
  }
  char* first = s;
  char* last = s;
  for (; *last; ++last) {}
  --last;

  for (; first < last; ++first, --last) {
    char temp = *first;
    *first = *last;
    *last = temp;
  }

  return s;
}



Тут пямять Q(1)
Re[6]: Типовые задачи на собеседованиях по программированию с решениями
От: playnext  
Дата: 13.12.16 15:26
Оценка:
Здравствуйте, playnext, Вы писали:

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


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


S>>>>>Строку перевернуть за О(1) памяти.

P>>>>это очень легкая задача, такие редко задают.
K>>>Тогда тебя не затруднит превести работающий код.

GIV>>Если в языке строки immutable то никак, тут O(N) без вариантов.

GIV>>Если mutable то какие проблемы поменять символы k и lenght-k-1 местами в цикле?

P>Если immutable то например:

P>
P>const char* reverseString(char* s) {
P>  if (!s || !*s) {
P>    return s;
P>  }
P>  char* first = s;
P>  char* last = s;
P>  for (; *last; ++last) {}
P>  --last;

P>  for (; first < last; ++first, --last) {
P>    char temp = *first;
P>    *first = *last;
P>    *last = temp;
P>  }

P>  return s;
P>}
P>



P>Тут пямять Q(1)


Если mutable, извиняюсь, слова перепутал.
Re[10]: Типовые задачи на собеседованиях по программированию
От: __kot2  
Дата: 13.12.16 15:54
Оценка:
Здравствуйте, antonio_banderas, Вы писали:
_>Нужно флажок -Wall дать, по умолчанию варнинги отключены.
_>Для гарантированного отсутствия варнингов можно -Werror. ))
нууу, знаешь, приходить в проект, а потом говорить — а давайте вы мне мои недефолтные опции компилятора подключим, это не дело

_>Скорей всего можно тестами подцепиться к std::cout, ну или если нельзя, выход в другой стрим направить, к которому подцепиться тестами. Всё. Дальше читаем output функции и проверяем.

no hire! следующий
Re: Типовые задачи на собеседованиях по программированию с решениями
От: playnext  
Дата: 14.12.16 16:16
Оценка:
Здравствуйте, RussianFellow, Вы писали:

RF>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?

RF>Желательно привести решения этих задач с комментариями или объяснениями. (Стандартный язык для ответов--C++, но можно использовать любой другой--Delphi, C#, Java и т.д.)

Вот например, весьма примитивная задача. Решается за 5 максимум 10 минут.
Есть стек элементов произвольного типа (тип можно выбрать самому).
Необходимо отсортировать элементы в первом стеке используя еще один такой же стек (изначально он тоже может быть непустой).
Само собой нельзя использовать другие коллекции кроме этого дополнительного стека.
Re[10]: Типовые задачи на собеседованиях по программированию
От: AlexGin Беларусь  
Дата: 14.12.16 16:30
Оценка:
Здравствуйте, antonio_banderas, Вы писали:

_>Скорей всего можно тестами подцепиться к std::cout, ну или если нельзя, выход в другой стрим направить, к которому подцепиться тестами. Всё. Дальше читаем output функции и проверяем.

А почему же не сделать сохранение результатов в коллекции — например в коллекции типа std::vector<string>
и в юнит-тесте уже данную коллекцию с выходными результатами крутить?

std::vector<string> vectOutStrings;
for (int i=1; i<=100; i++)
{
    bool mul3 = (i%3)==0;
    bool mul5 = (i%5)==0;

    if(mul3 && mul5)
    { 
    printf("FizzBuzz\n");
    vectOutStrings.push_back("FizzBuzz");
    }    
    else if(mul3) 
    {
    printf("Fizz\n");
    vectOutStrings.push_back("Fizz");
    }
    else if(mul5) 
    {
    printf("Buzz\n");
    vectOutStrings.push_back("Buzz");
    }
    else 
    {
    printf("%d\n",i);
    std::stringstream ss;
    ss << i;
    std::string s = ss.str();
    vectOutStrings.push_back(s);
    }
}


Как вариант — это сохранение в вектор подключать через опцию препроцессора.
Отредактировано 14.12.2016 16:42 AlexGin . Предыдущая версия .
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: Философ Ад http://vk.com/id10256428
Дата: 14.12.16 18:06
Оценка:
Здравствуйте, licedey, Вы писали:

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


RF>>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?

RF>>Желательно привести решения этих задач с комментариями или объяснениями. (Стандартный язык для ответов--C++, но можно использовать любой другой--Delphi, C#, Java и т.д.)

L>Мне в жизни не приходилось передвинуть бит! (с)

L>Вариации: посчитать биты в числе, возвести 2 в степень N без циклов

типа этого _mm_popcnt_u32?
ЗЫ: на плюсах не пишу
Всё сказанное выше — личное мнение, если не указано обратное.
Re[3]: Типовые задачи на собеседованиях по программированию с решениями
От: licedey  
Дата: 14.12.16 23:09
Оценка:
Здравствуйте, Философ, Вы писали:

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


L>>Мне в жизни не приходилось передвинуть бит! (с)

L>>Вариации: посчитать биты в числе, возвести 2 в степень N без циклов

Ф>типа этого _mm_popcnt_u32?

Ф>ЗЫ: на плюсах не пишу

Простите, вы о чем вообще? Погуглил и то не понял.
Re[4]: Типовые задачи на собеседованиях по программированию с решениями
От: licedey  
Дата: 14.12.16 23:40
Оценка:
Здравствуйте, licedey, Вы писали:

L>Здравствуйте, Философ, Вы писали:


Ф>>типа этого _mm_popcnt_u32?

Ф>>ЗЫ: на плюсах не пишу

L>Простите, вы о чем вообще? Погуглил и то не понял.


А, понял. Только на собеседованиях это надо ручками на листочке сделать в цикле for.
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: VladFein США  
Дата: 16.12.16 20:34
Оценка: +1 :)
Здравствуйте, Miroff, Вы писали:

M>FizBuzz


Почему-то самого простого решения никто не предложил:

printf("1\n2\nFizz\n\4\nBuzz\Fizz\n7 ...");
Re[11]: Типовые задачи на собеседованиях по программированию
От: antonio_banderas Россия  
Дата: 19.12.16 13:46
Оценка:
Здравствуйте, AlexGin, Вы писали:

AG>А почему же не сделать сохранение результатов в коллекции — например в коллекции типа std::vector<string>

AG>и в юнит-тесте уже данную коллекцию с выходными результатами крутить?

Потому что код должен быть един — для основной задачи и для тестов.
А у тебя для основной задачи один код (printf), а для тестов другой код (vectOutStrings.push_back).
Чем это плохо? Тем, что по факту тесты не проверяют основной код. Они проверяют код для тестов.

AG>Как вариант — это сохранение в вектор подключать через опцию препроцессора.


Такие ветвления очень усложняют чтение и дальнейшую поддержку. И проблема с двумя разными кодами остается.
Два минуса и ни одного плюса.

Решение — возвращать строку, и потом её выводить на консоль. А тесты эту строку будут просто разбирать и проверять.

std::string composeTask()
{
  // здесь мы всё накидываем в строку.
}

void printTask()
{
  std::cout << composeTask() << std::endl;
}

SOME_TEST_MACRO()
{
  std::string result = composeTask();
  // а здесь разбираем и оцениваем result.
}
Re[12]: Типовые задачи на собеседованиях по программированию
От: __kot2  
Дата: 19.12.16 15:38
Оценка:
Здравствуйте, antonio_banderas, Вы писали:
_>Решение — возвращать строку, и потом её выводить на консоль. А тесты эту строку будут просто разбирать и проверять.
ладно, не буду больше таить интригу — тест не может тестировать результат цикла целиком
Re[13]: Типовые задачи на собеседованиях по программированию
От: antonio_banderas Россия  
Дата: 19.12.16 16:07
Оценка:
Здравствуйте, __kot2, Вы писали:

_>>Решение — возвращать строку, и потом её выводить на консоль. А тесты эту строку будут просто разбирать и проверять.

__>ладно, не буду больше таить интригу — тест не может тестировать результат цикла целиком

Почему?
Re[14]: Типовые задачи на собеседованиях по программированию
От: __kot2  
Дата: 19.12.16 17:35
Оценка:
Здравствуйте, antonio_banderas, Вы писали:
_>Почему?
один тест тестирует одну вещь. а тут вычисление сразу ряда происходит.

если сказать "а ну и фиг с ним" и продолжить писать тесты в таком стиле, то это сделает тесты огромными и невменяемыми (парсинг аутпута — ну что может быть лучше? ). и вылазаит та проблема, на которую так любят жаловаться люди которые тысте не пишут — что писать их прихолится даже больше, чем кода
Re[15]: Типовые задачи на собеседованиях по программированию
От: antonio_banderas Россия  
Дата: 20.12.16 07:50
Оценка:
Здравствуйте, __kot2, Вы писали:

_>>Почему?

__>один тест тестирует одну вещь. а тут вычисление сразу ряда происходит.

__>если сказать "а ну и фиг с ним" и продолжить писать тесты в таком стиле, то это сделает тесты огромными и невменяемыми (парсинг аутпута — ну что может быть лучше? ). и вылазаит та проблема, на которую так любят жаловаться люди которые тысте не пишут — что писать их прихолится даже больше, чем кода


Ок, парсинг аутпута это плохо.
А так, интуитивно — тестировать надо минимальную логическую единицу (функцию, блок, модуль) — цельную. Для тестов код — это черный ящик, они не должны знать, как он устроен внутри, и тем более полагаться на это.
С исходным примером это как посчитать — может минимальной логической единицей быть как решение задачи целиком, так и построчно (каждая строка не зависит от остальных).
Мне больше нравится решение целиком, типа, здесь строки независимы, а где-то могут быть и зависимы. Возможно, дело вкуса.
Да и в чем проблема финальную строку разбить в тестах на массив строк.
Re: Типовые задачи на собеседованиях по программированию с решениями
От: serj.e  
Дата: 02.03.17 21:57
Оценка: 5 (1)
Развернуть на месте UTF8–строку, с варьируемой байтовой шириной символов. Запрещены промежуточные преобразования, сторонние библиотеки, аллокации памяти.
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: ArtK  
Дата: 15.03.17 10:47
Оценка:
Здравствуйте, nekocoder, Вы писали:

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


RF>>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?


N>Есть посвященная как раз этому книга Cracking the Coding Interview.


Я бы сказал что это первый шаг, т.к. набить руку можно только пытаясь решить эти задачи. Для практики есть всякие leetcode и interviewbit
Re[2]: Типовые задачи на собеседованиях по программированию с решениями
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 19.04.17 13:27
Оценка: :)
Здравствуйте, serj.e, Вы писали:

SE>Развернуть на месте UTF8–строку, с варьируемой байтовой шириной символов. Запрещены промежуточные преобразования, сторонние библиотеки, аллокации памяти.


wchar *s; // эта строка
wchar  c1, c2;
int  n;

n = wstrlen(s);
for (i=0; i<n/2; i++)
{
    c1 = s[i];
    c2 = s[n-i-1];
    s[i] = c2;
    s[n-i-1] = c1;
}


Так что-ли?
1613 г. = 2024 г.
Re[3]: Типовые задачи на собеседованиях по программированию с решениями
От: AleksandrN Россия  
Дата: 20.04.17 09:27
Оценка:
Здравствуйте, RussianFellow, Вы писали:

RF>Здравствуйте, serj.e, Вы писали:


SE>>Развернуть на месте UTF8–строку, с варьируемой байтовой шириной символов. Запрещены промежуточные преобразования, сторонние библиотеки, аллокации памяти.


RF>
RF>wchar *s; // эта строка
RF>wchar  c1, c2;
RF>int  n;

RF>n = wstrlen(s);
RF>for (i=0; i<n/2; i++)
RF>{
RF>    c1 = s[i];
RF>    c2 = s[n-i-1];
RF>    s[i] = c2;
RF>    s[n-i-1] = c1;
RF>}
RF>


RF>Так что-ли?


А с чего ты взял, что это код для переворота UTF-8?
Re[4]: Типовые задачи на собеседованиях по программированию с решениями
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 20.04.17 14:24
Оценка:
Здравствуйте, AleksandrN, Вы писали:

AN>А с чего ты взял, что это код для переворота UTF-8?


Ну так для UTF-8 используется тип wchar, не так ли?
1613 г. = 2024 г.
Re[5]: Типовые задачи на собеседованиях по программированию с решениями
От: AleksandrN Россия  
Дата: 20.04.17 15:14
Оценка:
Здравствуйте, RussianFellow, Вы писали:

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


AN>>А с чего ты взял, что это код для переворота UTF-8?


RF>Ну так для UTF-8 используется тип wchar, не так ли?


Для utf-8 — char. Но для кодировки каждого байта используется от 1 до 6 байт. В этом и сложность переворота такой строки.

https://ru.wikipedia.org/wiki/UTF-8
https://ru.wikipedia.org/wiki/UTF-16
https://ru.wikipedia.org/wiki/UTF-32
Re[6]: Типовые задачи на собеседованиях по программированию с решениями
От: RussianFellow Россия http://russianfellow.livejournal.com
Дата: 16.05.17 10:51
Оценка:
Здравствуйте, AleksandrN, Вы писали:

RF>>Ну так для UTF-8 используется тип wchar, не так ли?


AN>Для utf-8 — char. Но для кодировки каждого байта используется от 1 до 6 байт. В этом и сложность переворота такой строки.


Ну и как такая строка переворачивается?
1613 г. = 2024 г.
Re[7]: Типовые задачи на собеседованиях по программированию с решениями
От: AleksandrN Россия  
Дата: 16.05.17 12:28
Оценка:
Здравствуйте, RussianFellow, Вы писали:

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


RF>>>Ну так для UTF-8 используется тип wchar, не так ли?


AN>>Для utf-8 — char. Но для кодировки каждого байта используется от 1 до 6 байт. В этом и сложность переворота такой строки.


RF>Ну и как такая строка переворачивается?


Вариант 1:
Конвертировать в UTF-16, перевернуть, конвертировать обратно.

Вариант 2:
Без конвертации в кодировку с фиксированной шириной символа. Это тебе домашнее задание. Когда сделаешь — выложи код.
Проверь свою функцию на строке:

Как успехи? おそらく、それはあなたのために難しいことではありませんでしたか?

Re[8]: Типовые задачи на собеседованиях по программированию с решениями
От: IID Россия  
Дата: 19.05.17 17:50
Оценка:
Здравствуйте, AleksandrN, Вы писали:

AN>Вариант 1:

AN>Конвертировать в UTF-16, перевернуть, конвертировать обратно.

Вариант не подходит к условиям: аллокации запрещены.
kalsarikännit
Re: Типовые задачи на собеседованиях по программированию с решениями
От: Ночной Смотрящий Россия  
Дата: 20.05.17 19:41
Оценка:
Здравствуйте, RussianFellow, Вы писали:

RF>Коллеги, не могли бы вы подсказать, какие бывают типовые задачи на собеседованиях по программированию?


Если ты опять коллеге по лицу настучишь — один фик уволят. В трудовой то чего написали по поводу причины увольнения?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.