Здравствуйте, THESERG, Вы писали:
THE>все мужики, женатые, около 25-30 лет
THE>Здравствуйте, __kot2, Вы писали:
__>>Здравствуйте, THESERG, Вы писали: THE>>>нет, китаец __>>а народ наш примерно какого возраста был? интересно, кого они набирают все-таки, недавних выпускников (22), наш средний класс (лет 25), руководящий состав (около 30) или же, как тут где-то отмечалось, там хватает дядек и под 40?
Не все женатые и есть меньше 25 =) Но в большей массе возможно
[]
THE>killer question — реализация regexp match на листочке бумаги (просят сразу C/C++ код). Без предварительной подготовки
аее. китаец спрашивал. причем под конец интервью был забавный момент. он мне сказал, что * — жадная, т.е.
a*b
матчит
aoe2b1eb
когда я подкорректировал алгоритм, он начал менять условие, и она вдруг стала не жадной.
вероятность, что я просто не понял его английского — 10%.
он был совсем не френдли, все время ерзал и, как мне показалось, не был настроен на нормальное общение
моё мнение — за 45 минут а бумаге вменяемое решение написать очень трудно
THE>реализовать такое за менее чем 45 минут имхо нереально. Это видимо просто нужно было задрачивать THE>при подготовке к интервью. Я сразу выбрал недостаточно сильный алгоритм, у меня код даже не смотрели — "It doesn't work!" и баста!
КЛ>аее. китаец спрашивал. причем под конец интервью был забавный момент. он мне сказал, что * — жадная, т.е.
=) да да, доброжелательности не чувствовалось...
Здравствуйте, __kot2, Вы писали:
__>Здравствуйте, BulatZiganshin, Вы писали: BZ>>работать должно быстрее, но я бы с подозрением отнёсся к человеку, который даже на интервью занимается premature optimization __>работа у меня такая — оптимизация. целыми днями только ей, родимой, и занимаюсь. голова уже по другому работать не хочет.
Расскажите, как ваш алгоритм будет работать на на строках / паттернах вида
tlp>>Мне кажется, что эта "оптимизация" все равно будет работать за O(mn) (при этом еще и жрать много памяти).
K>Фиг знает, что хотел автор. Но O(mn) можно получить по времени и O(n) памяти, для двумерного дп хранить строчку предыдущего результата только.
Смысл это делать, если можно постоить конечный автомат и найти матчинг за O(длины строки)?
Здравствуйте, tlp, Вы писали:
tlp>>>Мне кажется, что эта "оптимизация" все равно будет работать за O(mn) (при этом еще и жрать много памяти).
K>>Фиг знает, что хотел автор. Но O(mn) можно получить по времени и O(n) памяти, для двумерного дп хранить строчку предыдущего результата только.
tlp>Смысл это делать, если можно постоить конечный автомат и найти матчинг за O(длины строки)?
Возможно — нет, если опишите как делать за O(n) строки — то понятно дело круто.
Здравствуйте, kuzmaprutkov2, Вы писали:
K>Здравствуйте, tlp, Вы писали:
tlp>>>>Мне кажется, что эта "оптимизация" все равно будет работать за O(mn) (при этом еще и жрать много памяти).
K>>>Фиг знает, что хотел автор. Но O(mn) можно получить по времени и O(n) памяти, для двумерного дп хранить строчку предыдущего результата только.
tlp>>Смысл это делать, если можно постоить конечный автомат и найти матчинг за O(длины строки)?
K>Возможно — нет, если опишите как делать за O(n) строки — то понятно дело круто.
Каждый раз встречая *, есть возможности: 1) заюзать звезду за букву 2) проскипать звезду и заюзать символ следующий за звездой.
Как сделать O(n) буду рад узнать решение.
Здравствуйте, kuzmaprutkov2, Вы писали:
K>Возможно — нет, если опишите как делать за O(n) строки — то понятно дело круто.
Не совсем за O(n), еще нужно время на построение автомата, оно зависиит от длины и конфигурации паттерна, но обычно одним автоматом матчится много строк, так что им можно принебречь.
Построение ДКА по паттернам у того же Кормена описано, тайны не составляет. Думаю, на собеседовании достаточно было бы рассказать про сам способ и показать на примере, как строить ДКА, а не писать код (он может быть довольно громоздким).
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, __kot2, Вы писали:
THE>>>нет-нет, простенький, как для файлов, и спец. символов — только звёздочка __>>есть, как мне кажется достаточно простой вариант реализации с временем О(длина имени файла). это вариант с бегущими указателями. начиная с одного такого он двигается вперед по регэкспу, застревая на звездочке и, порождая новые бегущие указатели с этого места в случае дальнейшего совпадения.
BZ>а ты пробовал его реализовать? мне кажется, что без рекурсии ты звёздочку не реализуешь, "порождение указателей" — это видимо способ переложить рекурсию в кучу?
В детстве на олимпиаде решал задачу такого плана: есть две маски (по типу файловых — с * и ?). Определить, есть ли строка, подходящая под обе. Решил без рекурсии, сам потом удивлялся, насколько с ней все проще.
Здравствуйте, tlp, Вы писали:
tlp>Смысл это делать, если можно постоить конечный автомат и найти матчинг за O(длины строки)?
конечный автомат будет делать ровно то же самое, что и обычное решение. просто это суперкомпиляция кода match() для конкретного паттерна. ну а учитывая, что паттерн и так представлен очень эффективной структурой данных — строкой — никакого выигрыша не будет вообще
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, tlp, Вы писали:
tlp>>Смысл это делать, если можно постоить конечный автомат и найти матчинг за O(длины строки)?
BZ>конечный автомат будет делать ровно то же самое, что и обычное решение. просто это суперкомпиляция кода match() для конкретного паттерна. ну а учитывая, что паттерн и так представлен очень эффективной структурой данных — строкой — никакого выигрыша не будет вообще
Не понял, что такое "обычное решение". То, что тут приводили, работает за O(mn). Если автомат построить заранее, то он будет матчить строку за O(n).
Здравствуйте, tlp, Вы писали:
tlp>Здравствуйте, BulatZiganshin, Вы писали:
BZ>>Здравствуйте, tlp, Вы писали:
tlp>>>Смысл это делать, если можно постоить конечный автомат и найти матчинг за O(длины строки)?
BZ>>конечный автомат будет делать ровно то же самое, что и обычное решение. просто это суперкомпиляция кода match() для конкретного паттерна. ну а учитывая, что паттерн и так представлен очень эффективной структурой данных — строкой — никакого выигрыша не будет вообще
tlp>Не понял, что такое "обычное решение". То, что тут приводили, работает за O(mn). Если автомат построить заранее, то он будет матчить строку за O(n).
На входе буковка из слова и в регэкспе *. В какое состояние переходит автомат?
Здравствуйте, tlp, Вы писали:
BZ>>конечный автомат будет делать ровно то же самое, что и обычное решение. просто это суперкомпиляция кода match() для конкретного паттерна. ну а учитывая, что паттерн и так представлен очень эффективной структурой данных — строкой — никакого выигрыша не будет вообще
tlp>Не понял, что такое "обычное решение". То, что тут приводили, работает за O(mn).
да, оно
tlp>Если автомат построить заранее, то он будет матчить строку за O(n).
пруфлинк? или хотя бы объяснение на пальцах, как он обойдётся без бектрекинга, когда в паттерне много '*'?
Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, tlp, Вы писали:
BZ>>>конечный автомат будет делать ровно то же самое, что и обычное решение. просто это суперкомпиляция кода match() для конкретного паттерна. ну а учитывая, что паттерн и так представлен очень эффективной структурой данных — строкой — никакого выигрыша не будет вообще
tlp>>Не понял, что такое "обычное решение". То, что тут приводили, работает за O(mn).
BZ>да, оно
tlp>>Если автомат построить заранее, то он будет матчить строку за O(n).
BZ>пруфлинк? или хотя бы объяснение на пальцах, как он обойдётся без бектрекинга, когда в паттерне много '*'?
Без бэктрекинга — двухмерное ДП =) вроде уже писал, но O(nm).
Здравствуйте, tlp, Вы писали:
tlp>Здравствуйте, kuzmaprutkov2, Вы писали:
K>>На входе буковка из слова и в регэкспе *. В какое состояние переходит автомат?
tlp>Автомат для регекспа "*" состоит из одного допускающего состояния, по всем входным символам он переходит в него же.
Не совсем то имел ввиду. Сейчас поясню.
str = abbbc
reg = a*bc
Вот такой простой в общем случае пример. "а" первая сматчилась с "а" из reg, потом b and * в какое состояние будет переходить автомат(Варианта 2 собственно поглотить букву или проскипать. D примере abbb a*bbb нужно например проскипать).
Здравствуйте, BulatZiganshin, Вы писали:
tlp>>Если автомат построить заранее, то он будет матчить строку за O(n).
BZ>пруфлинк? или хотя бы объяснение на пальцах, как он обойдётся без бектрекинга, когда в паттерне много '*'?
Обьяснение на паольцах сводится к тому, что нужно строить не НКА (где нужен бэктрекинг), а ДКА (где он, очевидно, не нужен)
