Randomized Binary Search - Google Top Interview Questions
Problem Statement :
Consider a modified binary search, where instead of picking the middle element as the pivot, we pick it randomly between the low and the high indices. Given a list of integers nums that's not necessarily sorted, return the number of elements that will always be found using this modified binary search. Constraints n ≤ 100,000 where n is the length of nums Example 1 Input nums = [1, 10, 5, 20] Output 2 Explanation We can always find the elements 1 and 20. For the element 5, if we had picked index 1 as the first pivot, we wouldn't be able to find it. Similarly for 10, if we had picked index 2 as the first pivot, it wouldn't be found. Example 2 Input nums = [0, 0] Output 0 Explanation For the first element, if we search for 0 we may have index 1 as the pivot and miss it. Similarly, if we search for the second element, we may get index 0 as the pivot. In both cases, we miss the elements.
Solution :
Solution in C++ :
int maxp[100005];
int mins[100005];
int solve(vector<int>& v) {
if (v.size() == 0) {
return 0;
}
int n = v.size();
maxp[0] = v[0];
for (int i = 1; i < n; i++) {
maxp[i] = max(maxp[i - 1], v[i]);
}
mins[n - 1] = v[n - 1];
for (int i = n - 2; i >= 0; i--) {
mins[i] = min(mins[i + 1], v[i]);
}
int ret = 0;
for (int i = 0; i < n; i++) {
bool prefixgood = i == 0 || v[i] > maxp[i - 1];
bool suffixgood = i == n - 1 || v[i] < mins[i + 1];
ret += prefixgood && suffixgood;
}
return ret;
}
Solution in Java :
import java.util.*;
class Solution {
public int solve(int[] nums) {
int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE, ct = 0;
boolean[] beg = new boolean[nums.length];
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max)
beg[i] = true;
max = Math.max(max, nums[i]);
}
for (int i = nums.length - 1; i > -1; i--) {
if (nums[i] < min && beg[i] == true)
ct++;
min = Math.min(min, nums[i]);
}
return ct;
}
}
Solution in Python :
class Solution:
def solve(self, nums):
# all elements on the left should be smaller than cur element
# all elements on the right should be greater than cur element
leftMax = [i for i in nums]
rightMin = [i for i in nums]
# the number of occurance has to be unique!
freq = collections.Counter(nums)
for i in range(1, len(nums)):
leftMax[i] = max(leftMax[i], leftMax[i - 1])
for i in range(len(nums) - 2, -1, -1):
rightMin[i] = min(rightMin[i], rightMin[i + 1])
res = 0
# now at each position check!!!
# if leftMax is = to rightMin then we are always going to be found!
# but make sure you are not having any duplicate
for i in range(0, len(nums)):
if freq[nums[i]] == 1 and leftMax[i] == rightMin[i]:
res += 1
return res
View More Similar Problems
Pair Sums
Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v
View Solution →Lazy White Falcon
White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi
View Solution →Ticket to Ride
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o
View Solution →Heavy Light White Falcon
Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim
View Solution →Number Game on a Tree
Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy
View Solution →Heavy Light 2 White Falcon
White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr
View Solution →