Очень долго долбался с задачей "String Similarity" с сайта InterviewStreet. И так, и эдак ковырял, но удавалось уложиться только в 8 тестов из 10.
А на самом деле оказалось, что нужно просто применить Z-функцию. Мда, пошел читать букварь... Кстати, не могу найти английское название Z-функции. Если кто знает, напишите, плз.
З.Ы. На Хабре можно почитать хороший разбор алгоритмов поиска подстрок.
Взято отсюда. На языке оригинала цитата звучит лучше, чем в переводе, поэтому оставляю как есть.
Most companies (including web startups) are looking to “wow” with their products, when in reality what they should be looking for is an ‘of course’ reaction from their users.Christian Lindholm,
Chief Innovation Officer at Fjord
В двух словах смысл следующий: хорошо спроектированный продукт в первую очередь должен вызывать у пользователя чувство, что он знает, как пользоваться продуктом, а уже потом чувство восхищения формами.
В инете довольно много вопросов типа "как перенаправить вывод googletest с консоли в окно VS Output" от людей, которые пытаются подружить Visual Studio и googletest. Советы им дают самые разные, например, использовать PostBuildEvent или установить какой-нибудь плагин к Студии.
Хотя на мой взгляд самый удобный (гибкий, масштабируемый, переносимый) способ - это создать свою реализацию класса Printer и подключить её к фреймворку параллельно с остальными принтерами. Такой подход описан в примере №9 док-ции по GoogleTest Framework.
Сначала реализовать класс принтера, наследованный от EmptyTestEventListener:
// Provides alternative output mode which produces minimal amount of
// information about tests.
class TersePrinter : public EmptyTestEventListener {
void outDebugStringA (const char *format, ...)
{
va_list args;
va_start( args, format );
int len = _vscprintf( format, args ) + 1;
char *str = new char[len * sizeof(char)];
vsprintf(str, format, args );
OutputDebugStringA(str);
delete [] str;
}
// Called after all test activities have ended.
virtual void OnTestProgramEnd(const UnitTest& unit_test) {
outDebugStringA("TEST %s\n", unit_test.Passed() ? "PASSED" : "FAILED");
}
// Called before a test starts.
virtual void OnTestStart(const TestInfo& test_info) {
outDebugStringA(
"*** Test %s.%s starting.\n",
test_info.test_case_name(),
test_info.name());
}
// Called after a failed assertion or a SUCCEED() invocation.
virtual void OnTestPartResult(const TestPartResult& test_part_result) {
outDebugStringA(
"%s in %s:%d\n%s\n",
test_part_result.failed() ? "*** Failure" : "Success",
test_part_result.file_name(),
test_part_result.line_number(),
test_part_result.summary());
}
// Called after a test ends.
virtual void OnTestEnd(const TestInfo& test_info) {
outDebugStringA(
"*** Test %s.%s ending.\n",
test_info.test_case_name(),
test_info.name());
}
}; // class TersePrinter
Теперь подключить к юнит тестам вместе с другими принтерами:
UnitTest& unit_test = *UnitTest::GetInstance(); TestEventListeners& listeners = unit_test.listeners(); listeners.Append(new TersePrinter);
Всё. Теперь результаты будут выводиться без проблем и в окно Output, и в консоль, и куда-то еще, если подключены дополнительные принтеры. Формат вывода можно изменять по своему вкусу. Кроме этого, по клику в окне Output можно будет "прыгать" на код "свалившегося" теста.
Часто встречающаяся задача на оптимизацию.
Есть два шарика и небоскрёб в 100 этажей. Если бросать шарики из окон небоскрёба, то начиная с какого-то этажа они будут разбиваться вдребезги (и после этого разбившийся шарик уже нельзя будет использовать). Нужно предложить алгоритм, который поможет найти этот роковой этаж за оптимальное число итераций. Шарики не обязательно сохранять целыми к концу алгоритма.
О проблемах переносимости приложений с использованием мьютексов. Мьютексы есть и в Windows и в POSIX, только работают они по-разному.
В Windows мьютексы позволяют выполнять рекурсивные локи из одного и того же потока без каких-либо deadlock'ов. В этом случае просто инкрементируется счетчик рекурсивных локов. Соответственно, чтобы освободить мьютекс для других потоков нужно будет столько же раз выполнить unlock(). Это их стандартное поведение, которое никак не изменить. Нужно просто учитывать это при дизайне алгоритмов приложения.
В POSIX мьютексы по-умолчанию не позволяют выполнять рекурсивные локи (т.е. второй вызов лока переведет поток в состояние ожидания), однако такое поведение может быть изменено путем изменения типа мьютекса. Возможно три варианта: 1) рекурсивные локи возможны (PTHREAD_MUTEX_RECURSIVE); 2) рекурсивные локи невозможны (PTHREAD_MUTEX_NORMAL); 3) режим errorcheck - рекурсивные локи невозможны, но вместо ожидания функция lock() возвращает ошибку (PTHREAD_MUTEX_ERRORCHECK).
Получается, что при необходимости портирования приложения с одной платформы на другую возможны некоторые проблемы. Например, при переходе с POSIX на Windows поведение PTHREAD_MUTEX_NORMAL невозможно, если не предусмотрено архитектурой. Как вариант, нужно будет заменить "родной" Windows-мьютекс на искусственный - можно использовать для этого семафор со значением 1, либо использовать какую-то стороннюю реализацию мьютекса, например из библиотеки Boost.
Девочки, когда мне было столько лет, сколько вам, мои родители говорили: "Том, доедай свой завтрак - люди в Китае и Индии умирают с голоду". А сегодня я говорю вам: "Девочки, доделывайте ваше домашнее задание — люди в Китае и Индии умирают от желания получить вашу работу".
В современном Китае Билл Гейтс — это Бритни Спирс. В современной Америке Бритни Спирс — это Бритни Спирс. Вот, в чем наша проблема.
Бесплатная утилита с функциональностью memcheck — Dr.Memory. Я давно такую искал, наконец-то она появилась.
Работает под Windows и Linux. Запускается из консоли, довольно легко настраивается (например, на отсеивание ненужных срабатываний). Отслеживает утечки памяти, неправильное освобожение, чтение/запись в "неправильные" области и т.п.
При этом позиционируется как самый быстрый, уверяют, что обгоняет даже valgrind. Думаю, что коммерческим инструментам он всё же будет проигрывать, но пользоваться им вполне можно — пробовал сам под Windows, рекомендую.
Вообще хороший список таких альтернатив: http://stackoverflow.com/questions/413477/is-there-a-good-valgrind-substitute-for-windows
Помню давным-давно в далекой далекой галактике в MS Visual C++ 6 был пункт меню "Generate Makefile", который делал возможным сборку C++-проектов без запуска IDE. Правда, Makefile использовал какие-то свои правила только частично похожие на обычные posixсовые, и вместо make был NMAKE. Но это мелочи.
Недавно обнаружил, что MS на этом не остановилась. Сейчас в VC++ 2010 еще пока есть NMAKE, но пункта генерирования makefile уже нет. Если хочется использовать makefile, то его нужно писать руками. Если есть нужда автоматизировать сборку проектов, то нужно пользоваться утилитой msbuild, которая идет в комплекте .Net Framework.
Отдельная утилита сбоки есть - и на том спасибо, как говорится. Да вот беда - чтобы собрать проект VC++ 7.0 при установленном .Net Framework 4, нужно либо открывать проект в IDE для конвертирования файла проекта в более новый формат, либо устанавливать более старый .Net Framework. Другого способа, кажется, нет.
Учитывая "нововведения" в последних версиях MSVS, то IDE скоро будет нужен только для сборки проекта.
UPD. В дополнение к .Net Framework еще нужно установить Microsoft Windows SDK с выбранными ".NET Development"->"Tools", "Visual C++ compilers" и "Intellisense and Reference Assemblies". Иначе проекты Visual C++ 2010 собираться скорее всего не будут.