Амазон зовет в Сиэтл, сколько денег просить?

[Alexandr]

У меня мозги испорчены мобилами и embedded, у меня в мозгах дополнительные временные массивы и контейнеры просто не укладываются.

делайте над собой усилие

[Леонид Ильич Брежнев]

чтобы был O(n) нужен хеш-меп

Разумеется хэш-мап.

[Alexandr]

чтобы был O(n) нужен хеш-меп

Разумеется хэш-мап.

поумничать ужо низя

[Леонид Ильич Брежнев]

Правильно делаешь, что умничаешь. Это все лишние баллы в плюс.

[vopros]

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

You are in the network operations center where they have found a puzzling issue.
Data packets seem to be looping within the network and they have asked that you find the loop.
It is discovered you can abstract this problem to a directed graph with non-negative values.
Note that in this directed graph each node N can traverse to multiple different nodes M’.
1) Describe how you would find whether there is a loop in the graph
2) Please create the pseudo-code
3) What is the runtime complexity of your algorithm?

[АццкоМото]

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

You are in the network operations center where they have found a puzzling issue.
Data packets seem to be looping within the network and they have asked that you find the loop.
It is discovered you can abstract this problem to a directed graph with non-negative values.
Note that in this directed graph each node N can traverse to multiple different nodes M’.
1) Describe how you would find whether there is a loop in the graph
2) Please create the pseudo-code
3) What is the runtime complexity of your algorithm?

Я такую в Квалкомме решал. Причем каким-то совершенно тупым способом в лоб, с растущим раздражением - ну есть же красивое решение, которого я не знаю, да засчитайте уже слив и давайте другую - а они довольны остались и даже офер сделали

[crypto5]

Ну если отсортированный тогда да. А вот если HE сортированный, тогда либо сортировать, O(n log n), либо использовать внешний мэп, и тогда это будет O(n)

не будет, вам надо еще в этом внешнем мэпе искать каждый раз, а это O(log n), чтобы был O(n) нужен хеш-меп

ЗЫ ну это я автоматом под мэпом подразумеваю реализацию на основе красно-черного дерева

Вопрос избитый, но если занудствовать то хешмап совсем не факт что О(н).

[Eug9n9]

Вот мой тест: Please write code to print out all permutations of a given string. A permutation represents all the ways in which the same collection of objects can be ordered. In this case you will print all possible orderings of the characters within the given string.

[АццкоМото]

Вот мой тест: Please write code to print out all permutations of a given string. A permutation represents all the ways in which the same collection of objects can be ordered. In this case you will print all possible orderings of the characters within the given string.

Ммм... а у строки "мама" будут еще три перестановки, читающиеся "мама" или их таки надо фефективно отфильтровывать? Хотя, по-моему, двольно просто и так и эдак.
НО. То, о чем я стараюсь никогда не забывать. Это хоть и просто, но в рамках интервью облажаться - как нефиг сделать

[Komissar]

общее число unique перестановок будет 4! / (2! * 2!) = 24/4 = 6

[АццкоМото]

общее число unique перестановок будет 4! / (2! * 2!) = 24/4 = 6

Это, очевидно, так и есть. Вопрос только, каковы условия задачи - выдать 24 перестановки как "all permutations" из условия задачи или таки выдать 6 "unique permutations" как подсказывает здравый смысл. Второе таки сложнее (или я не вижу простого шортката)

[AndreyT]

1) Describe how you would find whether there is a loop in the graph

Поиск цикла в орграфе - это просто банальный поиск в глубину (DFS). С стандартной DFS-терминологии ("белые", "серые" и "черные" вершины), в графе есть цикл если и только если в процессе DFS вы, пройдя через очередное ребро, наткнулись на "серую" вершину.

[AndreyT]

Вот мой тест: Please write code to print out all permutations of a given string. A permutation represents all the ways in which the same collection of objects can be ordered. In this case you will print all possible orderings of the characters within the given string.

В таких вопросах всегда возникает закономерный встречный вопрос: а можно просто воспользоваться 'std::next_premutation' и не вдаваться в детали алгоритма перечисления перестановок?

[Физик-Лирик]

общее число unique перестановок будет 4! / (2! * 2!) = 24/4 = 6

По-моему, это все-таки Combinations, а не Permutations.

[crypto5]

общее число unique перестановок будет 4! / (2! * 2!) = 24/4 = 6

По-моему, это все-таки Combinations, а не Permutations.

Да, пермутаций без учета уникальности наверное n! будет.

[Komissar]

общее число unique перестановок будет 4! / (2! * 2!) = 24/4 = 6

По-моему, это все-таки Combinations, а не Permutations.

из-за двух повторяющися букв (каждая по две) в данном случае совпало с C(4,2), но в общем случае надо брать все пермутации (n!) и делить на число перестановок каждой повторяющейся буквы.

http://answers.yahoo.com/question/index ... 938AA5x53p

[crypto5]

общее число unique перестановок будет 4! / (2! * 2!) = 24/4 = 6

По-моему, это все-таки Combinations, а не Permutations.

из-за двух повторяющися букв (каждая по две) в данном случае совпало с C(4,2), но в общем случае надо брать все пермутации (n!) и делить на число перестановок каждой повторяющейся буквы.

http://answers.yahoo.com/question/index ... 938AA5x53p

Чувствуется рука победителя всесоюзных олимпиад по математике ))

[Alex M. Jake]

В таких вопросах всегда возникает закономерный встречный вопрос: а можно просто воспользоваться 'std::next_premutation' и не вдаваться в детали алгоритма перечисления перестановок?

"- You may use any functions or classes from the JDK, STL, or .Net Framework."

PS: мда... Решение - одна строчка...

[Alexandr]

Ну если отсортированный тогда да. А вот если HE сортированный, тогда либо сортировать, O(n log n), либо использовать внешний мэп, и тогда это будет O(n)

не будет, вам надо еще в этом внешнем мэпе искать каждый раз, а это O(log n), чтобы был O(n) нужен хеш-меп

ЗЫ ну это я автоматом под мэпом подразумеваю реализацию на основе красно-черного дерева

Вопрос избитый, но если занудствовать то хешмап совсем не факт что О(н).

исходная задача O(n), hashmap - O(1)

[crypto5]

Ну если отсортированный тогда да. А вот если HE сортированный, тогда либо сортировать, O(n log n), либо использовать внешний мэп, и тогда это будет O(n)

не будет, вам надо еще в этом внешнем мэпе искать каждый раз, а это O(log n), чтобы был O(n) нужен хеш-меп

ЗЫ ну это я автоматом под мэпом подразумеваю реализацию на основе красно-черного дерева

Вопрос избитый, но если занудствовать то хешмап совсем не факт что О(н).

исходная задача O(n), hashmap - O(1)

Если все числа будут вызывать колизии то хешмап может вполне и до O(n) спустится.

[adda_]

общее число unique перестановок будет 4! / (2! * 2!) = 24/4 = 6

По-моему, это все-таки Combinations, а не Permutations.

из-за двух повторяющися букв (каждая по две) в данном случае совпало с C(4,2), но в общем случае надо брать все пермутации (n!) и делить на число перестановок каждой повторяющейся буквы.

http://answers.yahoo.com/question/index ... 938AA5x53p

Я понимаю что во первых абсолютно не квалифайед для такого рода задач и никогда не буду работать ни в одной приличной конторе которая требует умения решать такие задачи.
Но только честно скажите - а нафига это нужно? Кто нибудь хоть раз в реальном проекте заделывал что то подобное?
За 33 года что занимаюсь программированием лично мне ничего этого не понадобилось. И я не знаю никого кому бы такие вещи понадобились в работе.
Типа пытаемся найти умную голову? Ну бог в помощь. Умные головы на самом деле программированием не занимаются и уж точно код не пишут для амазоноф..
Они либо занимаются чем то неденежным из любви к искусству либо деньги делают.

[Alexandr]

Ну если отсортированный тогда да. А вот если HE сортированный, тогда либо сортировать, O(n log n), либо использовать внешний мэп, и тогда это будет O(n)

не будет, вам надо еще в этом внешнем мэпе искать каждый раз, а это O(log n), чтобы был O(n) нужен хеш-меп

ЗЫ ну это я автоматом под мэпом подразумеваю реализацию на основе красно-черного дерева

Вопрос избитый, но если занудствовать то хешмап совсем не факт что О(н).

исходная задача O(n), hashmap - O(1)

Если все числа будут вызывать колизии то хешмап может вполне и до O(n) спустится.

может, "но как правило, этого не происходит" (с) на то он и худший случай, чтоб не прям уж часто случаться

[fruit6]

общее число unique перестановок будет 4! / (2! * 2!) = 24/4 = 6

По-моему, это все-таки Combinations, а не Permutations.

из-за двух повторяющися букв (каждая по две) в данном случае совпало с C(4,2), но в общем случае надо брать все пермутации (n!) и делить на число перестановок каждой повторяющейся буквы.

http://answers.yahoo.com/question/index ... 938AA5x53p

Я понимаю что во первых абсолютно не квалифайед для такого рода задач и никогда не буду работать ни в одной приличной конторе которая требует умения решать такие задачи.
Но только честно скажите - а нафига это нужно? Кто нибудь хоть раз в реальном проекте заделывал что то подобное?
За 33 года что занимаюсь программированием лично мне ничего этого не понадобилось. И я не знаю никого кому бы такие вещи понадобились в работе.
Типа пытаемся найти умную голову? Ну бог в помощь. Умные головы на самом деле программированием не занимаются и уж точно код не пишут для амазоноф..
Они либо занимаются чем то неденежным из любви к искусству либо деньги делают.

это аналог стандартизированных IQ тестов. проверяется насколько боец обладает минимальным уровнем памяти, помнит ли простейшие вещи из школьного курса (в моей школе комбинаторика была частью программы).
кстати, некоторые IT конторы ориентированные на найм свежих выпускников натурально предлагают IQ тесты оптимизированные для спортсменов.
Если бы программирование было сложным, то спрашивали бы дифуры, например. А не пошлость типа на пальцах посчитать о большое.

[vopros]

1) Describe how you would find whether there is a loop in the graph

Поиск цикла в орграфе - это просто банальный поиск в глубину (DFS). С стандартной DFS-терминологии ("белые", "серые" и "черные" вершины), в графе есть цикл если и только если в процессе DFS вы, пройдя через очередное ребро, наткнулись на "серую" вершину.

Андрей вот бы вы еще пример кода привели, было бы просто замечательно.

[АццкоМото]

1) Describe how you would find whether there is a loop in the graph

Поиск цикла в орграфе - это просто банальный поиск в глубину (DFS). С стандартной DFS-терминологии ("белые", "серые" и "черные" вершины), в графе есть цикл если и только если в процессе DFS вы, пройдя через очередное ребро, наткнулись на "серую" вершину.

Андрей вот бы вы еще пример кода привели, было бы просто замечательно.

Там же все просто - красишь сначала все вершины в белое, потом делаешь DFS обход, при спуске вглубь, смотришь на цвет. если белый - красишь в серый и идешь дальше вглубь. если серый - вот он цикл, если черный - там уже были, туда ходить не надо. как уперся в тупик, на обратном пути все красишь в черное