RE: Interview question

Abe chovek, nikoi ne te kara da triesh elementi v masiv!!!

1 - Zadachata triabva da se implementira na C
2 - Da tragvash da triesh elementite v masiva pri vsiaka iteracia e ubiistvo - shiftvane na ostanalite, resize-vane - prostotii - dotuk si izgarmial ako si na tova interview! Prosto markirai elementite i ne gi broi pri sledvashtata iteracia...
3- Iska se samo indeksa na poslednia ostanal element v masiva

Eto ti primer - imash zalojnici - n na broi choveka, mejdu koito si i ti. Zalojnicite triabva da se podrediat v redica i terorista shte zastrelva vseki m-ti chovek, taka dokato nakraia ostane samo edin. Poslednia ostanal shte byde osvoboden! Opredeli kyde da zastanesh, za da si spasih jivota!
(Imash vreme 15-20 minuti. Ako tragnesh da otsraniavash vseki chovek za da si reshish zadachata ili da gi prepodrejdash, ili kakvoto tam bilo - samo shte vseesh smut i nai-veroiatno terorista parvo tebe da te gramne !)

I v nialokoto minuti jivot, koito ti ostavat, kato razmahash tozi STL pred terorista - toi shte zagubi uma i duma, shte si glatne ezika i shte umre ot zadushavane - eto ti edno udobno reshenie za vsichki onezi, koito mnogo dobre znaiat C++, Java i drugi tem podobni, a ne mogat da spetnat edna funksia na C...(kade ste tragnali da chetete goliamata kniga, kato ne znaete azbukata?)

[линк]

Eto ti programata koiato reshava zadachata za O(n). Az ia postnah vchera ama dira uspia da zamaje niakoi neshta v coda.

Ideata e slednata i e mnogo elementartna.

Vseki element koito triabva da bade premahnat zaema posledno miasto v masiva a na negovo miasto idva poslednia element. Sled tova masiva se sortia s inserion sort koito v sluchaia sortira sas sigurnost za O(n) tai kato vsichki indexi osven edin (tozi koito e bil posleden i e doshal na miasototo premahnatia).
Cialara rabota se povtaria dokato ostane element, tova e iasno.

Tam sam zakomentiral edin red s realloc koito mojesh i da go slojish moje i da ne. Ako ne ti triabvat elementite ot masiva koito mahash prosto rellocatvash pamet i s edin element po malko.

Много грозно ;)), щом няма for, malloc, realloc и то в големи количества не ста'а :))

Абе има един часовник, най-отдясно на таскбар-а. Като го посочиш с мишката
се появява tooltip с датата. При мен показва 02 Май 2004. Твоя да не е спрял някъде около 80-те ;)

Не обаче аз съм на мнение, че не бива да се трепе мухата с гюле и затова гледам винаги максимално да опростявам нещата. Пък и тук разглеждаме проблема като такъв а не кой ще напише по-грозна програма, която ще се компилира само с точно определен компилатор.

Niama nujda ot sortirovki! Tova samo dopalnitelno uslojniava. Eto kak e pravilnia podhod spored men - pak kazvam - ne e nujno da iztrivash, ne e nujno da znaesh dori kakvo ima v masiva - hora, iabalki ili krushi. I taka:

Pravia masiva 1,2,3 4,...n kadeto a[ i ] = i - stoinostite v masiva sa samite indeksi. Vseki podlejasht na izkluchvane element markiram s 0. Primer:

int a[] = {1,2,3,4,5,6,7};
int n = 7, m = 8;

1234567
0234567
0204567
0204067
0204060
0200060
0200000

Eto i koda:

/*----------------------------*/

int Foo(int n, int m){

int i = 0; num = m; pass = 0;

if(n == 0 || m == 0) return -1;

while(1)
{

if(a[ i ]==0){ i= (i+1)%n; continue;}

if(--num == 0) {

if(pass++ == n-1) return i;

a[ i ] = 0; num = m; i = 0;
}

else

i= (i+1)%n;

}
}
/*----------------------------*/
Chakam kritiki!

Slojnosta e mnogo visoka kato markirash elementi zashtoto vseki pat minava i prez markiranite. Az ne izkliuchvam elementi ot masiva. Na URL-to deto sam ti go dal sam zakomentiral reda s reallocatvaneto na elementite. I s nego i bez nego vse raboti. Sortraneto se pravi tochno za O(n) zashtoto samo edin ot indexite ne e sortiran.
Tova koeto ti si napravil e nai hamalskoto reshenie to na vsekigo sigurno parvo tova mu hrumva.

niki@linux:~> time ./drum 10000 10000
foo1: 4992

real 0m38.882s
user 0m37.737s
sys 0m0.203s
niki@linux:~> time ./matematic 10000 10000
foo1: 4992

real 0m1.629s
user 0m1.581s
sys 0m0.009s

----------------------------------------------------------------

Kakto mojesh da vidish. Tvoiata programa namira reshenieto dosta po-bavno. Slojnosta ti obache kloni kam O(n^2)

твойта памет май е като на 2-годишен павиан? я отиди пак прочети старата тема.

абе явно превеждането на статии след 2-3 часа през нощта ти се отразява зле....

Какво виждам в трите парчета код: твоето, на Дръм и на Куестор.

И в твоето и в дръмовото видях манипулации на индекси на масиви, malloc и realloc безумия и играчки с префикс/постфикс версиите на ++ и --. Не можах да разбера какво прави кода и искрено си пожелах да не ми попада такова нещо в ръцете с цел да правя промени по него.

В решението на Куестор от самолет се вижда културна работа с вектор и малко екзотично търсене, чрез триене от вектора.

Решението на Куестора не е грозно. 10 от 10 пъти ще избера неговата версия, защото виждам, че "говори" с езика на алгоритъма -- правим такъв вектор, вадим елементи от него по такива критерии. Другите версии ми говорят "заделям памет, намирам си място в нея по някакъв магически начин, презаделям, пускам магията с *, **, ++, --, отново и накрая вадя решение"

Защо другото решение е по-ясно и по-читаемо? Просто -- разчита на общия език (може да му викаме и набор от т.нар. patterns), който ни дава стандартната библиотека. Не мисля, че СТЛ е тежка артилерия, тъкмо обратното -- пренаписването на структурите от данни и ръчното управление на паметта е тежко.

Мога да предложа една евристика за яснота на кода. Като прост ориентир може да се използва дължината на решението. По-кратко често значи по-читаемо.

--
Екстремно програмиране на български.
[линк]

Пич, ти си нагъл. И тъп. Разгледах ти малко глупостите:

В отговор на:

---

Vseki element koito triabva da bade premahnat zaema posledno miasto v masiva a na negovo miasto idva poslednia element. Sled tova masiva se sortia s inserion sort koito v sluchaia sortira sas sigurnost za O(n) tai kato vsichki indexi osven edin (tozi koito e bil posleden i e doshal na miasototo premahnatia).
Cialara rabota se povtaria dokato ostane element, tova e iasno.

---

Значи, според теб insertion sort-a е по-бърз от обикновеното shift-ване на масива ли? Ако наистина така мислиш - в психиатрията свободни места има.

И в същото време ми говориш, че "не бива да се трепе мухата с гюле"...

А що реши, че решението ти е със сложност O(n)? Нали си математик, я сметни - имаш n на брой премахвания. Броят на операциите при всяко премахване, също ти е от порядъка на n. Нали сам се хвалиш, че insertion sort-a в случая е линеен. Та, това прави обща сложност O(n^2).

Май за съжаление си от тези математици, които просто не стават за програмисти.

Пълни глупости. Общата сложност не е в никакъв случай O(n^2), защото всяка итерация намалява масива с 1. Сложноста по-скоро е nlogn. О(n) е тялото на самата функция foo. Това имам впредвит под О(n) защото за нея става на въпрос в момента. Така или иначе операциите с масиви не са с константа сложност това е ясно на всички. Дали ще шифтваш или ще сортираш няма никакво значение в случая. Ако погледнеш кода там съм го направил и по-двата начина, но единия е закоментиран. Аз предложих просто още едно решение на проблема, като по този начин можеш да си запазиш масива с индексите цял без да го шифтваш. И моля те спести си коментарите, кой е тъп и кой не е, защото ти се показваш като такъв а не аз. Явно някой хора тук имате сериозни проблеми с комуникацията май е време да се обърнете към психиатър.

Аз в никакъв случай не отхвърлям сложните езици. Просто съм на мнение, че при решаването на даден алгоритмичен проблем с подобна сложнот. (нямам впредвид O нотацията) е по-добре да се реши по възможно най-универсалния начин да го наречем. Така възможноста да се вникне в проблема като такъв е по-голяма. На мен нищо не ми пречеше да напиша решението и на Java там също има обект Vector. В случая обаче видях възникването на още един проблем, а именно операциите върху самия масив. Иначе realloc съм го закоментирал той не е задължителен. Със същия успех ще напиша задачата и на Scheme. Не съм много сигурен обаче, колко хора са запознати със синтаксиса именно затова предпочетох C. Там нямаше да видиш malloc и realloc. Пък и в кръга на шегата то можеше директно да напишеш. #include <neshto.h> и foo(n,m) и да линкнеш библиотеката където foo е имплементирана.

Тежък случай си... значи n+ (n-1) + (n-2) +... e по-скоро N*logN така ли да го разбираме?

Ти и математик не си, марш към клуб "Идиоти".

Tz niamah tova predvit ama kakto i da e pisna mi veche.

В отговор на:

---

...Сложноста по-скоро е nlogn. О(n) е тялото на самата функция foo. Това имам впредвит под О(n) защото за нея става на въпрос в момента. Така или иначе операциите с масиви не са с константа сложност това е ясно на всички...

---

Това какво имаш ти предвид, никого не грее. О-нотацията си има ясни и фиксирани правила. Щом имаш предвид някакви други правила, означи си ги другояче, например с буквата М.

В отговор на:

---

И моля те спести си коментарите, кой е тъп и кой не е, ...

---

Why? Просто споменавам фактите. Такива, каквито са.
Човек, който бъкел не разбира, а се смята за всезнаещ, по дефиниция е тъп. И вреден. Защото дава акъл, само че погрешен. И някои по-неориентиран може да му се върже на глупостите.

Какво е сложен език? Предполагам може и на Ц да се направи еквивалента на вектор класа и да се заменят извикванията. Всъщност, за да е обработваем кода това е просто задължително. Защо езици като Java дават по-голяма възможност да се вникне в някой алгоритмичен проблем?

Как дефинираш "универсалния начин" за решаване на проблеми? Избяга ми дефиницията. Защо примерно на Scheme решението не е достатъчно универсално, а на C е? Кои свойства на C++ и Java решенията биха намалили универсалността?

Да не опряхме до проблема:
Lisp programmers know the value of everything and the cost of nothing. C programmers know the cost of everything and the value of nothing.

--
Екстремно програмиране на български.
[линк]

Ти да не ползваш 286?
На Celeron 1.2 GHz аз получавам резултата за 63 - 78 ms.
Ето ти едно грозно и неефективно решение - от сорта на тези дето не трябва да се показват. Само дето се прави бързо пък и май работи бързичко.


int GetIndex(int M,int Size)
{
if(M<=Size)
return M-1;
int Ret=(M%Size)-1;
if(Ret<0)Ret=Size-1;
return Ret;
}
void __fastcall TForm4::Button14Click(TObject *Sender)
{
//
Memo5->Clear();
int N;
int M;
char S[256];
int C=clock();
N=atoi(Edit5->Text.c_str());
M=atoi(Edit6->Text.c_str());
TList *TL=new TList;
for(int i=0;i<N;i++)
{
TL->Add((void*)(i+1));
}
for(int i=N;i>1;i--)
{
int G=GetIndex(M,i);
TL->Delete(G);
}
itoa((int)TL->Items[0],S,10);
Edit7->Text=S;
C=clock()-C;
itoa(C,S,10);
Memo5->SetTextBuf(S);
delete TL;
}

Bеer? Moooorrre?