Interview question

Colombino e прав! Прегледай си пак кода - трябва да работи с произволни целочислени стойности за m и n, като очевидно return value <= n-1.

Още: ако m%n == 0, то theRightIndex = -1 и какво се връща тогава? Представи си, че m = 8 и n = 4...?

Абе тая формула откъде я извади? Категорично ми казаха, че не ги интересува формулата, а кода, който имплементира правилното решение, демек - поне един цикъл през масива и т.н....

Както е казал Архимед: "Дайте ми масив да си го мажа и ще реша задачата". Трябва да има някакъв начин задачата да се реши в константна памет без да се ползват помощни масиви. Формула едва ли има. Въртят ми се разни неща за функции на Ойлер в главата, за взаимно прости числа, групи, пръстени ... Ама съм я позабравил алгебрата (по-точно теорията на числата) вече. Да каже някой студент дето скоро я е учил.
Задачата е интересна и никак не е тривиално дори да се изкоди ( имаше такива изхвърляния, че било елементарно ). Аз поне не бих я решил за 20 мин. на интервю, особено пък ако е на лист.


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

Сигурен съм че задачката има подводни камъни но все пак не съм аз на интервю Интерсното ми беше как тъй имаш алгоритъма пък не можеш да я решиш..все едно да кажеш "Знам как да я реша ама не мога"

----------

Кирилица Forever

Тва няква първоаприлска шега нали? Изтриване от circular buffer? Разказало ти играта?!? :О

Никой не ти е дал буфер, дали са ти n и m вход, искат index изход. Някъде да е споменал човека, че са го карали да реализира буфера?


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

Леко буквализъм а? Направи си буфера с индексите сам. Пишеш решението за 5 мин. останалите 15 прекарваш или в търсене на математическо решение или в бъркане в носа - поне си се подсигурил *shrug*

Виж, тук имаш известно право. Само дето пак няма да ти се наложи да реализираш цикличен буфер, защото от теб не се иска самия елемент, а индекса му. Ще трябва да се напише нещо от сорта:
1. Алокираш някакъв масив с флагове ( std::vector<bool> например ) да бележиш изтритите елементи.
2. Въртиш цикъл за всеки размер.
2.1 Инкрементираш (циклично) индекса елемент по елемент и броиш само неизключените. Като преброиш колкото там ти е текущия остатък изключваш намерения елемент и повтаряш.

Кофти алгротитъм, но ще работи. Има само един недостатък - няма да ти стигнат 5 мин. Следователно нямаш шанс да измислиш нещо по-умно, дори да си могъл. Пък може да се окаже, че ако помислиш ще измислиш нещо по-елегантно, няма как да знаеш предварително. Не е ясно какво точно е искал да разбере за теб работодателят.


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

Ти говориш за буфер с индекси. Това наистина ще стане по-лесно, не се бях сетил за това решение.


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

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

От където и да я гледаш - тъпанарското решение е точно 5 мин. за имплементация :) и ми се струва направо непростимо някой да реве колко гадна била задачата...виж ако бяха казали - а сега мойто момче - оптимизирай... :)

Инак има и много по-хитри решения, но както каза някой по нагоре - "да не съм аз на интервю" :)

Да, буфер с индекси е улеснение (виж по-нагоре темата Улеснение) - никой не ти пречи да си направиш живота по-лесен . Даже може да се направи индексите да са 1-базирани, а тези за изклюяване да се зануляват...и все пак, продължавам да твърдя, че дори и с тия улеснения задачата не е лесна за 'изкодване' (както казва Colombino).

И така, ако масива е например 123456 за n = 7 и m = 8 например. Така ще изглеждат елементите на масива през различните итерации:

1234567
0234567
0204567
0204067
0204060
0200060
0200000

Индекса на последниа оставащ елемент е 2 (или 1 при 0-базирани индекси).
Сега иде време за С кода който точно имплементира това решение ...

Хора, които на всяко нещо за кодиране казват 'това е много просто' и не написват нито ред код предварително изпадат от арената! На такива в сериозните фирми (ако изобщо идат на интервю) им викат:
Не, благодаря!

<rant>

Пич, не разбирам какво искаш, някой друг ли да ти напише кода?! *Ти* си бил на интервю - и да - засякох си за колко време я изкодвам след като съм измислил тривиалното решение - и не, не е повече от 5 минути. Освен това съм сигурен че 99% от четящите тук ще го напишат по-бързо. На всичкото от горе, никой в клуба не е нужен да ти се доказва (виж, може малко да ти се посмеем).

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

И още един път повтарям - чудя се за какво си я пуснал тази тема тука - нещо като за самоутешение че са ти казали, цитирам "Не, благодаря!" ли, какво ли?!?

</rant>

А сега си представи, че масива е например от 10000 елемента (n = 10000) и се изключва всеки 591-ви (m = 591)

мсигурно е значително по-трудно, отколкото ако се изключваше всеки 500?

да, по-трудно е, трябва по дълго парче хартия да си разпишеш кво става :)

Само малко ще подскажа - масив от индекси на 10000 елемента не 'фърфи' ;-)))

абе ти преди няколко поста не каза ли, че не ги е интересувало формулата, а да има поне 1 цикъл през масива?

така лииии? и що? нямаш 20к излишни ли кво?

>>10000 елемента не 'фърфи' ;-)))

Верно? Във времената когато програмирах, а не дърпах контроли от туулбокса, масиви със 64,000 елемента си вървяха - ако си спомняш добрият стар ДОС. Това беше преди 15 години, мисля.

Не знам, възможно е вече масиви с 10,000 елемента да не вървят - не съм виждал код от около 3-4 години и не знам какво генерира Вижуал Студиото под красивия дизайнер, понеже не знам синтаксиса на С#.

--
Increasing performance by lowering expectations.

Абе то 40K ще се намерят, ама сложността е квадратична, та може да позаспи програмата при по-голяма бройка.


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

само да ви подразня - разкрита е задачата - класическа задача от дискретната математика :)

от което следва колко е тъпа и неподходяща за даване на интервю...

--
корекция - задачата е само за м = 2. за различно от 2 нещо в момента не мога да зацепя дали ще може да се обобщи....