День пятьсот двадцать восьмой. #Оффтоп #ЗадачиНаСобеседовании
В чате просили ещё задачек. Вот вам на выходные)))

Дан массив целых положительных чисел, представляющих цену акции в разные дни (каждый элемент массива представляет день). Также дано целое число k, которое представляет количество сделок, которые вам разрешено совершить. Одна сделка состоит из покупки акции в определённый день и продажи в более поздний день (ВНИМАНИЕ: 1 сделка = 2 транзакции: покупка и продажа).
Найдите максимальную прибыль, которую вы можете получить, покупая и продавая акции, используя максимум k сделок.
Обратите внимание, что в определённый момент вы можете держать только одну акцию. То есть вы не можете купить более одной акции, и не можете купить акцию, если она у вас уже есть. Кроме того, не обязательно использовать все k сделок. Также допустим, что бюджет на покупку не ограничен.

Например,
prices = [5, 11, 3, 50, 60, 90]
k = 2
Результат: 93
//Покупка: 5, продажа: 11 (+6); покупка: 3, продажа: 90 (+87)

prices = [12, 14, 17, 10, 14, 13, 12, 15]
k = 3
Результат: 12

prices = [100, 30, 15, 10, 8, 25, 80]
k = 3
Результат: 72
//Только одна сделка

Усложнённый вариант: Написать решение со сложностью O(n*k) по времени и O(n) по памяти.

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

Источник: https://www.algoexpert.io/

День пятьсот тридцатый. #Оффтоп #ЗадачиНаСобеседовании
Ответ на задачу

Сначала попробуем решить задачу вручную. Создадим таблицу profits. В столбцах будут дни (day), как в исходном массиве, в строках – сделки (t) от 0 до k. Значениями массива будет максимальная возможная прибыль, полученная от каждой сделки в определённый день. Например:

Цены: 5 11  3 50 60 90

Если доступно 0 сделок, то и прибыль будет 0:

t=0 : 0  0  0  0  0  0

Если доступна 1 сделка, ищем максимальную прибыль от единственной сделки (прибыль в 1й день всегда 0):

t=1 : 0  6  6 47 57 87

Продажа во второй день даёт прибыль 6. Продажа в 3й день не даёт прибыли, поэтому максимум остаётся 6. Покупка в 3й день и продажа в 4й даёт прибыль 47 (больше 6, и больше покупки в 1й день по 5, поэтому максимум 47). Аналогично в 5й и 6й день максимальная прибыль будет 57 и 87 соответственно.
Теперь рассмотрим для 2х сделок. Первые 3 дня изменений не принесут. 1 сделка, прибыль 6:

t=2 : 0  6  6

В 4й день мы можем закрыть вторую сделку, получить прибыль 47 и сложить её с прибылью от первой сделки:

t=2 : 0  6  6 53

В 5й день нам нужно определить, принесёт ли продажа больше прибыли, чем уже есть. Прибыль от второй сделки принесёт 57, общая прибыль будет 63:

t=2 : 0  6  6 53 63

Продажа в 6й день даст нам прибыль в 87 (итого 93), что больше, чем текущий максимум 63:

t=2 : 0  6  6 53 63 93

Таким образом, можно заметить закономерность. Прибыль в определённый день для текущей сделки (profit[t,day]) будет рассчитываться как максимум между:
1) Прибылью за предыдущий день (profit[t,day-1]), если мы не продаём.
2) Если мы продаём, то нужно сложить цену за текущий день (prices[day]) с максимально выгодной покупкой в предыдущие дни. То есть за каждый предыдущий день x нам нужно найти разницу между прибылью от предыдущей(-их) сделки(-ок) в этот день (profit[t-1,x]) и покупкой в этот день (prices[x]). Максимум этой разницы за предыдущие дни и будет наиболее выгодной покупкой. Для второй сделки выгода по дням будет:
x=1: 0–5=-5 (прибыль 0 минус покупка за 5).
x=2: 6-11=-5 (прибыль от 1й сделки 6 минус покупка за 11).
x=3: 6-3=3 (прибыль от 1й сделки 6 минус покупка за 3).
x=4: 47-50=-3 (максимальная прибыль от 1й сделки 47 минус покупка за 50).
x=5: 57-60=-3 (максимальная прибыль от 1й сделки 57 минус покупка за 60).
Таким образом, для 2й сделки в 6й день выгоднее всего купить в 3й день. Получим: цена в 6й день 90 + максимальная выгода от предыдущей сделки 3 = 93, что больше, чем прибыль за предыдущий день 63.

Ответом будет прибыль от последней сделки за последний день.

Сложность по времени: обход n дней k раз - O(n*k) и расчёт максимальной выгоды в каждом случае O(n) – итого O(n^2*k).
Сложность по объёму: двумерный массив – O(n*k).

Оптимизации:
1) Мы можем рассчитывать максимальную выгоду по дням по мере заполнения таблицы прибылей, чтобы исключить дополнительный вложенный цикл. Таким образом, сложность по времени будет O(n*k).
2) Если внимательно посмотреть на алгоритм, нам не нужно хранить все k+1 рядов прибыли. Для расчёта каждого следующего ряда нам нужны данные только предыдущего. Тогда, таблицу можно сократить до двух рядов, соответственно сложность по объёму памяти будет O(n).

Полный код на C#

Более подробное объяснение решения на английском

Источник: https://www.algoexpert.io/

День пятьсот шестьдесят шестой. #ЗадачиНаСобеседовании
Топ 10 Умений Которые Понадобятся на Собеседовании
На собеседовании вам могут как задать самые разные вопросы по теории, так и дать практическое задание. Некоторые из них я уже приводил на канале: 1, 2, 3, 4.
Заучить их все просто нереально. Но большинство из них тестирует одно из следующих базовых умений, которым должен обладать каждый «уважающий себя» программист.

1. Двоичный (бинарный) поиск — классический алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины. Используется не только в элементарном нахождении элемента в отсортированном массиве. Он встречается настолько часто, что может быть скрыт даже в задании не на кодирование. К примеру, нужно найти в логах git версию, где в приложении допущена ошибка.

2. Умение строить структуры данных. Практически во всех задачах требуется правильная инкапсуляция данных. Особенно это относится к ООП. Иногда сложность задачи даже не столько в алгоритме, сколько в построении правильной структуры или класса. Поэтому без умения создавать лаконичные и непротиворечивые структуры данных никуда.

3. Рекурсия. Несмотря на то, что рекурсия – тема множества мемов и шуточек про программистов, в реальности она встречается довольно редко (а в таких мемах – почти никогда). Есть хорошее выражение: «Существует несколько задач, которые красиво и эффективно решаются рекурсией. Есть множество задач, которые красиво, но неэффективно решаются рекурсией. Подавляющее большинство задач решать рекурсией и некрасиво, и неэффективно». Тем не менее, знать принципы рекурсивного решения очень полезно. Пример: решение судоку.

4. Основы сортировки. Это не значит, что вам нужно заучить алгоритмы сортировки слиянием или быстрой сортировки. Но важно понимать общие принципы работы, почему сортировка слиянием быстрее сортировки пузырьком, время работы в O-нотации, уметь использовать факт, что коллекция уже отсортирована и т.п.

5. Разворачивание связанного списка. Вариантами задачи могут быть нахождение дубликатов в списке или определение, является ли связанный список зацикленным. Кроме того, важно правильно создать структуру элемента списка (данные и указатель).

6. Манипулирование несколькими переменными/указателями одновременно. Канонический пример: разворот строки, определение, является ли строка палиндромом, нахождение самого длинного палиндрома в тексте, - движение указателей в обе стороны, либо с разной скоростью.

7. Использование Хеш-таблиц (или множеств). Здесь вариантами могут быть задачи на оптимальное нахождение парного числа в массиве, задачи на обход графа с сохранением пути, мемоизация в рекурсии и т.п.

8. Нахождение закрывающей скобки. Вариантами могут быть проверка, все ли скобки закрыты в строке, либо нахождение, сколько скобок нужно добавить. Кандидат для использования стека. Добавляем открывающие скобки в стек, при нахождении закрывающей скобки – удаляем элемент из стека.

9. Поиск в глубину (Depth-first search) — один из методов обхода графа, который состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Можно реализовать с помощью стека и рекурсии. Для заданной вершины добавляем всех её потомков в стек, далее извлекаем первый элемент стека и повторяем процедуру для него рекурсивно.

10. Поиск в ширину (Breadth-first search) — обход всех ребер для «открытия» всех вершин, достижимых из заданной вершины. Можно реализовать с помощью очереди. Для заданной вершины добавляем всех её потомков в очередь. Далее, проходя по очереди добавляем всех потомков каждого элемента в конец очереди.

Источники:
- https://www.youtube.com/watch?v=r1MXwyiGi_U
- https://youtu.be/zHczhZn-z30

День пятьсот семьдесят седьмой. #Оффтоп #ЗадачиНаСобеседовании
В пандан ко вчерашнему посту про простоту и понятность решений, сегодня задачка на выходные.

Прямоугольная любовь
Команда учёных-любителей создала новый сайт знакомств. Отличительной особенностью его является инновационный способ представления профилей людей в виде прямоугольников на плоскости. Чем больше пересечение прямоугольников, тем больше у них шансов на успешные отношения.
Команде нужна помощь в написании алгоритма, находящего пересечение прямоугольников. Как показано на картинке ниже, стороны прямоугольников параллельны осям x и y.

Метод должен получать на вход 2 объекта класса Rectangle, имеющего свойства:
- координаты левой нижней точки
- длина
- ширина
На выходе должен получаться такой же объект Rectangle, представляющий собой пересечение.

Особенность этой задачи не в оптимизации по времени или памяти, а в получении результата, который работает, а главное легко читается. Многие могут описать решение на высоком уровне, но спотыкаются, когда вникают в детали. Поэтому:
1. Продумайте и нарисуйте все возможные варианты.
2. Используйте конкретные и информативные имена переменных.

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

День пятьсот семьдесят девятый. #Оффтоп #ЗадачиНаСобеседовании
Ответ на субботнюю задачу

Задача не очень сложная, главное грамотно разбить её на части.
Мы можем рассматривать «горизонтальное» пересечение прямоугольников (по оси x) отдельно от пересечения «по вертикали» (по оси y). Например, мы рассмотрим ширину прямоугольников как отрезки на одномерной числовой прямой x. Какие возможные случаи расположения этих отрезков?
1) Пересекаются частично
2) Один отрезок полностью содержится в другом
3) Не пересекаются
4) "Касаются" в одной точке
См. рисунок ниже.

Если рассматривать первые два варианта, можно заметить, что пересечение отрезков всегда начинается в точке старта с бОльшей координатой. Поэтому чтобы найти начало пересечения, выбираем максимум из значений S1 и S2. Аналогично конец пересечения будет в меньшей из точек E1 и E2.
Таким образом, найдя начало и конец отрезка, нам остаётся только узнать его длину. Если она положительная (конечная точка больше начальной), то пересечение есть, отрицательная – отрезки не пересекаются, нулевая – отрезки касаются.

static Segment Overlap(Segment s1, Segment s2)
{
  // начальная точка (максимальная из начальных)
  double start = Math.Max(s1.StartPoint, s2.StartPoint);
  // конечная точка (минимальная из конечных)
  double end = Math.Min(s1.StartPoint + s1.Length, s2.StartPoint + s2.Length);

  // отрезки не пересекаются
  if (start > end)
    return null;

  return new Segment(start, end - start);
}

В результате мы найдём отрезки пересечения по оси x и по оси y. Всё, что нам остаётся сделать – это совместить их. Начальные точки отрезков будут координатами левой нижней точки прямоугольника пересечения, длина отрезка по оси x будет шириной, а длина отрезка по оси y – высотой.

Замечание: в зависимости от условий задачи надо рассмотреть, допустимы ли варианты нулевых ширины и высоты (когда прямоугольники касаются сторонами, либо касаются в одной точке).

public static Rectangle RectangularOverlap(Rectangle r1, Rectangle r2)
{
  // пересечение по оси x
  Segment xOverlap = Overlap(
    new Segment(r1.StartPoint.X, r1.Width),
    new Segment(r2.StartPoint.X, r2.Width));
  // пересечение по оси у
  Segment yOverlap = Overlap(
    new Segment(r1.StartPoint.Y, r1.Height),
    new Segment(r2.StartPoint.Y, r2.Height));

  if (xOverlap?.Length >= 0 && yOverlap?.Length >= 0)
    return new Rectangle(
        new Point(xOverlap.StartPoint, yOverlap.StartPoint),
          xOverlap.Length,
          yOverlap.Length
        );

  // не пересекаются
  return null;
}

PS: я в коде использовал новый тип записи. Вот весь код объявления:

public record Point(double X, double Y);
public record Segment(double StartPoint, double Length);
public record Rectangle(Point StartPoint, double Width, double Height);

Можно использовать класс или структуру, но их описание со свойствами и конструкторами гораздо длиннее)))
PPS: да, в коде не хватает валидации исходных данных.
PPPS: строго говоря, решение можно слегка оптимизировать, не проверяя пересечение по y, если нет пересечения по x.

Источник: https://www.interviewcake.com/question/csharp/rectangular-love

День пятьсот девяносто восьмой. #Оффтоп #ЗадачиНаСобеседовании
Как насчёт задачки на выходные?)))
Думаю, большинство застало кнопочные телефоны с буками. А олды ещё помнят, что буквы были и на стационарных телефонах, особенно импортных (см. картинку).
На самом деле это довольно популярная система в основном в США для запоминания «красивых» корпоративных номеров. Номеров типа 8-800-700-8000 (кстати, это техподдержка Билайна, не спрашивайте, почему я его помню) на всех не хватит. Тогда придумали расположить алфавит на кнопках, и клиент должен был просто нажимать кнопки, соответствующие буквам. Например:
1-800-flowers означало номер 1-800-3569377
Сам номер «некрасивый», а слово легко запомнить.

Итак, к задаче. Дан номер телефона, например 3662277 и список слов, например ["foo", "bar", "baz", "foobar", "cap", "car", "cat"].
Нужно определить, какие слова из списка содержатся в номере телефона. Номер телефона может быть разной длины, но в разумных пределах. Слова должны содержаться целиком как подстроки.

День шестьсот первый. #Оффтоп #ЗадачиНаСобеседовании
Ответ на задачу про телефонные номера

На первый взгляд, всё довольно просто. Сначала для удобства представим все слова в виде соответствующих цифр. Таким образом, вместо
["foo", "bar", "baz", "foobar", "cap", "car", "cat"]
у нас получится
["366", "227", "229", "366227", "227", "227", "228"]
Это можно сделать, например, через функцию маппинга. Составим массив из 26 цифр, соответствующих каждой букве на кнопке:

int[] map = {2,2,2,3,3,3,4,4,4,…};

Затем в цикле проходим по буквам в слове, ищем соответствующую цифру и добавляем в результирующий массив:

int[] res = new int[word.Length];
for (int i = 0; i < res.Length; i++)
  res[i] = map[word[i] - 'a'];

Дальше интереснее.

Простой вариант
Для каждой цифры номера телефона составим древовидную структуру из цифр, где корень – текущая цифра телефона, а потомки – все цифры после неё. Таким образом, для числа из задачи 3662277 у нас получится нечто подобное:

3-6-6-2-2-7-7
6-6-2-2-7-7
6-2-2-7-7
2-2-7-7
2-7-7
7-7

Одинаковые корни объединим. То есть, например, у корня 2 будет 2 ветки, начинающиеся на 2 и 7:

2-2-7-7
 \
  7-7

Теперь для каждого слова мы будем по порядку его символов (цифр) проходить по этому дереву и искать, есть ли узлы со значением текущего символа слова. Например, для "bar" => 227:
- Корень – 2 – есть,
- Дочерний узел – 2 (2-2) – есть,
- Дочерний узел – 7 (2-2-7) – есть,
- Слово закончилось, значит это слово содержится в исходном номере.

Для "map" => 627:
- Корень – 6 – есть,
- Дочерний узел – 2 (6-2) – есть,
- Дочерний узел – 7 (6-2-7) – нет, значит такого слова нет.

Вариант "посложнее"
Как вы понимаете, этот алгоритм не слишком эффективный. Хотя, для цифр это ещё куда ни шло, а представьте размер дерева из всех возможных символов. Для таких случаев в 1975 году изобретён алгоритм Ахо—Корасик. Суть его в том, что дерево строится не на основе исходной строки, а специальным образом на основе искомых строк с прямыми и обратными ссылками на узлы. Если интересно и хочется поломать голову, можете почитать о нём. Алгоритм позволяет производить поиск подстрок за линейное время.

«Кандидат» на видео (ссылка ниже) о нём знал (не зря работает в Facebook), и ему даже приходилось его реализовывать. Но не пугайтесь, от вас на собеседовании этого вряд ли потребуют))).

Источник: https://www.youtube.com/watch?v=PIeiiceWe_w

День шестьсот пятьдесят четвёртый. #Оффтоп
Отвлечёмся ненадолго от жизненного цикла запроса в ASP.NET Core. Вчера в нашем чате завязалась дискуссия про базы данных, прелести и недостатки SQL и хранимых процедур. Вот решил вам на выходные дать задачку из собственной практики. Можно рассматривать её как из цикла #ЗадачиНаСобеседовании.

Допустим, у нас есть интернет-магазин (или любой аналогичный каталог товаров и их производителей/поставщиков, скажем, Алиэкспресс). Количество товаров очень большое. Пользователь ищет товар по названию или по категории, и ему выдаётся некоторый набор товаров с их характеристиками и производителем/поставщиком. Предположим для простоты, что из-за большого количества товаров, вся информация в рамках одного поискового запроса собирается в хранимой процедуре и кэшируется во временную таблицу в БД. То есть, если пользователь изменил сортировку или фильтры в текущем поиске, нам не нужно каждый раз извлекать данные из нескольких таблиц, все они уже кэшированы.

Пользователю нужно выдать только определённое количество результатов (разбив на страницы или просто выдавать только ТопХХХ). Пользователь может сортировать результаты (по цене, релевантности, рейтингу и т.п.), применять фильтры или переходить по страницам. Все эти запросы в рамках одного поискового запроса идут к временной таблице, которая создана ранее.

Теперь собственно задача. Производители хотят знать, сколько раз, по каким поисковым запросам и с какими товарами они появлялись на страницах сайта. То есть, если был запрос на «смартфон», который вернул 20000 результатов во временную таблицу, пользователю из них показали 1000 на первой странице и 1000 на второй, а дальше он смотреть не стал. Нам нужно сохранить для статистики данные только тех производителей, которые реально были показаны пользователю (попали в 2000 из 20000). (Да, я специально взял большие числа, а не стандартные 10 на страницу, потому что с 10 товарами решение вполне очевидно и не затратно).

Вопрос: как вы это реализуете? Оцените преимущества и недостатки каждого варианта.

Поскольку я сам с этим столкнулся, мне будет очень интересно узнать ваши версии в комментариях. Как такового правильного ответа тут, наверное, нет.

Жду ваших комментариев. Свою реализацию тоже опишу в комментариях позже.

День семьсот первый. #Оффтоп
5 обязательных навыков для разработчиков 2021. Окончание
Начало
3. Будьте «нанимаемым»
Компании хотят знать гораздо больше, чем просто о ваших навыках программирования. Они хотят видеть ваши достижения и подтверждения вашей квалификации, а также хотят убедиться, что у вас есть необходимые навыки хорошего работника.
- Задавайте профессиональные вопросы
Вам нужно научиться задавать профессиональные вопросы. Как на собеседовании, так и просто в разговоре с коллегами. Это скажет вашим работодателям о том, что вы обладаете обширными знаниями в своей области.

- Очистите свои социальные сети
Это может показаться паранойей, и вообще, это ваша личная жизнь. Но всё больше кадровиков ищут информацию о кандидатах в Интернете перед принятием решения о приёме на работу (иногда даже перед собеседованием). И довольно часто кандидаты отсеиваются уже на этом этапе. Поищите себя в сети и посмотрите, какие результаты вы получите. Вы бы приняли себя на работу?

- Обновите своё резюме
Убедитесь, что ваше резюме всегда отражает самую последнюю информацию, а также не содержит неактуальной или вводящей в заблуждение информации.

4. Навыки коммуникации
Ещё один отличный навык, который вам стоит освоить, - это создание социальных связей, знакомств, сотрудничество с коллегами в компании или в вашей сфере специализации. Никто не является кладезем знаний. Нужно сотрудничать с людьми, чтобы вы могли получать помощь, вместе работать над проектами и обмениваться навыками. Быть самым умным парнем с лучшими навыками тайм-менеджмента и знанием всех технических деталей - это хорошо, но рано или поздно найдётся проблема, которая даже вам окажется не под силу. Именно тут помогут сотрудничество и связи. Вы легко сможете найти решение при помощи других специалистов в этой области.

5. Навыки программирования
Как бы банально это ни звучало, будьте профессионалом в том, что вы делаете. Чтобы хорошо программировать, нужно много терпения, времени и постоянная практика. Практикуйте задачи на алгоритмы и частые задачи с собеседований (см. #ЗадачиНаСобеседовании), чтобы тренировать навыки решения задач, а также просматривайте частые вопросы на собеседовании (см. #ВопросыНаСобеседовании), чтобы не забывать теорию. Вы должны отлично владеть хотя бы одним языком программирования, что облегчит для вас изучение других языков.

Какими ещё важными навыками должен, по-вашему, обладать современный программист? Пишите в комментариях. И с наступающим всех!

Источник: https://medium.com/backenders-club/5-must-have-skills-for-developers-2021-e64d91f273cc
Автор оригинала – Solomon Eseme

День семьсот пятьдесят пятый. #Оффтоп #ЗадачиНаСобеседовании
В сегодняшний праздничный день у меня для вас сразу 2 видео. Наш старый знакомый Nick Chapsas выпустил одно из самых полезных, на мой взгляд, своих видео (в двух частях). Это одна из задач, которые вам могут дать на собеседовании. Она несколько отличается от рассмотренных нами ранее (предыдущие примеры см. по хештегу #ЗадачиНаСобеседовании).

Суть в том, что вам даётся небольшой «легаси» проект, и ваша задача – отрефакторить код, применяя все принципы, которые вы знаете: DRY, KISS, YAGNI, SOLID, вотэтовсё. Также есть ограничения. Например, вам нельзя никак изменять класс Program.cs (возможно и ещё какие-то). Кроме того, вы должны помнить, что класс является частью более крупного проекта, то есть нельзя бездумно менять открытый интерфейс класса. У вас есть обычно два часа. Можно дольше, если обоснуете, зачем вам дополнительное время. В общем, задачка показалась мне очень интересной.

Ещё интереснее было бы, конечно, взять исходный код, попытаться отрефакторить самому, а потом сравнить с тем, что получилось у Ника. Но Ник, как истинный англосакс, даёт исходники только патреонам за денюжку. Влепите ему диз за это)))

Как бы то ни было, просто посмотреть его решение тоже довольно познавательно. Так что выделите час праздничного дня, не пожалеете!
Часть 1: https://youtu.be/U3QvTaw224o
Часть 2: https://youtu.be/Yd4GnWeEkIY

День семьсот пятьдесят седьмой. #Оффтоп #ЗадачиНаСобеседовании
Что я Узнал о C# из Собеседований. Начало
Недавно я прошел серию собеседований в нескольких крупнейших технологических компаниях. Процессы собеседований в них сильно отличались, но у них также было много общего, например, упор на задачи на написание кода. Сортировка, нахождение всех возможных комбинаций или нахождение выхода из лабиринта. Я не знаю, как это связано с реальной разработкой ПО. Я не помню, чтобы мне когда-либо приходилось самому писать алгоритм сортировки в повседневной работе. Тем не менее, очевидно, что разработчик, способный решить эти проблемы, будет лучше справляться и с проблемами реальной жизни. Поэтому я хочу описать, что я узнал о C# во время собеседований. У меня больше 10 лет опыта в C#, но повседневная разработка и прохождение интервью – это разные вещи.

1. Многомерные массивы могут быть полезны
Не думаю, что я когда-либо использовал многомерный массив в своей работе. Конечно, я иногда использовал список списков List<List<T>> и, возможно, список массивов List<int[]>, а иногда даже список словарей массивов List<Dictionary<int,string[]>>. Но я обнаружил, что многомерные массивы очень полезны в упражнениях по кодированию.

Многомерные массивы - это не то же самое, что массивы массивов, например int[][] (зубчатые массивы). Последние представляют собой набор массивов, каждый из которых может иметь разную длину. Многомерный массив больше подходит для решения общих задач, таких как представление двухмерного лабиринта или трехмерного куба. Если вы собираетесь на собеседование в ближайшее время, освежите в голове синтаксис:

int[,] arr = new int[3, 2]
  {{1, 2},{3, 4},{5, 6}};
 
int dimLen1 = arr.GetLength(0); //3
int dimLen2 = arr.GetLength(1); //2
var p00 = arr[0, 0]; //1
var p01 = arr[0, 1]; //2
var p10 = arr[1, 0]; //3

Вот пример вопроса, в котором могут пригодиться многомерные массивы: для двумерного пространства размером MxN квадратных ячеек, где каждая ячейка является либо свободным пространством, либо стеной, найдите наибольшую связанную область из свободных ячеек и верните количество ячеек в ней.

2. Используйте кортежи, вместо классов
Я довольно редко использую кортежи. Вероятно потому, что я пока не привык к их более красивому синтаксису. Обычно я выбираю класс или структуру. Классы делают код более структурированным и, возможно, более читаемым. Но на самом деле у кортежей очень хороший и, что важно, более компактный синтаксис. Писать нужно меньше, менять нужно меньше. Эти вещи действительно важны на собеседовании. Нужно тратить минимум времени на ввод кода, чтобы у вас было больше времени на размышления.

Допустим, у меня есть метод, который возвращает точку в трёхмерном массиве. При использовании класса я бы написал:

class Point3D {
    public int X { get; set; }
    public int Y { get; set; }
    public int Z { get; set; }
}
private Point3D Calc() {…}

Тогда как с кортежами всё проще:

private (int X, int Y, int Z) Calc(){ ... }

Имейте в виду, что на собеседовании вы будете писать в своего рода онлайн-блокноте, где у вас нет сниппетов, автозаполнения и прочих прелестей, к которым вы привыкли в Visual Studio.

Продолжение следует…

Источник: https://michaelscodingspot.com/what-i-learned-about-c-from-job-interviews/
Автор: Michael Shpilt.

День семьсот пятьдесят восьмой. #Оффтоп #ЗадачиНаСобеседовании
Что я Узнал о C# из Собеседований. Продолжение
Начало

3. Бинарные операции – это вещь!
Как часто вы используете операторы <<, >>, & и | в ваших приложениях? Думаю, не часто. Я тоже, но они могут быть довольно полезны. Небольшое напоминание:

int a = 15;
Convert.ToString(a, to_base: 2); //1111
//сдвиг вправо дважды (деление на 4)
a = a >> 2; //11
//сдвиг влево трижды (умножение на 8)
a = a << 3; //11000
a = a & 0b_11111; // не изменяется
// остаётся 1000, т.к. левый бит обнуляется
a = a & 0b_1111; //1000
a = a | 0b_1; // становится 1001
a = a | 0b_110; // становится 1111

Одна из особенностей двоичного исчисления заключается в том, что итерация по основанию 2 может быть полезна в задачах на перестановку. Например: для заданного массива элементов, распечатать все возможные комбинации этих элементов, в которых каждый элемент может либо присутствовать, либо отсутствовать. Порядок не имеет значения. То есть для массива ["a", "b", "c"] вывод будет следующим:
"", a, b, c, ab, ac, bc, abc

Теперь рассмотрим итерацию в двоичном формате от 0 до 2^3. Если каждая цифра описывает элемент массива, который присутствует или нет, то это один из способов распечатать все возможные итерации. Требуемый выше результат можно описать как:

000, 001, 010, 100, 110, 101, 011, 111

4. Полезные штуки со строками и массивами
Большинство методов, используемых в задачах, аналогичны методам, используемым в реальной жизни. Для строк это .Substring, .Contains, .Replace, string.Equals, .ToLower, .ToUpper и т.д. Один из методов, полезных в этих задачах, но редко используемый в моей работе, - это string.Join:

var joined = string.Join(",", 
  new[]{"a","b","c"}); // "a,b,c"

Для массивов есть полезный метод Array.Sort, который может принимать делегат Comparison<T> для нужной вам сортировки. Предположим, вы хотите отсортировать группу строк по последней букве:

var words = new[]{"cat", "job", "zebra", "row"};
Array.Sort(words, (w1, w2) => {
  var last1 = w1[w1.Length-1];
  var last2 = w2[w2.Length-1];
  return last1 < last2 ? -1 : 1;
  //как вариант last1.CompareTo(last2);
});
// zebra, job, cat, row

Еще один полезный метод - Array.Copy. Помимо прочего, он может копировать фрагмент массива в новый массив:

var words = new[]{"cat", "job", "zebra", "row"};
string[] dest = new string[2];
Array.Copy(words, sourceIndex: 1, 
  dest, destinationIndex: 0, length: 2);
// job, zebra

Конечно, есть и другие способы это сделать, например, LINQ или с помощью диапазонов.

Источник: https://michaelscodingspot.com/what-i-learned-about-c-from-job-interviews/
Автор: Michael Shpilt.

День семьсот шестьдесят седьмой. #Оффтоп #ЗадачиНаСобеседовании
Давненько у нас не было задач.

Допустим, вы ищете квартиру. Для простоты представим улицу в виде одномерного массива кварталов. Пусть у нас будет только одна улица в городе, идеально прямая, а расстояния между кварталами одинаковы и равны 1.
В каждом квартале есть подходящая вам квартира. Кроме того, в кварталах случайным образом расположены важные для вас объекты: магазин, тренажёрный зал, школа для ребёнка и т.п. Допустим, что они одинаково для вас важны. Идеальная для вас квартира находится квартале с наименьшим расстоянием до самого дальнего важного объекта. Обратите внимание: не с минимальной суммой расстояний до всех объектов, а с минимальным наибольшим расстоянием! Задача – найти такой квартал.

Кварталы даны в виде массива словарей (не пугайтесь, это для наглядности, и чтобы не создавать кучи сущностей 😊). В словаре ключ – строковое название объекта, и логическое значение есть он в квартале или нет. Например, вот так:

[
 {{"gym",false},{"school",false},{"store",true}},
 {{"gym",true },{"school",false},{"store",false}},
 {{"gym",true },{"school",false},{"store",true}},
 {{"gym",false },{"school",false},{"store",false}},
 {{"gym",false },{"school",true},{"store",true}}
]

То есть, в первом квартале нет тренажёрного зала и школы, но есть магазин. Во втором есть только тренажёрный зал. В третьем – зал и магазин. И т.д.

Таким образом, в первом квартале дальше всего идти до школы - 4. А победителем получается квартал №4. Хотя там ничего нет, но из него до всех объектов расстояние 1.

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

На этот раз у меня для вас есть даже шаблон проекта с тестами: https://github.com/sbzenenko/NetDeveloper/tree/main/ApartmentFinder
Всё, что вам надо сделать – реализовать метод Find(), принимающий массив кварталов и возвращающий индекс идеального квартала.

Вопросы и предложения оставляйте в комментариях. Через пару дней выложу решение с объяснением.

День семьсот семидесятый. #Оффтоп #ЗадачиНаСобеседовании
Ответ на задачу про поиск квартиры.

Создадим двумерный массив для хранения расстояний. В строках будут кварталы, в столбцах объекты. При этом, если объект присутствует в квартале, отметим соответствующее расстояние как 0, если нет, для начала отметим его недостижимо большим значением, например, 999999 (ниже буду использовать *). Таким образом, для примера из задачи:

[
 {{"gym",false},{"school",false},{"store",true}},
 {{"gym",true },{"school",false},{"store",false}},
 {{"gym",true },{"school",false},{"store",true}},
 {{"gym",false },{"school",false},{"store",false}},
 {{"gym",false },{"school",true},{"store",true}}
]

Первый квартал будет

1: * * 0

Теперь проходим вдоль массива кварталов. Если соответствующий объект есть, заполняем ячейку нулём, в противном случае заполняем её значением на 1 больше, чем в предыдущем квартале. Например, во втором квартале объект "store" будет иметь значение 1. Большие значения нас пока не интересуют, там будет значение <очень много>+1 (оставим их как *). Тогда второй квартал будет:

2: 0 * 1

И так далее:

3: 0 * 0
4: 1 * 1
5: 2 0 0

Теперь проходим массив кварталов обратно. На этом этапе:
1. Задаём значение расстояния как минимальное между существующим значением и значением на 1 больше, чем в предыдущем квартале. То есть, если, проходя в одну сторону, мы получили расстояние до объекта в 3 квартала, но он находится в следующем квартале, то, проходя в обратную сторону, мы зададим минимальное расстояние между 3 и 1 – 1. Аналогичным образом мы заменим все большие значение, обозначенные *.
2. Кроме того, рассчитав все расстояния в квартале, считаем максимальное из них.

5: 2 0 0 (макс: 2)
4: 1 1 1 (макс: 1)
3: 0 2 0 (макс: 2)
2: 0 3 1 (макс: 3)
1: 1 4 0 (макс: 4)

И, наконец, из максимальных значений выбираем наименьшее – 1 в 4м квартале.

Таким образом, нам нужно дважды пройти массив кварталов, в каждом перебрать все объекты. Если количество кварталов взять за M, количество объектов – за N, то сложность решения по времени O(2*M*N), сложность по памяти – O(M*(N+1)).

Код решения с тестами: https://github.com/sbzenenko/NetDeveloper/tree/main/ApartmentFinderSolution

PS: есть ещё нахождение максимума по N и минимума по M, которые сами по себе добавляют O(logM) и O(logN) по времени, но их можно находить параллельно с обратным прохождением массива.

Источник: https://youtu.be/rw4s4M3hFfs

День семьсот восьмидесятый. #Оффтоп #ЗадачиНаСобеседовании
Доброй субботы, дорогие друзья. Новая задачка вам на выходной день. На этот раз никаких Big O, никаких сложных алгоритмов и оптимизаций. Просто на смекалку.

Задача максимально короткая:
С помощью генератора случайных чисел, выдающего значения от 0 до 1, вычислите число пи.

Внезапно?)))

Попытайтесь решить самостоятельно, а ответ и разбор в этом видео.

День семьсот девяносто девятый. #ЗадачиНаСобеседовании
Сегодня предложу вам к просмотру ещё один минисериал от Nick Chapsas на тему заданий на собеседовании. На этот раз Ник разбирает задачу интеграции API сервиса.

Смысл задачи в том, что вам дан REST API (в данном случае API сети ресторанов), вам нужно создать клиента этого API, отвечающего определённым требованиям.

Все подробности задачи Ник объясняет в видео, поэтому не буду их пересказывать.

В первой части https://youtu.be/_Pjjk4fOh8s довольно подробно описывается создание консольного клиента API. Что хотелось бы отметить из решения – это пакеты, которые Ник использует (помимо стандартных):
1. RefitClient – пакет, который создаёт код клиента API на основе интерфейса.
2. CommandLineParser – о нём я уже писал.
3. OneOf – пакет для объединения различных типов в один тип OneOf<T0,T1,…Tn>. Ник использует его для возврата из метода обобщённого объекта с результатом либо ошибкой. Вызывающий код может использовать методы Match() или Switch(), чтобы выполнять действия в зависимости от типа ответа. Не могу сказать, что мне нравится такой подход, но упоминания он заслуживает.
4. Microsoft.Extensions.Http.Polly – Polly на канале уже тоже упоминался, и не раз. Это, насколько я понимаю, версия от Mirosoft, доступная в .NET 5.

Вторая часть https://youtu.be/NPAK94ZCxD4 посвящена тестированию. И помимо обычных модульных тестов Ник описывает приёмочное (acceptance) тестирование: близкое к человеческому языку описание теста, которое парсится в коде и проверяется автоматически. «Ничего не понятно, но очень интересно»))) Кстати, подробно о приёмочном тестировании есть и третье видео https://youtu.be/qWEDkHGNhvk

День 1191.
Подборка тегов, используемых в постах на канале, чтобы облегчить поиск. Не могу гарантировать, что все 1190 постов идеально и корректно помечены тегами, но всё-таки, эта подборка должна помочь.

Общие
Эти посты на совершенно разные темы, помечены этими тегами только с целью различать общую направленность поста.

#ЗаметкиНаПолях – технические посты. Краткие описания теории, особенности языка C# и платформы .NET, примеры кода, и т.п.

#Шпаргалка - примеры кода, команды для утилит и т.п.

#Юмор – шутки, комиксы и просто весёлые тексты или ссылки на видео.

#Оффтоп – всё прочее.


Специализированные
Эти теги более тематические, выделяют основную тему поста.

#Карьера – советы по повышению продуктивности, карьерному росту, прохождению собеседований и т.п.

#Книги – обзоры книг, которые (чаще всего) я лично прочитал, либо ещё нет, но советую прочитать.

#Курсы – обзоры и ссылки на онлайн курсы.

#МоиИнструменты – различные программы, утилиты и расширения IDE, которые я использую в работе.

#ЧтоНовенького – новости из мира .NET.


Узкоспециализированные
Эти теги относятся к определённой узкой теме.

#AsyncTips – серия постов из книги Стивена Клири “Конкурентность в C#”
#AsyncAwaitFAQ – серия постов “Самые Частые Ошибки при Работе с async/await.”

#BestPractices – советы по лучшим практикам, паттернам разработки.

#DesignPatterns – всё о паттернах проектирования, SOLID, IDEALS и т.п.

#DotNetAZ – серия постов с описанием терминов из мира .NET.

#GC – серия постов “Топ Вопросов о Памяти в .NET.” от Конрада Кокосы.

#MoreEffectiveCSharp – серия постов из книги Билла Вагнера “More Effective C#”.

#Testing – всё о тестировании кода.

#TipsAndTricks – советы и трюки, в основном по функционалу Visual Studio.

#Quiz - опросы в виде викторины.

#97Вещей – серия постов из книги “97 Вещей, Которые Должен Знать Каждый Программист”.

#ВопросыНаСобеседовании – тег говорит сам за себя, самые часто задаваемые вопросы на собеседовании по C#, ASP.NET и .NET.
#ЗадачиНаСобеседовании – похоже на вопросы, но здесь больше приводятся практические задачи. Чаще всего это 2 поста: собственно задача и ответ с разбором.

#КакСтатьСеньором – серия постов «Как Стать Сеньором» с советами о продвижении по карьерной лестнице.

Помимо этого, можно просто воспользоваться поиском по постам и попробовать найти то, что вам нужно.

День 1387. #ЗадачиНаСобеседовании
Давненько у нас не было задачек. Сегодня предложу вам подумать над проектированием решения в контексте базы данных. Единственно правильного ответа тут, наверное, нет, просто предлагайте варианты.

Допустим, у нас есть огромная таблица инвентаря товаров в наличии в разных магазинах сети. Т.е. в таблице будет id магазина, артикул товара, количество и прочая информация о товаре. Из неё нас интересуют поля ID магазина и артикул. Таблица несколько раз в день обновляется по мере того, как магазины получают или распродают свой товар и присылают нам остатки.

Задача в следующем. Для клиента сайта требуется организовать «живые» подсказки в строке поиска. То есть по мере того, как клиент печатает артикул (для простоты пусть будет поиск только по артикулу), подсказка под полем показывает доступные артикулы и количество магазинов, в которых они есть в наличии. Например:

Поиск: ABC

Подсказка:

ABC280    - 10 магазинов
ABC100    – 5 магазинов
ABC101    – 2 магазина
ABCDEF-92 – 1 магазин
ABC-XYZ   – 1 магазин

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

Собственно задача. Понятно, что каждый раз запрашивать огромную таблицу слишком затратно. Предположим, что нам достаточно не иметь 100% точной информации в каждую секунду, и этот список должен актуализироваться, скажем, каждые 30 минут.

Фронтенд нас сейчас не интересует. Интересует быстрое получение результата на бэкенде. Как бы вы с точки зрения хранения данных и получения их из базы реализовали такой функционал?

День 1424. #Оффтоп #ЗадачиНаСобеседовании
Больше недели думал, писать ли что-нибудь про ChatGPT. Если кто не знает, что это, вот описание из русской Википедии:
«ChatGPT — это прототип чат-бота с искусственным интеллектом, разработанный OpenAI и специализирующийся на диалогах. ChatGPT — большая языковая модель, отлаженная как с помощью методов обучения с учителем, так и с подкреплением. Базовой моделью, которая была доработана, была языковая модель от OpenAI GPT-3.5, улучшенная версия GPT-3.
ChatGPT был запущен 30 ноября 2022 года и привлёк внимание своими подробными ответами и четкими формулировками, хотя его фактическая точность подверглась критике.»

Сам его пока не ковырял, не было времени, а отзывы в программистской среде пока самые разнообразные от восторженно-панических «программисты больше не нужны» до скептически-злорадных «да там косяк на косяке». Но сегодня всё-таки поделюсь пока самым впечатляющим из того что я видел. Видео от Клемента Михайлеску, создателя платформы AlgoExpert.io, которая предлагает задачи для собеседований на кодирование.

Клемент задал боту задачи «как есть», так, как они описаны на его сайте, предварительно дав ему контекст: «Ты проходишь собеседование в Google с написанием кода». Всего было 3 алгоритмических задачи разного уровня: простой, посложнее и самый сложный. Как сказал Клемент, если первые две задачи довольно стандартные и решения можно найти в сети, то третья (опять же, по его словам) в сети не встречается.

В общем, что из этого вышло, смотрите в новом видео от Клемента Михайлеску https://youtu.be/gOf2SQVMUL0

PS: Кстати, кому интересно, можете запаузить видео и попробовать решить сами.

День 2200. #ЗадачиНаСобеседовании
Код Ревью
Давно не было темы задач на собеседовании (если что, другие посты смотрите по тегу выше). А вот эта показалась интересной. Не буду говорить, откуда. Кто знает, тот знает. Ну и, надеюсь, не раскрою никакой тайны, вроде NDA не подписывал 😊

Итак, вам на ревью прислали вот такой код. А картинкой – это чтоб интереснее было, а то знаю я вас, сразу скопируете и в какой-нибудь жпт запихнёте))). Проверьте код и дайте фидбек. Всё, что вы сможете найти, насколько бы мелким и незначительным на фоне остального это ни казалось. Единственное замечание – мы исходим из того, что код компилируется и вообще проект успешно собирается, то есть все необходимые юзинги на месте, хоть их здесь и нет.

Удачи, жду ревью в комментариях.