asa@
asa
: 2007-10-19 23:16:55 UTC+0000
laporan interviu gugel lg, kali ini ga batal :P
pertama ditanya2 soal proyek lg, dan tentu cid karna cuman 1 itu.
ditanya bikin apa, dan ku bagian apa. kublg desain db dan implemen phpnya
lalu ditanya ada tabel apa ajah di dbnya (ga penting amat si)
trus pertanyaan teknis dimulai
dia: bikinin fungsi yang inputnya int[] a sama int x
fungsinya return true kalo ada 2 bilangan di a yang jumlahnya = x
kalo gada return false.
ngomonglah apa yg km pikir, proses berpikirnya lebi penting dr hasil akhir.
ku: yg pertama kepikir yah pake 2 for lup, kuli smua kombinasi 2 angka yg ada
dia: wah solusi pertamanya cepat, butuh brp lama?
ku: o(n^2)
dia: coba efisienin
ku: hmm sort dulu
dia: gimana sortnya?
ku: merge sort
dia: brp kompleksitasnya?
ku: n log n
ku: di a ada bilangan negatif ga?
dia: ada
ku: kalo gada bilangan negatif tdnya mo kucari sampe sebagian ajah, brenti kalo elemen di a uda > x
dia: kayanya uda bener disort dulu
ku: kalo gt simpan indexnya di i buat elemen terkecil j buat yg terbesar
misal i = 0 j = panjang arai
trus cek a[i] + a[j] kalo lebi besar dari x mundurin j, kalo lebi kecil dari x majuin i
gitu terus sampe ketemu
dia: brentinya kapan?
ku: kalo i = j
dia: coba contohin jalannya gimana kalo arainya 0 1 2 3 4 dan x=2
ku: ya pertama 0+4 > 2 jadi mundurin batas atas
jadi brikut cek 0+3 > 2 mundurin lg batas atas
lalu cek 0+2 = 2 jadi return true
dia: oh ok, kompleksitasnya brp?
ku: kalo i nambah a kali dan j berkurang b kali a+ b maksimal n (panjang arai maksudnya)
trus sortnya n log n jadi total o(n log n)
dia: ok, sekarang aku ada pertanyaan lg
ku punya daftar himpunan
tiap himpunan isinya banyak kata
ku minta mu ilangin kata yang dobel dari himpunan-himpunan itu
contoh ku punya daftar 2 himpunan
himpunan pertama isinya {kucing, anjing}
himpunan kedua isinya {anjing, burung}
ku mau mu ilangin salah satu kata anjing, terserah dari himpunan pertama ato k2, ku ga pduli yg mana
mu bisa random akses, ada pertanyaan?
ku: bisa random akses ke daftarnya?
dia: iyah
ku: gimana ku akses himpunannya?
dia: bisa asumsi kaya ... set (entah apa ku ga penah pake) di C ato di java
jd bisa set.has(key) dan set.remove(key)
ku: yg pertama kepikir cek himpunan pertama dulu ke smua himpunan lain
baca 1 anggota himpunan pertama trus cek apa himpunan 2 dan seterusnya jg punya anggota yg sama
kalo punya yg sama hapus yg di nomer himpunan lebi besar
brikutnya cek himpunan 2 dengan himpunan 3,4,5 ... dst
dia: ok, kalo gt kompleksitasnya brp?
ku: kalo ada n himpunan
trus himpunan ke i punya anggota sebanyak ai
brati butuh a1 * (n-1) + a2*(n-2) + ... + an-1 * (1)
dia: bisa sederhanain dalam n saja?
ku: ya kira2 jumlah smua anggota tiap himpunan * n (salah kali yah)
dia: bisa dianggap kira2 n^2 gt yah
ku: ga yakin jg
dia: coba efisienin
ku: karna himpunan pertama dibandingin ke smua himpunan lain
dan kalo sisa 2 himpunan cuman perlu bandingin ke 1 himpunan lain
jadi bisa disort dulu himpunannya berdasarkan jumlah anggota
jadi cek himpunan yg anggotanya dikit dulu
dia: ok, itu bisa lebih efisien, tapi dasarnya km tetap bandingin dengan smua set,
coba efisienin lg
mu bisa pake 'eksternal storage'(ga tau mo terjemah jd apa) ga pelu lakukan di tempat
ku: variabel sementara gt?
dia: iyah
ku: kalo gt ku pake 1 himpunan lg sebut ajah t
baca 1 1 tiap himpunan
kalo cek tiap elemennya kalo ada di t brati hapus elemen itu dari himpunan asal
kalo gada di t tambahin elemen itu ke t
dia: kompleksitasnya?
ku: a1 + a2 +....+ an
dia: jadi linear
dia: skrg kita punya kira2 10 mnt lg, ada pertanyaan?
setelah itu lanjut dgn pertanyaan2 ga penting ....
kali ini cuman bentar, pas kututup telp baru 6:33
katanya akan dikasi kabar sama tukang rekrut ttg hasil, udah gt ajah