## Facebook Interview Question for Software Engineers

• 1
of 1 vote

Country: UK
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
7
of 7 vote

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

``````Random 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;

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;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````/**
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;
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];
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@inucoder: very nice solution to pick without iterating twice

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 == 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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think @inucoder should use temp var to reserve the shouldPick method parameter,and add else statement"temp--".
Cause there is a possibility that every shouldPick method will return false,then result will return -1.
My poor English..:D

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm::
1.Find max and its count C
2.Choose a number m from [1..C]
3.Get the m_th largest number (max) from the array.

Requires two iteration of the given array. O(n) time complexity and O(1) space complexity.

It seems to me that this solution works, and looks simple.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def maxRand(arr):
if len(arr) == 0:
return -1

a, b = arr, 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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import random

def randMaxIndex(seq):
maxValue = seq
count = 1
seq = 0
for i in xrange(1, len(seq)):
if seq[i] > maxValue:
maxValue = seq[i]
count = 1
seq = i
elif seq[i] == maxValue:
seq[count] = i
count += 1

#return random.choice(seq[:count])
return seq[random.randint(0, count - 1)]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
arr = 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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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
arr = 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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 - 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 - 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import random
def max_idx_rand(lst):
return random.choice([num for num, i in enumerate(lst) if i == max(lst)])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
//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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)+"") ;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) ;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````/*
Find min,max in O(n)
Select all indices where max.
*/
a = [ 1, -2, 0, 6, 2, -4, 6, 6 ]
#(min,MAX) = minmax(a)
indices = select(a) where { \$.o == MAX } as { \$.index }
println(indices)``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.