Facebook Interview Question Software Engineers
Country: UK
Interview Type: Phone Interview
As @inucoder suggested, reservoir sampling is probably the ideal solution.
Another pretty interesting one would be to shuffle the array in place using Knuth-shuffle in O(n), get the max using O(n) and return the first index of a max element. O(n)
Total time complexity: O(n), space complexity: O(1)
/**
Approach 1: O(n) time and O(n) space. Iterate through the array and find the indices containing the maximum value. Store these indices in a
separate array list. Inside the run function, choose a random value in the array list.
Approach 2: O(n) time and O(1) space. Iterate through the array (A) and find the maximum value (max).Create an
index variable (i-initialized to 0) and a counter variable (count-initialized to 0). Iterate through the array again,
everytime you encounter max at an index j, set A[i++] = j and increment count (count ++). Inside the run function,
choose a random integer (idx) between 0(inclusive) and count - 1 (inclusive), return A[idx]-this will be an index
which contained the maximum value.
**/
public class RandMaxSvc{
private int[] vals;
private int count;
public RandMaxSvc(int[] arr){
vals = arr;
count = 0;
initialize()
}
private void initialize(){
int max = vals[0];
for(int i = 1; i < vals.length; i++){
max = Math.max(max,vals[i]);
}
int idx = 0;
for(int i = 0; i < vals.length; i++){
if(vals[i] == max){
vals[idx++] = i;
count++;
}
}
}
public int run(){
Random rnd = new Random();
int idx = rnd.nextInt(count);
return vals[idx];
}
}
Here is another way to obtain completely randomly a maximal element from an array of n elements using constant space
1) Find the maximal element of the array
2) Choose randomly a number x between 1 and n
3) Iterate the array spacing it x until you find a maximal element.
3.1) If you iterate over n increase x by one and start iterating from the beginning of the array.
3.2) If x gets over n choose randomly another spacing value.
3.3) For subsequent calls start iterating from the last found element
Python one liner for the n spatial solution
from random import choice
def get_max(s):
return choice(filter(lambda x: x[1] == max(s), enumerate(s)))
Python version for the constant spatial solution
from random import randint
def get_max(s):
maximum_value = max(s)
spacing = randint(1, len(s) -1)
next = spacing
while True:
if s[next] == maximum_value:
yield next, maximum_value
next = (next + spacing)
if next >= len(s):
next %= len(s)
spacing += 1
if spacing >= len(s):
spacing = randint(1, len(s) -1)
def maxRand(arr):
if len(arr) == 0:
return -1
a, b = arr[0], 1
for i in xrange(1,len(arr)):
if arr[i] == a:
b += 1
elif arr[i] > a:
a = arr[i]
b = 1
from random import randint
c = randint(1, b)
for i in xrange(len(arr)):
if arr[i] != a:
continue
if c == 1:
return i
else:
c -= 1
return -1 # exception; should not get here
import random
def randMaxIndex(seq):
maxValue = seq[0]
count = 1
seq[0] = 0
for i in xrange(1, len(seq)):
if seq[i] > maxValue:
maxValue = seq[i]
count = 1
seq[0] = i
elif seq[i] == maxValue:
seq[count] = i
count += 1
#return random.choice(seq[:count])
return seq[random.randint(0, count - 1)]
import random
arr = [ 1, -2, 0, 6, 2, -4, 6, 6 ]
max = 0
indexes = 0
# Shaffle the array O(n)
for index in xrange(len(arr)):
rnd = random.randint(0,len(arr)-1)
tmp = arr[0]
arr[0] = arr[rnd]
arr[rnd] = tmp
print arr
# Find the max O(n)
for elem in arr:
if elem > max:
max = elem
# Find the indexes O(n)
for index,elem in enumerate(arr):
if elem == max:
indexes = index
# Execution: O(n) + O(n) + O(n) = O(n)
# Memory: O(1)
print indexes
import random
arr = [ 1, -2, 0, 6, 2, -4, 6, 6 ]
max = 0
indexes = 0
# Shaffle the array O(n)
for index in xrange(len(arr)):
rnd = random.randint(0,len(arr)-1)
tmp = arr[0]
arr[0] = arr[rnd]
arr[rnd] = tmp
print arr
# Find the max O(n)
for elem in arr:
if elem > max:
max = elem
# Find the indexes O(n)
for index,elem in enumerate(arr):
if elem == max:
indexes = index
# Execution: O(n) + O(n) + O(n) = O(n)
# Memory: O(1)
print indexes
A C++ solution
Part 1 - Using O(n) for both time and space complexity.
Nothing special here. Just loops through and stores
max indices into a vector, and resetting the vector
when a new max is found.
int getMax(const std::vector<int>& arr)
{
if (arr.size() == 0) return -1;
int max = arr[0] - 1; // Guarantee first index
std::vector<int> maxes; // Vector of indices
maxes.reserve(arr.size()); // Vector memory efficiency
// Get the max value
for (size_t i = 0; i < arr.size(); ++i)
{
// Refresh vector on new max
if (arr[i] > max)
{
maxes.clear();
max = arr[i];
}
// Store the index
if (arr[i] >= max) maxes.push_back(i);
}
return maxes[rand() % maxes.size()];
}
Part 2 - Using O(n) for time and O(1) for space
This is similar to the above solution but doesn't save
each max index found. Instead, when a new max is found,
the max index is refreshed, and when a duplicate max is
found, the max index has a probability to flip to the new
index, based on a degrading probability.
int getMax(const std::vector<int>& arr)
{
if (arr.size() == 0) return -1;
int max = arr[0] - 1; // Guarantee first index
int maxIndex = 0;
int numMaxFound = 0; // Save number of max indices
// Get the max value
for (size_t i = 0; i < arr.size(); ++i)
{
// Refresh count on new max
if (arr[i] > max)
{
numMaxFound = 1;
max = arr[i];
maxIndex = i;
}
// Random chance to flip the max index
// based on a degrading probability
else if (arr[i] == max)
if (rand() % ++numMaxFound == 1)
maxIndex = i;
}
return maxIndex;
}
For the O(1) solution - first find the max and then iterate through the array in a cycle from a random "start" index until length+"start" where the index i is the mod value
Return the first value equals to max
public static int randomIndexOfMax(Integer[] arr) {
Random rand = new Random();
int max = arr[0];
//Find max
for(int i=1; i<arr.length; i++) {
if(max < arr[i]) {
max = arr[i];
}
}
int index = -1;
int start = rand.nextInt(arr.length);
//Iterate from start to length+start in mod indexes
for(int i=start; i<arr.length+start; i++) {
int loc = i%(arr.length);
if(max == arr[loc]) {
index = loc;
}
}
return index;
}
import java.util.*;
class RandomMax {
public static void main(String[] args) {
int[] array= {1,-2,0,6,2,-4,6,6};
System.out.println("Max index: "+ getRandomIndex(array));
System.out.println("Max index: "+ getRandomIndex(array));
System.out.println("Max index: "+ getRandomIndex(array));
}
public static int getRandomIndex(int[] array) {
int max = Integer.MIN_VALUE;
String indexs = "";
for (int i = 0; i < array.length; i++){
int temp = Math.max(max, array[i]);
if (temp > max) {
indexs = "";
max = temp;
}
else indexs += i+"";
}
Random rand = new Random();
int randomIndex = rand.nextInt(indexs.length());
return Integer.parseInt(indexs.charAt(randomIndex)+"") ;
}
}
My O(n) and O(1) solution
import java.util.*;
class RandomMax {
public static void main(String[] args) {
int[] array= {1,-2,0,6,2,-4,6,6};
System.out.println("Max index: "+ getRandomIndex(array));
System.out.println("Max index: "+ getRandomIndex(array));
System.out.println("Max index: "+ getRandomIndex(array));
}
public static String getRandomIndex(int[] array) {
int max = Integer.MIN_VALUE;
String indexs = "";
for (int i = 0; i < array.length; i++){
int temp = Math.max(max, array[i]);
if (temp > max) {
indexs = "";
max = temp;
indexs += i+"";
}
else if (array[i] == max)
indexs += i+"";
}
Random rand = new Random();
int randomIndex = rand.nextInt(indexs.length());
//System.out.println(indexs);
return indexs.substring(randomIndex, randomIndex+1) ;
}
}
Time O(N)
Space O(1)
Steps:
1) Loop through to find Max of the array and the maxIndex(which will be the last MaxIndex, but doesn't matters which one)
2) Loop through again to find index(called currentMaxIndex) containing maxElement and make maxIndex = Random(maxIndex , currentMaxIndex)
Print maxIndex -> This is the random Index of the max value element
//Time is O(N) , Space is O(1)
public static void getMaxValueIndexEvenly2(int[] arr){
int maxValue = Integer.MIN_VALUE;
int maxIndex = -1;
for(int i=0;i<=arr.length-1;i++){ // O(N)
if(arr[i] > maxValue){
maxValue=arr[i];
maxIndex=i;
}
}
int currentMaxIndex = -1;
Random random = new Random();
for(int i=0;i<=arr.length-1;i++){ // O(N)
if(arr[i] == maxValue){
currentMaxIndex = i;
int randomIndex = random.nextInt(2); // random between maxIndex and currentMaxIndex i.e 2 elements. It returns 0 or 1
if(randomIndex == 0){
maxIndex=maxIndex; // keep maxIndex as maxIndex
}else{
maxIndex=currentMaxIndex; // update maxIndex as currentMaxIndex
}
}
}
System.out.println("Random O(1) Max Index = " + maxIndex);
}
Getting an O(n) time/space solution is not hard. First find the max value in A, then, iterate it again and store in a list M all the positions where it appears. Generate a random integer x between 0 and |M| (exclusive) and return M[x].
For a O(1) space solution, use the idea for getting a random element from a stream of unknown length:
It's works as follows:
1) First find the max value in A
2) Let maxSeenSoFar = 0 and maxIndex = -1
3) For each element of A, at position i, if it's the max value:
3.1) increase maxSeenSoFar by one
3.2) do maxIndex = i with probability 1 / maxSeenSoFar
4) Return maxIndex
- inucoder May 22, 2017Random random = new Random(); boolean shouldPick(int maxSeenSoFar){ int value = random.nextInt(maxSeenSoFar); return value == 0; //this returns true with 1 / maxSeenSoFar probability } int getRandMaxIndex(int[] A){ int max = A[0]; for (int i = 1; i < A.length; i++){ max = Math.max(max, A[i]); } int maxIndex = -1; int maxSeenSoFar = 0; for (int i = 0; i < A.length; i++){ if (A[i] != max){ continue; } maxSeenSoFar++; if (shouldPick(maxSeenSoFar)){ maxIndex = i; } } return maxIndex; }