RE: Interview question

Imate array of size n. Zapochvate da izkluchvate vseki m element, dokato ostane samo edin nakraia. Koi e indeksa na poslednia ostavasht element. Zadachata ima slednia prototip:

int Foo(int n, int m){
...
return index;
}

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

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

-------------------------------------------------------------------
Ako sam razbral zadachata pravilno

Otgovora za sluchaia kogato n >= m e elementaren:

int foo1(int n, int m) {
if( m == 1 ) return n;

if( (m % 2) == 1 ) return m-1;
else return 2;
}

Kogato e po-goliamo obache vse oshte ne sam go izmislil, no mi se struva che sashto moje da se nameri zavisimost.

Zabravih da napisha edin ot sluchaite. Sorry no barzam che triabva da izlizam.

int foo1(int n, int m) {
if( m == 1 ) return n;
else if ( m == 2 ) return 1;
else {
if( (m % 2) == 1 ) return m-1;
else return 2;
}
}

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

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

А, бях забравил лафа 'куха лейка', thanx :)

Da, beshe obsyjdana, no NIKOI NE NAPISA vernia kod!!!

Vish tova koeto az napisah po-gore. Bi triabvalo da vaji v sluchaia kogato broia na elementite n v masiva e po-goliam ili raven na m. Siguren sam che i za obratnia sluchai ima zavisimost vchera pochti ia namerih, no se iadosah i zaebah zadachata.

Samo edna zabelejka: funkciata koiato sam napisal vrashta kato parvi element 1 a ne 0 toest ako indexite gi smiatash ot 0 prosto mu sloji edno -1.

Az otkrih slednata zavisimost shte ti go napisha za 7 elementa i m = 1 do 7

1 2 3 4 5 6 7 - 7 - m = 1
1 2 3 4 5 6 7 - 1 - m = 2
1 2 3 4 5 6 7 - 2 - m = 3
1 2 3 4 5 6 7 - 2 - m = 4
1 2 3 4 5 6 7 - 4 - m = 5
1 2 3 4 5 6 7 - 2 - m = 6
1 2 3 4 5 6 7 - 6 - m = 7

Ako zabelejish vsichki chetni m bez 2 vrashtat index 2 kato rezultat.
Vsichki nechetni bez 1 vrashtat index m -1 kato index na poslednia element.

Ne sam mnogo siguren dali sam razbral pravilno uslovieto. Popravi me ako gresha niakude. Sega shte vidia kakva e zavisimosta v obratnia sluchai.

Dori ne ti triabvat i masivite kato takiva. Defakto samo broia elementi e dostatachen. To ne sluchaino spored men v prototipa na funkciata sa dadeni samo elementite. Inache shteshe da ima i masiv ako se iskashe da se raboti i s masiva.

[линк]

В отговор на:

---

Da, beshe obsyjdana, no NIKOI NE NAPISA vernia kod!!!

---

Я погледни пак.

Vsashnost napravih malka popravka. Triabvashe da izprobvam s c m do 10 sled tova vsichko se povtaria.

Ugovorkata zasega e che n >= m

int foo1(int n, int m) {
if( m == 1 ) return n;
else if ( m == 2 ) return 1;
else if ( (m % 10) == 9 ) return ( ( ( (m+1)/10 )*4 )+2);
else if ( (m % 10) == 0) return (m/10*4+2);
else {
if( (m % 2) == 1 ) return m-1;
else return 2;
}
}

[линк]

това според мен въобще не е вярно - ако от 10 елемента триеш всеки втори, според теб трябва да остане 2-ри елемент. А той първи ще бъде изтрит.
А онова последното за % 10 - ума ми не го побира от къде го измисли....

else if ( m == 2 ) return 1;

Ako triesh vseki vtori triabva da ostane 1-vi a ne vtori. Izrichno sam napisal che smiatam indexite ot 1 a ne ot 0 za ulesnenie. Ako iskash da poluchish tochnia index prosto napishi edno -1 v return na funkciata.

%10 == 9 triabva da se izpalni kogato m == 9,19,29,39,49....etc.

Pri 9,10 indexa na elementa e 6 a pri 19,20 e 10 i t.n.
Vsichki drugi m kogato sa chetni vrashtat 2 i kogato sa nechetni vrashtat m-1

Matematic, pozdravlenia za uporitata rabota! Bravo, che vse pak edin chovek se opitva da napishe niakakyv kod!

V originalnata zadacha obache ne se kazva m da e < n! Ottuk idva goliamata capanica s indeksite. Kakvoto i da pishesh zanapred, otchitai, che m moje da e po goliamo ot n i broeneto se povtaria otnachaloto na masiva i taka dokato se dostigne m.

S uvajenie!
Drum

Сори, че ти го казвам, ама я ходете двамата в клуб "Идиоти".

Ne minava bratchged !

мда те разочаровам, обаче хамалското решение и твоето решение се различават, като се почне за

shit at m = 15 n=15
shit at m = 15 n=16
shit at m = 16 n=16
shit at m = 15 n=17
shit at m = 16 n=17
shit at m = 15 n=18
shit at m = 16 n=18
shit at m = 15 n=19
shit at m = 16 n=19
shit at m = 19 n=19
shit at m = 15 n=20
shit at m = 16 n=20
shit at m = 19 n=20
shit at m = 20 n=20
shit at m = 15 n=21
shit at m = 16 n=21
shit at m = 19 n=21
shit at m = 20 n=21
shit at m = 21 n=21
shit at m = 15 n=22
shit at m = 16 n=22
shit at m = 19 n=22
shit at m = 20 n=22
shit at m = 21 n=22
shit at m = 22 n=22
shit at m = 15 n=23
shit at m = 16 n=23
shit at m = 19 n=23
shit at m = 20 n=23
shit at m = 21 n=23
shit at m = 22 n=23
shit at m = 15 n=24
shit at m = 16 n=24
shit at m = 19 n=24
shit at m = 20 n=24
shit at m = 21 n=24
shit at m = 22 n=24
shit at m = 15 n=25

(бтв за такива неща като доказателства вие двамата юнаци (Дръм и ти) чували ли сте... )

ето ви и reference implementation-a.
(за инфо на Дръм - спомням си, че според тебе имало много сложни цикли, проблеми с индексите и такива ми ти работи...)

class incr
{
public:

incr()
{m_a = 1;}

int operator()()
{
return m_a++;
}


int m_a;

};

int bar(int n, int m)
{
vector<int> v;
v.resize(n);

generate ( v.begin ( ), v.end ( ) , incr() );

while (v.size() > 1)
{
int mm = m % v.size();
int toe = mm == 0 ? v.size() : mm;
v.erase(v.begin() + toe - 1);
}

return v[0];
}

подкрепям те напълно

Ne varvi naistina. Ne biah probval s tolkova golemi chisla.
Opredeleno obache otkrih zavisimosti koito mogat da pomognat zadachata da se reshi v O(1)

Slednite neshta primerno vajat vinagi kogato m < n

1. indexa e vinagi cheten ako gi smiatame ot 1 i necheten ako gi smiatane ot 0
2. Indexite primerno mogat direktno da se sakratiat po slednia nachin

ako imame n = 10 i m = 5

indexite koito ostavat sa 2 i 4

ako imame n = 20 i n = 15 primerno indexite koito ostavat sa

2 4 6 8 10 12 14

ako imame n = 20 i m = 14 (sluchaia kogato n ne e chetno chislo )

2 4 6 8 10 12

ot tuk direktno moga da ti kaja primerno che otpadat kakto sledva

14 % 6 = 2 otpada 4
14 % 5 = 4 otpada 10
14 % 4 = 2 otpadata 6
14 % 3 = 2 otpada 8

ostana 2 i 12
m e chetno direktno izbirame 2 kato ostanal index

do tuk dobre ama zadachata se reshava vse oshte v O(n) pak na men ne mi e tova celta. Inache hamalski nachini kolko shtesh. Zatova tragnah v druga nasoka.

Groznichko. Ako go napishesh i na neshto po-choveshko kato ansi c, scheme ili haskel niama da e zle. Ili nai malkoto go napishi kato pseudo-code che da vniknem i nie prostosmartnite v ideata.

Eto ti reshenie koeto namira elementa za O(n). Men obache tova ne me zadovoliava.

void ins(int numbers[], int array_size)
{
int i, j, index;

for (i=1; i < array_size; i++)
{
index = numbers;
j = i;
while ((j > 0) && (numbers[j-1] > index))
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}

int foo1(int n, int m) {

int *k = (int *) malloc(n * sizeof(int));

int i;
for (i=0; i < n; i++) k = i+1;

if( m == 1 ) return n;
else if ( m == 2 ) return 1;
else {

int j;

while( n >= 2 ) {
if (m > n) {
j = m % n;
if (j == 0) j = n-1;
else j--;
}
else { j = m; j--; }
printf("%d\n",k[j]);
n--;
k[j] = k[n];
k = (int *) realloc(k,n*sizeof(int));
ins(k,n);
}

return (k[0]);
}
}