Я ничего не перепутал. Алгоритм КМП работает с подстроками, а не с регекспами.
Если построить ДКА по паттерну, любую строку он отматчит за O(n). По ссылкам, что я привел, достаточно информации о том, как это делается и почему это работает.
По ссылке на историю создания бибилотеки re2, кстати, очень подробно написано про то, почему большинство людей заблуждается относительно скорости работы регекспов и считают, что нужен бэктрекинг (они банально не в курсе про разницу между НКА и ДКА). Я когда это читал, не верил, что все так плохо. Теперь верю.
> K>После 3го собеседования сказали) где-то читал легенду что если 3 собеседования то дело худо =)
> Фигня. У нас у всех по 3 технических было + HR. Предварительно HR сказала что количество ни на что не влияет.
HR так всем говорит
Но вообще я знаю людей которым после 3-х (+одно с HR) сделали
предложение. Так что про 3 собеседования не совсем верно.
Здравствуйте, Shellac, Вы писали:
S>В связи с очередным приездом Bing Team, делитесь информацией у кого уже был скриниг, что спрашивали. Может, кто-нибудь уже получил приглашение на face-to-face интервью. И вопрос к тем, кто в прошлом году получил оффер: как готовились, какие источники использовали?
а можно общественности теперь сказать кто шел как .NET какие вопросы были?
Общая идея — если по паттерну построить НКА, то чтоб сматчить строчку — надо обойти этот НКА. Обойти его можно как вширь так и вглубь (аналогично обходам графа). Обход вглубь — это и есть алгоритм с откатами (бэктрекингом). Обход вширь — это это обход с запоминанием более чем одного состояния (то есть в каждый конкретный момент можем находиться в нескольких состояниях). В первом случае тратим время, во втором — память.
Каждый НКА можно преобразовать в эквивалнтный ДКА. Для ДКА обходы вширь и вглубь совпадают — так как из каждого состояния есть только один переход по заданному символу.
Для примера возьмем шаблон "a*a*b". Построим автомат:
Обход вглубь (с откатами) для строки "aaab":
^aaab q0
a^aab q1
aa^ab q1 Пошли по q1-*->q1
aaa^b q1 Пошли по q1-*->q1
aaab^ q1 Пошли по q1-*->q1, Fail, строка кончилась а q1 не терминальное состояние
aaa^b q1 Откатываемся
aaa^b q1 q1-a->q1 не подходит
aa^ab q1 Откатываемся дальше
aa^ab q2 Пошли по q1-a->q2
aaa^b q2 Пошли по q2-*->q2
aaab^ q2 Пошли по q2-*->q2, Fail, строка кончилась а q2 не терминальное состояние
aaa^b q2 Откатываемся
aaab^ q3 Пошли q2-b->q3, q3 финальное и строка кончилась — Epic win
Теперь обход вширь (уже без откатов):
^aaab {q0}
a^aab {q1} q0-a->q1
aa^ab {q1,q2} q1-*->q1,q1-a->q2
aaa^b {q1,q2} q1-*->q1,q1-a->q2,q2-*->q2
aaab^ {q1,q2q3} q1-*->q1,q2-*->q2,q2-b->q3, Win: строка кончилась, в нашем множестве состояний есть финальное
Здесь мы одновременно можем находиться во всех состояниях, поэтому худшая сложность O(l*n) где l — длина строки, n — количество сотояний. Зато откатов уже нет.
Ну и теперь преобразуем этот автомат в ДКА:
Теперь для обходя надо помнить только одно состояние, и не надо делать откаты:
^aaab q0
a^aab q1
aa^ab q2
aaa^b q2
aaab^ q3 Win: строка кончилась, состояние финальное
Очевидно, что здесь сложность O(l) где l — длина строки. Где же нас кидают? При постороении ДКА число сотояний может вырасти экспоненциально. Впрочем здесь простые шаблоны, нет альтернатив и групп (например мы не можем написать шаблон ((a*)*)*) поэтому в данном конкретном случае все достаточно просто.
В случае с регулярками алгоритм с откатами в худшем случае будет работать за экспоненциальное время, без откатов (обход вширь) — за O(l*n), ДКА будет работать за O(l) но надо будет потратить время на построение ДКА.
ЗЫ Извиняюсь за капитанство, выше tlp написал тоже самое, только без картинок
Здравствуйте, ettcat, Вы писали:
E>Но вообще я знаю людей которым после 3-х (+одно с HR) сделали E>предложение. Так что про 3 собеседования не совсем верно.
Хм =) это уже в последний заезд бригады)? августовский
Здравствуйте, ettcat, Вы писали:
>> K>После 3го собеседования сказали) где-то читал легенду что если 3 собеседования то дело худо =)
>> Фигня. У нас у всех по 3 технических было + HR. Предварительно HR сказала что количество ни на что не влияет.
E>HR так всем говорит
E>Но вообще я знаю людей которым после 3-х (+одно с HR) сделали E>предложение. Так что про 3 собеседования не совсем верно.
И ещё небольшой вопросик) Были ли те кому предложение делали прямо после интервью, на беседе с HR. Или так делают всем кого берут ?
Поделитесь инфой плиз)
но в любом случае, это не та задача, которую следует задавать на 45-минутом собеседовании
Здравствуйте, Константин Л., Вы писали:
КЛ>Здравствуйте, THESERG, Вы писали:
КЛ>[]
THE>>killer question — реализация regexp match на листочке бумаги (просят сразу C/C++ код). Без предварительной подготовки
КЛ>аее. китаец спрашивал. причем под конец интервью был забавный момент. он мне сказал, что * — жадная, т.е.
КЛ>a*b КЛ>матчит КЛ>aoe2b1eb
КЛ>когда я подкорректировал алгоритм, он начал менять условие, и она вдруг стала не жадной. КЛ>вероятность, что я просто не понял его английского — 10%. КЛ>он был совсем не френдли, все время ерзал и, как мне показалось, не был настроен на нормальное общение
КЛ>моё мнение — за 45 минут а бумаге вменяемое решение написать очень трудно
THE>>реализовать такое за менее чем 45 минут имхо нереально. Это видимо просто нужно было задрачивать THE>>при подготовке к интервью. Я сразу выбрал недостаточно сильный алгоритм, у меня код даже не смотрели — "It doesn't work!" и баста!
КЛ>[]
In the above case, the routine will find that the first "b" after the wildcard matches the source after the "a", but the following "d" in the patterh doesn't match the "c" from the source and returns false, although the sequence "bd" exists later in the string.
If one character fails in the "exact matching" routine after a wildcard, the routine should extend the wildcard and search the rest of the string and see whether the exact match comes later in the string.
Sign In·View Thread·Permalink
I was able to address the bug by modifying the following section:
case AnyRepeat:
match = true;
s++;
if (*s == *q) p++;
break;
to
case AnyRepeat:
match = true;
s++;
if (*s == *q){
// make a recursive call so we don't match on just a single character
if (pattern_match(s,q) == true {
p++;
}
}
break;
Здравствуйте, kuzmaprutkov2, Вы писали:
K>Хм =) это уже в последний заезд бригады)? августовский
Кому-нибудь уже проводили телефонное собеседование в Ad Team? Или пока только сбор резюме и рано суетиться?
Наихудший случай для этого алгоритма — '***...*a' против 'aa.....aab' будет давать экспоненциальное время/память (мемоизация или прямое построение ДП-таблицы спасет).
С практической точки зрения — просто, красиво, и для большинства шаблонов пойдет (я не видел шаблонов с более чем 3 звездочками).
Здравствуйте, Faland, Вы писали:
F>Здравствуйте, THESERG, Вы писали:
THE>>Здравствуйте, kuzmaprutkov2, Вы писали:
THE>>Да тут вроде простенький просмотр вдоль строки работает THE>>Про карасиков я ничего не знаю (пока что), а ДП это не решение — это скорее подход.
THE>>На контрпример времени совсем не осталось. Он попытался привести парочку, а что-то THE>>промямлил про то, что это не сработает, так как [...]. На что чувак говорит, что, короче, THE>>это не будет работать. Раз пять повторил IT DOES NOT WORK. Я записал его в неадекваты и согласился
F>Я так понимаю речь идет о Деби (немолодой суровый индус) из infrastructure team? "It doesn't work. Why you can't do it? It's easy!" F>Так что там был скорее не killer question, а killer person. Многие отлично отсобеседовались с другими, но Деби похоже давил жестко всех
Оо, узнаю этого индуса У меня на нем все и закончилось, хотя до него все нормально шло. Вообще после этого решил такие интервью впредь не посещать, сомнительное удовольствие это. Время только зря тратить.
Здравствуйте, Shellac, Вы писали:
S>Оо, узнаю этого индуса У меня на нем все и закончилось, хотя до него все нормально шло. Вообще после этого решил такие интервью впредь не посещать, сомнительное удовольствие это. Время только зря тратить.
Здравствуйте, THESERG, Вы писали:
THE>нет-нет, простенький, как для файлов, и спец. символов — только звёздочка K>>Ого! regexp match прямо таки полнофункциональный? или что-нибудь из серии вайлд кард?
Больше похоже на логическую задачу На яве написал, но как работает я думаю понятно. Для особых случаев, когда начинается или кончается * нужно модифицировать.
public boolean match(String str, String pattern, boolean greedy) {
// разбить паттерн на подстроки разделенные *
String[] parts = pattern.split("\\*");
for (int i = 0; i<parts.length; ++i) {
int idx = greedy ? str.lastIndexOf(parts[i]) : str.indexOf(parts[i]);
if (idx == -1) {
return false;
}
str = str.substring(idx + parts[i].length());
}
// остаток строки должен быть пустымreturn str.length() == 0;
}
> Больше похоже на логическую задачу На яве написал, но как работает я думаю понятно. Для особых случаев, когда начинается или кончается * нужно модифицировать. > >
> public boolean match(String str, String pattern, boolean greedy) {
> // разбить паттерн на подстроки разделенные *
> String[] parts = pattern.split("\\*");
> for (int i = 0; i<parts.length; ++i) {
> int idx = greedy ? str.lastIndexOf(parts[i]) : str.indexOf(parts[i]);
> if (idx == -1) {
> return false;
> }
> str = str.substring(idx + parts[i].length());
> }
> // остаток строки должен быть пустым
> return str.length() == 0;
> }
>
> > best regards, > ziggy
В данном случае без разницы — жадные или нет наши звездочки. Есть
разница когда subgroup извлекаем, а для простого match разницы нет.
Ваш пример не будет работать в случае: 'a*a' ~ 'aaaaaa'.
> аее. китаец спрашивал. причем под конец интервью был забавный момент. он мне сказал, что * — жадная, т.е.
> когда я подкорректировал алгоритм, он начал менять условие, и она вдруг стала не жадной.
В данном случае не важно — жадная звездочка или нет. Мы же должны
сматчить всю строчку (или не сматчить), а не префикс.
Жадность важна при subgroup matching, или для поиска подстроки по
шаблону.
Например 'a*a*a' ~ 'aaaaaaa' — неважно как мы сматчим 'a(a)a(aaa)a'
(нежадная *) или 'a(aaa)a(a)a' (жадная) или вообще 'a(aa)a(aa)a' (не
пойми что). На выходе все равно true.
Здравствуйте, ettcat, Вы писали:
E> В данном случае без разницы — жадные или нет наши звездочки. Есть E>разница когда subgroup извлекаем, а для простого match разницы нет.
E> Ваш пример не будет работать в случае: 'a*a' ~ 'aaaaaa'.
да, есть такое, проблема поиска первой подстроки, можно пофиксить так
// первая подстрока паттерна не может быть "жадной"int idx = (greedy && i != 0) ? str.lastIndexOf(parts[i]) : str.indexOf(parts[i]);
if (i == 0 && idx != 0) {
return false; // первая подстрока паттерна должна быть в началае
}
вместо
int idx = greedy? str.lastIndexOf(parts[i]) : str.indexOf(parts[i]);
> // первая подстрока паттерна не может быть "жадной"
> int idx = (greedy&& i != 0) ? str.lastIndexOf(parts[i]) : str.indexOf(parts[i]);
> if (i == 0&& idx != 0) {
> return false; // первая подстрока паттерна должна быть в началае
> }
>
?
