Help needed with a google interview problem

Правка en2, от Romok007, 2019-11-12 12:16:00

Given an unsorted array find the numbers in the array that return true for the following function (defined below).

  1. Function will return true for value x, if all numbers on left side of x are small and all number on the right side of x are greater.

But the question asks us to use randomized binary search (mid element is not decided by (high + low)/2 but by using a random function) to find the solution.

Link to the question : Your text to link here... (Round 3 Onsite question)

Example : Input : [ 4, 3, 1, 5, 7, 6, 10] Output : 5,10

Expected Time Complexity : O(n) Expected Space Complexity : O(n)

Теги #help, #binary search, #randomisation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Romok007 2019-11-12 12:17:18 103
en2 Английский Romok007 2019-11-12 12:16:00 29
en1 Английский Romok007 2019-11-12 12:15:25 714 Initial revision (published)