## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 8 vote

1. Go through the array once, find the max and the number of occurrences (n).
2. Generate a random number (r) between 1 and n.
3. Go through the array again, return rth occurrence.

Time: O(n)
Space: O(1)

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

Comment hidden because of low score. Click to expand.
3
of 9 vote

Use the online version of Reservoir Sampling. One pass algorithm.

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

Reservoir sampling is used to return k samples from the list of n items in random order.
With reservoir sampling how are you going to satisfy the requirement where we have to return only the locations of the maximum elements randomly?

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
3

to complete this solution ,
1) currentMaxNum = current max number
2) currentMaxCount = how many instances of current max we have seen

every time we update currentMaxNum we update the currentMaxCount to 0.
initialize {currentMaxNum , CurrentMaxCount} ={a[0],1}
foreach a[i]
if (a[i] < currentMaxNum) -- continue;
else if ( a[i] > currentMaxNum)
{
currentMaxNum = a[i]; currentMaxCount = 0;
}
else
{
// a[i] == currentMaxNum
currentMaxCount ++;
replace currentMaxNum with a[i] with probability 1 / currentMaxCount;
}

This algorithm guarantees that currentMaxNum will be max number at the end.
now lets say there are 5 max in the array all over the array .
the first element will get selected with 100% (first time). the chances that it will remain the final outout that it has to survive the next 4 coin toss. which means
1* (1 -1/2) * (1-1/3)*(1-1/4)*(1-1/5) = 1*1/2/*2/3*3/4*4/5 = 1/5

prob that 2nd max becomes the final number =
(1/2)*(1-1/3)*(1-1/4)*(1-1/5) = 1/5. ....

though my first thought was to simply count the total number of max element in first pass and just generate a random number (x) between 1 to 5 ( if 5 is the total count) and in 2nd pass simply return the xth element.

Comment hidden because of low score. Click to expand.
3

It can be done with a single pass over the array (Python):

``````import random

def rand_max(arr):
curr_max = 0
curr_max_idx = 0
curr_max_count = 1
for i,x in enumerate(arr):
if x > curr_max:
curr_max = x
curr_max_idx = i
curr_max_count = 1
elif x == curr_max:
curr_max_count = curr_max_count + 1
if random.random() < 1.0 / curr_max_count:
curr_max_idx = i
return curr_max_idx``````

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

First go through the array and find max with all indices(store indices in arrayList).
This can be done in O(n).
Now with newly created indices arraylist, return the random element.

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

Worst case space complexity could be O(N) - if all the elements are max values (cause you store max elements in a separate list/array).

If we can modify array - better in terms of space complexity:
1. Do in-place random shuffle of array.
2. Choose only one max element.

time: O(N)
space: O(1)

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

``````int array[] = {1,4,9,7,3,9,4,7,2,7,3,0,1,2,9,6,5,7,8,9};
int maxIndex = 0;
int count = 0;
for(int i= 0;i<array.length;i++){
if(array[maxIndex] == array[i])
count++;
else if(array[maxIndex] < array[i]){
maxIndex = i;
count = 1;
}
}
int len = array.length;
int lenSize = 1;
while( len != 0){
len = len / 10;
lenSize = lenSize * 10;
}
int r = (int)(Math.random() * lenSize);
int randomCount = (r%count)+1;
int j = maxIndex;
while(randomCount != 0)
if(array[j++] == array[maxIndex])
randomCount--;
System.out.println("The Max Number is " + array[maxIndex] +" and it's random index is " + (j));``````

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

I understood the part for determining the maximum occurring element and the maxCount for the element. Can you please explain the logic for coming up with the random index?
Thanks

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

Assumption :
1. If an array contains only 1 max element than return the same indices
2. Random(x1,x2,x3,x4.....xn) = Random(x1, Random(x2, Random.... xn) )
( not sure if this is true , and makes every indices to be picked up with equal probability.)

Observations
1. O(n) algorithm
2. Best-So-Far approach

Pseudo algo:

For each number
If greater than current max
Reset maxIndex
If equal to current max
set Max index as Random(maxIndex , currentIndex)
If less than current max
continue
End

Will think more on Assumption 2 , and see if we can get result without any flaw in boundary scenarios.

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

``````int getMaxRandmonIndex(int[] arr) {
int currentMax = Integer.MIN_VALUE;
int count = 0;
ArrayList<Integer> index = new ArrayList<Integer>();

for (int i = 0; i < arr.length; i++) {
if (arr[i] > currentMax) {
currentMax = arr[i];
count = 1;
if (index.size > 0) {
index.removeRange(0, index.size());
}
} else if (arr[i] == currentMax) {
count++;
}
}
Random rand = new Random();
int ind = rand.nextInt(count);
return index.get(ind);
}``````

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

It depends, if the values in array is subject to change than each time we need to check the current max.

``````To randomize the return index each time start the search from a random index
For the length of array until current index equals random index
Go through the end of the array
if at the end move to beginning
Each time check if the value of current index is larger than the one found so far
return the last or first index found``````

This will work O(n) each time with no additional memory and will return a random index.

-If the array not subject to change

``````if first run
Iterate each item
if current is larger
wipe previous
set current as max
store current index
If current equals largest
store current index
return random index from stored indexed``````

This will work O(n) for the first run O(1) for the next (depending on the data structure)

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

We can have separate array to hold all the indices of max elements. Give any random number among them!

``````int getIndexOfMaxRandomly(int arr[], int size)
{
int i = 0;

if (size <= 0)
return -1;

int* idxArr = (int *) malloc (sizeof(int) * size);
memset (idxArr, 0, size*sizeof(int));

if (!idxArr)
return -1;

srand(time(NULL));

int curMax = arr[0], maxCnt = 1;
for (int i = 1; i < size; i++)
{
if (curMax < arr[i])
{
curMax = arr[i];
maxCnt = 0;
idxArr[maxCnt++] = i;
}
else if (curMax == arr[i])
idxArr[maxCnt++] = i;
}
/*
for (int i = 0; i < maxCnt; i++)
printf ("%d  ", idxArr[i]);
*/
int randIdx = idxArr[rand()%maxCnt];
free (idxArr);
return randIdx;
}``````

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

Earlier one is O(n) time & space solution.
We can further optimize the space, if we use the existing array for holding the index of the max elements. Then return random index from them!

We can reduce the space complexity in O(1)..

``````int getIndexOfMaxRandomly(int arr[], int size)
{
if (size <= 0)
return -1;

srand(time(NULL));

int curMax = arr[0], maxCnt = 1;
arr[0] = 0; // For the momemt treat this first elememt as max

for (int i = 1; i < size; i++)
{
if (curMax < arr[i])
{
curMax = arr[i];
maxCnt = 0;
arr[maxCnt++] = i;
}
else if (curMax == arr[i])
arr[maxCnt++] = i;
}

return arr[rand()%maxCnt];
}``````

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

``````import java.util.ArrayList;
import java.util.Random;

public class RandomArray {

public static void main(String[] args)
{

int[] array={45,53,73,13,89,73,89,89,89,89,89,73,452,12,132,89};
int kb=0;
int big=array[0];
try
{
for(kb=0;kb<array.length;kb++)
{
if(array[kb+1]>big)
{
big=array[kb+1];
}
}
}
catch(ArrayIndexOutOfBoundsException e)
{

}
ArrayList<Integer> alist=new ArrayList<Integer>();

for(int i=0;i<array.length;i++)
{
if(array[i]==big)
{

}
}
Random r =new Random();
int random=	r.nextInt(alist.size());

System.out.println("Max element is"+big);
System.out.println("Position is"+alist.get(random));
}
}``````

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

According to the description, the max is guaranteed to be in multiple places.
Set the max number variable to the minimum number.
Loop through the values and store each value in a hashtable.

-If it is the first time insert that number into the table, continue to the next number
-If that number has appeared more than the once, compare it to the current max number and if it is bigger, it becomes the new max. Otherwise continue to the next number.

Loop until you reach the end.
Return max number.

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

According to the description, the max is guaranteed to be in multiple places.
Set the max number variable to the minimum number.
Loop through the values and store each value in a hashtable.

-If it is the first time inserting that number into the hashtable, continue to the next number.
-If that number has appeared more than the once, compare it to the current max number and if it is bigger, it becomes the new max. Otherwise continue to the next number.

Loop until you reach the end.
Return the max number.

You can return a random index by starting at a random position and wrapping around until you reach the starting point again.

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

1. Generate a random array of integers
2. Loop through to find max and store max_indices in the array.
3. Generate a random number between 0 and max_indices length.
4. Return that value from the max_indices array.

``````a= []
250.times { a.push(rand(50)) }
max_indices = []
max = nil
a.each_with_index do |v,i|
max_indices.push( i ) if v == max
if max.nil? || v > max
max = v
max_indices = [i]
end
end

p max_indices[rand(max_indices.length)]``````

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

The last line should be

``p max_indices[rand(max_indices.length-1)]``

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

``````<?php

function maxPosition(\$numbers)
{
\$maxValue = 0;
\$maxPositions = [];
foreach (\$numbers as \$index => \$number) {
if (\$number > \$maxValue) {
\$maxValue = \$number;
\$maxPositions = [\$index];
continue;
}
if (\$number < \$maxValue) {
continue;
}
\$maxPositions[] = \$index;
}
return \$maxPositions[rand(0, count(\$maxPositions) - 1)];
}``````

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

``````#!/usr/bin/env python
from __future__ import print_function
import random

arr = [1,2,3,4,5,5,3,5]

maxValue = max(arr)
max_indices = []

for idx,val in enumerate(arr):
if (val == maxValue):
max_indices.append(idx)

random_idx = random.randint(0,len(max_indices)-1)
print("The maximum value is {}. It occurrs at indices {}".format(maxValue,', '.join(map(str,max_indices))))
print("A random index at which this value occurs is: ", max_indices[random_idx])``````

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

I think the simplest solution is this:

``````#include "stdafx.h"
#include <algorithm>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
int array[] = { 1, 4, 9, 7, 3, 9, 4, 7, 2, 7, 3, 0, 1, 2, 9, 6, 5, 7, 8, 9 };
int elements = sizeof(array) / sizeof(array[0]);

std::sort(array, array + elements);

printf("the value is %d", array[elements-1]);

getchar();

return 0;
}``````

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

``````public static void main(String[] args){

int[] a = new int[]{9,3,1,2,3,4,5,7,8,9,9};
solve(a);
}

static void solve(int[] a){
ArrayList<Integer> ar= new ArrayList<>();
for(int i=0;i<a.length;i++){
}

Collections.sort(ar);

System.out.println(ar.get(ar.size()-1));

}``````

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

``````private static int getRandomMaxiumNumber(int[] input) {
if (input==null || input.length==0)
return -1;
if (input.length==1) {
return 0;
}

int start = (int) (Math.random()*input.length-1);
int max = Integer.MIN_VALUE;
int maxidx = -1;
int i=start;
do {
if (input[i]>max) {
max = input[i];
maxidx = i;
}
i++;
if (i==input.length) i=0;
} while(start!=i);
return maxidx;``````

}

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

Consider a situation where the last two digits are the max value. there are (n-1)/n probability we would select a[n-2]

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

``````package pkg;

import java.util.Arrays;
import java.util.Random;

public class MaxRandom {

/**
* Given an array of integers. We have to find the max element of the array,
* which is at multiple places in the array and return any one of the
* indices randomly.
*/
public static int findMaxElementIndiceRandom(int[] a) {

int maxIndice = 0;

for (int i = 0; i < a.length; i++) {
if (a[i] > a[maxIndice]) {
maxIndice = i;
} else if (a[i] == a[maxIndice]) {
maxIndice = randSelect(maxIndice, i);
}
}

return maxIndice;
}

public static int randSelect(int numberOne, int numberTwo) {
Random random = new Random();
return (random.nextInt(2) % 2) == 0 ? numberOne : numberTwo;
}

public static void main(String[] args) {
int[] a = new int[] { 3, 6, 3, 9, 8, 9, 4, 3, 2, 9, 1, 6 };
System.out.println(findMaxElementIndiceRandom(a));

}

}``````

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

Here my solution:

``````public static int randomPosition(int[] array) {
int max = 0;
List<Integer> positionsMax = null;
for (int i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
positionsMax = new ArrayList<Integer>();
System.out.println("new max found: " + max + " in position " + i);
} else {
if (array[i] == max) {
System.out.println("another max in position " + i);
}
}

}
Random random = new Random();
return positionsMax.get(random.nextInt(positionsMax.size()+1));
}``````

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

uint find_max(vector<int> intArray) {
int max =std::numeric_limits<int>::min();
uint index=0, count=0;
for(std::vector<int>::iterator it = intArray.begin(); it< intArray.end(); ++it) {
if(*it> max) {
max = *it;
index = count;
}
count++;
}

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

Are there any other constraints to this question? Can we use additional memory ?

If yes,

1. Create a TreeMap of element value vs ArrayList of element position. Create this TreeMap with reverse Sort class

``Map<Integer, List<Integer>> valueMap = new TreeMap<Integer, List<Integer>>(new ReverseSort());``

2. This ReverseSort class implements Comparator interface which implements compare method.

``````Class ReverseSort implements Comparator<Integer>(){

public int compare(int a, int b){
return b - a; //reverse sorting
}``````

Now get the keySet from the treeMap and get ArrayList for the 0th Key which gives you the largest element in the array.

The value of this key is an array list of all the locations where this largest element appears, return any location randomly.

Total time complexity: O(N)
Total Space complexity: O(N)

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

Guys ... we are all here to learn, so those who are giving negative votes, please post why negative vote is given so that we can improve.
Just giving down vote does not help in understanding what improvement is needed.

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

Not really sure why either, all of the answers are possible answers to the problem posted, no reason for someone to go through and down vote everything. I like your solution, in your case what happens without the sort, do they order from least to greatest by default?

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

Yes, if we dont use class to sort in the reverse order, the default order is smallest to the largest.

We can do this way also where after getting a keySet, just use the last index key instead of 0th one so that we get the largest element position array.

But by passing comparator class, you are trying to prove to the interviewer that you can code these interfaces as well. (You have 20 to 30 mins max to impress the interviewer so this is just a small step in that direction :)

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

``````#include <stdio.h>
#include <stdlib.h>

// randomly select an index of the two
int
randomSelect(int a, int b)
{
if (rand() % 2 || a < 0) {
return b;
}

return a;
}

//find max and maxIndex
int
findMax(int a[], int size)
{
int max = 0;
int maxIndex = -1;
int i = 0;
time_t t;

srand((unsigned) time(&t));

for (i = 0; i < size; i++) {
if (max < a[i]) {
max = a[i];
maxIndex = i;
} else if (max == a[i]) {
maxIndex = randomSelect(maxIndex, i);
}
}

return maxIndex;
}

int
main()
{
int a[6] = {1, 2, 1, 2, 1, 2};
printf("%d \n", findMax(a, 6));
}``````

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

One big issue here is the inclusion of multiples in the data set. One way to not have to deal with comparisons is to use a Hashtable.

Basically we dump the array into a Hashtable using the array value as the key and the index as the hashtable value. Some java code would like like this:

``````t = new Hashtable<Integer, Integer>();

//list is an array of ints, but this should scale to doubles and floats as well
for(int i = 0; i < list.length; i++)
t.put(list[i], i);

Enumeration<Integer> e = t.keys();
int biggest = 0;
if(e.hasMoreElements())
biggest = e.nextElement();

System.out.println(t.get(biggest));``````

From this you can see that all we need to do, after the dump, is to get the first key and returns its corresponding value. Mileage may vary for other Hashmap implementations

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.