цитирую: "It doesn't work!"

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

Здравствуйте, __kot2, Вы писали:

__>Здравствуйте, THESERG, Вы писали:
THE>>нет-нет, простенький, как для файлов, и спец. символов — только звёздочка
__>есть, как мне кажется достаточно простой вариант реализации с временем О(длина имени файла). это вариант с бегущими указателями. начиная с одного такого он двигается вперед по регэкспу, застревая на звездочке и, порождая новые бегущие указатели с этого места в случае дальнейшего совпадения.

Здравствуйте, THESERG, Вы писали:

THE>цитирую: "It doesn't work!"

THE>причём интервьювер не захотел разбираться в моём решении (оно чем-то похоже на то, что ты предлагаешь),
THE>и даже не смог привести контрпример. Как я потом узнал, он был уверен, что это надо делать рекурсией,
THE>и всё остальное работать не будет. Спорить я пробывал, но бесполезно — как об стенку горох.

Да тут вроде простенькое двумерное ДП работает =) (не претендую на лучшее решение, может Ахо-Карасика можно приладить и будет лучше в случае серии матчей).

Контрпример дело хорошее, а ты его спрашивал почему он сделал вывод или контрпример?..

Здравствуйте, kuzmaprutkov2, Вы писали:

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

На контрпример времени совсем не осталось. Он попытался привести парочку, а что-то
промямлил про то, что это не сработает, так как [...]. На что чувак говорит, что, короче,
это не будет работать. Раз пять повторил IT DOES NOT WORK. Я записал его в неадекваты и согласился

K>Здравствуйте, THESERG, Вы писали:

THE>>цитирую: "It doesn't work!"

THE>>причём интервьювер не захотел разбираться в моём решении (оно чем-то похоже на то, что ты предлагаешь),
THE>>и даже не смог привести контрпример. Как я потом узнал, он был уверен, что это надо делать рекурсией,
THE>>и всё остальное работать не будет. Спорить я пробывал, но бесполезно — как об стенку горох.

K>Да тут вроде простенькое двумерное ДП работает =) (не претендую на лучшее решение, может Ахо-Карасика можно приладить и будет лучше в случае серии матчей).

K>Контрпример дело хорошее, а ты его спрашивал почему он сделал вывод или контрпример?..

Здравствуйте, THESERG, Вы писали:

THE>Здравствуйте, kuzmaprutkov2, Вы писали:

THE>Да тут вроде простенький просмотр вдоль строки работает
THE>Про карасиков я ничего не знаю (пока что), а ДП это не решение — это скорее подход.

Ясен перец, что подход, его же не везде можно применить, а тут именно указывалось что можно квадратичный зафигачить =) Простенький просмотр.. хм, сколько символов поглащать звёздочкой? как определить что на текущем нужно остановится полгащать звездой и переходить к другим символом строки).


THE>На контрпример времени совсем не осталось. Он попытался привести парочку, а что-то
THE>промямлил про то, что это не сработает, так как [...].
Ну да, это его косяк. Сказать, что не работает и не пояснить.

Здравствуйте, Dfg5, Вы писали:

D>Здравствуйте, kuzmaprutkov2, Вы писали:

K>> Мне сказали что мол через неделю дадут.
K>>После 3го собеседования сказали) где-то читал легенду что если 3 собеседования то дело худо =)
K>>А у вас как дело было?

D>Фигня. У нас у всех по 3 технических было + HR. Предварительно HR сказала что количество ни на что не влияет.
D>Просто пытаются определиться с решением.

Ну тогда желаю удачи =) Отпишитесь, в случае успеха как это было!

Здравствуйте, THESERG, Вы писали:

THE>Здравствуйте, kuzmaprutkov2, Вы писали:

THE>Да тут вроде простенький просмотр вдоль строки работает
THE>Про карасиков я ничего не знаю (пока что), а ДП это не решение — это скорее подход.

THE>На контрпример времени совсем не осталось. Он попытался привести парочку, а что-то
THE>промямлил про то, что это не сработает, так как [...]. На что чувак говорит, что, короче,
THE>это не будет работать. Раз пять повторил IT DOES NOT WORK. Я записал его в неадекваты и согласился

Я так понимаю речь идет о Деби (немолодой суровый индус) из infrastructure team? "It doesn't work. Why you can't do it? It's easy!"
Так что там был скорее не killer question, а killer person. Многие отлично отсобеседовались с другими, но Деби похоже давил жестко всех

Здравствуйте, kuzmaprutkov2, Вы писали:
K>Ээээ. Образец — abcdacd и маска ab*cd. Где останавливаться при звёздочке? до куда бежать?. В общем случае неясно сколько символов нужно покрыть *(при том алго что вы написали).
K>Как предлагаете выяснить количество символов замещаемых звёздочкой? не всё так просто) хотя и не сложно.
шаг 1 — состояние поиска ^ab*cd, где ^ — указатель, разделяющий пройденные символы регэкспа и непройденные еще.
шаг 2 — a^b*cd извлечены буквы a
шаг 3 — ab^*cd извлечены буквы ab. указатель намертво застревает на звездочке, дожидаясь следующего символа после него — c
шаг 4 — ab^*c^d — извлекается символ с, указатель раздваивается
шаг 5 — ab^*cd^ — дошли до конца, но еще не все символы извлечены, последний указатель помирает, идем дальше
шаг 6 — ab^*cd — извлекается a, пропускается
шаг 7 — ab^*c^d — извлекается c
шаг 8 — ab^*cd^ — извлекается d, регэксп пройден, символы кончились, все зашибись, матч есть.

Здравствуйте, THESERG, Вы писали:
THE>причём интервьювер не захотел разбираться в моём решении (оно чем-то похоже на то, что ты предлагаешь),
THE>и даже не смог привести контрпример. Как я потом узнал, он был уверен, что это надо делать рекурсией,
THE>и всё остальное работать не будет. Спорить я пробывал, но бесполезно — как об стенку горох.
не, ну тут его косяк конечно. еще с универа — если тебя на экзамене спрашивают и не хотят разбираться в твоем решении или даже просто привести контрпример, значит, препод сам не знает, заучил одно решение и его и спрашивает.

Здравствуйте, __kot2, Вы писали:

THE>>нет-нет, простенький, как для файлов, и спец. символов — только звёздочка
__>есть, как мне кажется достаточно простой вариант реализации с временем О(длина имени файла). это вариант с бегущими указателями. начиная с одного такого он двигается вперед по регэкспу, застревая на звездочке и, порождая новые бегущие указатели с этого места в случае дальнейшего совпадения.

а ты пробовал его реализовать? мне кажется, что без рекурсии ты звёздочку не реализуешь, "порождение указателей" — это видимо способ переложить рекурсию в кучу?

реализация проста:

match (re,str)
  switch (*re)
    '*': return match(re+1,str) || match(re,str+1)
    '?': return match(re+1,str+1)
    0:   return *str==0
    default: return *re==*str && match(re+1,str+1)

Здравствуйте, BulatZiganshin, Вы писали:
BZ>реализация проста:
BZ>

BZ>match (re,str)
BZ>  switch (*re)
BZ>    '*': return match(re+1,str) || match(re,str+1)
BZ>    '?': return match(re+1,str+1)
BZ>    0:   return *str==0
BZ>    default: return *re==*str && match(re+1,str+1)  
BZ>

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

Здравствуйте, __kot2, Вы писали:

K>>Ээээ. Образец — abcdacd и маска ab*cd. Где останавливаться при звёздочке? до куда бежать?. В общем случае неясно сколько символов нужно покрыть *(при том алго что вы написали).
__>шаг 4 — ab^*c^d — извлекается символ с, указатель раздваивается

а если abcdcdcdcdcd — то делаем десять копий указателя?

Здравствуйте, BulatZiganshin, Вы писали:

BZ>Здравствуйте, __kot2, Вы писали:

K>>>Ээээ. Образец — abcdacd и маска ab*cd. Где останавливаться при звёздочке? до куда бежать?. В общем случае неясно сколько символов нужно покрыть *(при том алго что вы написали).
__>>шаг 4 — ab^*c^d — извлекается символ с, указатель раздваивается

BZ>а если abcdcdcdcdcd — то делаем десять копий указателя?
ога

Здравствуйте, __kot2, Вы писали:
BZ>>а если abcdcdcdcdcd — то делаем десять копий указателя?
__>ога
впрочем, добиться исчерпания стека куда проще, чем кучи

Здравствуйте, __kot2, Вы писали:

BZ>>а если abcdcdcdcdcd — то делаем десять копий указателя?
__>ога

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

работать должно быстрее, но я бы с подозрением отнёсся к человеку, который даже на интервью занимается premature optimization

Здравствуйте, BulatZiganshin, Вы писали:
BZ>работать должно быстрее, но я бы с подозрением отнёсся к человеку, который даже на интервью занимается premature optimization
работа у меня такая — оптимизация. целыми днями только ей, родимой, и занимаюсь. голова уже по другому работать не хочет.

Здравствуйте, __kot2, Вы писали:

__>Здравствуйте, BulatZiganshin, Вы писали:
BZ>>реализация проста:
BZ>>

BZ>>match (re,str)
BZ>>  switch (*re)
BZ>>    '*': return match(re+1,str) || match(re,str+1)
BZ>>    '?': return match(re+1,str+1)
BZ>>    0:   return *str==0
BZ>>    default: return *re==*str && match(re+1,str+1)  
BZ>>

__>не, ну этот вариант конечно компактнее будет. наверное, его и хотели. но что-то мне кажется тормозной он на длинных данных

Да, это легко завернуть и использовать технику как в ДП. А можно как-то быстрее? быстрее чем O(n^2)?

Здравствуйте, 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. Многие отлично отсобеседовались с другими, но Деби похоже давил жестко всех

Здравствуйте, kuzmaprutkov2, Вы писали:
K>Да, это легко завернуть и использовать технику как в ДП. А можно как-то быстрее? быстрее чем O(n^2)?
с какой-нибудь хитрой предварительной подготовкой, думаю, можно. это лучше в книгах каких-нить умных посмотреть. вон, понапридумывали же стописят вариантов деревьев, наверное и с регэкспами что-то есть.

Здравствуйте, THESERG, Вы писали:
THE>нет, китаец
а народ наш примерно какого возраста был? интересно, кого они набирают все-таки, недавних выпускников (22), наш средний класс (лет 25), руководящий состав (около 30) или же, как тут где-то отмечалось, там хватает дядек и под 40?

все мужики, женатые, около 25-30 лет

Здравствуйте, __kot2, Вы писали:

__>Здравствуйте, THESERG, Вы писали:
THE>>нет, китаец
__>а народ наш примерно какого возраста был? интересно, кого они набирают все-таки, недавних выпускников (22), наш средний класс (лет 25), руководящий состав (около 30) или же, как тут где-то отмечалось, там хватает дядек и под 40?