Здравствуйте, minorlogic, Вы писали:
M>Здравствуйте, EM, Вы писали:
EM>>Здравствуйте, denisko, Вы писали:
D>>>Здравствуйте, EM, Вы писали:
D>>>Решение как решение, сразу видно, что человек хотел сказать.
EM>>А еще видно, что оно мягко говоря не оптимальное
M>А какое оптимальное ? если предположить что буква строки имеет сложный компаратор, кодировка, case ?
По всем этим причинам не следует перебирать все символы
Реальные пацаны хвалят http://ru.wikipedia.org/wiki/Алгоритм_Бойера_—_Мура_—_Хорспула
Опыт — это такая вещь, которая появляется сразу после того, как была нужна...
Здравствуйте, VsevolodC, Вы писали:
VC>Interview Questions здесь
А самое прикольное, что когда спрашиваеться написать стандартную функцию , то
из ответов на сайте следует, что народ усиллено переписывает эти стандартные
функции по нескульку раз за день в течении своей прогр. практики...
Interview Question for Software Development Engineer at Microsoft: 05.05.2009
Phone interview question: Describe how you would implement the C standard
library function atoi.
Answers & Comments (1)
05.05.2009by Interview Candidate:
I've actually implemented this many time, so it was pretty straightforward to me.
Make sure you define your loop to cover your corner cases, and don't forget about
negative numbers!
Здравствуйте, Nuseraro, Вы писали:
N>Здравствуйте, VsevolodC, Вы писали:
VC>>Interview Questions здесь
N>Нашел там
N>
N>Interview Question for Senior Software Engineer at Google
N>Look for a string in a very long string - a needle in a haystack. Write the program in pseudo-code.
N>function isSubstring (needle, haystack) {
N> for(int i=0; i<length(haystack); i++) {
N> if (needle[0] == haystack[i]) {
N> for(int j=0; j<length(needle; j++)
N> if(needle[j] != haystack[i+j]) break;
N> if (j==length(needle)) return true;
N> }
N> }
N> return false;
N>}
N>
Здравствуйте, EM, Вы писали:
EM>Здравствуйте, Nuseraro, Вы писали:
N>>Здравствуйте, VsevolodC, Вы писали:
VC>>>Interview Questions здесь
N>>Нашел там
N>>
N>>Interview Question for Senior Software Engineer at Google
N>>Look for a string in a very long string - a needle in a haystack. Write the program in pseudo-code.
N>>function isSubstring (needle, haystack) {
N>> for(int i=0; i<length(haystack); i++) {
N>> if (needle[0] == haystack[i]) {
N>> for(int j=0; j<length(needle; j++)
N>> if(needle[j] != haystack[i+j]) break;
N>> if (j==length(needle)) return true;
N>> }
N>> }
N>> return false;
N>>}
N>>
Здравствуйте, denisko, Вы писали:
D>Здравствуйте, EM, Вы писали:
D>Решение как решение, сразу видно, что человек хотел сказать.
Учитывая, что тут может произойти обращение к haystack[length(haystack) — 1 + length(needle) — 1], то просто офигительное решение. Что человек хотел сказать понятно, только косноязычие на лицо.
Здравствуйте, VsevolodC, Вы писали:
VC>Interview Questions здесь
Нашел там
Interview Question for Senior Software Engineer at Google
Look for a string in a very long string - a needle in a haystack. Write the program in pseudo-code.
function isSubstring (needle, haystack) {
for(int i=0; i<length(haystack); i++) {
if (needle[0] == haystack[i]) {
for(int j=0; j<length(needle; j++)
if(needle[j] != haystack[i+j]) break;
if (j==length(needle)) return true;
}
}
return false;
}
Здравствуйте, ArtomNIK, Вы писали:
ANI>А самое прикольное, что когда спрашиваеться написать стандартную функцию , то ANI> из ответов на сайте следует, что народ усиллено переписывает эти стандартные ANI> функции по нескульку раз за день в течении своей прогр. практики...
Здравствуйте, hrensgory, Вы писали:
H>shrecher пишет: >> >> Главная >> "дойная корова" наших H1B-шников пошла под нож.
H>А можно подробнее, для тех кто не в теме ?
Микрософт людей сокращает активно, а МС был основной импортер прогов.
Здравствуйте, olegkr, Вы писали:
O>Здравствуйте, shrecher, Вы писали:
S>>Микрософт людей сокращает активно, а МС был основной импортер прогов. O>Сокращают сейлов.
Сокращают всех: где-то больше, где-то меньше. К примеру, почикали E&D. Вообще маркетинг в последнюю очередь режут, т.к. они рельные деньги прямо сейчас дают. Обычный подход бизнеса: cократи R&D и год живи старыми запасами. Почитай, http://minimsft.blogspot.com/
Здравствуйте, EM, Вы писали:
EM>Здравствуйте, denisko, Вы писали:
D>>Здравствуйте, EM, Вы писали:
D>>Решение как решение, сразу видно, что человек хотел сказать.
EM>А еще видно, что оно мягко говоря не оптимальное
А какое оптимальное ? если предположить что буква строки имеет сложный компаратор, кодировка, case ?
Здравствуйте, EM, Вы писали:
EM>Здравствуйте, denisko, Вы писали:
D>>Здравствуйте, EM, Вы писали:
D>>Решение как решение, сразу видно, что человек хотел сказать.
EM>А еще видно, что оно мягко говоря не оптимальное
Он сойдет если кусок не критичен по быстродействию. И если есть ограниченное время на решение. У большинства извращений худшая ассимптотика таже n*m.
Одно замечение, что если это c++ то код не скомпилиццо.
Здравствуйте, EM, Вы писали:
M>>А какое оптимальное ? если предположить что буква строки имеет сложный компаратор, кодировка, case ?
EM>По всем этим причинам не следует перебирать все символы EM>Реальные пацаны хвалят http://ru.wikipedia.org/wiki/Алгоритм_Бойера_—_Мура_—_Хорспула
Алгоритм посмотрел, но не уверен что будет работать если у символа несколько пердставлений. Буду курить дальше.
Здравствуйте, olegkr, Вы писали:
O>Здравствуйте, shrecher, Вы писали:
S>>Микрософт людей сокращает активно, а МС был основной импортер прогов. O>Сокращают сейлов.
Здравствуйте, Ушастый Ёж, Вы писали:
УЁ>Здравствуйте, EM, Вы писали:
D>>>Решение как решение, сразу видно, что человек хотел сказать. EM>>А еще видно, что оно мягко говоря не оптимальное
УЁ>Треп на тему "оптимальное решение" без указания критерия оптимальности — пустой звон.
А так же признак дилетантизма в обсуждаемом вопросе.
Не указан критерий оптимальности для поиска подстроки... это сильно. Интернесно какой он может быть?
Признак твоего глубокого профессионализма в вопросе "как обкуриться чтобы крыша съехала совсем"
Опыт — это такая вещь, которая появляется сразу после того, как была нужна...
Здравствуйте, EM, Вы писали:
УЁ>>Треп на тему "оптимальное решение" без указания критерия оптимальности — пустой звон. УЁ>А так же признак дилетантизма в обсуждаемом вопросе.
EM>Не указан критерий оптимальности для поиска подстроки... это сильно. Интернесно какой он может быть?
Надо же, ты опять сел в лужу, показав свое полнейшее непонимание окружающего тебя мира. Ладно, дам еще один бесплатный урок. Найти одно единственное слово в огромном тексте в реальном мире мало кому интересно (особенно гуглу), гораздо интересней найти в одном и том же тексте сразу несколько слов (или часть из них). Поэтому критерий может быть выражен не для одного поиска, а для серии. В зависимости от среднестатистического количества слов в группе эффективней будет тот или иной алгоритм. Про ограничение на память (и на носитель/тип доступа к носителю) я молчу, такие вещи в детском саду в кружке по программированию рассказывают.
А еще, как тебе уже намекнули, в реальном мире существуют интервью, на которых критерий оптимальности имеет ограничения в виде размера бумажки\доски и времени, а первое решение часто является лишь поводом продолжить беседу на заданную тему и никто не ждет от тебя реализации алгоритма Боера-Мура. Поэтому критерием оптимальности будет ясное и простейшее решение, которoе вскрывает проблематику задачи.
EM>Признак твоего глубокого профессионализма в вопросе "как обкуриться чтобы крыша съехала совсем"
Ну-ну. В качестве домашнего задания подумай, зависит ли оптимальное решение в смысле того или иного критерия от языка (сравнить русский, английский и китайский языки).
Здравствуйте, Ушастый Ёж, Вы писали:
УЁ>Здравствуйте, EM, Вы писали:
D>>>Решение как решение, сразу видно, что человек хотел сказать. EM>>А еще видно, что оно мягко говоря не оптимальное
УЁ>Треп на тему "оптимальное решение" без указания критерия оптимальности — пустой звон. А так же признак дилетантизма в обсуждаемом вопросе.
Но оно и правда очень странное -- если не требуется оптимальность, то от if(needle[0] == haystack[i]) можно избавиться.
А если требуется, то это извините не оптимизация а хрень полная(ссылку уже дали).
Здравствуйте, maykie, Вы писали:
D>>>>Решение как решение, сразу видно, что человек хотел сказать. EM>>>А еще видно, что оно мягко говоря не оптимальное УЁ>>Треп на тему "оптимальное решение" без указания критерия оптимальности — пустой звон. А так же признак дилетантизма в обсуждаемом вопросе. M>Но оно и правда очень странное -- если не требуется оптимальность, то от if(needle[0] == haystack[i]) можно избавиться. M>А если требуется, то это извините не оптимизация а хрень полная(ссылку уже дали).
Да пускай то конкретное решение странное и с ошибками, но образованные люди всегда рядом со словами "оптимальное решение" пишут слово "критерий".
Здравствуйте, Nuseraro, Вы писали:
N>Здравствуйте, VsevolodC, Вы писали:
VC>>Interview Questions здесь
N>Нашел там
N>
N>Interview Question for Senior Software Engineer at Google
N>Look for a string in a very long string - a needle in a haystack. Write the program in pseudo-code.
N>function isSubstring (needle, haystack) {
N> for(int i=0; i<length(haystack); i++) {
N> if (needle[0] == haystack[i]) {
N> for(int j=0; j<length(needle; j++)
N> if(needle[j] != haystack[i+j]) break;
N> if (j==length(needle)) return true;
N> }
N> }
N> return false;
N>}
N>
N>Удивился.
Действительно. А почему бы не сделать так:
function isSubstring (needle, haystack){
return strstr(haystack, needle) != 0;
}
Здравствуйте, ArtomNIK, Вы писали:
ANI>Здравствуйте, VsevolodC, Вы писали:
VC>>Interview Questions здесь ANI>А самое прикольное, что когда спрашиваеться написать стандартную функцию , то ANI> из ответов на сайте следует, что народ усиллено переписывает эти стандартные ANI> функции по нескульку раз за день в течении своей прогр. практики...
ANI>
ANI>Interview Question for Software Development Engineer at Microsoft: 05.05.2009
ANI>Phone interview question: Describe how you would implement the C standard
ANI>library function atoi.
ANI>
дебильный вопрос на самом деле. хотя спрашивают его в МС регулярно. проблема в том, что на ТА вопросы должны быть общие, без головоломок. А это не так просто. Кстати на этом атои 80% рисует неправильные решения. так что с одной стороны хочется его выкинуть, а с другой вроде свое дело делает.