Просили подробно про интервью в Google...

[febb]

Гуглята издеваются на интервью. Например они задают такие классические задачки.

Дан массив целых чисел (положительные и отрицательные) найти кусок в этом массиве,
сумма элементов в котором максимальная.

Это известная задачка. Поэтому кто знает ответ, не залезая в Гугл,
может просто написать тут "знаю". Это своеобразные азы, ликбез
для молодого гугловода... :)

А кто не знает, можете предложить алгоритм тут.
Нам будет забавно узнать какие вы умные. :))

Comments

[bespechnoepero.livejournal.com]

написал бы ты мне програмку, пока не работаешь. попрактикуешься, а заодно и проверим какой ты умный)))

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

[febb.livejournal.com]

Какую програмку?)

[bespechnoepero.livejournal.com]

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

[febb.livejournal.com]

Очень любопытная задачка!

[febb.livejournal.com]

С одинаковыми шариками всё просто:
http://en.wikipedia.org/wiki/Close-packing_of_spheres

[bespechnoepero.livejournal.com]

да, с одинаковыми шариками все просто, поэтому стоит ввести ограничение в программу, что число размеров должно быть от 2 до, скажем, 9. ну и также предотвратить создание кластеров в модели, чтобы программа не жульничала.

мне кажется, что есть смысл ввести понятие "квантов", то есть очень маленьких частиц пространства, из которых состоят и шарики, и пустота между ними. тогда задача сводится на нахождению комбинации с максимальным числом непустых квантов.

[febb.livejournal.com]

Ограничения врядли помогут. Если аналитическое решение затруднительно, то просто "кухне" они вряли помешают.
Задача напоминает о гравитации многих тел. Ведь компактность - минимум энерги... Кажись шравитация 3-х - это максимум на что способна аналитика.

[bespechnoepero.livejournal.com]

Жаль. Такая програмка здорово бы помогла в разработке сверхтвердых керамик и сплавов, но раз аналитика не может помочь, то будем алхимичить по-старому, интуитивно. Авось, что-нибудь испечется съедобное.

[febb.livejournal.com]

В принципе это известный класс задач.
Нахождение минимум функционала с ограничениями.
Задачу надо центрировать.
Центр - это центр тяжести кластера.
Надо найти минимум его момента инерции.
Ограничения просты - расстояния между точками больше суммы радиусов.
Можно пофантазировать, что на самом деле кластеров будет не один, а много...
И тп.п.

[febb.livejournal.com]

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

[febb.livejournal.com]

Точнее приблизиться к центру кластера и с некоторой случайной вероятностью отклониться от этого прямого пути.