CareerCup

while (!haystack.empty())
{
if (haystack.element() == needle)
return true;
else
haystack.removeElement();
}

lol...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

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

Knuth Moris Pratt Algorithm

OMG! Boyer Moore is the only one :D hehe

Hashing is easier to code in an interview and works well in practice. KMP is good to mention to convey to the interviewer that one knows about worst case complexities