Беседа об алгоритмах


!!НАШ БЛОГ ПЕРЕЕХАЛ!!

Мы создали свой сайт! Все материалы, опубликованные в этом блоге, переехали туда.

Наш новый сайт maddevelop.ru


Первая задача

Условие

Дан массив целых неповторяющихся положительных чисел. Числа, соседние по числовой оси (при этом они могут находиться в разных частях массива), следует заключить в диапазон типа string, в котором указываются через тире начальное число диапазона и конечное. Необходимо получить строку, где в порядке возрастания указаны все диапазоны и/или отдельные цифры, в них не входящие.

Пример

Входной массив: { 3, 7, 5, 9, 4, 10 }

Ответ: "3 - 5, 7, 9 - 10"

Решение

// Массив преобразуется в строку "на лету". Сложность - O(n).
private static string ArrayToString(int[] array)
{
    Array.Sort(array);
    StringBuilder sb = new StringBuilder();
    int length = array.Length;
    if (length == 0)
        sb.Append("");
    else if (length == 1)
        sb.Append(array[0].ToString());
    else
    {
        bool defis = false;

        for (int i = 1; i < length; i++)
        {
            if (array[i] - array[i - 1] == 1)
            {
                // Если дефис не поставлен, а числа идут подряд, то пишу число и дефис.
                if (!defis)                                         
                {
                    sb.Append($"{array[i - 1].ToString()} - ");
                    defis = true;
                }
                continue;
            }

            // Если число идёт не подряд, то пишу предыдущее число и ставлю запятую.
            sb.Append($"{array[i - 1].ToString()}, ");      
        
            defis = false;
        }

        // Добавляю последнее число.
        sb.Append(array[length - 1].ToString());                    
    }
    return sb.ToString();
}

Конечно, сначала массив следует упорядочить и только потом пытаться получать выходную строку.

Решение следовало продемонстрировать на бумаге. А для этого необходимо сразу держать в голове все граничные случаи, такие как идущие подряд числа, все числа массива не лежат в диапазонах, последнее значение - отдельное и прочие. Учитывая их, я запутался и не смог решить задачу.

Товарищ предложил мне попробовать её сделать не "на лету", а через списки диапазонов. Такой способ действительно проще для реализации, хоть и увеличатся пространственная и временные сложности.

// Более длинный способ, сложность в худшем случае O(n*n).
private static string ArrayToStringLong(int[] array)
{
    Array.Sort(array);
    StringBuilder sb = new StringBuilder();
    int length = array.Length;
    if (length == 0)
        return "";
    else if (length == 1)
        return array[0].ToString();
    else
    {
        IList<List<int>> list = new List<List<int>>();          // Создаю список списков
        
        // Текущий список, описывающий диапазон.
        List<int> current = new List<int>() { array[0] };       
        for (int i = 1; i < length; i++)
        {                    
            if (array[i] - array[i - 1] == 1)
            {
                current.Add(array[i]);                        
                continue;
            }
            else
            {
                // Обязательно делать ToList(), так как List - ссылочный тип. 
                // Метод ToList() позволит передать список по значению.
                list.Add(current.ToList());                     
                current.Clear();
                current.Add(array[i]);
            }
        }
        list.Add(current.ToList());       // Последний диапазон добавляем в список списков.

        // Преобразую список диапазонов в выходную строку.
        for (int i = 0; i < list.Count; i++)
        {
            if (list[i].Count == 1)
                sb.Append($"{list[i].ElementAt(0).ToString()}, ");
            else
                sb.Append($"{list[i].ElementAt(0).ToString()} - 
                    {list[i].ElementAt(list[i].Count - 1).ToString()}, ");
        }

        string output = sb.ToString();
        return output.Remove(output.Length - 2, 2);
    }            
}

Вторая задача

Условие

Даны два массива целых неповторяющихся положительных чисел одинаковой длины. Создать третий массив такой, что его i-е значение, равняется количеству пар одинаковых чисел из значений от 0 до i первых двух массивов.

Пример

Первый массив: { 1, 2, 42, 8, 15 }

Второй массив: { 2, 5, 8, 7, 1 }

Выходной массив: { 0, 1, 1, 2, 3 }

Пояснение к получению выходного массива

0-й элемент
Первый массив: { 1 }
Второй массив: { 2 }
Числа различаются, поэтому выходной массив { 0 }.

1-й элемент
Первый массив: { 1, 2 }
Второй массив: { 2, 5 }
И в первом массиве, и во втором есть цифра 2, поэтому выходной массив { 0, 1 }.

2-й элемент
Первый массив: { 1, 2, 42 }
Второй массив: { 2, 5, 8 }
В массивах по-прежнему одинаковая цифра - 2, поэтому выходной массив { 0, 1, 1 }.

3-й элемент
Первый массив: { 1, 2, 42, 8 }
Второй массив: { 2, 5, 8, 7 }
Появляется ещё пара цифр 8, поэтому выходной массив { 0, 1, 1, 2 }.

4-й элемент
Первый массив: { 1, 2, 42, 8, 15 }
Второй массив: { 2, 5, 8, 7, 1 }
Цифра 1 есть также в обоих массивах, поэтому выходной массив { 0, 1, 1, 2, 3 }.

Решение

То, что следует использовать хеш-таблицу я придумал почти сразу. Ещё время ушло на догадку о второй хеш-таблицы.

public static int[] GetPairs(int[] first, int[] second)
{
    int length = first.Length;
    if (length == 0)
        return null;
    int[] output = new int[length];            
    HashSet<int> firstHash = new HashSet<int>();
    HashSet<int> secondHash = new HashSet<int>();

    if (first[0] == second[0])
        output[0] = 1;
    firstHash.Add(first[0]);
    secondHash.Add(second[0]);

    for (int i = 1; i < length; i++)
    {
        output[i] = output[i - 1];
        firstHash.Add(first[i]);
        secondHash.Add(second[i]);
    
        if (first[i] == second[i])
        {
            output[i] = ++output[i];
            continue;
        }

        if (secondHash.Contains(first[i]))
            output[i] = ++output[i];
        if (firstHash.Contains(second[i]))
            output[i] = ++output[i];
    }
    return output;
}

К сожалению, снова не смог подумать о таких случаях, как пара массивов { 1, 2 } - { 1, 2 } и { 1, 2 } - { 2, 1 }. Поэтому итоговый ответ получил после пары подсказок.

Вывод

Для успешного прохождения собеседований с алгоритмами достаточно набить руку на сайтах типа Leetcode и Codewars. Тогда при взгляде на задачу будет видеть��я верное решение с учётом всех граничных ситуаций. Я, правда, прорешал их небольшое количество из-за того, что посвятил своё время освоению некоторых технологий.