Interview question

Да, задачата става много тежка за изпълнение. Аз я написах с 2 цикъла - един за n-1 итерации и един за намиране на m-тия елемент. Сложността е О(n2) - kвадратична и при 10000 става и доста бавна. При това не се прави никакво изключане на елементи. Мисля, че това не му хареса на интервюиращия или пък използването на допълнителна памет с такъв размер - само мога да предполагам какво не е наред (още нямам резултат oт интервюто). Ако някой може да измисли и да кодира по-елегантно решение на задачата - нека да го направи, затова съм я пуснал тука.

Ми ако имаш под ръка учебника на Краси Манев, направо разказвай. Подозирах, че има формулка.

Иначе без формула, с един std::vector<int> става на три реда за две минути. Ако трябва да се оптимизира за скорост, може да се ползва по-подходяща структура, например някакво rank tree.

quick and dirty solution :)
N=100000
M=1291
A=1289
Time = 33 sec (Celeron 1200)

TList *Array;
inline int RetArrayNumber(int N,int M)
{
M--;//Aray - Индекса почва от нула
if(N>M)return M;
else return M%N;
}
void __fastcall TForm15::Button1Click(TObject *Sender)
{
int N,M,Ans;
int CN;
int CC=clock();
char SS[64];
Edit1->GetTextBuf(SS,63);
N=atoi(SS);
CN=N;
Edit2->GetTextBuf(SS,63);
M=atoi(SS);
Array=new TList;
Array->Capacity=N;
for(int i=0;i<N;i++)
{
Array->Add((void*)i);
}
int FF;
while(CN-1)
{
FF=RetArrayNumber(CN,M);
Array->Delete(FF);//Това бави доста
CN--;
}

itoa((int)Array->Items[0],SS,10);
Edit3->Text=SS;
delete Array;
CC=clock()-CC;
itoa(CC,SS,10);
Edit4->Text=SS;
}

Bеer? Moooorrre?

ами не ми се рови в него :) имам Concrete mathematics.
(10х на един друг Пешо дето ми каза как се казва задачата).

та значи казва се Josephus problem. за m != 2 няма поне доколкото търсих аналитично решение (включително в Кнут има само решение с цикъл), сложност м*н

10х много Questor!

Намерих я в Кнут том 1/1.3.2 точка 22 задача, ама е написана на някакъв псевдо-език...Може ли някои да преведе?

(Да, задачата е Josephus problem и искат да се реши с масив, а не с цикличен списък! Освен това и в Кнут се пита за решение при големи m и n.)

ам не е псевдо език а е асемблер за една негова си машина

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


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Нарочно го искат с масив - да ти стъжнят живота и да допуснеш бъгове с индексите! Иначе имплементацията с цикличен списък е много проста (в Алгоритми на С на Р. Седжуик го има).

Ами, dude, нищо правилно няма в дека в нашия случай. И при него erase на елемент в средата на масива си е линейна операция.

Единствената правилна структура в случая е някакво rank tree, най-добре RB дърво, поддържащо индексиране. Има и други структури с подобни характеристики, които не са дървета - например skip lists.

Но всъщност стд::декът наистина се държи по-добре от стд::вектора при тази задача. Та ето моята версия на "quick & dirty" solution-a:

int foo1(int n, int m) {

    deque<int> v(n);

    for (unsigned i = 0; i < v.size(); ++i) v[ i ] = i + 1;

    while (v.size() > 1) v.erase(v.begin() + ((m - 1) % v.size()));

    return v[0];

}

N=100000
M=1291
A=1290 (разликата е щото bira_more при пълненето на масива почва от нула)
Time = 2 sec (Athlon XP 1800+)

Josephus problem е друг. Или поне не е точно такъв, какъвто го интерпретира Drum, и съответно и ние останалите. При Josephus броенето всеки път продължава от мястото на последния изключен елемент. Пък в нашия случай винаги почваме от начало.

Drum, защо не си дефинираш ясно условията на задачите? Така както си я написал, би могла да означава поне 4-5 различни задачи. Всеки може да си я тълкува както си иска.

А иначе и за оригиналния Josephus с rank tree има елементарно решение със сложност n*log(n) - по-добро от Knuth очевидно.

A ето и quick&dirty за Josephus със стд::дек. Сложност n*n.

int fooJosephus(int n, int m) {

    deque<int> v(n);

    for (unsigned i = 0; i < v.size(); ++i) v[ i ] = i + 1;

    for (unsigned i = (m - 1) % n; v.size() > 1; i = (i + m - 1) % v.size()) 

        v.erase(v.begin() + i);

    return v[0];

}

ами той каза, че му бил Josephus...

иначе - ако почваш винаги отначало, първо ще изтриеш всички от м-тия нататък, и накрая винаги ще остава от м-1 да изтриваш м-тия, което ми се струва, че има решение със сметка?

а тия ранк дърва какво представляват?

Декът има добро време за индексиране и добро време за триене. Не ми е нужно да го тествам за да знам какъв резултат ще даде. Всъщност грешката ми е, че смесих абстрактна структура от данни ( дек ) с начина й на реализация в stl - списък от вектори. Затова си се объркал за сложността (да ме извинява Шишков(бог да го прости)). Всъщност не ми трябва добавяне/триене отпред и отзад ( каквато е същността на дека ), а реализацията му. Знам, че единствената СД в STL, освен вектора имаща оператор[] е тази. Не че не биха могли да го дефинират std::list например, но представи си как разни прогърмисти ще правят такива цикли:
for(...; ... ; .... )
L = L[I+1];

А иначе декът по принцип няма бонус. Аз лично бих го изкодил с някаква версия на RLE ( елементарна компресия за битмапи ) ако се налага да пиша оптимално по скорост решение.


System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

също има opеrator [] :)

Rank дръвцата са си обикновени двоични търсещи дръвца, модифицирани да поддържат ranking операции, или иначе казано индексиране. Тоест може да се намира елемент по пореден номер, и обратното - по стойността на елемента, да се намери поредния му номер (да не се бърка поредния номер с ключа). Това се постига, като за всеки node от дървото се пази броя на елементите например в лявото му поддърво.

Red-black дърветата и AVL дърветата лесно се поддават на такава модификация (std::map и std::set са red-black дървета, но не поддържат ranking операции).

Questore, tova deto go pishesh mi se struva edno dosta dobro reshenie za sluchaia - ako mojesh drasni 2-3 reda poveche obasnenie ili kod - iskam da go napisha posle i da vidia (mai shte izleze neshto taia rabota...).

Задачата още като дадоха аз възкликнах: Тва е проблема на Йосиф и има много просто решение с цикличен списък. Дотук добре, ама взеха да усложняват. Изришно ми казаха следните 2 неща:

- Започва се винаги от началото;

- Търси се имплементация с масив (и нищо друго).


Струва ми се Кнут го е написал, ама ще ми трябва време да си преведа неговия MIX асемблер. Ако може някои да го преведе по-бързо - ще го черпя една бира!

ахааа мерси

кое? нещо не разбрах.... за това, че като почваш винаги отначало, ще изтриеш първо всички след м-тия е очевидно, а после, като останат само м-1 елемента, така като драскам на хартия забелязвам, че се трият през един първото минаване....

ама код няма да ти пиша :) - все пак не разбрах ти мина ли го това интервю или тепърва ще се явяваш....

е като си възкликнал, що не написа отначало?
а след като се започва винаги отначало, значи не е на Йосиф....