Facebook Interview Question
Country: Israel
Interview Type: Phone Interview
what should it return: the index of max value, if max values occurs multiple times, should it have a state and cycle through the max values or should it return one of the indexes with equal probability?
if the question was with equal probability, then this would be the solution:
int getIndex(const std::vector<int>& numbers) { // suppose, MIN_INT doesn't occure in numbers
int maxNum = numeric_limits<int>::min();
size_t idx = -1;
size_t maxNumCtr = 0;
for(size_t i = 0; i<numbers.size(); ++i) {
int num = numbers[i];
if(num > maxNum) {
idx = i; // probability 1
maxNumCtr = 1;
} else if (num == maxNum) {
maxNumCtr ++;
idx = ((rand() % maxNumCtr) == 0) ? i : idx;
// P(idx=i) = 1/(maxNumCtr+1): 1/2 for 2nd, 1/3 for 3rd...
// you can prove it's uniform by induction
// if P((rand() % maxNumCtr) == 0) would be 1/maxNumCtr which it is not exactly.
// modulo will not generate uniform distributions
}
}
return idx; // -1 if empty array
}
the solution is O(n), the only improvement when knowing maxCount previously would be, to select which occurence of maxValue would be picked in advance. This results in less calles to rand (which is usually not a big problem because they are fast) and in O(n/2) average runtime which is still O(n). On large n certainly a plus, expecially if max values tend to be in the front of the vector opposed to the end.
Further if the function get's called repeatedly with the same vector<int> one could change the signature to a set and a query function and remember the maxValue indexes, so we had a O(n) scan first and O(1) subsequent calls.
Java Code with O(logN)
public class FindMaxElementStateLess {
public static void main(String[] args) {
Elem[] e = new Elem[7];
e[0] = new Elem(0, 0);
e[1] = new Elem(-1, 1);
e[2] = new Elem(6, 2);
e[3] = new Elem(4, 3);
e[4] = new Elem(5, 4);
e[5] = new Elem(6, 5);
e[6] = new Elem(6, 6);
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
}
public static int getMaxIndex(Elem[] e) {
maxHeapMod(e);
e[0].acc += 1;
int index = e[0].index;
for (int i = 0; i < e.length; i++)
e[i].acc += 1;
swap(e, 0, e.length - 1);
return index;
}
//0 -1 6 4 5 6 6
public static void maxHeapMod(Elem[] e) {
int n = e.length - 1;
for (int i = n; i > 0; i--) {
int j = ((i + 1) / 2) - 1;
if (e[i].acc == e[j].acc) {
if (e[i].val > e[j].val) {
swap(e, i, j);
maxHeapMod(e);
} else if (e[i].val == e[j].val && e[i].index < e[j].index) {
swap(e, i, j);
maxHeapMod(e);
}
} else if (e[i].acc < e[j].acc) {
swap(e, i, j);
maxHeapMod(e);
}
}
}
public static void swap(Elem[] e, int i, int j) {
Elem t = e[i];
e[i] = e[j];
e[j] = t;
}
static class Elem {
int val;
int index;
int acc;
public Elem(int val, int index) {
this.val = val;
this.index = index;
}
}
}
Java Code O(logN)
public class FindMaxElementStateLess {
public static void main(String[] args) {
Elem[] e = new Elem[7];
e[0] = new Elem(0, 0);
e[1] = new Elem(-1, 1);
e[2] = new Elem(6, 2);
e[3] = new Elem(4, 3);
e[4] = new Elem(5, 4);
e[5] = new Elem(6, 5);
e[6] = new Elem(6, 6);
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
}
public static int getMaxIndex(Elem[] e) {
maxHeapMod(e);
e[0].acc += 1;
int index = e[0].index;
for (int i = 0; i < e.length; i++)
e[i].acc += 1;
swap(e, 0, e.length - 1);
return index;
}
//0 -1 6 4 5 6 6
public static void maxHeapMod(Elem[] e) {
int n = e.length - 1;
for (int i = n; i > 0; i--) {
int j = ((i + 1) / 2) - 1;
if (e[i].acc == e[j].acc) {
if (e[i].val > e[j].val) {
swap(e, i, j);
maxHeapMod(e);
} else if (e[i].val == e[j].val && e[i].index < e[j].index) {
swap(e, i, j);
maxHeapMod(e);
}
} else if (e[i].acc < e[j].acc) {
swap(e, i, j);
maxHeapMod(e);
}
}
}
public static void swap(Elem[] e, int i, int j) {
Elem t = e[i];
e[i] = e[j];
e[j] = t;
}
static class Elem {
int val;
int index;
int acc;
public Elem(int val, int index) {
this.val = val;
this.index = index;
}
}
}
public static void main(String[] args) {
Elem[] e = new Elem[7];
e[0] = new Elem(0, 0);
e[1] = new Elem(-1, 1);
e[2] = new Elem(6, 2);
e[3] = new Elem(4, 3);
e[4] = new Elem(5, 4);
e[5] = new Elem(6, 5);
e[6] = new Elem(6, 6);
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
System.out.println(getMaxIndex(e));
}
public static int getMaxIndex(Elem[] e) {
maxHeapMod(e);
e[0].acc += 1;
int index = e[0].index;
for (int i = 0; i < e.length; i++)
e[i].acc += 1;
swap(e, 0, e.length - 1);
return index;
}
//0 -1 6 4 5 6 6
public static void maxHeapMod(Elem[] e) {
int n = e.length - 1;
for (int i = n; i > 0; i--) {
int j = ((i + 1) / 2) - 1;
if (e[i].acc == e[j].acc) {
if (e[i].val > e[j].val) {
swap(e, i, j);
maxHeapMod(e);
} else if (e[i].val == e[j].val && e[i].index < e[j].index) {
swap(e, i, j);
maxHeapMod(e);
}
} else if (e[i].acc < e[j].acc) {
swap(e, i, j);
maxHeapMod(e);
}
}
}
public static void swap(Elem[] e, int i, int j) {
Elem t = e[i];
e[i] = e[j];
e[j] = t;
}
static class Elem {
int val;
int index;
int acc;
public Elem(int val, int index) {
this.val = val;
this.index = index;
}
}
If I'm reading the problem correctly and assuming we are allowed to modify the input array.
- Then we can simply find all max valued indices and -Infinity index( will only be one -Infinity)
- If no -Infinity index, set the first index in max-valued-indices to -Infinity and return that value
else cycle using the -Infinity max valued index
Wow, without memorize the last state or modify the input array and return the index of next max number. It sounds like a computer runs without memory or cache. I would like know how it works.
- jiahuang September 21, 2017