Mulakat Sorulari

[Penthesilea]

Yeni bir baslikla harassliyorum sizi, yardim edecek herkese simdiden cok tesekkur ederim.

Elimde bircok soru var, onlari teker teker cozuyorum. Arada cikardigim algoritmalarin olabileceginin en iyisi oldugundan emin olmadiklarim var, cozemediklerim de var. Kendinizce cozumunu yazarsaniz hem size de faydasi olur hem de bana buyuk bi iyilik yapmis olursunuz.

Etki etmemek icin kendi cozumlerimi eklemiyorum. Hatta siz de cozumleri spoilerla verirseniz baya iyi olur.


1- Binary bir tree'yi descending order'da (yani en buyuk elemani en basta ve azalacak bicimde) print eden, non-recursive ve constant memory kullanan bir function yaziniz.
(Stack kullanamiyoruz constant memory sebebiyle, yani ben bu cikarimi yaptim ki mantikli bi cikarim)

2- n'lik bir integer array'e 1'den n-1'e kadar olan sayilardan yerlestiriliyor. O(nlogn) de calisan, constant memory kullanan ve arrayin elemanlari degistirmeyen, arraydeki herhangi bir duplicate elemani donduren bir fuction yazin.
benim aklima gelen ilk cozum arrayin 0. indexinden baslayarak, ornegin array[ i ]= x ise array[x ] ve array[ i] yi swap etmekti, sonra iste i++ ve devam loopa. hatta O(n) la bu diye sevinmistim, gel gor ki eleman degistiremezsiniz diyo. E constant memory de diyo. Yine arrayin degismemesi olayi yuzunden O(nlogn) lik bi sort cakip sonra altinda O(n) lik bi arama yapmak da mumkun degil.

3- 2. soruyu O(n) time da cozecek bi algoritma.
Yorum: ...

4- Bir integer arrayinde herhangi iki elemanin toplaminin M sayisina esit olup olmadigini bulan bir function yaziniz. (Yani array de toplami M yapan bir cift var mi yok mu) Function O(nlogn) de calismali.
Yorum: Simdi burada kendi cozumumu ekleyeyim: Hashtable kurarim, arrayi bi bastan gecerim O(n), gecerken her elemani hashtable'a atarim. Sonra arrayin basina donerim, yine tum arrayin uzerinden gecen bi loop: O(n) ve gecerken M-array[i] yi Hashtable'da var mi yok mu diye arayan (O(1) ) bi kod.
O(n) tabi bu ondan killandim biraz. bi de extra memory ihtiyaci var

[Cons]

1) 6
2) 24
3) evet
4) 2

[aquila]

cons

cevaplarin dogru ama gidis yolunu gostermedigin icin puan veremiyorum

[Cons]

ÜFF hoca bana taktı

[aquila]

2. soruda duplicate elemani dondurenden ne demek istedigini anlamadim. return mu etcek, bu dupllicate diye? anlasamda cevap veremem gerce, ama olsun acikliga kavussun.

[Penthesilea]

evet abi
farketmez yani duplicate oldugunu boolean olarak ifade etse de olur, oradan sonrasi 1 satir degistirme zaten :)

[Kojiroh]

O(n.logn) ayarlanır bi şekilde de, O(n)'e kafam girsin. Yatıyorum lan sdfgkj

edit: 2. ve 3. sorular yani

[riglous]

2 - Abi bi yerde log goruyosan emin ol ki cozum binary search'le alakalidir.
Array'den BST olusturursan nlogn'de cozmus olursun.
3 - Dedigin gibi

for i in size(array):
array2[array[i]]+=1

for i in size(array2):
if array2[i]>1:
print i

[Prosciutto]

1. soru

1. soru direk heap sort. binary tree'yi array kullanarak implement ettiğini düşün. indexi n olan node'un parentı (n - 1)/2 left child'ı 2n + 1 right child'ı 2n + 2 oluyor. toplamda da sıralamak için arka plandaki arrayden başka bişi kullanmıyosun yani inplace.

[Penthesilea]

riglous said:

2 - Abi bi yerde log goruyosan emin ol ki cozum binary search'le alakalidir.
Array'den BST olusturursan nlogn'de cozmus olursun.
3 - Dedigin gibi

for i in size(array):
array2[array[i]]+=1

for i in size(array2):
if array2[i]>1:
print i

abi sorularin hepsi constant memory kullanmamizi istiyor

yeni tree veya array olusturamam yani.

[Penthesilea]

Prosciutto said:

1. soru

1. soru direk heap sort. binary tree'yi array kullanarak implement ettiğini düşün. indexi n olan node'un parentı (n - 1)/2 left child'ı 2n + 1 right child'ı 2n + 2 oluyor. toplamda da sıralamak için arka plandaki arrayden başka bişi kullanmıyosun yani inplace.

arka planda array yok abi, constant memory. dedigini yapmak icin once bi arraye yerlestirmeye gerek yok mu, bana var gibi geldi.


1. soruyu biraz yanlis anlamissin, birinci soru direk inorder traversal'in tersten yapilmisi. once left yerine once right cagiriyoruz, bu kadarcik. yani bu soru non recursive demese:

	void fonksiyon (Node *node) {

	if(node->right != NULL)

		fonksiyon(node->right);

	cout << node->val << endl;

	if(node->left != NULL)

		fonksiyon(node->left);

	}

	

olacakti. Eger constant memory demese yine cok kolay, stack kullanicaktik. Da ikisini de diyor.

Dun gece nette bunun icin bi cozum buldum galiba ama sinavim var bugun ondan ugrasamadim bunlarla

[riglous]

Bence orda demek istenen array'lerin locked olmasi, yeni array yaratamaman degil. O mantikla hic bir islem yapamazdin zaten.
bst demisim, pardon, http://en.wikipedia.org/wiki/Mergesort olacak 2'nin cevabi. Adamlarin senden istedigi temel seyleri bilmen abi, kili kirk yarman degil. Heleki zaman sinirin olan yerlerde bu tur seyleri dogrudan pseudocode'la verip gecmen gerek.
3. icin de dedigim gibi. Zira herhangi bi sort algoritmasinin O(n) olmasi diye bir ihtimal yok.

[Penthesilea]

abi constant memory: istersen 1 GB memory kullan. ama program her calistiginda ayni memory'i kullanicak, n'den bagimsiz olacak memory gereksinimi.

bence de ekstrem sorular ama Microsoft mulakatinda sorulmus sorular bunlar (beyaz tahtada kodla diye), orada recruitmentta calismis bir tanidigim yolladi cunku.

boyle biseyi cat diye yapmandan ziyade adamla tartisa tartisa herifin de yardimlariyla bisey bulmani bekliyolardir tahminen.

ama constant memory dediginde yeni bi array veya tree yaratamazsin, ondan eminim. hic buna izin veren soru sorulmadi bana daha :P zaten oyle olsa cok kolay olurdu sorular.

[Mum_Chamber]

ben vaktim olmadigi icin pek bakamiyorum bu aralar.

fakat konuyu sticky yaptim, bir sure sticky kalsin, hem ilkenin isi gorulsun, hem de merakli patiler yeni seyler ogrensin.

[Penthesilea]

cok tesekkurler abi
isterseniz ben elimdeki sorulari buraya gecirebilirim hatta, guzel bi mulakat kitabim ve bi soru database'i var, herkes faydalanmis olur
su mulakat gecsin bi ondan sonra ugrasirim, baska mulakatlara giren insanlar da gonderir falan guzel bi db yapmis oluruz burda.

[aquila]

nlogn diyince benim de aklima direk merge sort gelmisti fekat tam baglantisini kuramadiydim.

[Penthesilea]

Guzel bi soru daha koyayim, bunu cozdum cok sukur de :)

Bir integer arrayinin ilk m elemani ve geriye kalan p elemani kendi aralarinda sorted ise, bu arrayin minimum elemanini bulan ve O(logn) de calisan bir function yaziniz. (m ve p elbetteki bilinmiyor)

cagirilirken question28(array, arraysize, 0, arraysize-1, false) diye cagiriliyor. tek fonksiyon yazmamizi istemisler o yuzden boyle bi recursive iteration mi yoksa ilk cagirim mi anlasilsin diye rec booleani koydum

	int question28(int a[], int const size, int lo, int hi, bool rec) {

		if(!rec) {

			int min = question28(a, size, lo, hi, true);

	

			return (a[0] < a[min] ? a[0] : a[min]);

		}

		else {

			if(lo == hi-1) {

				int p;

				if(a[lo] < a[hi])

					p = lo;

				else

					p = hi;

	

				if(a[p-1] > a[p] && a[p] < a[p+1])

					return p;

				else

					return -1;

			}

			int mid = (lo+hi)/2;

			if(a[mid] > a[hi]) {

				// search right

				return question28(a, size, mid, hi, true);

			}

			if(a[lo] > a[mid]) {

				return question28(a, size, lo, mid, true);

			}

	

			int i = question28(a, size, lo, mid, true);

			int j = question28(a, size, mid, hi, true);

	

			return (i== -1 ? j : i);

		}

	}

	

[Penthesilea]

4. sorunun cevabi benim verdigimden de basit, bugun baska biseye ugrasirken aklima geldi:

4

O(nlogn) diyor, O(n) kasmak gerekirse anca benim yaptigim mantikli.
Aksi takdirde, O(nlogn) quicksort ilk olarak arrayi.
Ardindan her eleman icin (O(n) lik bi loop yani), M-"o eleman" in arrayde olup olmadigini binary search (O(logn)) ile bul.

O(nlogn) + O(nlogn) = O(nlogn)

diger 3 soruya kafa yormak lazim

[Penthesilea]

ey pati, beni hayal kirikligina ugratiyosun alooo :(

[Breedan]

abi yarım yamalak ingilizce kelimeler kullanıcağınıza
adam gibi ya tamamını ingilizce yazın
yada türkçe
sonra topik topik gezip
de ayrı filan yazılıyo
enteresan oluyo

[Penthesilea]

LOL

Arkadaslar hadi ama ozyinelemeli bir islemsel surec verin, uygulamayi kosturacam.

[Penthesilea]

1'in cevabini da buldum
bu da calismalarim ise yariyo demek, iserken geldi bu da aklima sdfs

yazamicam simdi zaman yok da pseudocode'umsu asagida

1

Maximum node'u bul = O(logn)

Sonra maximum node'dan baslayarak: (asagida ancestor'dan bahsettigim, node'un valuesundan kucuk, en buyuk node tree'deki.
tree'de 3 ve 4 degerleri varsa, ancestor(4) 3 donduruyor kisaca.

print node;
node'un ancestorini bul : O(logn);

ancestor kodu basit bi sekilde:
eger node'un left child'i varsa ona git, sonra leaf'e ulasana kadar right childlara git.
eger yoksa, o zaman parenta bak. eger node, parentin right childiysa, parenti dondur. eger degilse node = parent; parent = parent->parent

parent null ciktiysa, ancestor i yok demektir, bu da minimum node u da bastin dmektir.

iste null degilse,
node = ancestor(node);

nullsa, terminate
O(nlogn) (n tane node icin logn lik ancestor arama zamani), hic de fena degil. constant memory nonrecursive oley!

[Penthesilea]

Tamamdir miladini doldurdu bu baslik, cok tesekkurler yardimda bulunan herkese :)
Cok guzel gecti benim mulakatim, o kadar guzeldi ki imkani yok ise alinmamamin zaten alinacagim yonunde beyanlarda bulundu son adam.

Bence yine de boyle bi baslik lazim tabi, burada soru/cozumler falan tartisiriz super olur.

[Prosciutto]

hadi hayırlı olsun :)

[Mum_Chamber]

hayirli olsun simdiden =)