Как изменится среднее арифметическое при замене последнего элемента на большее значение

Что проверяют

Умеете ли вы посчитать изменение без пересчёта всего массива и видите ли, что задача на самом деле про сумму, а не про среднее. Следом почти всегда просят написать это за O(1) и спрашивают про целочисленное деление и переполнение в C#.

Как отвечать

Среднее это сумма, делённая на количество: avg = S / n. При замене последнего элемента a[n-1] на x количество не меняется, меняется только сумма: S' = S - a[n-1] + x. Отсюда всё остальное:

• формула изменения: Δ = (x - a[n-1]) / n. Если x > a[n-1], среднее растёт ровно на эту величину, и чем длиннее массив, тем слабее эффект одной замены;
• пример: у [2, 4, 6, 8] среднее 5, замена 8 на 10 даёт Δ = 2 / 4 = 0.5, новое среднее 5.5. Пересчитывать сумму заново не нужно;
• O(1) на поток замен: храните текущую сумму и сдвигайте её на разницу старого и нового значения. Тогда каждый запрос среднего стоит константу вместо прохода за O(n);
• типы: int / int в C# отбрасывает дробную часть, 22 / 4 даст 5. Делите в double или decimal: (double)sum / n;
• переполнение: сумму большого массива int храните в long. По умолчанию арифметика в C# не проверяется, и переполнение молча превращает сумму в отрицательное число, если не включить checked.

Стоит добавить про LINQ: Enumerable.Average() удобен, но каждый вызов проходит всю коллекцию, поэтому при частых заменах инкрементальная сумма выигрывает. Если разговор уйдёт в дисперсию, скажите, что её тоже можно обновлять без полного прохода, если хранить ещё и сумму квадратов.

Где спотыкаются

Пересчитывают среднее полным циклом по массиву, хотя интервьюер ждёт формулу через разницу старого и нового значения.

Пишут sum / n на целых, получают 5 вместо 5.5 и потом ищут ошибку в логике, а не в типах.

Забывают про пустой массив. Для int это DivideByZeroException, для double результат NaN, а Average() на пустой последовательности бросает InvalidOperationException.