Рубрики

Directi Интервью | Набор 7 (Вопросы программирования)

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

1) Вам дается строка S. Каждый символ S является либо «a», либо «b». Вы хотите повернуть ровно одну подстроку S так, чтобы новая строка была лексикографически меньше всех других строк, которые вы можете получить, обращая ровно одну подстроку.
Например, если задано «abab», вы можете обратить вспять подстроку «ab», которая начинается с индекса 2 (начиная с 0). Это дает вам строку «abba». Но если вы выберите обратную подстроку 'ba', начиная с индекса 1, вы получите 'aabb'. Нет способа получить строку поменьше, поэтому обращение подстроки в диапазоне [1, 2] является оптимальным.

вход
Первая строка содержит число T, количество тестовых случаев.
Каждый тестовый пример содержит одну строку S. Символы строки будут из набора {a, b}.

Выход
Для каждого теста выведите два числа через запятую; например «x, y» (без кавычек и без каких-либо дополнительных пробелов). «X, y» описывает начальный индекс (на основе 0) и конечный индекс соответственно подстроки, которая должна быть обращена для достижения наименьшей лексикографической строки. Если существует несколько возможных ответов, выведите ответ с наименьшим «х». Если все еще возможно несколько ответов, выведите ответ с наименьшим «у».
Ограничения
1 <= T <= 100
1 <= длина S <= 1000
Пример ввода
5
ABAB
авва
bbaa
аааа
babaabba
Пример вывода
1,2
1,3
0,3
0,0
0,4

2) Даны две строки I и F, где I — начальное состояние, а F — конечное состояние. Каждое состояние будет содержать «a», «b» и только один пустой слот, представленный «_». Ваша задача — перейти из исходного состояния в конечное состояние с минимальным количеством операций.
Разрешенные операции
1. Вы можете поменять пустой символ на любой соседний символ. (Например, «aba_ab» можно преобразовать в «ab_aab» или «abaa_b»).
2. Вы можете поменять местами пустой символ рядом с соседним символом, только если соседний символ отличается от соседнего символа. (Например, «aba_ab» может быть преобразовано в «a_abab» или «ababa_», но «ab_aab» не может быть преобразовано в «abaa_b», потому что «a» не может перепрыгнуть через «a»).
вход
В первой строке записано единственное целое число T — количество тестов (не более 25). Т-тесты следуют.
Каждый тестовый пример содержит две строки I и F в двух разных строках, где I — начальное состояние, а F — конечное состояние. Я и F могут быть равны. Их длина всегда будет одинаковой. Их длина будет не менее 2. Их длина никогда не будет больше 20.

Выход
Для каждого тестового примера выведите одну строку, содержащую минимальное количество шагов, необходимых для достижения конечного состояния из исходного состояния. Вы можете предположить, что всегда возможно достичь конечного состояния из исходного состояния. Вы можете предположить, что нет ответа больше 30.
пример
Входные данные :
2
a_b
ab_
aba_a
_baaa

Выход:
1
2

3) вероятностный обход предзаказа генерируется для двоичного дерева поиска из следующего псевдокода

function preorder(u) {
    if u is null then return
    print u.label
    r = either 0 or 1 with 50% probability
    if r == 0
        preorder(u.left_child)
        preorder(u.right_child)
    if r == 1
        preorder(u.right_child)
        preorder(u.left_child)
}

Учитывая обратный порядок обхода дерева двоичного поиска, вы всегда можете однозначно построить дерево двоичного поиска. Поскольку обход по бинарному дереву поиска — это, конечно, отсортированный список меток.
Учитывая один из вероятностных обходов предварительного заказа некоторого бинарного дерева поиска, выведите количество различных вероятностных обходов предварительного заказа, которые может сгенерировать приведенный выше алгоритм. Смотрите раздел объяснения для ясности.

вход
Первая строка на входе равна N, количество тестов. Затем следует описание N тестовых случаев. Первая строка в каждом тестовом примере — это целое число N, количество узлов в двоичном дереве поиска. На следующей строке есть N целых чисел — вероятностный предварительный обход дерева двоичного поиска. Все метки узлов в тестовом примере будут отличаться. Значение каждой метки в тестовом примере будет от 1 до N включительно. Вы можете предположить, что ввод будет действительным вероятностным обходом предварительного заказа некоторого двоичного дерева поиска.

Выход

Для каждого теста выведите одно число в отдельной строке. Это число должно быть числом различных вероятностных прохождений предварительного заказа, которые существуют для бинарного поискового тройника, включая число, указанное в тестовом примере. Вы можете предположить, что ответ всегда будет меньше или равен 1 000 000 000. На самом деле, легко увидеть, что ответ никогда не может быть больше 2 ^ 30 (читай во власть).
Ограничения
1 <T <= 10000
1 <= N <= 30

Пример ввода
3
3
2 1 3
3
1 2 3
5
2 4 3 5 1

Пример вывода
2
1
4

4) Вам предоставляется большой массив из 10 000 000 бит. Каждый бит изначально равен 0. Вы выполняете несколько операций типа «Перевернуть все биты между start_index и end_index включительно». Учитывая последовательность нескольких таких операций, выполните все операции над массивом. Наконец, разбейте массив на наборы из 4 битов — сначала четыре, следующие четыре, затем следующие четыре и так далее. Каждый набор может представлять шестнадцатеричное целое число. Там будет ровно 250000 шестнадцатеричных целых. Вычислите частоту каждого из шестнадцатеричных целых чисел от '0' до 'f' среди 2 500 000 целых чисел и напечатайте ее. См. Ввод / вывод и пояснения к примеру ввода / вывода для ясности.
вход
Первая строка ввода содержит целое число T (1? T? 10), количество тестовых случаев. Затем следует описание T тестовых случаев. Вы должны предположить, что массив имеет ровно 10 000 000 битов и что все биты сбрасываются в начале каждого теста. Первая строка каждого теста содержит целое число N (1? N? 10000) — количество выполненных операций. Следующие N строк содержат два целых числа, разделенных пробелом, start_index и end_index для соответствующей операции. Обратите внимание, что операция переворота выполняется от start_index до end_index включительно. Кроме того, массив индексируется 1 — это означает, что наименьший индекс равен 1, а наибольший индекс равен 10 000 000.
Выход
Для каждого теста выведите 16 целых чисел в одной строке, разделенных пробелами. Первое целое число должно представлять число случаев, когда 0 встречается среди 250000 шестнадцатеричных целых чисел, созданных в соответствии с формулировкой задачи. Второе целое число должно представлять число раз, которое 1 встречается среди 250000 шестнадцатеричных целых чисел, созданных в соответствии с формулировкой задачи, и так далее.
Ограничения
1 <= start_index <= end_index
start_index <= end_index <= 10 000 000
Пример ввода
2
2
1 4
9999997 10000000
2
3 6
5 8

Пример вывода
2499998 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
2499998 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0

5) Вам даны две строки, скажем, A и B, одинаковой длины, скажем, N. Вы можете поменять местами A [i] и B [i] для всех i от 1 до N включительно. Вы не можете поменять местами два символа в пределах A или B. Кроме того, вы можете поменять местами только символ в A с символом с тем же индексом в B и без другого символа. Вы можете выполнить эту операцию ноль или более раз.
Вы хотите изменить строки с помощью операций таким образом, чтобы количество уникальных символов в строках было небольшим. Фактически, если n (A) — количество уникальных символов в A, а n (B) — количество уникальных символов в B; Вы хотите выполнить операции так, чтобы max (n (A), n (B)) было как можно меньше.
Выведите значение max (n (A), n (B)) после всех операций.

вход
Первая строка ввода содержит T, количество тестовых случаев. Затем следует описание T тестовых случаев. Каждый тестовый пример содержит число N в первой строке. Следующие две строки контрольного примера содержат две N буквенных строки, A и B соответственно. Буквы строчные английские буквы.
Выход
Выведите одну строку для каждого теста. Выведите значение max (n (A), n (B)) после выполнения всех операций, чтобы значение было как можно меньше.
Ограничения
1 <= T <= 100
1 <= длина (A) <= 16
длина (B) = длина (A)

Пример ввода
3
7
Directi
itcerid
5
Абеба
babab
5
abaaa
baabb

Пример вывода
4
1
2

6) Давайте определим строку как открывающий тег, где x — любая маленькая буква латинского алфавита.
Каждый открывающий тег соответствует закрывающему тегу типа, где x — это одна и та же буква.
Теги могут быть вложены друг в друга, т. Е. Одна пара открывающих и закрывающих тегов может быть расположена внутри другой пары.

Давайте определим понятие XML-текста:

1) Пустая строка — это XML-текст
2) Если S является XML-текстом, то « S » (кавычки и пробелы для ясности) также является XML-текстом,
где любая маленькая латинская буква
3) Если S1, S2 являются XML-текстами, то «S1 S2» (кавычки и пробелы для ясности) также является XML-текстом

Вам дана строка. Вы должны проверить, является ли данная строка допустимым XML или нет.
вход
Первая строка содержит T количество тестов
Для каждого теста:
Только одна строка, содержащая строку с тегом xml S.
Выход
Выведите в одной строке строку ИСТИНА, если s является допустимым значением xml FALSE, если это не так.
Ограничения
0 <Т <= 10
0 <длина S <= 10 ^ 5
пример
Входные данные :
2

Выход:
ПРАВДА
ЛОЖНЫЙ

7) В этой задаче мы рассматриваем две лестницы, A и B, которые параллельны друг другу. Обе лестницы, A и B, имеют N ступеней, каждая из которых A [i], B [i] представляет i-й шаг A и B соответственно.
Каждый шаг связан с определенной суммой штрафа, и если вы используете этот шаг, вы будете оштрафованы на ту же сумму. После нескольких шагов вы накапливаете штраф за все шаги, которые вы посетили.
У вас есть максимальная длина прыжка K, т. Е. От A [i] вы можете перейти вперед к A [i + 1] или A [i + 2]… или A [i + K] без использования каких-либо промежуточных шагов.
Вы также можете перепрыгнуть через лестницу с дополнительным штрафом P за изменение лестницы. Например, из A [i] вы можете перейти к B [i + 1] или B [i + 2]… или B [i + K] с дополнительным штрафом P и штрафом за посещаемый вами шаг. Вы также можете прыгнуть с лестницы B на лестницу A, и это также влечет за собой дополнительный штраф P наряду с штрафом за шаг, который вы посещаете.
Заметьте, что с каждого шага вы можете прыгать только вперед. Ваш последний штраф будет штрафом за все шаги, которые вы посетили, плюс P раз, сколько раз вы пересекли лестницу.
Вы можете начать с A [1] или B [1] и должны достичь A [N] или B [N], сводя к минимуму штраф, накопленный на пути. Найдите минимальный штраф, который вы будете накапливать.
вход
Первая строка на входе равна T, количество тестов. Затем следует описание T тестовых случаев. Первая строка в каждом тестовом примере имеет три целых числа N, количество шагов в обеих лестницах, K, максимальная длина прыжка, P, штраф за пересечение лестницы. Во второй строке каждого теста есть N целых чисел, где i-е целое число соответствует штрафу шага A [i]. В третьей строке каждого теста есть N целых чисел, где i-е целое число представляет штраф за шаг B [i].
Выход
Для каждого теста выведите одну строку, содержащую минимальное наказание, которое вы можете накопить на своем пути, начиная с {A [1] или B [1]} и заканчивая {A [N] или B [N]}.
Ограничения
1 <= T <= 10

1 <= N <= 1000

0 <= P <= 1000

1 <= K <= N

0 <= A [i], B [i] <= 1000
пример
Входные данные :
6
4 1 0
1 2 3 4
1 2 3 4
4 1 0
1 2 3 4
4 3 2 1
4 2 0
1 2 3 4
4 3 2 1
4 1 10
1 2 3 4
4 3 2 1
4 2 10
1 2 3 4
4 3 2 1
5 1 50
0 0 102 104 0
101 103 0 0 105

Выход:
10
6
4
10
7
100

8) В этой задаче мы рассматриваем корневое дерево Tr с корнем r (необязательно бинарное дерево). Первый поиск dfs — глубина — обход дерева Tr, начиная с корня r, посещает узлы Tr в определенном порядке. Давайте назовем этот порядок как dfs ordering.
Обратите внимание, что во время обхода dfs от каждого узла у нас есть выбор между дочерним объектом, который необходимо пройти первым.
Эти разные варианты приводят к разным упорядочениям dfs. Вы должны найти различные способы, которыми dfs может посещать узлы, т. Е. Число различных порядков расположения узлов, возможных для dfs на Tr, начиная с корня r.

Рассмотрим пример Tr с 3 узлами, помеченными 1, 2, 3, где 1 — корень, а 2 и 3 — потомки 1.

DFS на этом Tr могут посещать узлы в порядке (1, 2, 3) или (1, 3, 2). Следовательно, есть 2 способа упорядочения dfs.

Смотрите примеры тестов для большего количества примеров.
вход
Первая строка на входе равна T, количество тестов. Затем следует описание T тестовых случаев. Первая строка в каждом тестовом примере — это целое число N, количество узлов в дереве Tr. Каждый узел помечен отдельным целым числом от 1 до N включительно. На следующей строке есть N целых чисел, где i-е целое число представляет родительскую метку узла с меткой i в корневом дереве Tr. Значение каждой метки в тестовом примере будет от 1 до N включительно. Родительский узел узла с меткой i будет иметь метку меньше i. Узел с меткой 1 является корневым узлом r. Родительский узел корневого узла будет задан как 0 в тестовых случаях.
Выход
Для каждого тестового примера выведите одну строку, содержащую количество возможных упорядочений с помощью dfs в дереве Tr. Поскольку это число может быть огромным, выведите значение по модулю 1 000 000 007.

Ограничения
1 <= T <= 100
1 <= N <= 1000
0 <= A [i] <i

пример

Вход :
6
2
0 1
3
0 1 1
4
0 1 1 1
3
0 1 2
4
0 1 1 2
5
0 1 1 2 2

Выход :
1
2
6
1
2
4

9) Катрина супер гик. Она любит оптимизировать вещи. Предположим, что она находится в позиции (0,0) двумерной сетки, содержащей строки «m» и столбцы «n». Она хочет достичь нижней правой точки этой сетки, проходя через как можно меньшее количество ячеек.
Каждая ячейка сетки содержит положительное целое число, положительное целое число определяет количество ячеек, которые Катрина может перескакивать либо вправо, либо вниз, когда она достигает этой ячейки. Она не может двигаться влево или вверх.
Вам нужно найти оптимальный путь для Катрины, чтобы, начиная с верхнего левого положения в сетке, она достигала нижнего правого положения за минимальное количество прыжков.
вход
Вам предоставляется шаблон, в котором вам нужно реализовать одну функцию minHops. Объявление minHops выглядит так

C / C ++
int minHops (int matrix [64] [64], int m, int n)

Джава
statuc int minHops (матрица int [] [], int m, int n)

Выход
Функция должна возвращать минимальное количество ячеек, к которым нужно прикоснуться, чтобы добраться от верхнего левого угла сетки до нижнего правого угла (включая касание как левого верхнего, так и нижнего правого ячеек). Вернуть 0, если путь не существует.
пример
Предположим, что сетка выглядит так

2 4 2
5 3 8
1 1 1

Начиная с A (0,0), содержится «2», поэтому вы можете перейти к (0,2) или (2,0).
Таким образом, существуют следующие два пути для достижения (2,2) из (0,0)
(0,0) => (0,2) => (2,2)
(0,0) => (2,0) => (2,1) => (2,2)

Следовательно, результат для этого теста должен быть 3

Пример 2

5 3 8 2
6 4 2 1

Нет пути от (0,0) до (1,3), поэтому выход для этого случая должен быть 0

Пример 3

2 3 2 1 4
3 2 5 8 2
1 1 2 2 1

Различные пути в этом случае
(0,0) => (0,2) => (2,2) => (2,4)
(0,0) => (2,0) => (2,1) => (2,2) => (2,4)

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

10) Рассмотрим город Нью-Йорк с решетчатой структурой домов. Вам предоставляется карта города в виде матрицы. Каждая клетка представляет собой здание. Из каждого здания вы можете пройти к соседним четырем зданиям в четырех направлениях: восток, запад, север, юг. Человек-паук хочет спасти жертву, которая находится в каком-то здании. Вам будет предоставлено местонахождение жертвы, а человек-паук находится в (1,1) здании. Но есть условие, что человек-паук не может прыгать между зданиями, если разница в их высоте больше некоторой конкретной величины. Найдите способ, чтобы человек-паук мог добраться до жертвы, пересекая минимальное количество зданий.

вход
Вход содержит несколько тестовых случаев. Первая строка — это целое число T, представляющее количество тестовых примеров, которым необходимо следовать.

В первой строке каждого теста есть 4 числа — M, N, X, Y, D. Здесь MxN — размерность городской сетки. (X, Y) — местоположение жертвы.

Далее следуют М строк. Каждая строка состоит из N разделенных пробелом натуральных чисел, соответствующих высоте здания. D — это максимальная разница между высотами зданий, которые человек-паук может пересечь.
Выход
Одна строка для каждого тестового примера, содержащая одно целое число, обозначающее минимальное количество зданий, которые человек-паук должен пересечь. Верните -1, если это невозможно.
Ограничения
Должен содержать все ограничения на входные данные, которые могут у вас быть. Отформатируйте это как:
1 <= T, M, N, X, Y <= 100
1 <= D <= 100000
Высота каждого здания будет меньше 100000

пример
Входные данные:
3
3 3 3 3 2
1 2 3
6 9 4
7 8 5
3 3 3 3 1
1 8 3
9 5 6
7 2 4
3 3 3 3 1
1 6 7
2 5 8
3 4 9

Выход:
3
-1
7

11) Вам дано дерево из N узлов. Каждый из узлов будет пронумерован от 0 до N-1, и каждый узел i связан со значением vi.
Предположим, что дерево укоренено в узле 0.
Узел y называется потомком узла x, если x встречается на пути от узла 0 к узлу y. Поддерево с корнем в узле x определяется как набор всех узлов, которые являются потомками x (включая x).
Поддерево называется univalued, если значения всех узлов в поддереве равны.
Учитывая дерево и значения, связанные с узлами в дереве, вы должны найти число неустановленных поддеревьев в дереве.
вход
Первая строка содержит целое число N, которое является числом узлов в дереве. Следующие N строк содержат N целых чисел, представляющих значения, связанные с каждым узлом, т.е. i-я строка содержит значение, связанное с узлом i-1. Следующие N-1 строки дают информацию о ребрах в дереве. Каждая строка содержит два разделенных пробелом целых числа x и y, обозначающих ребро между узлом x и узлом y.
Выход
Вы должны напечатать количество неустановленных поддеревьев, которые содержатся в данном дереве.
Ограничения
N <= 30000
пример
Входные данные :
5
0
0
1
1
1
0 1
0 2
2 3
2 4
Выход:
4

12) Directi время от времени организует FNCS (пятничная холодная сессия) (много веселья!). Directians приходят и наслаждаются различными событиями, а затем выходят, когда они устают, и возвращаются снова, когда они освежаются. Для удобства в / из любого человека записывается. В конце дня организатор интересуется, какое максимальное количество человек было во время мероприятия. Поэтому он просит вашей помощи. Он дает вам время входа и выхода каждого человека следующим образом:

Person   Entry_time Exit_time
#1       6          10
#2       1          7
#3       1          4  
#4       8          10
#5       6          10

Личность человека не имеет значения. № 1 и № 4 могут быть одним и тем же человеком. В этом случае максимальное количество людей, присутствующих на мероприятии в любое время, составляет 3 человека.
Ваша задача — прочитать записи и рассчитать максимальное количество людей, присутствующих в ходе мероприятия.
вход
Вход содержит несколько тестовых случаев. Первая строка — это целое число T, представляющее количество тестовых примеров, которым необходимо следовать. Первая строка каждого теста — это число N, количество записей входа-выхода. Далее следуют N строк. Каждая строка состоит из двух разделенных пробелом целых чисел, соответствующих времени входа и времени выхода человека.
Выход
Одна строка для каждого контрольного примера, содержащая одно целое число, обозначающее максимальное количество людей, присутствующих на вечеринке в любое время.
Ограничения
1 <= T <= 100
1 <= N <= 100
1 <= ENTRY_TIME <EXIT_TIME <= 10000000
Время входа и выхода людей гарантированно будет отличаться

пример
Вход :
1
6
7 8
4 9
6 9
8 17
2 14
2 10

Выход :
5

Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Все практические проблемы для Directi !Рекомендуемые посты:

Directi Интервью | Набор 7 (Вопросы программирования)

0.00 (0%) 0 votes