Given an array of strings with commit ids, and a predicate isBuggy that returns if a single commit is buggy, write a program that finds the first buggy commit.
- When a commit is buggy, we assume that all its children are buggy.
- When a commit is not buggy, we assume that all its ancestors are not buggy.

After solving it, I had to describe its time complexity and spatial complexity and how would I choose the test cases.

Question

Given an array of strings with commit ids, and a predicate isBuggy that returns if a single commit is buggy, write a program that finds the first buggy commit.
- When a commit is buggy, we assume that all its children are buggy.
- When a commit is not buggy, we assume that all its ancestors are not buggy.

After solving it, I had to describe its time complexity and spatial complexity and how would I choose the test cases.

Robin Kalia · Accepted Answer

This is really easy. Lets say that you have n-commits. Test for the 1st one. If it is buggy, tis is the beginning one, else try for nth commit. If this is buggy, try for (n/2)th one to test if it is buggy. If it is buggy, try for (n/4)th one or else try for (3n/4)th one. Thus, it is a recursive binary search until you find the first non-buggy one away from the buggy-one. Thus it is an O(lg(n)) solution.

OP · Answer

Each commit-id is represented by one String. The array is not sorted by commit-ids, but instead the order would be "chronological", as the commits were made.

Sigiloso · Answer

So you were basically asked to implement binary search.

Sigiloso · Answer

What does 'children' of a commit mean? the following commits? If in an array of 10 commits, 5th commit is that first buggy commit then will the isBuggy method return true for 6th commit also because all subsequent commits will be buggy.

Sigiloso · Answer

I wrote a recursive binary search. Firstly, my solution had an complexity of O(log n * n), then after following the interviewer hint I improved it to be O(log n)

Anonymous · Answer

I am assuming that you have array is sorted by commit ids. What are the strings that you are referring to.
Can explain the solution and the problem too ?

Yelp

Pergunta de entrevista da empresa Yelp

Respostas da entrevista

Empresas seguidas

Buscas de vagas