Zadaci sa Facebook intervjua

Ukoliko želite da saznate kako izgleda sâm proces prijavljivanja za praksu, ~~strpite se, pošto će tekst o tome uslediti kasnije.~~ pratite ovaj link.

Kao što sam pre nekoliko meseci pisao o zadacima sa intervjua za praksu u MDCS-u (Microsoft Development Center Serbia), tako ću sada sa vama podeliti i zadatke sa intervjua za praksu u Facebook-u. Iako bi se možda moglo očekivati da zadaci budu teški, s obzirom da pričamo o veoma jakoj kompaniji, primetićete da su slični onima za MDCS koji je ipak samo regionalni centar.

Koliko sam uspeo da primetim, za software engineer pozicije u većini kompanija uglavnom zadaci i jesu ovog tipa, pa verujem da će tekst koristiti svima koji razmišljaju o prijavljivanju za takav posao.

Zadatke sam podelio u dve kategorije — programerske i matematičke. Međutim, nemojte da vas to zavara, pošto je sve trebalo isprogramirati – za druge je samo bilo potrebno i određeno znanje matematike. Sva rešenja su napisana u C++u.

Programerski zadaci

Zadatak: Datu jednostruko povezanu listu potrebno je obrnuti tako da njeni članovi budu u obrnutom redosledu. (1 4 5 6 2 -> 2 6 5 4 1)

Rešenje: Verovatno najlakši zadatak od svih, potrebno je samo primetiti da nema potrebe ni za kakvim pomoćnim nizovima/listama, odnosno za alokacijom dodatne memorije, pošto se lista može obrnuti u jednom prolazu kroz istu. Funkcija prima dvostruki pokazivač na listu (da bi on mogao da se menja).

struct node
{
	node *next;
	int value;
};

void reverse(node **start)
{
	node *newList = 0;
	node *oldList = *start;

	while (oldList != 0)
	{
		node *currentElement = oldList;

		oldList = oldList->next;
		
		currentElement->next = newList;
		newList = currentElement;
	}

	*start = newList;
}

Zadatak: Potrebno je implementirati komandu cd (change directory). Funkcija prima dva parametra: apsolutnu putanju do trenutnog foldera i apsolutnu ili relativnu putanju do željenog foldera. Imena foldera se sastoje samo od slova, putanje su ispravno formatirane, a putanja do željenog foldera može sadržati i tačku ili dve tačke (trenutni, odnosno prethodni folder).

Rešenje: U pitanju je jednostavna manipulacija stringovima, bitno je samo razmotriti sve moguće slučajeve, kao i kada treba vratiti grešku.

string cd(string currentPath, string desiredPath)
{
	vector<string> folder;

	int i = 1; // Skip the slash

	// Parse the current folder

	while (i < currentPath.length())
	{
		string f;

		while (i < currentPath.length() && currentPath[i] != '/')
		{
			f += currentPath[i];
			i++;
		}

		folder.push_back(f);

		i++; // Skip the slash
	}

	// Parse the desired path

	i = 0;

	if (desiredPath[0] == '/')
	{
		// We were given an absolute path;

		folder.clear();
		i++;
	}

	while (i < desiredPath.length())
	{
		if (desiredPath[i] == '.')
		{
			if (i+1 < desiredPath.length() && desiredPath[i+1] == '.')
			{
				// Go to parent folder

				if (folder.size() == 0)
				{
					return "ERROR";
				}
				else
				{
					folder.pop_back();
					i += 3; // We skip the second dot and the slash
				}
			}
			else
			{
				i += 2;
			}

			continue;
		}

		string f;

		while (i < desiredPath.length() && desiredPath[i] != '/')
		{
			f += desiredPath[i];
			i++;
		}

		folder.push_back(f);

		i++;
	}

	// Form the final path

	string result = "/";

	for (i = 0; i < folder.size(); i++)
		result += folder[i] + "/";

	return result;
}

Zadatak: Dat je niz brojeva. Potrebno je proveriti da li neka tri broja iz tog niza imaju zbir 0.

Rešenje: Ovo je relativno poznat problem — čak ima i svoju stranicu na Wikipedii. Rešenje u O(n³) je trivijalno. Nešto brži algoritam, O(n² log n), se dobija sortiranjem niza, fiksiranjem dva elementa uz pomoć dve FOR petlje, i traženjem trećeg elementa binarnom pretragom. Međutim, zadatak se jednostavno rešava i u O(n²) — čak je i kôd jednostavniji nego kod binarne pretrage.

Naime, ideja je da se niz sortira i da se jednom FOR petljom fiksira jedan element, nakon čega znamo koliki treba da nam bude zbir preostala dva broja. Isto tako znamo da će oba broja biti desno u nizu od fiksiranog elementa. Kroz taj deo niza ćemo prolaziti sa dva indeksa istovremeno: jedan će ići od kraja niza na levo, a drugi od fiksiranog elementa na desno. U svakoj iteraciji proveravamo zbir ova dva elementa. Ukoliko je veći od traženog, smanjujemo desni indeks, i time smanjujemo zbir; ukoliko je zbir manji od traženog, pomeramo levi indeks. Pošto nema potrebe nastavljati pretragu kada se ovi indeksi mimoiđu, složenost ovog prolaza je O(n). Zajedno sa fiksiranjem prvog elementa, dobijamo O(n²).

bool 3sum(vector<int> numbers)
{
	sort(numbers.begin(), numbers.end());

	for (int i = 0; i < numbers.size() - 2; i++)
	{
		int j = i + 1;
		int k = numbers.size() - 1;

		while (j < k)
		{
			int sum = numbers[i] + numbers[j] + numbers[k];

			if (sum == 0)
				return true;
			else if (sum < 0)
				j++;
			else
				k--;
		}
	}

	return false;
}

Matematički zadaci

Zadatak: Potrebno je generisati partitivni skup za zadati skup brojeva.

Rešenje: Pošto je partitivni skup nekog skupa zapravo skup svih njegovih podskupova, znamo da će partitivni skup imati 2ⁿ elemenata. Postoje dva načina da generišemo ovaj skup. Prvi je da generišemo podskupove sa nula elemenata (jedan prazan skup), pa skupove sa po jednim elemetom (n skupova), pa skupove sa po dva elementa itd. Međutim, za programiranje nam više odgovara drugi pristup, a to je da u svakom koraku dupliramo trenutne podskupove, i element dodamo samo u novu polovinu. Na primer, ukoliko imamo skup {1, 2, 3}, krećemo od praznog skupa i ubacujemo element po element:

{}
{}, {1} – dodali smo jedinicu u drugi skup
{}, {1}, {2}, {1, 2} – dodali smo dvojku u treći i četvrti skup
{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3} – dodali smo trojku u poslednja četiri skupa

Na kraju ovog procesa biće generisani svi podskupovi. Bitno je primetiti da je ovaj algoritam eksponencijalan, pošto treba generisati 2ⁿ skupova, pa je spor već za skupove sa nekoliko desetina elemenata.

vector<set<int>> powerset(set<int> s)
{
	vector<set<int>> pset;

	set<int> emptySet;

	pset.push_back(emptySet);

	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		int currentSize = pset.size();

		for (int i = 0; i < currentSize; i++)
		{
			set<int> newSet(pset[i]);
			newSet.insert(*it);
			pset.push_back(newSet);
		}
	}

	return pset;
}

Zadatak: Potrebno je izračunati koren broja bez korišćenja funkcije sqrt(). Kvadrat dobijene vrednosti može da odstupa od vrednosti zadatog broja za određenu toleranciju.

Rešenje: Ovo je veoma zanimljiv zadatak, pošto postoji nekoliko pristupa. Na Wikipedii se može naći lista načina za nalaženje korena nekog broja. Ja sam problem rešio upotrebom binarne pretrage, pa ću obraditi samo to rešenje. Naime, vršimo najobičniju binarnu pretragu i u svakoj iteraciji proveravamo da li smo došli do broja koji je dovoljno blizu pravom korenu. Treba samo obratiti pažnju na početni interval: ako je zadati broj X veći od jedan, tražimo između 1 i X; ako je manji od jedinice, tražimo između X i 1.

double sqrt(double x, double tolerance)
{
	if (x < 0)
		return 0;

	double left, right;

	if (x < 1)
	{
		left = x;
		right = 1;
	}
	else
	{
		left = 1;
		right = x;
	}

	while (true)
	{
		double mid = (left + right) / 2;

		double squared = mid * mid;

		if (abs(squared - x) <= tolerance)
			return mid;

		if (squared < x)
			left = mid;
		else
			right = mid;
	}
}

Zadatak: Data je funkcija bool fair_coin() koja u 50% slučajeva vraća true. Potrebno je napisati funkciju koja će u N procenata slučajeva vraćati true (zadato je dozvoljeno odstupanje).

Rešenje: Pošto nam je dostupna samo funkcija fair_coin(), očigledno je da ćemo taj novčić morati da bacamo više puta. Ali koliko?

Ako ga bacimo jednom, imamo dva ishoda sa verovatnoćama od po 50%. Ako ga bacimo dva puta, imamo četiri ishoda sa verovatnoćama 25%, 50%, 75% i 100%. Tri puta i dobićemo verovatnoće 12.5%, 25%, 37.5% itd. Dakle, jasno je da novčić treba baciti dovoljan broj puta tako neka od ovih verovatnoća bude dovoljno blizu traženoj verovatnoći. Zato ćemo mi bacati novčić, pamtiti dobijenu vrednost, i ponavaljati proces sve dok ne bacimo novčić dovoljno puta. Kada to uradimo, pogledaćemo vrednosti dobijene bacanjem i odrediti da li vraćamo 0 ili 1.

Da bismo to uradili, od dobijenih vrednosti ćemo formirati binarni broj. Recimo da je tražena verovatnoća 37.5% — novčić ćemo baciti 3 puta i dobićemo trocifreni binaran broj. Ovaj broj može imati 8 različitih vrednosti, i mi ćemo vratiti 1 ukoliko dobijemo neku od prve tri vrednosti (0, 1 ili 2) je jer 3/8 = 37.5%.

int biased_coin(double p, double prec)
{
	if (p == 0)
		return 0;

	if (p == 1)
		return 1;

	unsigned int previousTosses = 0;

	int numOfPossibilities = 1;
    
	double prob = 1;
    
	while(true)
	{
		numOfPossibilities *= 2;
    
		int randomValue = fair_coin();
        
		previousTosses = (previousTosses << 1) | randomValue;
    
		prob /= 2; // Probability for each binary string
        
		// Find the closest probablity for this number of tosses

		int closestNum = round(p / prob);

		// We don't want 0% or 100%
        
		if (closestNum == 0)
			closestNum++;

		if (closestNum == numOfPossibilities)
			closestNum--;

		double closestProb = closestNum * prob;

		if (abs(closestProb - p) < prec)
		{
			if (previousTosses < closestNum)
				return 1;
			else
				return 0;
		}
	}
}

Zadaci sa Facebook intervjua

Programerski zadaci

Matematički zadaci

2 Comments

Thoughts? Comments? Share them below!Cancel reply