Я смотрел лаже в лицо и не боюсь называть её по имени

[feldgendler]

Кандидат приходит устраиваться на работу водителем. В резюме у него пять лет за баранкой пылесоса грузовика и восемь - легковушки. Я сажаю его в малолитражку и прошу в качестве демонстрации проехать полсотни метров по прямой, повернуть направо и там остановиться возле знака «P». Почти оскорбительно простое задание, не правда ли

Comments

[feldgendler]

Я не могу раскрывать задачи, которые использую на собеседованиях, но вот задачка примерно такого же уровня сложности. Подсчитать, сколько раз в текстовой строке встречается заданное сочетание из двух букв (именно в указанном порядке, регистронезависимо).

count(str, char1, char2)

[grundik]

1. Язык?
2. Буквы подряд, или между ними могут быть другие буквы?

[feldgendler]

Буквы подряд и именно в таком порядке. Язык не существенен, пусть будет, к примеру, плоский C.

count('repetition', 't', 'i') = 2

[max630]

а count("eee", 'e', 'e')? :)

[feldgendler]

Тоже 2.

[grundik]

У меня в резюме си вообще нет, но на собеседовании написал бы как-то так:

int count(char *str, char ch1, char ch2)
{
int res = 0;
int len = strlen(str); // про size_t пока забудем, некритично, про случай, когда *str=null тоже забудем
for (int i = 0; i

Как это связано с моим реальным скиллом я хз, если честно. В реальности таких функций обычно не нужно, а если нужно - есть библиотеки, стековерфлоу и прочий гугль, есть контекст (например, тред-сейф нам надо или там перфоманс дикий).

Меня никогда, ни на одном собеседовании, не просили писать подобное.

[feldgendler]

Здесь я бы на собеседовании попросил избавиться от дополнительного прохода по строке для вычисления её длины, но вообще зачёт. У тех, о ком пост, даже близко нет такого уровня, который ты сейчас продемонстрировал.

[ext_767932]

Но ведь это логично и просто (последний раз за Си и плюсы садился 14 лет назад)

[bamsic]

А какая разница, какой язык?
Ведь это в первую очередь алгоритм, а уже потом язык.
Сначала реализуешь алгоритм, потом улучшаешь его в зависимости от возможностей конкретного языка.

[ext_363140]

Я без спойлеров минут за 15 написал такое

for (i=0; str[i]!='\0' && str[i+1]!='0';i++)
if str[i] == char1 && str[i+1] == char2:
count++;
// ??? if str[i+2] == '\0' break else i++

при том что не знаю С вообще, но вообще я мыслю примерно в таких категориях:

(count (re-matches (re-pattern (apply string char1 char2)) str))

[ext_506501]

Я тоже сразу подумал про такое решение, но мне не понравилось, что мы смотрим на элементы дважды. Один раз как i+1 а второй раз как на i, когда i увеличили. Получается O(2*n) ( что всё ещё O(n), но всё же...)
можно чуть оптимальнее. Код а-ля Джава/C#
int count(string str, char c1, char c2){
int prevC1 = Int32.MinValue();
int result = 0;
for (int i = 0; i < str.Length; i++){
result += (str[i] == c2 && i - prevC1 == 1) ? 1 : 0;
if (str[i] == c1) prevC1 = i;
}
return result;
}

У нас такие простые штуки спрашивают разве что на телефонном скрининге.
Но такие задачки - это хорошо.
Меня очень радуют интервьюиры, которые пытаются спросить сигнатуры методов каких-нибудь библиотек. Или когда 3 человека раунд за раундом спрашивают что такое хэшфункция.
Или как использовать Wait/Notify и ответ, что это вообще-то устарелые вещи и я использую Read/Write locks их не устраивает. :)

[ext_363140]

Вполне вероятно, что доступ к строкам в моем куске кода будет оптимизирован компилятором до состояния O(n).

Вообще, в первую очередь я вспомнил про одну статью в которой Брайан Керниган описывает базовый движок регулярных выражений на С, поддерживающий паттерны типа "^c.с*с$" и у него все это укладывалось в 15 строк кода.

Для меня локи, если их больше двух - это минное поле, поэтому лично я в минимально нетривиальных вещах использую акторы.

[feldgendler]

В Вашем решении тоже два чтения каждого элемента.

[feldgendler]

Забыли о регистронезависимости. И попрошу сделать его без библиотечных функций (ограничимся поддержкой ASCII).

[ext_1207342]

/* Преобразование символов в верхний регистр */
char upper(char c)
{
/* в C++ такая констукция (константный массив) возможна, но не помню, возможна ли в чистом C */
static const char UPPER[256] = { /* массив из 256 символов, в которых на месте маленьких букв a-z расположены большие A-Z, для сообщения на форум этот массив писать не стал */ } ;

return UPPER[(unsigned char)c];
}

int count(const char *str, char c, char c1)
{
if ( str == NULL ) // некоррек
return -1;
if ( !str[0] || !str[1] ) // длина меньше 2
return 0;

int result = 0;
char *s = (char *)str;
char *s1 = s+1;

while ( s1 )
{
if ( upper(*s) == upper(c) && upper(*s1) == upper(c1) )
result++;

s++;
s1++;
}

return result;
}
/* компилировать и запускать не пробовал */

[feldgendler]

Непонятно, зачем нужна переменная s, отдельная от str.

Код выглядит правильным, но его можно значительно ускорить.

Ну и хотелось бы увидеть код, инициализирующий массив UPPER, ведь не вручную же Вы будете перечислять его элементы.