1

I was recently in an interview and the interviewer asked me the following question:

Given an unsorted array, how do you calculate the mode in O(N)?

I answered along the lines of using a hashmap, O(N) loop through array and O(1) lookups.

Then he said

If you had to use constant memory but were allowed more processor time, how would you do it?

I answered 'sort the array and find the longest run, runtime = O(nlgn)

The next question he asked fucked me up..

If you had to use constant memory and linear time how would you do it?

I didn't know how to answer this and he left this for me as an exercise for later. It's been days and I still dunno how to do it.

Can anyone know how to do?>

Thomas Ahle
  • 30,774
  • 21
  • 92
  • 114
  • How can you sort an array in constant memory? Constant memory means the items can't be moved. You either have to make a copy and sort the copy or use an array of pointers and sort the array of pointers by their target values. – Thomas Matthews Nov 15 '14 at 20:19
  • 1
    +1 for the f word sorry had to be :-) – markus Nov 15 '14 at 21:45
  • @ThomasMatthews When one says that a sort algorithm use a constant amount of memory, it means that the algorithm introduces a constant memory overhead, but obviously storing the array is O(n). That said, how do you compare the quick sort and the merge sort ? Is is well known that the quick sort uses O(1) memory and the merge sort O(n), so sorting an array using O(1) memory (with the relevant definition) is definitely possible – Dici Nov 15 '14 at 23:23
  • Unfortunately this probably can't be done unless the size of the universe (maximum int size) is considered constant. If it is, you can use the solution given here: http://stackoverflow.com/questions/11781720/most-common-element-in-an-array-finding-the-relative-majority-deterministical# – Thomas Ahle Nov 15 '14 at 23:32
  • @Dici: The requirements said `constant memory`, which I understand is read-only memory or values in memory that cannot be changed. – Thomas Matthews Nov 16 '14 at 01:21
  • @ThomasMatthews Constant means that it does not depend on the size of the array, namely O(1). Quick sort matches this condition because it only perfoms swap operations. – Dici Nov 16 '14 at 01:26
  • @Dici: What's the difference between `constant memory` and `constant time`? – Thomas Matthews Nov 16 '14 at 01:31
  • @ThomasMatthews Constant memory means that the data the algorithm needs to store does not depend on the size of the input. Constant time means the number of elementary operations (it can be method calls, additions, etc) performed by the algorithm does not depend on the size of the input – Dici Nov 16 '14 at 01:39

1 Answers1

0

If the numbers are within a reasonable range, you calculate the mode linearly by using an array that has the size of the range of values.

The value in the array would be the index into the mode array. Increment the value. Keep two other variables that are the greatest frequency and the index of the value that has the greatest frequency.

#include <stdio>

int main(void)
{
  unsigned int frequencies[11] = {0}; // Assume range 1..10, inclusive.
  const unsigned int values[] =
    {1, 8, 4, 8, 7, 3, 2, 8, 5};
  const unsigned int value_quantity =  
    sizeof(values) / sizeof(values[0]);
  unsigned int greatest_frequency = 0;
  unsigned int value_of_greatest_frequency = 0;

  for (unsigned int i = 0; i < value_quantity; ++i)
  {
    // Calculate new frequency.
    const unsigned int frequency_index = values[i];
    ++frequencies[frequency_index];

    // Update "running" variables
    if (frequencies[frequency_index] > greatest_frequency)
    {
      greatest_frequency = frequencies[frequency_index];
      value_of_greatest_frequency = frequency_index;
    }
  }
  std::cout << "Mode is " << value_of_greatest_frequency
            << ", with frequency of " << greatest_frequency
            << "\n";
  return 0;
}

One pass, many variables. This will only work if the range of values is reasonable.

Another suggestion is to use std::map</*value*/, /*frequency*/>.

This algorithm is not constant time, but O(N) or less.

Thomas Matthews
  • 56,849
  • 17
  • 98
  • 154