Тестовое задание C#.md

Дан List<uint> list и некое число ulong sum. Ожидаемое количество элементов в list - несколько миллионов. Необходимо написать метод FindElementsForSum, который сможет найти наименьшие индексы start и end такие, что сумма элементов list начиная с индекса start включительно и до индекса end не включительно будет в точности равна sum. Если таких start и end нельзя найти, то установить start и end равными 0. Решение предоставить в виде метода. Сигнаруту и название метода менять нельзя, только тело.

public void FindElementsForSum(List<uint> list, ulong sum, out int start, out int end)
{
	// your code here
}

Примеры:

FindElementsForSumTest(new List<uint> { 0, 1, 2, 3, 4, 5, 6, 7 }, 11, out start, out end); //start будет равен 5 и end 7;
FindElementsForSumTest(new List<uint> { 4, 5, 6, 7 }, 18, out start, out end); //start будет равен 1 и end 4;
FindElementsForSumTest(new List<uint> { 0, 1, 2, 3, 4, 5, 6, 7 }, 88, out start, out end); //start будет равен 0 и end 0;

Кроме самой функции нужно придумать и написать несколько примеров (тестов) чтобы убедиться что ваша реализация работает хорошо и правильно.

Здравствуйте, у меня возник вопрос: не должен ли второй пример выводить 0 и 0?
Исходя из условия и первого примера, элемент индекса end не включается в сумму, таким образом, чтобы результатом был 1 и 4, в списке должно быть пять элементов.

Нет, потому что диапазон ответа [start, end)

Посмотрите внимательнее на первый пример, в нём диапазон [5, 7) => 5 + 6 = 11

Ответ второго примера получен по той же логике

Понял, спасибо за ответ!

Но ведь во втором случае { 4, 5, 6, 7 } всего 4 значения, соответственно индексы от 0 до 3. Что есть индекс 4?

Здравствуйте, у меня возник вопрос: какое примерное время выполнения считать успехом?
В моем случае получилось:
10 миллионов - примерно 45 миллисекунд;
3 миллиона - примерно 15 миллисекунд.

Здравствуйте. Являются ли элементы в листе упорядоченными? потому что в примерах именно такие числа.

@nokosimova Нет, порядок элементов может быть любым, сортированность списка не заявлена, просто в примерах так получилось.

@asmcodersource Тот факт что у вас 10 миллионов выполняются в три раза медленнее чем 3 миллиона уже говорит о правильном решении задачи (если конечно результаты корректны и сравниваются результаты когда искомого подмассива нет). Понятно что если искомый массив находится в начале скорость будет значительно выше.
Моя реализация на миллионе, в случае когда искомой суммы не находится, т.е. требуется перебор всего массива, затрачивает 27 миллисекунд на i5-9600K@4.5 GHz

@Busyrev спасибо за выложенное задание! Буду вам признателен, если найдёте время взглянуть на моё решение

В результате будет, видимо, некоторое количество подсписков, отвечающих условию. Из них надо будет выбрать один.
Но что значит 'наименьшие индексы'?

1. В буквальном смысле ('наименьшие индексы', т.е. ближайшие к 0), т.е. первый же подсписок, отвечающий условию.
2. Сравниваются значения, стоящие на крайних значениях подсписка - start и end. А если один '>', другой '<'?
3. Подсписок с наименьшей длиной. Может быть несколько таких, какой тогда возвращать?
4. Другой вариант.