Directi Опыт собеседования | Набор 15 (на территории кампуса)

Раунд 1: онлайн-тест на Codechef содержит 3 вопроса по программированию

1. Аманада, школьник, изучает английский алфавит. Ее учитель придумал небольшую игру, чтобы сделать задание увлекательным. Сетка из m строк и n столбцов заполнена английскими алфавитами. Ей нужно искать английские слова в этой сетке, перемещаясь по одному шагу в любой из соседних ячеек сетки. Приведены английские слова. Аманда может начать из любой точки сетки и может перемещаться по любой из 8 соседних ячеек сетки, шаг за шагом. Каждую ячейку сетки можно использовать только один раз.
Вход
Вам предоставляется шаблон, в котором необходимо реализовать функцию, подпись которой приведена ниже.
C
int findWordInAGrid (сетка символов [128] [128], int m, int n, char word [32])
/ * возвращаем 0 для false, 1 для true. * /

C ++
bool findWordInAGrid (char grid [128] [128], int m, int n, char word [32])

Ява
статическое логическое значение findWordInAGridJava (char [] [] grid, int m, int n, String word)

grid [] [] представляет символы, которые находятся в данной сетке. Только первые m строк и первые n столбцов должны считаться релевантными. word - это слово, вхождение которого необходимо найти в сетке. Помните, что слово может начинаться с любого места в сетке. слово никогда не будет содержать более 30 символов. Вернуть true, если слово найдено в сетке, иначе false.
Выход
Функция должна возвращать true, если вы можете найти слово в сетке, и false в противном случае.
Пример
Рассмотрим приведенную ниже сетку:
abc
def
Гхи
И набор слов для поиска:
abc
Abedhi
эфгх
Выход:
Результатом приведенного выше примера должен быть:
abc: правда
абеди: правда
efgh: false

2. Вам дается сетка с 3 строками и N столбцами. Каждая ячейка в сетке изначально содержит значение 0. Вы выполняете несколько операций следующего типа на сетке. Выберите строку, скажем r. Выберите начальный и конечный столбцы, например s и e. Конечно, 1 ≤s ≤ e ≤ N. Теперь установите все значения в сетке в строке r, от столбца s до столбца e, равным 1. После выполнения всех операций вы хотите найти подсетки в этой сетке (или прямоугольники, пожалуйста), которые содержат только единицы. Самое главное, вы хотите найти прямоугольник с наибольшей площадью. Распечатайте площадь этого прямоугольника.
Вход
Первая строка ввода содержит число T - количество тестов. Первая строка каждого тестового примера содержит числа N и M соответственно, разделенные одним пробелом. N - количество столбцов в сетке. M - это количество операций, которые вы выполняете над сеткой. Каждая из следующих M строк содержит три целых числа R, C1 и C2 соответственно для описания операции. R - строка, в которой выполняется операция. C1 и C2 - начальный и конечный столбцы соответственно. Вы можете предположить, что 1 ≤ C1 ≤ C2 ≤ N.
Выход
Для каждого тестового примера выведите одно число в отдельной строке. Это число должно быть площадью самого большого прямоугольника, который можно выбрать в сетке, который содержит только единицы.
Ограничения
1≤T ≤ 100
1 ≤ N ≤ 1000000
1 ≤ M ≤ 1000
Внимание: данные тестирования разработаны таким образом, что решения, моделирующие каждую операцию в O (N), получат TLE. Вы должны суметь решить каждый тестовый пример за O (N). Подсказка: преобразуйте каждую операцию в пару событий «начало» и «конец». Обратите внимание, что порядок операций не имеет значения. Таким образом, вы можете обрабатывать события в порядке возрастания столбцов. Вы также можете просто сохранить, сколько событий начинается / заканчивается в каждой ячейке (поскольку все события одинаковы и имеют идемпотентный эффект). Теперь вы можете перемещаться по столбцу сетки, сохраняя самую длинную полосу из единиц влево в каждой строке. Это помогает рассматривать наилучшие возможные прямоугольники с их правым краем в текущем столбце.
Пример ввода
3
5 2
1 1 4
2 3 5
10 3
1 1 8
2 2 10
3 1 9
5 2
2 1 4
3 3 5
Пример вывода
4
21 год
4
Объяснение
В первом тестовом примере итоговая сетка выглядит как
11110
00111
00000
Мы видим, что самый большой прямоугольник с единицами имеет площадь 4. Таких прямоугольников два. 1,1 -
1,4. И 1,3 - 2,4.
Во втором тестовом примере итоговая сетка выглядит как
1111111100
0111111111
1111111110
Самый большой прямоугольник 1,2 - 3,8. Площадь этого прямоугольника 3 * 7 = 21.

3. Вам дается N камней, пронумерованных от 1 до N. Вес i-го камня W [i]. Есть M цветов, обозначенных целыми числами от 1 до M. i-й камень имеет цвет C [i] (конечно, целое число от 1 до M включительно). Вы хотите наполнить рюкзак этими камнями. Рюкзак может выдержать общий вес X. Вы хотите выбрать ровно M камней; по одному каждого цвета. Сумма веса камней не должна превышать X. Поскольку вы заплатили премию за рюкзак с вместимостью X (в отличие от ранца с меньшей вместимостью), вы хотите заполнить рюкзак как можно больше.
Напишите программу, которая принимает все указанные выше значения в качестве входных данных и вычисляет наилучший способ наполнения рюкзака, то есть способ, минимизирующий неиспользуемую емкость. Выведите эту неиспользованную емкость. См. Объяснение примеров тестовых случаев для ясности.
Вход
Первая строка ввода содержит целое число T - количество тестов. Затем следует описание T-тестов. Первая строка каждого тестового примера содержит три целых числа N, M и X, разделенных одиночным пробелом. Следующая строка содержит N целых чисел, W [1], W [2], W [3]… W [N], разделенных одним пробелом. Следующая строка содержит N целых чисел C [1], C [2], C [3]… C [N], разделенных одним пробелом.
Выход
Оптимальный способ наполнения рюкзака сводит к минимуму неиспользованный объем. Оптимальных способов наполнения рюкзака может быть несколько. Для оптимального результата выведите неиспользованную вместимость ранца (одно целое число в отдельной строке). Если нет возможности наполнить рюкзак, выведите -1. Выведите T строк, по одной для каждого теста.
Ограничения
1 ≤ Т ≤ 10
1 ≤ M ≤ 100
M ≤ N ≤ 100
1 ≤ W [i] ≤ 100
1 ≤ C [i] ≤ M
1 ≤ Х ≤ 10000
Пример ввода
4
9 3 10
2 3 4 2 3 4 2 3 4
1 1 1 2 2 2 3 3 3
9 3 10
1 3 5 1 3 5 1 3 5
1 1 1 2 2 2 3 3 3
3 3 10
3 4 4
1 2 3
3 3 10
3 3 3
1 2 1
Пример вывода
0
1
-1
-1
Объяснение
В первом тестовом случае вы можете выбрать камень 2, камень 5 и камень 9. Рюкзак будет полностью заполнен. Конечно, есть несколько других способов подобрать камни, чтобы рюкзак был полным. Неиспользованная емкость во всех случаях равна 0.
Во втором тесте нельзя отбирать камни так, чтобы рюкзак был полностью заполнен. Вы можете выбрать камни {1, 4, 9} так, чтобы неиспользованная емкость была 10-1-1-5 = 3. Но есть способ получше. Выберите камни {2, 5, 8}. Неиспользованная емкость 10-3-3-3 = 1. Это оптимальный вариант. Есть еще один оптимальный способ. Выберите камни {1, 5, 9}. Неиспользованная емкость составляет 10-1-3-5 = 1. В третьем тестовом примере есть только один вариант. Выберите камни {1, 2, 3}. Общий вес будет 11. Это больше, чем может вместить рюкзак. В четвертом тестовом примере нет камня цвета 3. Таким образом, правильный выбор камней невозможен.
Ответ будет -1.
На второй тур отбирались те, кто решил один вопрос.
Раунд 2: (Skype-интервью - 45 минут)

1. Учитывая сетку m * n, игроки P1 и P2 находятся в узлах (x1, y1) и (x2, y2) соответственно. Есть n драгоценных камней, размещенных в разных позициях сетки, например (G1, G2, G3… ..Gn). Рассчитайте минимальную стоимость, необходимую для сбора всех драгоценных камней. Камень может выбрать один игрок. Драгоценные камни следует собирать в определенном порядке, то есть сначала нужно выбрать G1, затем G2, затем G3 и так далее.
Например:
P1 (1,1) и P2 (3,4)
Есть 4 камня:
G1 (1,1), G2 (2,2), G3 (3,2), G4 (4,2)
Общая стоимость: 5
P1 выберет G4.
P2 выберет G1, G2, G3.
Сложность: O (n)
Раунд 3: (Skype-интервью - 45 минут)
1. Дан массив из n элементов. Над массивом необходимо выполнить n операций. Для каждой операции дается start_index, end_index, trim_value. У одного есть обрезка значения, начиная с start_index и заканчивая end_index включительно. Если значение в этом индексе больше или равно значению обрезки, сделайте его равным trim_value, иначе оставьте его как есть. После выполнения n операций найдите максимальное значение массива.
Сложность: O (n)

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

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию . Если вы готовы, проверьте свои навыки с помощью серий тестов TCS, Wipro, Amazon и Microsoft.