Вопросы для интервью в Citadel

Цитадель Массив Вопросы

Вопрос 1. Вставить Удалить GetRandom O(1) Решение Leetcode Постановка задачи Решение LeetCode Insert Delete GetRandom O(1) — «Insert Delete GetRandom O(1)» просит вас реализовать эти четыре функции с временной сложностью O(1). insert(val): вставить val в рандомизированный набор и вернуть true, если элемент изначально отсутствует в наборе. Возвращает false, когда...

Подробнее

Вопрос 2. Решение для улавливания дождевой воды Постановка задачи Решение LeetCode для захвата дождевой воды – «Захват дождевой воды» утверждает, что задан массив высот, который представляет собой карту высот, где ширина каждого столбца равна 1. Нам нужно найти количество воды, попавшей в ловушку после дождя. Пример: Ввод: высота = [0,1,0,2,1,0,1,3,2,1,2,1] Вывод: 6 Объяснение: Проверить...

Подробнее

Вопрос 3. Coin Change 2 Решение для литкода Постановка задачи Размен монет 2 Решение LeetCode — «Раздача монет 2» утверждает, что задан массив монет с различными целыми числами и целое число, представляющее общую сумму денег. Нам нужно вернуть подсчет общего количества различных возможных комбинаций, которые в сумме составляют сумму. ...

Подробнее

Вопрос 4. Подсчет пар индексов с равными элементами в массиве Допустим, мы дали целочисленный массив. Задача «Подсчет пар индексов с равными элементами в массиве» просит определить номер пары индексов (i, j) таким образом, чтобы arr [i] = arr [j] и i не было равно j . Пример arr [] = {2,3,1,2,3,1,4} 3 пары объяснений ...

Подробнее

Вопрос 5. Самый длинный подмассив, содержащий не более K различных элементов Задача «Самый длинный подмассив, не имеющий более K различных элементов» утверждает, что предположим, что у вас есть массив целых чисел, в формулировке задачи предлагается найти самый длинный подмассив, содержащий не более k различных элементов. Пример arr [] = {4, 3, 5, 2, 1, 2, 0, 4, 5} ...

Подробнее

Вопрос 6. Минимальная операция, чтобы все элементы в массиве были равны Задача «Минимальная операция по уравновешиванию всех элементов в массиве» гласит, что вам дан массив с некоторыми целыми числами в нем. Вы должны выяснить минимальный объем операций, которые можно выполнить, чтобы сделать массив равным. Пример [1,3,2,4,1] 3 Пояснение Либо 3 вычитания могут быть ...

Подробнее

Вопрос 7. Разница между наивысшей и наименьшей частотами в массиве Проблема «Разница между наивысшей и наименьшей частотами в массиве» утверждает, что предполагается, что у вас есть целочисленный массив. В постановке задачи предлагается найти максимальную разницу между самой высокой и самой низкой частотой двух различных чисел в массиве. Пример arr [] = {1, 2, 3, ...

Подробнее

Вопрос 8. k-й отсутствующий элемент в возрастающей последовательности, которого нет в данной последовательности Проблема «k-й отсутствующий элемент в возрастающей последовательности, которого нет в данной последовательности» утверждает, что вам даны два массива. Один из них расположен в порядке возрастания, а другой - нормальный несортированный массив с номером k. Найдите k-й недостающий элемент, которого нет в нормальном ...

Подробнее

Вопрос 9. Проверьте, содержит ли данный массив повторяющиеся элементы на расстоянии k друг от друга Задача «Проверить, содержит ли данный массив повторяющиеся элементы на расстоянии k друг от друга» гласит, что мы должны проверить наличие дубликатов в данном неупорядоченном массиве в пределах диапазона k. Здесь значение k меньше заданного массива. Примеры K = 3 arr [] = ...

Подробнее

Вопрос 10. Найдите все пары (a, b) в массиве такие, что a% b = k Постановка задачи. В задаче «Найти все пары (a, b) в массиве, такие, что a% b = k» указано, что вам дан массив целых чисел и целочисленное значение, называемое k. В постановке задачи предлагается найти пару таким образом, чтобы x ...

Подробнее

Вопрос 11. Запросы по XOR наибольшего нечетного делителя диапазона Постановка задачи Задача «Запросы по исключающему ИЛИ наибольшего нечетного делителя диапазона» утверждает, что вам дан массив целых чисел и запрос q, каждый запрос состоит из диапазона. В постановке задачи предлагается найти исключающее ИЛИ наибольшего нечетного делителя в заданном диапазоне ...

Подробнее

Вопрос 12. Трехстороннее разбиение массива по заданному диапазону Постановка задачи. Вам дан массив целых чисел и диапазон lowValue и highValue. Задача «Трехстороннее разбиение массива по заданному диапазону» требует разбить массив таким образом, чтобы массив был разделен на три части. Разделы массивов будут: Элементы ...

Подробнее

Вопрос 13. Заменить два последовательных одинаковых значения на одно большее Постановка задачи. Предположим, у вас есть целочисленный массив. Задача «Заменить два последовательных равных значения на одно большее» предлагает заменить все эти парные значения, скажем, «а», которое идет последовательно с числом «а + 1», на 1 большее их (два последовательных числа), так что даже после модификации или повторение там ...

Подробнее

Вопрос 14. Найдите отсортированную подпоследовательность размера 3 за линейное время Постановка задачи Задача «Найти отсортированную подпоследовательность размера 3 за линейное время» утверждает, что у вас есть целочисленный массив. В постановке задачи предлагается найти три числа таким образом, чтобы array [i] <array [k] <array [k] и i <j <k. Пример arr [] ...

Подробнее

Вопрос 15. Переставьте массив по порядку - наименьший, наибольший, 2-й по величине, 2-й по величине Постановка задачи. Предположим, у вас есть целочисленный массив. Задача «Переупорядочить массив по порядку - наименьший, наибольший, 2-й наименьший, 2-й наибольший, ..» требует переупорядочить массив таким образом, чтобы сначала было наименьшее число, затем наибольшее число, затем второе наименьшее и затем второе. ...

Подробнее

Вопрос 16. Подсчитать пары из двух отсортированных массивов, сумма которых равна заданному значению x Постановка задачи «Подсчитайте пары из двух отсортированных массивов, сумма которых равна заданному значению x». Задача состоит в том, что вам даны два отсортированных массива целых чисел и целое значение, называемое суммой. В постановке задачи предлагается узнать общее количество пар, которое в сумме составляет до ...

Подробнее

Вопрос 17. Печать скобок в задаче умножения цепочек матриц Постановка задачи. Нам нужно найти такой порядок умножения матриц, чтобы количество операций, связанных с умножением всех матриц, было минимальным. Затем нам нужно вывести этот порядок, т.е. распечатать скобки в задаче умножения цепочки матриц. Предположим, у вас есть 3 матрицы A, B, ...

Подробнее

Вопрос 18. Вставить Удалить GetRandom В задаче Insert Delete GetRandom нам нужно разработать структуру данных, которая поддерживает все последующие операции в среднем за время O (1). insert (val): вставляет значение элемента в набор, если оно еще не присутствует. remove (val): удаляет элемент val из набора, если он присутствует. getRandom: возвращает случайный элемент из текущего набора ...

Подробнее

Вопрос 19. Увеличивающаяся подпоследовательность длины три с максимальным произведением Постановка задачи В задаче «Увеличение подпоследовательности длины три с максимальным произведением» мы дали массив положительных целых чисел. Найдите подпоследовательность длины 3 с максимальным произведением. Подпоследовательность должна увеличиваться. Формат ввода Первая и единственная строка, содержащая целое число N, обозначающее размер ...

Подробнее

Вопрос 20. Найдите максимальное повторяющееся число в массиве Постановка задачи В задаче «Найти максимальное повторяющееся число в массиве» мы дали несортированный массив размера N. Данный массив содержит числа в диапазоне {0, k}, где k <= N. Найдите число, которое приближается к максимальному числу. раз в массиве. Формат ввода ...

Подробнее

Вопрос 21. Количество троек с суммой меньше заданного значения Постановка задачи. Мы дали массив, содержащий N элементов. В данном массиве Подсчитайте количество троек с суммой меньше заданного значения. Пример Входные данные a [] = {1, 2, 3, 4, 5, 6, 7, 8} Sum = 10 Выход 7 Возможные тройки: ...

Подробнее

Вопрос 22. Найти триплет в массиве с заданной суммой Постановка задачи. Для массива целых чисел найдите комбинацию из трех элементов в массиве, сумма которых равна заданному значению X. Здесь мы напечатаем первую полученную комбинацию. Если такой комбинации нет, выведите -1. Пример ввода N = 5, X = 15 arr [] = ...

Подробнее

Вопрос 23. Первый повторяющийся элемент Постановка задачи. Мы дали массив, содержащий n целых чисел. Нам нужно найти первый повторяющийся элемент в данном массиве. Если повторяющегося элемента нет, то выведите «Не найдено повторяющегося целого числа». Примечание: повторяющиеся элементы - это те элементы, которые встречаются более одного раза. (Массив может содержать дубликаты) ...

Подробнее

Вопрос 24. Головоломка с массивом продуктов Постановка задачи. В задаче загадки массива товаров нам нужно построить массив, где i-й элемент будет произведением всех элементов в данном массиве, кроме элемента в i-й позиции. Пример входных данных 5 10 3 5 6 2 выходных данных 180 ...

Подробнее

Вопрос 25. Найти первое повторяющееся число в заданном массиве Постановка задачи. В массиве может быть несколько повторяющихся чисел, но вы должны найти первое повторяющееся число в данном массиве (встречающееся во второй раз). Пример входных данных 12 5 4 2 8 9 7 12 5 6 12 4 7 Выход 5 - первый повторяющийся элемент ...

Подробнее

Цитадель Строка Вопросы

Вопрос 26. Различные способы добавления скобок Решение Leetcode Постановка задачи Различные способы добавления круглых скобок Решение LeetCode — «Различные способы добавления круглых скобок» утверждает, что задано строковое выражение, состоящее из чисел и операторов. Нам нужно вернуть все возможные результаты вычислений всеми возможными способами группировки чисел и операторов. Верните ответ в любом порядке. ...

Подробнее

Вопрос 27. Проверьте, все ли строки матрицы вращаются по кругу друг друга Постановка задачи В задаче «Проверить, все ли строки матрицы вращаются по кругу друг друга» мы задали символьную матрицу, напишите программу, чтобы определить, все ли строки вращаются по кругу друг друга или нет. Если все строки представляют собой круговые вращения друг друга, выведите ...

Подробнее

Вопрос 28. Длина самой длинной действительной подстроки Постановка проблемы В поле «Длина самой длинной действительной подстроки» мы указали строку, содержащую только открывающую и закрывающую круглые скобки. Напишите программу, которая найдет самую длинную допустимую подстроку в круглых скобках. Формат ввода Первая и единственная строка, содержащая строку s. Формат вывода Первые и ...

Подробнее

Цитадель Дерево Вопросы

Вопрос 29. Построить двоичное дерево из заданных обходов в порядке и в порядке следования В этой задаче у нас есть порядок и предварительный порядок двоичного дерева. Нам нужно построить двоичное дерево из заданных обходов Inorder и Preorder. Пример ввода: Inorder = [D, B, E, A, F, C] Preorder = [A, B, D, E, C, F] Вывод: предварительный обход дерева, образованного ...

Подробнее

Вопрос 30. Проверить дерево двоичного поиска Проблема В задаче «Проверить дерево двоичного поиска» мы указали корень дерева, мы должны проверить, является ли это деревом двоичного поиска или нет. Пример: Выход: true Объяснение: Данное дерево является двоичным деревом поиска, потому что все элементы, оставленные для каждого поддерева ...

Подробнее

Вопросы по стеку Цитадели

Вопрос 31. Решение для улавливания дождевой воды Постановка задачи Решение LeetCode для захвата дождевой воды – «Захват дождевой воды» утверждает, что задан массив высот, который представляет собой карту высот, где ширина каждого столбца равна 1. Нам нужно найти количество воды, попавшей в ловушку после дождя. Пример: Ввод: высота = [0,1,0,2,1,0,1,3,2,1,2,1] Вывод: 6 Объяснение: Проверить...

Подробнее

Цитадель Очередь Вопросы

Вопрос 32. Приоритетная очередь с использованием двусвязного списка Постановка задачи Задача «Приоритетная очередь с использованием двусвязного списка» предлагает реализовать следующие функции приоритетной очереди с использованием двусвязного списка. push (x, p): поставить элемент x с приоритетом p в очередь с приоритетом в соответствующей позиции. pop (): удалить и вернуть элемент с наивысшим приоритетом ...

Подробнее

Цитадель Матрица Вопросы

Вопрос 33. Печать скобок в задаче умножения цепочек матриц Постановка задачи. Нам нужно найти такой порядок умножения матриц, чтобы количество операций, связанных с умножением всех матриц, было минимальным. Затем нам нужно вывести этот порядок, т.е. распечатать скобки в задаче умножения цепочки матриц. Предположим, у вас есть 3 матрицы A, B, ...

Подробнее

Вопрос 34. Проверьте, все ли строки матрицы вращаются по кругу друг друга Постановка задачи В задаче «Проверить, все ли строки матрицы вращаются по кругу друг друга» мы задали символьную матрицу, напишите программу, чтобы определить, все ли строки вращаются по кругу друг друга или нет. Если все строки представляют собой круговые вращения друг друга, выведите ...

Подробнее

Цитадель Другие вопросы

Вопрос 35. Решение LRU Cache Leetcode Постановка задачи Кэш LRU Решение LeetCode – «Кэш LRU» просит вас спроектировать структуру данных, которая следует за кэшем наименее недавно использовавшихся (LRU) Нам необходимо реализовать класс LRUCache со следующими функциями: LRUCache(int capacity): Инициализирует кэш LRU с положительной размерной емкостью. int get(int key): вернуть значение...

Подробнее

Вопрос 36. Оценка обратной польской записи LeetCode Solution Постановка задачи Вычислить обратную польскую запись Решение LeetCode – Оценить значение арифметического выражения в обратной польской записи. Допустимые операторы +, -, * и /. Каждый операнд может быть целым числом или другим выражением. Обратите внимание, что деление между двумя целыми числами должно усекаться до нуля. Гарантируется, что данный...

Подробнее

Вопрос 37. Хранилище ключей и значений на основе времени Решение LeetCode Постановка задачи Хранилище данных типа "ключ-значение" на основе времени Решение LeetCode. Разработайте структуру данных типа "ключ-значение" на основе времени, которая может хранить несколько значений одного и того же ключа с разными временными метками и получать значение ключа в определенной временной метке. Реализуйте класс TimeMap: TimeMap() Инициализирует объект структуры данных. void set (строковый ключ, строка...

Подробнее

Вопрос 38. Найти медиану из потока данных Решение LeetCode Постановка задачи Найти медиану из потока данных LeetCode Решение. Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения нет, а медиана — это среднее значение двух средних значений. Например, для arr = [2,3,4] медиана...

Подробнее

Вопрос 39. Решение LeetCode для столкновения с астероидом Постановка задачи Столкновение с астероидом Решение LeetCode. Нам дан массив астероидов из целых чисел, представляющих астероиды в ряду. Для каждого астероида абсолютное значение представляет его размер, а знак представляет его направление (положительное значение означает право, отрицательное значение означает лево). Каждый астероид движется с одинаковой скоростью. Узнать состояние...

Подробнее

Вопрос 40. Решение LeetCode для сериализации и десериализации двоичного дерева Постановка задачи Сериализация и десериализация двоичного дерева Решение LeetCode. Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по каналу сетевого соединения для последующего восстановления. в ...

Подробнее

Вопрос 41. Продукт массива, кроме решения Self LeetCode Постановка задачи Product of Array Except Self LeetCode Решение – Учитывая целочисленный массив nums, вернуть такой массив ответа, что answer[i] равен произведению всех элементов nums, кроме nums[i]. Произведение любого префикса или суффикса чисел гарантированно соответствует 32-битному целому числу. Вы должны написать алгоритм, который работает за время O(n) и не использует деление...

Подробнее

Вопрос 42. K-й наименьший элемент в решении BST Leetcode Постановка задачи K-й наименьший элемент в решении BST Leetcode. Учитывая корень двоичного дерева поиска и целое число k, вернуть k-е наименьшее значение (с индексом 1) всех значений узлов в дереве. Примеры: Ввод: root = [3,1,4,null,2], k = 1 Вывод: 1 Ввод: root = [5,3,6,2,4,null,null,1], k ...

Подробнее

Вопрос 43. Уродливое решение LeetCode номер XNUMX Постановка задачи Уродливое число II Решение LeetCode. Уродливое число — это положительное целое число, простые множители которого ограничены значениями 2, 3 и 5. По заданному целому числу n верните n-е уродливое число. Ввод: n = 10 Выход: 12 Объяснение: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] — последовательность первых 10...

Подробнее

Вопрос 44. Решение LeetCode для разрыва целых чисел Постановка задачи Целочисленное разбиение LeetCode Решение – Учитывая целое число n, разбейте его на сумму k положительных целых чисел, где k >= 2, и максимизируйте произведение этих целых чисел. Нам нужно вернуть максимальный продукт, который мы можем получить. Вход: n = 2 Выход: 1 Объяснение: 2 = 1 + 1, ...

Подробнее

Вопрос 45. Максимальное произведение трех чисел Решение LeetCode Постановка задачи Максимальное произведение трех чисел Решение LeetCode. Нам дан массив, вопрос просит нас вычислить максимальное произведение любых трех чисел. Примеры Пример 3: Ввод: nums = [1] Вывод: 1,2,3 Пример 6: Ввод: nums = [2] Вывод: 1,2,3,4 Пример 24: Ввод: nums = ...

Подробнее

Вопрос 46. Word Ladder Решение LeetCode Постановка задачи Лестница слов Решение LeetCode. «Лестница слов» утверждает, что вам дана строка beginWord, строка endWord и список слов. Нам нужно найти кратчайшую длину последовательности преобразований (если путь не существует, выведите 0) из beginWord в endWord, следуя заданным условиям: Все промежуточные слова должны ...

Подробнее

Вопрос 47. Лучшее время для покупки и продажи решения LeetCode для акций Постановка задачи Лучшее время для покупки и продажи акций Решение LeetCode — «Лучшее время для покупки и продажи акций» утверждает, что вам дан массив цен, где цены[i] — это цена данной акции в i-й день. Вы хотите максимизировать свою прибыль, выбрав ...

Подробнее

Вопрос 48. Выведите n членов последовательности Ньюмана-Конвея Постановка задачи Задача «Вывести n членов последовательности Ньюмана-Конвея» утверждает, что вам дано целое число «n». Найдите первые n членов последовательности Ньюмана-Конвея и распечатайте их. Пример n = 6 1 1 2 2 3 4 Объяснение Все напечатанные термины следуют последовательности Ньюмана-Конвея ...

Подробнее

Вопрос 49. Максимум скользящего окна В задаче «Максимум скользящего окна» мы дали массив чисел, для каждого непрерывного окна размера k найти максимальный элемент в окне. Пример Входные числа [] = {1,3, -1, -3,5,3,6,7} k = 3 Выходные данные {3,3,5,5,6,7} Объяснение Наивный подход для максимума скользящего окна для каждое смежное окно размера k, пройти ...

Подробнее

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

Подробнее

Вопрос 51. Сериализация и десериализация двоичного дерева Мы дали двоичное дерево, содержащее N узлов, каждый из которых имеет какое-то значение. Нам нужно сериализовать и десериализовать двоичное дерево. Сериализация Процесс сохранения дерева в файле без нарушения его структуры называется сериализацией. DeserializeSerialize и десериализация двоичного дерева Процесс ...

Подробнее

Translate »