Videó: Így működik a valóságban egy állásinterjú a Google-nél
2017-04-10T09:36:06+02:00
2017-04-15T19:29:47+02:00
2022-07-21T14:06:41+02:00
  • Bocsi a spamért, benéztem. Abba csak a komplementer elemek lesznek :)
    Mutasd a teljes hozzászólást!
  • Sziasztok!

    Set tartalmazhat az alábbi esetben két 4-es elemet? (unordered_set - C++ Reference)
    Mutasd a teljes hozzászólást!
  • Ott van a videóban, hadd be rágjam már a szádba a sült galambot!
    Mutasd a teljes hozzászólást!
  • Nézd meg még egyszer a videót. A feladat a következő:

    Határozza meg, hogy van-e egy egészeket tartalmazó tömbnek két olyan eleme, melynek összege az előre meghatározott X érték.

    Nem pedig:

    Határozza meg az alábbi négy elemű tömbben, hogy mely két érték összege 8.

    A példa csak azért van, hogy legyen egy példa.
    Mutasd a teljes hozzászólást!
  • Tehát ciklusmagonként 4 művelet, azaz 4n (ha a dupla memóriafoglalást nem nézzük).

    Az alábbi egyenletet megoldva:

    4n = n * (n-1) / 2

    n = 9
    (n != 0)

    Tehát az algoritmus 9 elem esetén lesz ugyanolyan hatékony.

    Persze, azt nem mondta senki, hogy kis és nagy elemszám esetén ugyanaz a megoldás. Természetesen eljön pl. az a kellően nagy elemszám is, amikor már megéri sorrendezni, és úgy a műveleteket végrehajtani.
    Mutasd a teljes hozzászólást!
  • #include <stdio.h> #define MAX 100000 void printPairs(int arr[], int arr_size, int sum) { int i, temp; bool binMap[MAX] = {0}; for (i = 0; i < arr_size; i++) { temp = sum - arr[i]; if (temp >= 0 && binMap[temp] == 1) printf("Pair: (%d, %d) \n", arr[i], temp); binMap[arr[i]] = 1; } } int main() { int A[] = {1, 4, 45, 6, 10, 8}; int n = 16; int arr_size = sizeof(A)/sizeof(A[0]); printPairs(A, arr_size, n); getchar(); return 0; }
    Mutasd a teljes hozzászólást!
  • Ha leirod, hogy hogyan, akkor elhiszem.
    Mutasd a teljes hozzászólást!
  • A feladat maga pedig sima ismétlés nélküli kombináció

    Ha végigmész az ismétlés nélküli komnbinációkon, akkor buktad, ennyi.

    A feladat megoldható 4 lépéssel...
    Mutasd a teljes hozzászólást!
  • Igen, borul, egyébként ha tetszőlegesen sok elem összege lehet a keresett szám, akkor az egy NP teljes probléma:

    Subset sum problem - Wikipedia
    Mutasd a teljes hozzászólást!
  • Csak átfutottam a video-t, de arról nem is volt szó, hogy mi van akkor, hogyha a rendezettlen tömb nem 2, hanem 3 vagy több elemének összege a keresett szám, abban az esetben már az elképzelés is borul.
    Mutasd a teljes hozzászólást!
  • Az algoritmusod worst-case n*(n-1)/2 összehasonlítást végez, ez négyzetes komplexitásnak felel meg. Te mire gondolsz, mennyi?
    Mutasd a teljes hozzászólást!
  • "Az általad írt megoldás N^2-es"

    Nem hiszem :)
    Mutasd a teljes hozzászólást!
  • Torolve.

    Mutasd a teljes hozzászólást!
  • Helyes a megoldás, de az "in coll" miatt a lépésszáma ennek is O(n^2) lesz, mellékhatásként pedig még meg is ette az inputot. Nem javasolnám.
    Mutasd a teljes hozzászólást!
  • Próbáld ki egymillió elemű tömbökkel. 6 lépés kell a megoldáshoz? Ennyi erővel ránézhetett volna a táblára és mondhatta volna, hogy "return true".
    Mutasd a teljes hozzászólást!
  • "Viszont ha az algoritmusokhoz tartozó matematikai modellt ismered, akkor az algoritmusodat alá tudod támasztani, miért éppen az a legjobb."

    Az általad írt megoldás N^2-es
    Ezzel szemben az első bináris kereséses megoldása n*log(n)
    A végső létetős megoldás pedig N-es nagyságrendű.
    Mutasd a teljes hozzászólást!
  • A feladatban az algoritmizáló képességet keresik. Magyarul: favágó vagy-e vagy szobrász? A fickó a videóban egyből nekiállt kódolni, mint egy favágó.

    Viszont ha az algoritmusokhoz tartozó matematikai modellt ismered, akkor az algoritmusodat alá tudod támasztani, miért éppen az a legjobb.

    Jelen esetben (ismétlés nélküli kombináció) 6 lépés kell a megoldáshoz a legrosszabb esetben. A rendezettség nem számít. Körülbelül ezt kellett volna látni a táblán:

    for (i = 0; i < iMax - 1; i++) { for (j = i + 1; j < iMax; j++) { if (8 == a[i] + a[j]) { return true; } } } return false;
    A fickó pl. írt find() metódust, ami, ha nem rendezett a lista, szekvenciális keresést hajt végre, azaz 4-et. 4 * 4 = 16 lépést használ fel, ami több, mint 2,5-szer lassabb kódot eredményez a tiszta matematikai modellben.
    Mutasd a teljes hozzászólást!
  • A Google-nél sem fognak leültetni olyan feladathoz, ami ennél sokkal bonyolultabb, mert mire odáig jutsz, hogy konkrét kódot kell implementálnod, már nagyon apró részekre van bontva egy feladat és csak lokálisan kell optimálisnak lenned.

    Amúgy ilyen tényleg létezik? Nem dolgoztam a Google-nél, de dolgoztam kis cégnél is, multinál is, de sehol nem működött ez így, vagy csak elméletben, a gyakorlatban soha nem volt ilyen apró részletekre lebontva minden feladat, vagy már eleve maguk a fejlesztők bontogatták le maguknak. Ehhez képest kis cégnél nagyon sokan előadtak, hogy a multiknál bezzeg semmi önállóság nincs, ott apró részletekre le van bontva minden feladat, neked már csak implementálnod kell. Mondanom sem kell, hogy ezek az emberek sosem dolgoztak multinál, vagy nem annál a multinál dolgoztak, amit emlegettek.
    Mutasd a teljes hozzászólást!
  • Sziasztok. Elöljáróban annyit, nem vagyok programozó, csak gyerekkoromban megcsapott a mozdony füstje, és érdekel a téma. Azt szeretném kérdezni, hogy a fenti feladatot mennyire tipikus úgy megoldani, hogy közben "felemésztem" az eredeti kollekciót.
    A saját kis eszemmel erre jutottam (python):

    def has_pair_with_sum(coll, su): while coll: if su-coll.pop() in coll: return True return False
    Mutasd a teljes hozzászólást!
  • Egy interjún azt mondanám, hogy természetesen a legegyszerűbb párhuzamosított algoritmusra gondoltam, ahol minden sorra külön szálon számítjuk ki az értéket, így elég a két ciklus.

    Butaságot írtam, el is ismertem, túl is tettük magunkat rajta, koncentráljunk inkább arra, hogy egy interjún vajon önvezető robotot kelljen alkotnod, vagy inkább egyszerűbb algoritmizálási feladatokat kelljen megoldanod. Az új beszélgetés ugyanis erről szólt, és továbbra is tartom, hogy a munkád során sem kapsz olyan feladatot, ami egy whiteboard-ra felírható mennyiségű kódnál többet igényelne egy nap, vagy ha igen, akkor rossz helyen dolgozol. Így viszont pont az ilyen feladatok elvégeztetése a legjobb mércéje a fejlesztő képességének. Ha még íratnának vele unit tesztet és dokumentációt, abszolút reprodukálni tudnák egy átlagos munkanapját.
    Persze nem dolgoztam még a Google-nél, így nem tudhatom, de nem hiszem, hogy ott csak zsenik ülnek. Egy jó képességű, szorgalmas, jól képzett ember bárhova eljuthat, és a multiknál a feladatok elképesztő méretű részekre bontása és delegálása miatt, na meg a szokásos "multis" overhead miatt valójában a kóderek sem kódolnak sokat.
    Mutasd a teljes hozzászólást!
  • gondolom egy interjún is így szoktál reagálni...

    béke 
    Mutasd a teljes hozzászólást!
  • Pont nem rendezés volt a feladat, sőt kifejezetten ártott az interjún, ha a megszokott algoritmusokat vetted elő és nem gondolkoztál a feladat megoldásán.
    Arról nem is beszélve, hogy ez feltételezem, hogy nem a teljes interjú, és sok esetben multiknál a soft skillek felmérése és az assessment center sokkal többet számít, mint az interjú technikai része.

    A Google-nél sem fognak leültetni olyan feladathoz, ami ennél sokkal bonyolultabb, mert mire odáig jutsz, hogy konkrét kódot kell implementálnod, már nagyon apró részekre van bontva egy feladat és csak lokálisan kell optimálisnak lenned.
    Mutasd a teljes hozzászólást!
  • Nem fogsz ilyen feladatot kapni a munkahelyeden

    Jó, de ez nem egy munkahely a Pistike Bt Piripótyfalun, hanem a Google. Ott azért csak vannak komolyabb feladatok. Amúgy ilyen rendezős hülyeséget tényleg itt is bármelyik kis sufni cég felad interjún Magyarországon.
    Mutasd a teljes hozzászólást!
  • * három ciklussal

    Remélem, ettől jobban telik a napod.
    Mutasd a teljes hozzászólást!
  • Egy mátrixszorzás is "óvodásoknak való" feladat, mégis emberéveket öltek matematikusok és informatikusok a hatékony megvalósításába. Ha te implementálod két ciklussal, az nagyságrendekkel lassabb lesz, mint az ipari sztenderd megoldások, pedig a dolog elég primitív.

    kíváncsi vagyok erre a 2 ciklusos megoldásodra, mert az "veri" a CW-t... (remélem nem jössz majd azzal, hogy skalárral való szorzásra gondoltál, vagy osztott/párhuzamos algoritmusra, ...)

    bocs, de ha már ma van a a magyar költészet napja:

    Ne légy szeles. Bár a munkádon más keres -dolgozni csak pontosan, szépen, ahogy a csillag megy az égen, úgy érdemes.
    Mutasd a teljes hozzászólást!
  • attol fugg hany darab van, ha 1 millio 4 elemu tomb, akkor gpu-n 1000-szer lesz gyorsabb kb
    Mutasd a teljes hozzászólást!
  • Akkor meg körberöhögik, ha a 4 elemű tömböt gpu-n akarja biton rendezni, pedig az lenne a leggyorsabb.
    Mutasd a teljes hozzászólást!
  • eleve a gyorsrendezesnek hivott formedveny a letezo legroszabb megoldas,  mar itt elbukna a fejleszto, amikor kiejti a szajan, hisz nem ismer jobbakat, es csodalkozik ha a program elkezd szaggatni
    Mutasd a teljes hozzászólást!
  • Javaslat: google állásinterjúra mindig vigyél magaddal számológépet;)

    A srác hiába tudta fejből a gyorsrendezés átlagos lépésszámát (2n ln n), kiszámolni nem tudta, jelen esetben: 11. A feladat maga pedig sima ismétlés nélküli kombináció (4 alatt a 2) = 6. (Válassz ki 4 elemből 2-őt, sorrend mindegy. Ha összegük 8 -> true). Tehát ha sorrendezel, buktad, ennyi.

    Viszont eme egyszerű feladat, a megfogalmazása miatt (sum = 8 jól elvisz a málnásba) szerintem mégiscsak a fogós/találós kategóriába esik.
    Mutasd a teljes hozzászólást!
  • nem ugy erzem hogy ilyen felmeres a jobbakat hozna eloterbe,  eleve kommunikaciora epul,  a zsenik meg altalaban mind frusztral gatlasos "pocsfejek" akik keptelenek az emberi kommunikaciora
    persze a googlenak rabszolgak kellenek, akik gyorsan cserelhetok, hisz nagy a fluktuacio
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd