Как завершить это в O(1)

Я только что получил это от компании для теста на собеседование, и я с легкостью прошел его, но они сказали, что мои функции были в порядке (n). Вот вопросы

Напишите класс IntegerTracker с этими методами:

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.

Убедитесь, что каждый метод, включая трек, выполняется в постоянное время (O(1) сложность времени).

Вот как я это сделал

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

Может кто-нибудь показать мне, как я должен завершить это в O(1). Я уже потерял сознание из-за этого, так что не думайте, что вы даете мне ответ на интервью. Я не собираюсь там работать. Я просто хочу посмотреть, как я должен это выяснить, не перебирая массив.

Источник

2 ответа

Решение

Заставить функции работать в O(1) означает, что внутри них не может быть итерации. На самом деле нет никаких причин хранить цифры. Вам нужно только хранить статистику:

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

Добавлена ​​демонстрация mode расчет с использованием NSCountedSet, NSCountedSet может быть смоделирован с помощью словаря / карты на других языках (мы должны использовать структуру с O(1) операциями в среднем случае). Единственная хитрость - выполнить необходимые операции при добавлении.

Также обратите внимание, что в настоящее время функции не соответствуют соглашениям об именах Obj-C, и это также должно быть важно в интервью.

Источник

Я бы предположил, что вы должны написать trackInt: по-другому:

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

Таким образом, всякий раз, когда добавляется новый номер, вы можете легко вычислить max (и другие значения) в постоянном времени.

Настоящий max Затем метод выглядит так:

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

Логика инкрементальных вычислений для mode, avg и т. Д. Просто выглядит немного иначе, вам, вероятно, никогда не придется использовать numbers хотя массив, но, скорее всего, есть count и sum следить за.

За mode Вы можете держать словарь, который отображает number на счетчик, который отслеживает, как часто это число встречалось еще. Кроме того, вы сохраняете текущий счетчик числа, которое происходило чаще всего, maxNumberCount, Если вновь увеличенный счетчик больше сохраненного счетчика, у вас есть новый mode значение, текущий number хранить / возвращать и менять maxNumberCount соответственно.

Источник
Другие вопросы по тегам