Given a binary array of 0 and 1, u are provided with a function taking l and r as inputs and it return a boolean answer whether there exists a '1' in between l and r or not. We needed to find the indices of every occurence of '1' in the array using minimum calls to the given function.

Question

Sigiloso · Accepted Answer

Brute approach : call for every index : O(N)
Better : pass 0 and n-1 : then keep on checking whether we have a 1 or not : if found a one break the array into two halfs and check again : Basically a mix of Binary search and Merge Sort algo

Google

Pergunta de entrevista da empresa Google

Resposta da entrevista

Empresas seguidas

Buscas de vagas