Pergunta de entrevista da empresa Google

Find the max and second largest max in an array of integers. What is run time? How to test function?

Respostas da entrevista

Sigiloso

18 de ago. de 2011

very simple O(n) comparison.

Sigiloso

14 de mar. de 2017

void returnMaxes( int &array[]) { int max = 0, max2 = array[i], i = 0; while( i max) { max2 = max; max = array[i]; i++; } else if (array[i] > max2) { max2 = array[i]; i++; } else i++; } cout << "The two maxes in order are from greatest to least: \n << max <

Sigiloso

14 de mar. de 2017

Missing from my answer above corrections: - while( i max) Run time complexity is as the first poster stated, @ O(n) because it runs through the array only ones, "N" amount of times. We also save space by taking the array by reference, instead of creating a new value for the function in case of 2 things: 1. It's scaled to size. Since Google uses and focuses a lot on scalability, we need to worry about what happens if we're given a larger array from the get go. A million numbers perhaps? 2. Its performance will adequately not be affect TOO harshly at run time due to the reference variable if function is called multiple times. We can call this a "helper" function of sorts in another global context scope.

Sigiloso

14 de mar. de 2017

Okay. It won't let me post my corrections for some reason...but it's not a hard algorithm to figure out.