![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Просили подробно про интервью в Google...
Гуглята издеваются на интервью. Например они задают такие классические задачки.
Дан массив целых чисел (положительные и отрицательные) найти кусок в этом массиве,
сумма элементов в котором максимальная.
Это известная задачка. Поэтому кто знает ответ, не залезая в Гугл,
может просто написать тут "знаю". Это своеобразные азы, ликбез
для молодого гугловода... :)
А кто не знает, можете предложить алгоритм тут.
Нам будет забавно узнать какие вы умные. :))
Дан массив целых чисел (положительные и отрицательные) найти кусок в этом массиве,
сумма элементов в котором максимальная.
Это известная задачка. Поэтому кто знает ответ, не залезая в Гугл,
может просто написать тут "знаю". Это своеобразные азы, ликбез
для молодого гугловода... :)
А кто не знает, можете предложить алгоритм тут.
Нам будет забавно узнать какие вы умные. :))
no subject
ну и в портфолио такая програмка не помешает. слова хорошо, но лучше один раз показать, что ты можешь, чем сто раз рассказать.
no subject
no subject
no subject
no subject
http://en.wikipedia.org/wiki/Close-packing_of_spheres
no subject
мне кажется, что есть смысл ввести понятие "квантов", то есть очень маленьких частиц пространства, из которых состоят и шарики, и пустота между ними. тогда задача сводится на нахождению комбинации с максимальным числом непустых квантов.
no subject
Задача напоминает о гравитации многих тел. Ведь компактность - минимум энерги... Кажись шравитация 3-х - это максимум на что способна аналитика.
no subject
no subject
Нахождение минимум функционала с ограничениями.
Задачу надо центрировать.
Центр - это центр тяжести кластера.
Надо найти минимум его момента инерции.
Ограничения просты - расстояния между точками больше суммы радиусов.
Можно пофантазировать, что на самом деле кластеров будет не один, а много...
И тп.п.
no subject
no subject
no subject
no subject
no subject
no subject
no subject
no subject
no subject
И сложность O(n).
подумав немного
еще подумав
Re: еще подумав
Простой перебор не считается в среде программистов "алгоритмом"! :)
Re: еще подумав
no subject
нужен пост про правильно :)
<%
//int arr[]={-1,0,2,7,-10,8,4,3,-4,1};
int arr[]={3,0,2,-7,5,-8,4,3,-4,1};
int max = 0, sum = 0, step=0, firstpos = 0, a=0, b=0;
for (int i=0;i<10;i++)out.println(arr[i]+" ");
out.println("
");
boolean isfirst=true;
if(arr[1]<0)isfirst=false;
for (int i=0;i<10;i++)
{
if (arr[i]<0) {
if(sum>max)
{
max=sum;
a=firstpos;
b=firstpos+step-1;
}
sum=0;
isfirst=true;
step=0;
}
else {
if(isfirst) {
firstpos=i+1;
step=0;
isfirst=false;
}
sum = sum+arr[i];
step++;
}
}
out.println("max= "+max+" a = "+a+ " b= "+b);
%>
no subject
Но это на самом деле не так. Ведь за небольшим отрицательным может быть очень хорошее положительное!
Надо быть оптимистом! :)
Спасибо!
no subject
а ведь вы правы. :)))))))))
ладно. буду думать дальше.
no subject
листья - элементы массива
сумма 2 соседних элементов - узлы первого уровня (если нечетное к-во элементов, до дополняем до четного псевдоэлементом == 0)
сумма 4 соседних элементов - узлы 2 уровня
итд до корня
потом обойти дерево и найти узел/лист, в котором значение максимально
no subject
и алгоритм выполняем дважды соответственно
no subject
no subject
и как же правильно решается задача?
no subject
no subject