Задачи на интервью

[sergant]

Не сомневаюсь, что уже где-то проскакивало, но найти не смог (да, двойка )

Предлагаю прикрепить тему как "важную" и копить тут задачки/решения, что попадались на интервью...

Речь, не о каком-лобо конкретном языке, но об алгоритме. (я лично, предпочитаю Си для пододных случаев)
Для затравки.
Самому попалось:
1. how to remove duplicate characters in a string?
abcabc -> abc
abcabcdabcdefg -> abcdefg

Алгоритм прикинул, что надо завести HASH, где отмечать всем прибывших...
Не ответ, но алгоритм дает, просто и надеюсь со вкусом:

Code: Select all

#include <stdio.h>
#include <strings.h>
#define	LEN	256
main()
{
	char str[] = "agaabbbcccdddaeffffffffg", *s1, *s2;
	short table[LEN];
	bzero( table, sizeof( table ) );
	printf( "1st: %s\n", str );
	for ( s1 = s2 = str; *s2; )
	{
		table[*s1]++;
		while ( table[*++s2] );
		*++s1 = *s2;
	}
	printf( "2nd: %s\n", str );
}

[sergant]

Если проскочит задачка на интервью, дайте знать, вне зависимости от сложности/срочности...

[Flying Hen]

Рекомендация: всегда делать анализ времени и памяти, даже если не требуют на интервью.

[KVA]

Тут еще важно какие characters. ANSI? UNICODE? UTF-8?

[Flying Hen]

Дополнительные вопросы:
Как сделать линейное время?
Как уменьшить размер table?

[Интеррапт]

Не ответ, но алгоритм дает, просто и надеюсь со вкусом:

Жаль, что для китайцев не сработает. Такой алгоритм наверняка был бы подходящим во времена выхода книги Кернигана-Ритчи.

[avitya]

Дополнительные вопросы:
Как сделать линейное время?
Как уменьшить размер table?

Куда уж линейнее?
А вот к стилю кодирования я бы мог придираться бесконечно

[choto]

На правах рекламы: Cracking the Coding Interview: 150 Programming Questions and Solutions
В этой книге есть и этот и большенство других подобных вопросов с решением.
Вот если бы сюда запостили пару-тройку вопросов не из нее...

[Sergunka]

Не сомневаюсь, что уже где-то проскакивало, но найти не смог (да, двойка )

Предлагаю прикрепить тему как "важную" и копить тут задачки/решения, что попадались на интервью...

Речь, не о каком-лобо конкретном языке, но об алгоритме. (я лично, предпочитаю Си для пододных случаев)
Для затравки.
Самому попалось:
1. how to remove duplicate characters in a string?
abcabc -> abc
abcabcdabcdefg -> abcdefg

Алгоритм прикинул, что надо завести HASH, где отмечать всем прибывших...
Не ответ, но алгоритм дает, просто и надеюсь со вкусом:

Code: Select all

#include <stdio.h>
#include <strings.h>
#define	LEN	256
main()
{
	char str[] = "agaabbbcccdddaeffffffffg", *s1, *s2;
	short table[LEN];
	bzero( table, sizeof( table ) );
	printf( "1st: %s\n", str );
	for ( s1 = s2 = str; *s2; )
	{
		table[*s1]++;
		while ( table[*++s2] );
		*++s1 = *s2;
	}
	printf( "2nd: %s\n", str );
}

Это не имеет особого смысла так как задачки постоянно меняются есть какойто дебильный набор вечно повторяющихся я вроде как год назад описал после длительного поиска, что традиционно спрашивают

http://sergey-vyatkin.livejournal.com/1433.html

Сечас попробовал пройти несколько интервью набор слегонца изменился, но не особо все таже рутина -- хеш стали почаще задавать как сговорились. Порадовали вопросами по пулу потоков -- даже попросили написать свою имплементацию http://download.oracle.com/javase/6/doc ... cutor.html
Я всегда умиляюсь откуда всевозможные фрики берутся на мою голову во время интервью видимо я произвожу правильное впечатление "ботаника"

[sergant]

Это не имеет особого смысла так как задачки постоянно меняются есть какойто дебильный набор вечно повторяющихся я вроде как год назад описал после длительного поиска, что традиционно спрашивают

Таки думаю, что имеет, ибо КМК все работодатели:
1. спрашивают одно и то-же.
2. если ты в состоянии не просто запомнить ответ, но и найти решение, то это плюс...

http://sergey-vyatkin.livejournal.com/1433.html

Отличная история,
Спасибо!

[IvanF]

Алгоритм прикинул, что надо завести HASH, где отмечать всем прибывших...
Не ответ, но алгоритм дает, просто и надеюсь со вкусом:

Code: Select all

#include <stdio.h>
#include <strings.h>
#define	LEN	256
main()
{
	char str[] = "agaabbbcccdddaeffffffffg", *s1, *s2;
	short table[LEN];
	bzero( table, sizeof( table ) );
	printf( "1st: %s\n", str );
	for ( s1 = s2 = str; *s2; )
	{
		table[*s1]++;
		while ( table[*++s2] );
		*++s1 = *s2;
	}
	printf( "2nd: %s\n", str );
}

Код со вкусом...со вкусом глюков. Обычно char - signed, а это значит что даже если это однобайтовые символы, то все что больше 0x7F будет глючить и при не которых условиях вылетать при попытке получить доступ за пределы table.
А зачем было использовать short я вообще не понимаю.
А bzero вы наверное использовали, чтобы даже столь примитивная программа была несовместима с некоторыми main stream компиляторами?

This function is deprecated (marked as LEGACY in POSIX.1-2001): use memset(3) in new programs. POSIX.1-2008 removes the specifica- tion of bzero().

[ZmeyeeD]

1. how to remove duplicate characters in a string?
abcabc -> abc
abcabcdabcdefg -> abcdefg

Если на C++ or Java, то воспользуйтесь чем-нибудь вроде Set/LinkedHashSet etc.

Эти классы проверяют на дубликаты при добавлении. Псевдокод выглядит как-то так:

Code: Select all

Set set;
String newString=null;

while(c = readCharacterFromOriginalString(originalString) != null)
{
    if(set.add(c))
       addCharacterToString(c, newString);
}
return newString;

Учитывая, что Set - это темплейт (если в терминах С++), то, при условии, что тип об'екта в originalString известен, это решение должно работать даже для иерoглифов (для классического Set, если не ошибаюсь, требуется, чтобы об'екты можно было сравнивать на больше-меньше, надеюсь что возможность сравнения существует для иероглифов; если нет, то найти структуру, которая этого не требует ; Java-вская LinkedHashSet это не требует, насчет аналога в C++ - не помню).

[sergant]

Код со вкусом...со вкусом глюков. Обычно char - signed, а это значит что даже если это однобайтовые символы, то все что больше 0x7F будет глючить и при не которых условиях вылетать при попытке получить доступ за пределы table.
А зачем было использовать short я вообще не понимаю.
А bzero вы наверное использовали, чтобы даже столь примитивная программа была несовместима с некоторыми main stream компиляторами?

This function is deprecated (marked as LEGACY in POSIX.1-2001): use memset(3) in new programs. POSIX.1-2008 removes the specifica- tion of bzero().

Замечания не принимаются по трем причинам:
1. "Не ответ, но алгоритм дает"
2. ни первое и ни второе замечание на алгоритм не влияет
3. не факт, что даже "Hello world" заработает на ВСЕХ компиляторах.

[IvanF]

Замечания не принимаются по трем причинам:
1. "Не ответ, но алгоритм дает"
2. ни первое и ни второе замечание на алгоритм не влияет
3. не факт, что даже "Hello world" заработает на ВСЕХ компиляторах.

1. Если бы вы хотели описать алгоритм, то надо было это делать на псевдо языке. Как только вы написали

Code: Select all

#include <stdio.h>
#include <strings.h>

Это уже не алгоритм, а реализация на конкретном языке. И на месте работодателя, я бы такого кандидата с таким алгоритмом выгнал бы в три шеи.

2. см. пункт 1. Неумение/незнание основных элементарний типов используемого языка - полная проф не пригодность.

3. Я не говорил про ВСЕХ. Я упомянул MAIN STREAM. И такую элементарную программу можно сделать совместимой со всеми стандартными компиляторами C.

[ZmeyeeD]

A за такой код

Code: Select all

for ( s1 = s2 = str; *s2; )
   {
      table[*s1]++;
      while ( table[*++s2] );
      *++s1 = *s2;
   }

я бы прекращал интервью немедленно (если это только не кусок какого-нибудь супер-пупер embedded firmware чего-то-там, где памяти 128К а места на диске 2 МВ (но это явно не в данном примере). Это издевательство над тем, кто читает код (и дебагирует его).

[sergant]

Здесь можно спорить долго, алгоритм-реализация-нет коментариев-нет универсальности- и т.д.
Что касается потенциального интервью, КМК это всегда лотерея, всем угодить не реально.

PS. Я 15 лет не программировал.
Естественно отстал от моды...

[ZmeyeeD]

Здесь можно спорить долго, алгоритм-реализация-нет коментариев-нет универсальности- и т.д.
Что касается потенциального интервью, КМК это всегда лотерея, всем угодить не реально.

Код должен быть понятным. Ваше решение вызывает головную боль при остальных его недостатках (главный из которых - это работает только на Extended ASCII).

Кстати, кто помнит порядок операций в

Code: Select all

*++s2

?

Я не помню и помнить не хочу. Если писать, то

Code: Select all

*s2; ++s2

(или в дрогом порядке, в зависимости от того, что правильно)

PS. Я 15 лет не программировал.
Естественно отстал от моды...

Дело не в моде. Если хотите, я поищу в закромах вопросы по алгоритмам и С++.

[StrangerR]

Оё блин!!! А можно это без классовых подходов. писать? Первый то вариант был вполне сносным, а еще его можно просто на битовую шкалу заменить - нужно только помнить что символы могут иметь знак и что нужно заложиться (возможно отдельной программой) и на 16 битный вариант

А то написать это на крутых классах (а еще можно бы и темплейт подсунуть а для полного счастья нужно туда и макросы подложить) и получится -смерть анализатору кода а также отладчику-.

1. how to remove duplicate characters in a string?
abcabc -> abc
abcabcdabcdefg -> abcdefg

Если на C++ or Java, то воспользуйтесь чем-нибудь вроде Set/LinkedHashSet etc.

Эти классы проверяют на дубликаты при добавлении. Псевдокод выглядит как-то так:

Code: Select all

Set set;
String newString=null;

while(c = readCharacterFromOriginalString(originalString) != null)
{
    if(set.add(c))
       addCharacterToString(c, newString);
}
return newString;

Учитывая, что Set - это темплейт (если в терминах С++), то, при условии, что тип об'екта в originalString известен, это решение должно работать даже для иерoглифов (для классического Set, если не ошибаюсь, требуется, чтобы об'екты можно было сравнивать на больше-меньше, надеюсь что возможность сравнения существует для иероглифов; если нет, то найти структуру, которая этого не требует ; Java-вская LinkedHashSet это не требует, насчет аналога в C++ - не помню).

[sergant]

(если это только не кусок какого-нибудь супер-пупер embedded firmware чего-то-там, где памяти 128К а места на диске 2 МВ (но это явно не в данном примере). Это издевательство над тем, кто читает код (и дебагирует его).

Существенное замечание.
Хотя наверное опять же зависит, где спрашивают

[StrangerR]

A за такой код

Code: Select all

for ( s1 = s2 = str; *s2; )
   {
      table[*s1]++;
      while ( table[*++s2] );
      *++s1 = *s2;
   }

я бы прекращал интервью немедленно (если это только не кусок какого-нибудь супер-пупер embedded firmware чего-то-там, где памяти 128К а места на диске 2 МВ (но это явно не в данном примере). Это издевательство над тем, кто читает код (и дебагирует его).

Ну почему же - код еще можно сократить раза в полтора и послать на конкурс _кто напишет данную фигню самым коротким и непонятным путем_ (не используя перл).

[ZmeyeeD]

Оё блин!!! А можно это без классовых подходов. писать?

Ну так и ассемблере можно писать - будет еще эффективнее. Если нет сер'езных constrains, то приносить простоту/читабельность в жертву эффективности я бы не стал.

[StrangerR]

Оё блин!!! А можно это без классовых подходов. писать?

Ну так и ассемблере можно писать - будет еще эффективнее. Если нет сер'езных constrains, то приносить простоту/читабельность в жертву эффективности я бы не стал.

Так речь про то, что излишнее использование классов уменьшает простоту и читабельность... Опыт уже был, и когда 2 человека за 3 дня не смогли найти в 1000 строк кода на C++, как его автор там запрограммировал таймер (в итоге код пошел в помойку и после переписи на перле стал где то 100 строк), и когда тут уже перепись библиотеки с темплейтов и крутых классов на простой подход _пиши как можно проще, а темплейты юзай лишь там где без них никуда_ привел к сокращению бинарников раза в 2 или в 3 (ну и заодно доксиджен смог этот код разобрать). Чем кстати жаба отличается так это абсолютной непонятностью кода в ряде случаев - потому как класс на классе сидит и классом погоняет, и найти _где эта дура копирует файл вместо того чтобы создать симлинк_ становится нереально.

[Medium-rare]

я бы прекращал интервью немедленно (если это только не кусок какого-нибудь супер-пупер embedded firmware чего-то-там, где памяти 128К а места на диске 2 МВ

Да по любому, ничем не оправдано. При чём тут embedded? И там можно писать и эффективно, и красиво и ясно.

[Flash-04]

в этом плане я до сих пор с содроганием вспоминаю Symbian OS, с его непереваримой иерархией классов доведенной до абсурда. Чтобы сделать элементарную вещь, нужно было создавать россыпь экземпляров разных классов.

[ZmeyeeD]

StrangerR, темплейты тоже разными бывают.

String <char> очень сильно облегчает жизнь во многих случаях, если его использовать вместо char *, хотя есть определенная потеря производительности. Но ведь ты согласен, что на C писать удобнее, чем на ассемблере. Почему же ты тогда не согласен использовать возможности C++/Java - это oблегчает жизнь по сравнению с C?