How to complete this in O(1)

Question

I just got this from a company for a interview test and I completed it with ease but they said that my functions were in o(n). Heres the questions

Write a class IntegerTracker with these methods:

track(int) - Receives an integer for tracking. 
get_max() - Returns the max (int) of all integers seen so far. 
get_min() - Returns the min (int) of all integers seen so far. 
get_mean() - Returns the mean (float) of all integers seen so far.
get_mode() - Returns the mode (int) of all integers seen so far.

Ensure each method, including track, runs in constant time (O(1) time complexity).

This is how I completed it

- (instancetype)init{
    if(self == [super init]){
        self.numbers = [[NSMutableArray alloc]init];
    }
    return self;
}

- (void)trackInt:(int)number{
    [self.numbers addObject:[NSNumber numberWithInt:number]];
}

- (int)getMax{

    NSNumber *max = [self.numbers valueForKeyPath:@"@max.self"];
    return [max intValue];
}

- (int)getMin{

    NSNumber *min = [self.numbers valueForKeyPath:@"@min.self"];
    return [min intValue];
}

- (float)getMean{
    NSNumber *average = [self.numbers valueForKeyPath:@"@avg.self"];
    return [average floatValue];
}
- (int)getMode{

    int maxCount = 0;
    int value = 0;
    NSMutableDictionary *mode = [[NSMutableDictionary alloc]init];
    for(NSNumber *n in self.numbers){
        int currentCount = [[mode objectForKey:n.stringValue]intValue];
        currentCount++;
        [mode setObject:@(currentCount) forKey:n.stringValue];
        if(maxCount < currentCount){
            maxCount = currentCount;
            value = [n intValue];
        }
    }

    return value;
}

Can someone show me how I am supposed to complete this in O(1). I already got passed up cause of this so don't think your giving me an answer for the interview. I'm not going to work there. I just want to see how i'm supposed to figure this out without iterating through the array.

Answer 1

I would assume you have to write trackInt: in a different way:

- (void)trackInt:(int)number{
    if (number > self.max) {
        self.max = number;
    }
    // different logic for the other desired outcomes
}

That way whenever a new number is added you a simple calculation for determining the max (and the other values) in constant time.

The actual max method then looks like:

- (int) getMax { return self.max; }

The logic for incremental calculation for mode, avg, etc. simply looks a bit different, you will probably never have to use the numbers array though, but more likely have a count and a sum to keep track of.

For mode you can keep a dictionary that maps number onto a counter that keeps track of how often that number has occurred yet. Additionally you store the current count of number that has occurred the most times, maxNumberCount. If the newly incremented counter is bigger than that stored counter you have a new mode value, the current number to store / return and change maxNumberCount accordingly.

Answer 2

To make the functions work in O(1) means that there cannot be any iteration inside them. There is actually no reason to actually store the numbers. You need only to store the statistics:

@property (nonatomic) NSInteger min;
@property (nonatomic) NSInteger max;
@property (nonatomic) NSInteger sum;
@property (nonatomic) NSInteger count;

@property (nonatomic) NSCountedSet *numberCounts; // must be initialized in `init`
@property (nonatomic) NSInteger mostFrequentNumber;

- (void)track:(NSInteger)number {
   if (self.count == 0) { 
      self.min = number;
      self.max = number;
      self.sum = number;
      self.count = 1;
      [self.numberCounts addObject:@(number)];
      self.mostFrequentNumber = number;
   } else {
      self.min = MIN(number, self.min);
      self.max = MAX(number, self.max);
      self.sum += number;
      self.count += 1;
      [self.numberCounts addObject:@(number)];
      if ([self.numberCounts countForObject:@(number)] > [self.numberCounts countForObject:@(self.mostFrequentNumber)] {
         self.mostFrequentNumber = number;
      }
   }
}

- (float)getMean {
   if (self.count == 0) { // protection against dividing by zero!
     return 0;
   }

   return ((float) self.sum) / self.count;
}

- (NSInteger)getMode {
   return self.mostFrequentNumber;
}

Added a demonstration of mode calculation using NSCountedSet. NSCountedSet can be simulated using a dictionary/map in other languages (we have to use a structure with O(1) operations in an average case). The only trick is to perform the necessary operations when adding.

Also note that currently the functions don't follow Obj-C naming conventions and that should be important in an interview, too.