Directi Интервью Вопросы

01.01.2020Интервью

Сегодня я принял участие в 1-м раунде кодирования при наборе в кампусе Direct I. Поделиться 2 вопросами, которые были заданы.

Вопрос 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? Т? 100
1? длина S? 1000

Sample Input:
5
abab
abba
bbaa
aaaa
babaabba

Sample Output:
1,2
1,3
0,3
0,0
0,4

Внимание:
Ограничения разработаны таким образом, чтобы алгоритм O (N ³ ) для каждого тестового случая не проходил.

Вопрос 2 (Запросы к базе данных): 2 балла
У вас есть набор из N объектов. Каждый из этих объектов имеет определенные свойства, связанные с ними. Свойство представлено парой (ключ, значение). Например, предположим, у вас есть следующие два объекта.

Tower:
{
      (height, 100), (weight, 50),
      (xposition, 25), (yposition, 36)
}

Tree:
{
      (area, 100), (noofleaves, 500),
      (height, 25), (yposition, 36)
}

Каждый ваш объект будет иметь максимум 4 свойства. Объект будет иметь как минимум 1 свойство. Обратите внимание, что из двух вышеприведенных объектов необязательно, чтобы ввод свойств был одинаковым для всех объектов. Кроме того, не обязательно, чтобы ключ отличался.
Теперь, учитывая N таких объектов, вы хотите ответить на M запросов. Каждый запрос представлен набором свойств (опять же не более 4 свойств и не менее 1 свойства). Ответом на запрос является количество объектов в наборе, которые имеют все заданные свойства. Два свойства считаются равными, если и ключ, и значение совпадают.
Например, если у вас есть два вышеупомянутых объекта, то ответ на следующие запросы
Запрос: {(высота, 100), (yposition, 36)}
Ответ: 1 // соответствует башне, но не дереву

Запрос: {(yposition, 36)}
Ответ: 2 // соответствует и Башне и Дереву

Запрос: {(высота, 100), (без листьев, 500)}
Ответ: 0 // ни Башня, ни Дерево не удовлетворяют обоим свойствам

Входные данные :
Первая строка ввода содержит N и M. Далее следует описание N объектов. Описание i-го объекта начнется с числа k, которое является количеством свойств, связанных с объектом. Следующие k строк содержат две разделенные пробелами строки — ключ свойства и значение свойства. Обратите внимание, что значение свойства не обязательно является целым числом (хотя это относится к примеру выше).
Далее следует описание M запросов. Формат запроса будет точно таким же, как и у объектов. Проверьте образец ввода для уточнения.
Один тестовый файл будет содержать только один тестовый пример. Один тестовый пример может содержать несколько запросов.

Выход:
Распечатать M строк. Каждая строка должна быть ответом на соответствующий запрос.

Ограничения:
1? N? 10000
1? М? 100000
1? к? 4

Sample Input
2 3
4
height 100a
weight 50b
xposition 25a
yposition 36b

4
area 100a
noofleaves 500
height 25
yposition 36b

3
weight 80
xposition 25a
yposition 36b

1
yposition 36b

2
xposition 25a
yposition 36b

Sample Output:
0
2
1

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

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

Рекомендуемые посты:

Directi Интервью Вопросы

0.00 (0%) 0 votes