пятница, 19 ноября 2010 г.
четверг, 11 ноября 2010 г.
Ну и еще одна практически классическая задача
You are given an array X with n elements. Can you compute in linear time a new array A with n elements, where A[i] is the product of all elements in X, but X[i] is excluded. You cannot use division, you may use additional space
Ну и классическое решение примерно такое:
int* test(int* n,int size)
{
int* a = new int[size];
for(int i = 0,temp = 1;i,size;temp*=n[i],++i)
a[i]=temp;
for(int i=size-1,temp=1;i>=0;temp*=n[i],--i)
a[i]*=temp;
return a;
}
{
int* a = new int[size];
for(int i = 0,temp = 1;i,size;temp*=n[i],++i)
a[i]=temp;
for(int i=size-1,temp=1;i>=0;temp*=n[i],--i)
a[i]*=temp;
return a;
}
а вот красивое функциональное O(N) решение я придумать не могу...
Еще одна почти стандартная задача
All numbers in an array repeat twice except two numbers which repeat only once. All the numbers are placed randomly. Find out efficiently the two numbers that have not repeated with O(1) extra memory.
O(1) extra memory - значит никаких хэшей.
очевидный ответ - отсортировать массив - слишком очевиден. А поскольку он выполняется за O(NlogN) можно предположить что это достичь результата можно за O(N) как минимум.
среда, 10 ноября 2010 г.
интересная задачка
Given two integer arrays and the size of each array.
Determine if arrays match.
Order of elements does not matter.
Number of occurrences does matter.
Return true for match, false for no match
Computational complexity is important.
Интересна она тем что первые пришедшие в голову решения - сортировка O(NlogN) либо хэш O(N) не оптимальны.
Гораздо эффективнее было бы посчитать какую-то характеристику этих массивов и затем сравнить эти характеристики. Возможный вариант - (сумма_элементов/произведение_элементов). Ну не без ограничений,да.
Но важна сама идея - вместо сравнения элементов сравнивать какую-то характеристику на основании этих элементов.
Петзольд, Книга Программирование Windows Phone 7 - бесплатно.
Книга Чарльза Петзольда Программирование Windows Phone 7 доступна для загрузки в формате PDF бесплатно.
четверг, 4 ноября 2010 г.
понедельник, 1 ноября 2010 г.
Задачка
You are given a sorted array such that all the number is repeated except one.
Find that non repeated number in O(log(n))
Find that non repeated number in O(log(n))
Подписаться на:
Сообщения (Atom)