Sziasztok,

Egy enyhén sznob magyar cégnél voltam állásinterjún, és a következő feladatot adták, melyre pár napom van. Azt szeretném kérdezni, hogy valaki hozzá tudna -e egy algoritmust, esetleg egy konkrét implementációt adni az egymástól függő elemek rendezésére?

Köszönöm,
Mericles

Függőség

Adott elemek egy halmaza. Az elemek között értelmezve van egy függőségi reláció (tranzitív, nem reflexív, nem szimmetrikus). Minden elemhez hozzárendelhető egy halmaz, mely az adott elem közvetlen függőségeit tartalmazza. Egy adott A elem közvetve függ a B elemtől, ha létezik egy olyan C elem, melytől az A elem közvetlenül függ, továbbá a
B elem közvetve vagy közvetlenül függ a C elemtől. Minden elem rendelkezik egy egyedi névvel, mely név a programozási nyelvekben szokásos azonosító fogalomnak megfelelő feltételeknek tesz eleget (az angol abc betűit és számokat tartalmazhat és betűvel kezdődik, továbbá különbség van a kis és nagy betűk között).

Előállítandó az elemek olyan rendezése, melyre teljesül hogy egyik elem sem előzi meg egyik közvetett vagy közvetlen függőségét sem !

Elvárások:

• Az elkészítendő program egy futtatható .jar file, mely a teszt adatokat a standard input periférián várja, az eredményeket a standard output perifériára, az esetleges hibajelzéseket pedig a standard error perifériára írja.

• Input formátum

• white space karakterek bárhol előfordulhatnak (kivéve név belsejében), nincs szerepük az inputban, egyszerűen figyelmen kívül hagyandóak

• egy elem formátuma: (itemName, {dependency1Name, dependency2Name, … })

• amennyiben az adott elemnek nincs függősége, úgy a függőség halmaz egy üres halmaz:

(itemName, { })

• az input itemek sorozata (közöttük opcionálisan white space karakterekkel):

(item1, {})(item9, {item4, item5}) (item5, {item3}) …

• Output formátum: az elemek nevei a feladat kiírásnak megfelelő sorrendben, egymástól szóközzel elválasztva:

item1 item3 item5 item4 item9

• A feladat megoldásának tartalmaznia kell az alábbi két interface implementálását. Az Items implementációja

lehetőleg különböző Item implementációkkal is képes legyen együttműködni.

public interface Item
{
String getName();
String setName(String value);
Set getDirectDependencies();
}
public interface Items extends Map
{
Iterator dependencyIterator();
void load(Reader input) throws IOException, ParseException;
void save(Writer output) throws IOException;
}

• A megoldást .zip formátumban kell elküldeni, mely minimálisan tartalmaz egy src (.java források) egy dist(futtatható .jar file) és egy test (junit tesztek) könyvtárat, valamint egy build.xml filet (ant build file).