ugrás a tartalomhoz

Strukturáltság

bbaga · 2011. Már. 31. (Cs), 12.30
Üdv!

Pár napja jelentkeztem egy állásra, három fordulós volt a felvételi, az írásbeli teszten továbbjutottam a második fordulóba ami "házi feladat" volt elbuktam.

Megcsináltam a feladatokat, majd azt a választ kaptam, hogy nem elég strukturált amit beküldtem.

Kértem őket, hogy akkor legyen kedvesek és küldjenek egy jó megoldást ha van rá mód, de úgy látszik nem volt rá mód.

Szóval szeretnélek titeket megkérdezni, hogy Ti mit alakítanátok a kódokon, figyelembe véve azt, hogy a feladatok leírásában kiemelik a hatékonyságot.

A feladatok leírása a scriptek elején kommentezve olvasható.

Feladatok: Piramis, Egyensúlyi index

Nem felvágni, vagy háborogni akarok (azon már túl vagyok), hanem tényleg érdekelne a jó megoldás.
‹ sql hiba, pls help - megoldva Cikk szerkesztő ›
 ■
1

A másodikra néztem rá

kuka · 2011. Már. 31. (Cs), 13.43
A másodikra néztem rá alaposabban.
  • for helyett while - rontja az olvashatóságot
  • ciklusban ciklus - rontja a hatékonyságot
  • rövid változó nevek - rontják a karbantarthatóságot
Nem pöcsségből írom, de én is erősen elgondolkoznék rajta, hogy ha alkalmazlak és pár hónap/év után kilépsz, akkor mennyit fogok káromkodni ha utána nekem kellene karbantartani a kódodat.

Az én próbálkozásom:

function e_index3(&$list)
{
  $osszeg=array_sum($list);
  $balresz=$jobbresz=array();

  $resz=0;
  foreach ($list as $szam) {
    $balresz[]=$resz;
    $resz+=$szam;
    $jobbresz[]=$osszeg-$resz;
  }

  for ($i=0,$l=count($list);$i<$l;$i++) {
    if ($balresz[$i]==$jobbresz[$i]) return $i;
  }

  return -1;
}
Eredmény 10000 véletlen számra:
E  : 3584 - 7.2434208393097
E2 : 3584 - 14.741687059402
E3 : 3584 - 0.011682987213135

A harmadik oszlopban a futásidők másodpercben. Szóval nem értem a második megoldásod mitől tűnt neked gyorsabbnak.

Szerkesztés: újragondoltam és hülyének találtattam:

function e_index4(&$list)
{
  $osszeg=array_sum($list);

  $resz=0;
  for ($i=0,$l=count($list);$i<$l;$i++) {
    if ($resz==$osszeg-$resz-$list[$i]) return $i;
    $resz+=$list[$i];
  }

  return -1;
}
2

Kösz!

bbaga · 2011. Már. 31. (Cs), 13.48
Köszönöm a választ! Ha nem szeretném tudni mit rontottam el, nem kérdeztem volna meg, így semmilyen kritikát nem veszek pöcsségnek.

Valóban szebb ez így (és gyorsabb is) erre megoldásra - hogy az egyik oldal részösszegét az egész összegből vonjam ki - nem gondoltam.

Az első megoldásra (a két while-os) céloztam azzal hogy gyorsabb. A második megoldás csak addig gyorsabb amíg hamar talál eredményt egyébként lassabb volt jóval, mint ahogy az látszik.
3

Megjegyzések

Poetro · 2011. Már. 31. (Cs), 14.10
Nem tudom, én vagyok-e látássérült, de én nem látok egyetlen megjegyzést sem, egyik kódban sem, mit takarnak a változók (ha már a változónevek nem beszédesek), valamint azt sem, hogy mit csinál, és miért úgy csinálja az algoritmus. Ezt például a saját release managerem úgy dobná vissza ezért, hogy még porzik is. Ha nem is minden sorba írsz megjegyzést, azért egy bonyolultabb algoritmusnál az egyes nagyobb lépések elején le kellene írni, hogy mit és miért csinálsz úgy, ahogy csinálsz. Valamint a változókat tényleg okosan kellene elnevezni, elvégre minden normális IDE felkínálja neked a változókat, azaz nem kell többet gépelned, és memóriából se foglal többet a kód.
4

Igazad van

bbaga · 2011. Már. 31. (Cs), 14.19
Igazad van, belátom, hogy lehettek volna beszédesebbek is, de ~7db változónál amiből 2 az $i és a $j (ami az esetek 99,9%-ában ciklusváltozó) nem éreztem akkora szükséget arra, hogy:

//Maximum költség
$max = 0;
Ettől független igazad van, valószínűleg ezeket is hiányolták.
5

második feladat futási idő

bearfoot · 2011. Már. 31. (Cs), 14.50
Szia,

a második kóddal az lehet a legnagyobb baj (amellet, hogy tényleg kevés benne a komment), hogy nem fut le O(n) alatt. Mindkét megoldásod O(n^2) futási idejű, tehát nem teljesíti a feladatot.

üdv,
bearfoot
6

Ezt a másodikat nagyon

bbaga · 2011. Már. 31. (Cs), 15.04
Ezt a másodikat nagyon eltoltam ezek szerint... Ha tovább nézem talán én is megláttam volna az egy ciklusos megfejtést benne. Elkapkodtam.
7

Megnéztem az elsőt is.

kuka · 2011. Már. 31. (Cs), 15.40
Megnéztem az elsőt is. Őszintén szólva, ha nem házi feladat, akkor ott helyben akkora baromságot műveltem volna, amekkora vagyok: nekiestem volna backtractinggel. De pici gondolkozás után:

$meret=$max=0;
while (true) {
  echo $meret+1,' szambol allo sor : ';
  $sor=fgets(STDIN);
  if (!$sor) break;
  $szam=explode(' ',chop($sor));
  if (count($szam)!=$meret+1) echo 'Hiba: a sor ',count($szam),' szamot tartalmaz',PHP_EOL;
  else {
    $max+=max($szam);
    $meret++;
  }
}

$fakt=1;
for ($i=1;$i<=$meret;$i++) $fakt*=$i;
echo 'lehetseges utak ',$meret,' magas piramisban: ',$fakt,PHP_EOL;
echo 'legnagyobb koltseg: ',$max,PHP_EOL;
Vagyis még a lehetséges utak számát is ellőtted. (Backtracking bebizonyította, hogy a faktoriális adja a helyes eredményt.)

Az alapgondolatot egyébként éppen ma írta meg dtamas Twitteren:
The fastest page is a blank one. Everything you add to a page slows it down.
Ebben az esetben a leggyorsabb számítás az elvégzetlen.

A személyes következtetésem: a feladatok nagyon ügyesek, de én nem látom mit lehetne ennyin strukturálni. A tippem, hogy a vizsgáztató valahonnan kimásolta őket, de érteni kevesebbet értett belőle mint te.
8

Hát igen, ilyen csalafintaság

bbaga · 2011. Már. 31. (Cs), 16.10
Hát igen, ilyen csalafintaság sem jutott eszembe, hogy beolvasás után keressem meg a maximumot ráadásul van rá gyári fv...

Viszont a faktoriálissal nekem nem jön ki.

$meret = 4;
$fakt = 1;

for ($i=1;$i<=$meret;$i++) $fakt*=$i;
1*1 => 1
1*2 => 2
2*3 => 6, szerintem ennek 4nek kéne lennie.
6*4 => 24, ez meg 8 nálam.

Szerk: Nem szoltam hülye vagyok...
9

Viszont a faktoriálissal

kuka · 2011. Már. 31. (Cs), 16.11
Viszont a faktoriálissal nekem nem jön ki.
Akkor lássuk szemléletesen:
.  1    : 1 = 1 = 1!
  2 1   : 12 11 = 2 = 2!
 4 1 8  : 124 121 128 114 111 118 = 6 = 3!
2 2 3 4 : 1242 1242 1243 1244 1212 1212 1213 1214 1282 1282 1283 1284 1142 1142 1143 1144 1112 1112 1113 1114 1182 1182 1183 1184 = 24 = 4!

Szerk: akkor én sem szemléltettem. :)
10

128 szerintem nem lehet. A

bbaga · 2011. Már. 31. (Cs), 16.14
128 szerintem nem lehet. A feladat szövege szerint:
Függőleges út: Irányítatlan (fentről lefelé vagy lentről fölfelé ugyanaz), az adott elem alatt közvelenül álló két elemből az egyiket választva végighaladunk a háromszögön függőleges irányban.
11

Hű a nemjóját! Arról a

kuka · 2011. Már. 31. (Cs), 16.30
Hű a nemjóját! Arról a feltételről megfeledkeztem. Akkor vissza mindent, mégiscsak backtracking kell hozzá.
12

Én is próbáltam azzal, de a

bbaga · 2011. Már. 31. (Cs), 16.38
Én is próbáltam azzal, de a két while-os megoldás gyorsabb lett - persze lehet neked jobban sikerül a megvalósítása.
13

Jobban átgondolva tényleg nem

kuka · 2011. Már. 31. (Cs), 18.53
Jobban átgondolva tényleg nem kell rá sok bonyolítás. Hiszen mindegyik elemet az előző sor két eleme közül az egyikkel kell összeadni.

$meret=0;
$max=array(); // *
while (true) {
  echo $meret+1,' szambol allo sor : ';
  $sor=fgets(STDIN);
  if (!$sor) break;
  $szam=explode(' ',chop($sor));
  if (count($szam)!=$meret+1) echo 'Hiba: a sor ',count($szam),' szamot tartalmaz',PHP_EOL;
  else {
    for ($i=0;$i<$meret;$i++) $szam[$i]+=max($max[$i-1],$max[$i]); // *
    $max=$szam; // *
    $meret++;
  }
}

echo 'legnagyobb koltseg: ',max($max),PHP_EOL; // *
A lehetőség számítást hagyom, mert hosszú nap volt.

Az újabb kódom ismeretében most már megértettem a tiédnek is a működését. (Azok a while-ok nekem nagyon bekavarnak.) Tulajdonképpen ugyanúgy működnek.

Viszont így már egyáltalán nem értem miféle strukturálást akartak. Lehet kellett volna beolvas_egy_sort($hanyadik_sort) függvény meg hasonló babalépések. Amivel személy szerint nem értek egyet.

Ui: Köszönet a fejtörőért, pont jókor jött. Mostanság csak dokumentációkat kellett bújjak, már hiányzott egy kis programozási feladat az agyamnak.
14

Én köszönöm a válaszokat!

bbaga · 2011. Már. 31. (Cs), 19.17
Én köszönöm a válaszokat!
15

utak száma

bearfoot · 2011. Ápr. 1. (P), 15.01
Az utak száma 2^(n-1), tehát jó amit írtál.
Bizonyítás: legyen 0 ha egy adott pontból balra lépek, legyen 1, ha jobbra. Egy n szintű piramisban n-1 hosszú utakat vannak. Tehát az (n-1) hosszú 0-1 számokból álló sorozatokat akarjuk megkapni, ezekből az összeset. Az ilyen sorozatok száma pedig pontosan 2^(n-1).
16

Ahh, akkor legalább ez jó

bbaga · 2011. Ápr. 2. (Szo), 20.22
Ahh, akkor legalább ez jó volt.