Romok007's blog

By Romok007, history, 4 weeks ago, In English,

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 : Original Question Source (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)

Any kind of help will be helpful as i am stuck with the question :).

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For the randomized, I still confused, but I have an idea. You make an array that is maxx[i] = max a[i] (i start from 1 to i), and an array that is minn[i] = min a[i] (i start from n to i). Then you make binary search on both of these array to see if the element exists. It may be wrong, but it is good to have a look at.

Edit: Sorry, I didn't see the "Expected Space Complexity" line .P

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So we scan each element of the array maxx and do a binary search on the array minn and see if the element exists. But the time complexity will be O(n*log(n)). Am i missing something?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, however the problem is space compexity is N*3, so I don't know whether this solution is accepted.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

a[i] will be good if a[i] >=max(a[1], a[2]..a[i-1] ) and a[i]<=min(a[i+1], a[i+2]..a[n]).

You can use prefix and suffix array to achieve the answer in required complexities

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes thats a valid solution but the question asks us to use binary search(using a random function) and i am confused in that part. You can refer the link as well

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      IMO, questions asks to output the numbers which would be detected by new "randomized binary search". You are not supposed to run the "randomized binary search".