Google L3 onsite

I gave my google onsite today and was asked this question
We have been given N ingredients. There exists a pair of ingredients such that if we combine them, the dish becomes bad. We need to find any such pair. We are also given a test() method which can be treated as a black box. It takes a set of integers and returns false if there is any pair of ingredients in that set which would create a bad dish, otherwise it returns true.

I started out with a N*N approach of checking each pair. Interviewer asked me to optimize it and I had to think a lot of a different approach and even interviewer also hinted me. The solution I proposed is to check for every prefix of elements (1,2,..,i) and find the longest prefix which returns true using test() function. Then element i+1 will definitely constitute a bad pair with prefix (1,...i) for which we can just do a linear traversal again and check every pair (i+1, j), j>=1 && j<=i.
But this is still O(N*N) because runtime of test() method is assumed to be proportional to the size of subset ( and I had missed asking about this runtime to the interviewer).
Upon this I further optimized the solution using binary search to find the length of longest prefix which brought time complexity to O(log(N) * N).
Although the interviewer mentioned he is happy with the solution, he told that we can even do this in O(N). Does someone has any idea about how to solve in linear time.
What do you guys feel is the difficulty of this problem? Is it medium or hard?