Google | L5 | Phone Screening

Anonymous User

3408

I recently completed a phone screening for a L5 SWE position at google. I have not been able to find a similar problem anywhere. Is there a similar problem on leetcode? Maybe there is a dynamic programming solution.

"We have a suite of tests that pass when run individually, but fail when run together. Specifically, there are two tests that cannot be run together. We are given an 'oracle' function that can tell us whether a set of tests pass or fail when run together in constant time. We need to write a function to find the 'bad pair'"

Helper function:

boolean doFail(Set<Integer> testNumbers);

Function to implement:

// signature can be anything that returns the two bad tests (pair, array of size 2, list of size two, helper object .. etc)
// input could also be an array, set, or list - that part wasn't too important
int[] badTests(List<Integer> testNumbers);

Brute force:
time O(n^2)
space O(1)

public int[] badTests(List<Integer> testNumbers) {
        for (int i = 0; i < testNumbers.size(); i++) {
            for (int j = i + 1; j < testNumbers.size(); j++) {
                if (doFail(new HashSet<>(List.of(testNumbers.get(i), testNumbers.get(j))))) {
                    return new int[] {testNumbers.get(i), testNumbers.get(j)};
                }
            }
        }
        return new int[] {-1, -1};
    }

We discussed a variant of binary search that the interviewer said would have a time complexity of O(n log(n)) due to some edge case - but I didn't not complete the the implementation.

Sometime after the interview I thought of this solution:
time O(n)
space O(1)

public int[] badTests2(List<Integer> testNumbers) {
        int leftCursor = 0;
        int rightCursor = testNumbers.size() - 1;

        boolean rightFailingTestFound = false;
        boolean leftFailingTestFound = false;

        do {
            if (!rightFailingTestFound) {
                if (doFail(new HashSet<>(testNumbers.subList(leftCursor, rightCursor+1)))) {
                    rightCursor--;
                } else {
                    if (rightCursor != testNumbers.size() - 1) {
                        rightCursor++;
                    }
                    rightFailingTestFound = true;
                }
            } else {
                if (doFail((new HashSet<>(testNumbers.subList(leftCursor, rightCursor+1))))) {
                    leftCursor++;
                } else {
                    if (leftCursor > 0) {
                        leftCursor--;
                    }
                    leftFailingTestFound = true;
                }
            }
        } while (!rightFailingTestFound || !leftFailingTestFound);

        return new int[] {testNumbers.get(leftCursor), testNumbers.get(rightCursor)};
    }

I imagine there must be a O(log(n)) solution using dynamic programming or some clever binary search.

Comments (6)