Facebook Interview Question
Software Engineer / Developerslol...haystack aint hay+Data structure wala stack.its haystack!!!!
first of all the above solution is wrong as its O(n) and n=millions in a Haystack.
Possible tools used: a very precise weighing machine that can weigh a needle and a hay.
Logic:
1.Divide the haystack in half by weight
2.Search for needle in the heavier one.
Algo:binary search
Possible test for needle: wieght or magnet
If you divide a haystack in half by weight, then neither half is heavier ... duh. Put each half on a floating platform -- the one that displaces less water is denser, and contains the needle. But it would be easier to spread the haystack thinly and search by eye, or point a fan at the haystack ...
Also, it says interviewer was looking for coding skills, so the "haystack" obviously is a data structure -- probably a string. People who cannot accurately and unambiguously describe their interview questions should fail all interviews.
Assume each needle is unique there can be many way to think about it like haystack can array of needles or linked list of nodes then 2nd thing is that on the basic of what criteria we will find the needle is that
size or type/colour etc..
then if needle are unsorted then we can sort the needle on the basis of size & then search using binary search so time O(nlogn) in case of linked list we will use merge sort thats also has O(nlogn) where n is size of haystack
else if array or linked are sorted then we can find the needle in O(logn) in array & O(n) in linked list
else as its the grayStack so put all the needles into stack & retrieve one by one until retrieve needle is not equals to given needle we checking the needle here based on some type /name/ranking/etc on the basis of which we can compare the needle with others.
while (!haystack.empty())
{
if (haystack.element() == needle)
return true;
else
haystack.removeElement();
}
it can also be done in O(n)
Correct me if anything wrong
rajcools if you are not satisfied with above answer you may like it using KMP Algorithm
basically we have to Write a program that finds all occurences of a given pattern in a given input string. This is often referred to as finding a needle in a haystack.
The algorithm has to detect all occurences of the needle in the haystack. It should take the needle and the haystack as input, and output the positions of each occurence, as shown below. The suggested implementation is the KMP algorithm, as, a naive approach will probably exceed the time limit, whereas other algorithms are more complicated...e.g Rabin Karp so The choice is yours.
so if we do pattern matching using KMP algorithm we can find the needle inn O(m+n)
n=length of haystack
m=length of needle
also it depends on how one understand the question & how one approach as i am sure this problem can be solved by many ways but i think KMP is best Suitable for this.
I provide the efficient solution let me know if better one exist
Shashank
while (!haystack.empty())
- Anonymous May 11, 2011{
if (haystack.element() == needle)
return true;
else
haystack.removeElement();
}