Забавление

Я, какво ми е писал mlee:
Ако си тръгнал прост да се забавляваш :) предлагам ти да помислиш за два едносвързани списъка, които потенциално имат общ елемент(и).

И аз сега се чудя - как става тази работа!
Примерно, ако елемент от списъка ми е от следния клас:

struct MyNode
{
MY_TYPE data;
MyNode* pNext;
};

Освен да имат общ(и) последен елемент(и)...
Подозирам, че това е някаква задача за интервюта пак.
Хайде да поумуваме дружно, а!

Dum loquo hora fugit

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

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

Още една задачка-закачка взета от тест в една не толкова велика фирма

Условие:
Двама играчи, маса с произволна /недефинирана/ форма и площ.
Всеки от играчите разполага с безброй абсолютно еднакви монети.
Играчите се редуват последователно поставяйки монета на масата. За коректно поставяне на монета се счита, ако тя не припокрива друга и геометричния й центъра е върху масата. Монетите могат да се поставят както ви хрумне (на ръб, на плоскост,.... не е дефиниран броя на възможните поставяния на монета). Играта свършва с победа за играча поставил последен монета на масата

Задачата: Да се намери стратегия при която първият играч винаги печели.

Освен да имат общ(и) последен елемент(и)...
Точно така - последните им X (където Х >= 1) елемента на двата едносвързани списъка са едни и същи.

Елементарната имплементация е с точно m + n + 2 (където m - брой на елементите в единия списък, n - брой на елементите в другия списък) извиквания на GetNext и точно едно сравнение (използва се идеята, че ако последните елементи на двата списъка са различни значи двата списъка нямат нито един общ елемент). Интересно дали има още по-ефективен алгоритъм

-----
просто, брат ми, сам си правиш проблем...

Хм, ако масата не е със съфсем произволна форма - има елегантно решение за стратегия на първия играч. Уговорката е формата на масата да е симетрична спрямо една точка - огледално или ротационно. Тогава първия играч поставя своята монета така, че нейният център да лежи върху тази точка и след това поставя всички други монети симетрично на монетите, които поставя втория играч. Идеята е, че ако втория играч намери начин да постави още една монета на масата то и първия играч ще може да постави още една монета.

Ако формата на масата обаче наистина е абсолютно произволна - не знам.

-----
просто, брат ми, сам си правиш проблем...

Мислех си за центъра на тежестта, но при произволна форма, може да не се падне върху масата ...

Dum loquo hora fugit

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

-----
просто, брат ми, сам си правиш проблем...

Аз друго си мисля - възможно ли е да има такава маса, с такава форма, така щото да може първият да загуби. И нищо не измислям.

Dum loquo hora fugit

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

Dum loquo hora fugit

Монети.
Маси.
Явно некъф шафьор (ка) точно след подобен изпит нагледно беше показал (а) как една кола може да заеме 4 паркоместа.
Вие с некви монети се ебавате.
Те така се прави.

Bеer? Mоre?
Плацебото

Не е грешка в условието :-) Освен това, монетата може да се постави на ръба на масата така, че да примерно 3/4 от нея да е върху масата (примерно). С други думи не е дефинирано и възможните видове ходове (поставяне) на монетата върху масата.

Колкото колеги съм питал, никой (вкл. и аз) не я е решил досега тази задача. Един колега нещо ми говореше за размити множества ... но доста общо. Най общо требе така да праиш, че броя ходове след твоя ход, да бъде нечетно число по голямо от 1

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

-----
просто, брат ми, сам си правиш проблем...

Със Светила май напипахме обещаваща посока на размисъл... и всъщност тфа със симетричната маса ще се окаже просто частен случай на по-общата задача...

Мисленето продължава...

-----
просто, брат ми, сам си правиш проблем...

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

То

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

Остава да докажем, че след краен брой ходове по описаната страгетия останалата непокрита част от масата ще има такава форма, че втория играч гарантирано винаги да е прецакан

-----
просто, брат ми, сам си правиш проблем...

Ако сложиш първата монета така, че да раздели масата на 2 полупространства, винаги печелиш. Според мен такава е тактиката. Разделяш на 2 полупространства - в едното от тях губиш - защото в него вторият играч предприема разделяне на 2 полупорстранства пръв, а в другото се пада да си победител. Това е тактиката.

Dum loquo hora fugit

Коя е тая фирма да не кандидатстваме в нея.

Възможна е такава форма. Слагаш 4 клечки да подпират бръснарско ножче във вертикално положение и готово. :) Имаш бленуваната 'маса'.

Предлагам ви друг подход по задачата :) да се докаже, че задачата няма решение. С други думи, ако при определена площ и форма на масата, втория винаги печели, следва, че има поне 1 вариант в който първия никога не печели, следователно задачата няма решение.

Първото нещо, което ще направя като видя такава задача на интервю, е да отида и да набутам главата на шефа на фирмата в задника му!
Какво точно се опитват да постигнат с такава задача? Те програмисти ли търсят или професори по теоретична и дискретна математика?

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

General Protection Fault in module 0xDEEBAA. Рестартирайте държавата!