Country: Israel
Interview Type: Phone Interview

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

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.

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

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.

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

The signature is const std::Vector this implies that you CANT change the input array

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

@penchief: Do you have a answer/idea to this outside of using probability as Chris suggested.

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

Javascript
var arr = [2,3,4,5,19, -1]
return arr.indexOf(Math.max.apply(null, b))

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

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

}``````

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

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

}``````

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

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

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

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

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.