Directi Интервью | Набор 8 (вне кампуса)

Я подал заявку на участие в Directi за пределами кампуса на его сайте вакансий, и мне позвонили. Всего было 5 туров.

Раунд онлайн-кодирования: 1,5 часа
Всего было 3 вопроса. Все они были вопросами по кодированию, охватывающими ad-hoc, dp, хеширование, графики и т. Д., И вы могли сделать это только в том случае, если бы регулярно выполняли конкурентное онлайн-кодирование. Этот раунд был самым сложным, и вам следует с умом подбирать вопросы, которые вы хотите задать. Я сделал два из них.
Q1- Черничный сырный торт:
Описание проблемы
В селе есть школа. Имеет N классов. В один прекрасный день кто-то подарил школам сырные лепешки B с голубой ягодой. Теперь нужно эти коржи разделить так, чтобы:
Каждый класс получает не менее 1 торта.
Каждый класс разделит торт (ы) между учениками.
Ваша цель - минимизировать максимальное количество студентов на торт в любом классе.
Вход
Первая строка входных данных содержит два целых числа N и B, разделенных пробелами, обозначающих количество классов и общее количество сырных лепешек с голубой ягодой, соответственно.
В следующих N строках указано количество учеников в каждом классе.
Выход
Для каждого тестового примера выведите максимальное количество студентов, которые разделят торт.
Ограничения
2 <= N <= 5 * 105 N <= B <= 2 * 106 1 <= количество студентов в i-м классе <= 5 * 106 Пример исходных данных - 1 1 2 35 Пример выходных данных - 1 18 Пример входных данных - 2 2 7 20 50 Пример вывода - 2 10

Q2: Плохой камердинер
Наш шеф-повар открывает новый ресторан в городе. Сегодня, когда состоится открытие его нового ресторана, и огромная популярность шеф-повара привлекла большое количество людей на торжественное открытие. Для удобства клиентов автомобили всех клиентов помечены цифрами от 1 до N, где N - общее количество автомобилей, соответствующее номеру их парковочного места, на котором должна быть припаркована каждая машина. Из-за большого скопления людей парковка заполнена, за исключением одного парковочного места. Более того, поскольку автомобили приезжали слишком часто, их нельзя было припарковать на соответствующем парковочном месте. Бедному камердинеру на парковке ресторана, Рака, остается нелегкая задача - припарковать машины на своих местах. К счастью для него, парковка была закрыта, машины больше не едут, и теперь он может расставить машины на своих местах. Поскольку Рака остается один, чтобы припарковать машины, он может переместить только одну машину с одной стоянки на другую.
другая парковка. Он может использовать пустую стоянку для передвижения машин. Он хочет расставить машины за как можно меньше ходов. Рака просит вас помочь найти оптимальную стратегию расстановки машин на своих местах.

Вход
Целое число T, обозначающее количество тестовых случаев.
Для каждого тестового примера есть 2 строки.
Первая строка содержит одно целое число N, где N обозначает количество автомобилей.
Во второй строке записано N целых чисел.
K0 - KN-1, где Ki представляет собой номер, нанесенный на автомобиль, стоящий на парковочном месте номер i в исходной конфигурации.
Парковка номер N остается пустой.
Выход
Для каждого теста выведите единственное целое число M, где M - количество перемещений машин, необходимых для того, чтобы все машины вернулись на свои места.
Пример
Вход:
2
3
1 0 2
4
2 1 3 0

Выход:
3
4

Q3: XML Validator
Описание проблемы
Определим строку как открывающий тег, где x - любая строчная буква латинского алфавита.
Каждый открывающий тег соответствует закрывающему тегу типа , где x - та же буква.
Теги могут быть вложены друг в друга, т. Е. Одна пара открывающих и закрывающих тегов может располагаться внутри другой пары.

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

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

Вам дана строка. Вы должны проверить, является ли данная строка допустимым xml или нет.
Вход
Первая строка содержит T количество тестов
Для каждого тестового примера:
Только одна строка, содержащая строку с тегами xml S.
Выход
Для каждого тестового примера
Одна строка, содержащая строку ИСТИНА, если s является допустимым xml ЛОЖЬ, если это не так.
Ограничения
0 <T <= 10 0 <length of S <= 10 ^ 5 Пример ввода: 2 <a><b> </b> </a>
<a> <b> </a>

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

Объяснение
В первом примере <b> </b> - это действительный текст xml внутри другого допустимого текста xml <a> </a>.

Следовательно, общая строка - это текст XML

Во втором примере <b> не имеет подходящей пары и, следовательно, строка не является допустимым текстом xml

Раунд 2: Лицом к лицу (Skype - 1 час)
Это был раунд DS + алгоритм + кодирование. Они сказали, что будет три раунда DS + Algo и необходимо пройти любые два из них, я прошел первые два, поэтому они не взяли мой третий.
Q1- Дано n диапазонов [a1, b1], [a2, b2], [a3, b3]…. [an, bn], где все диапазоны лежат между [0, 10 ^ 6]. Все записи целые. Укажите общее количество уникальных целых чисел во всех диапазонах.
Пример:
Вход:
[1, 3]
[4, 9]
[3, 7]
вывод: 9
Здесь он настоял на создании оптимального кода после моего первого подхода, одобрил второй и попросил меня написать его. У него есть несколько хороших угловых случаев.

Q2: Проверьте, можно ли разбить массив на пары, сумма которых делится на k.
Ввод: arr [] = {92, 75, 65, 48, 45, 35}, k = 10
Выход: True
Мы можем разделить массив на (92, 48), (75, 65) и
(45, 35). Сумма всех этих пар кратна 10.

Раунд 3: Лицом к лицу (скайп - 1 час)
Также раунд DS Algo. В этом раунде был задан один вопрос.
Он попросил объяснить общие вопросы о графах и dfs и попросил объяснить код dfs и его приложения. Затем он задал мне вопрос.

В. Вам дано дерево. У каждого узла может быть любое количество дочерних элементов, но не обязательно. Теперь мы создаем строку из нулей и единиц. Сначала предположим, что вы проходите в dfs, поэтому всякий раз, когда вы проходите узел, вы пишете добавление 1 в строке, проходите все его дочерние элементы и внуки, теперь, когда вы снова возвращаетесь к этому конкретному узлу со всеми дочерними элементами, которые прошли вас добавьте 0 в строку и вернитесь дальше. Таким образом, вам нужно выполнить полный обход.
Например, возьмем дерево с корнем, двумя его дочерними элементами, а у левого дочернего элемента есть еще один ребенок. Соответствующая ему строка будет 11100100.
Теперь фактический вопрос заключается в том, что, учитывая эту строку для дерева, во-первых, получить эту древовидную структуру из этой строки и, во-вторых, определить, может ли эта соответствующая древовидная структура иметь более 1 возможной строки, то есть отличную от указанной.
(Подсказка: DFS может выполняться по-разному в зависимости от того, какой дочерний элемент вы проходите первым. Также подумайте об изоморфизме дерева для всех его дочерних дочерних элементов.)
Я нашел время, обсудил с ним каждый шаг, он был мне полезен и попросил меня написать код. У меня получилось, это интервью длилось 80 минут.

Раунд 4: Технический раунд (Skype - 45 минут)
Этот раунд состоял из ОС, СУБД, сетей и базовых компьютерных основ. Мы подробно обсудили все ответы
Q1- о потребительском процессе производителя и всех его концептуальных деталях
Q2-решение проблемы производителя-потребителя, все решения (аппаратные и программные) с объяснением всех трех условий с примерами (взаимное исключение, прогресс и ограниченное ожидание)
Q3-. Это привело к замкам и семафорам. Спросил меня, что такое блокировки мьютексов и приложения блокировок и семафоров.
Q4 - Процесс связан с одним вопросом, объясняя для одной программы все его этапы как процесс и его обработку (в основном новые-> готовые-> запущенные и т. Д.).
Q5- Что такое swapper? Он работает.
Q6- Диспетчер и функционирование.
Q7- Пробуждение и, следовательно, затем он пошел спрашивать сегментацию пейджинга по запросу.
Q8- Что такое HTTP? Как это протокол без состояния.
Q9 - Модель OSI и ее аналогия из реальной жизни, если я что-нибудь знал.
Q10- Модель TCP / IP и чем она отличается от OSI.
Q11- Один запрос SQL, я точно не помню, но он был в группе и имел концепции подзапроса и соединения.
Q12 - Спросил меня об индексировании, типах и какой структуре данных использовать. Я сказал Btrees и попросил объяснить, как и почему это помогает. Он перепутал меня с BST и спросил, хотя временная сложность будет такой же, тогда почему Btree (я подумал и обсудил, а затем пришел к выводу о записи на диск)

Раунд 5: (общий -1: 30 часов, Skype)
Это было снято каким-то крупным человеком, похоже на старшего менеджера / ED.
Это был тотальный технический + ds + алгоритм + HR.
Q1 - Спросил меня подробно о моем проекте стажировки, об используемых технологиях, о том, сколько я внес и т. Д.
Q2 - Создайте локализованный Twitter, который показывает твиты людей в радиусе 2 миль. Работа с делами
2.1-Каждый раз, когда человек пишет твит (в пределах 2 миль), он должен мгновенно появляться на вашей странице, в основном путем нажатия. (спросили об оптимизации)
2.2-Разработайте таблицы базы данных, покажите отношения между ними, какие атрибуты я беру и почему?
2.3- Попросили написать 2 запроса о извлечении данных из БД.
2.4. На вопрос об оптимизации одного запроса я дал несколько методов использования объединений и вложений, но он дал намек на использование индексации, поэтому я использовал индексацию (использовал Btree для индексации - не писал код btree, просто концепция)
Q3-Объяснил мне концепцию, т.е. учитывая массив размера n, содержащий числа от 1 до n, попросил меня написать массив, содержащий текущие числа, ближайшее число слева от него, которое меньше текущего числа.
Теперь вопрос задается только этому (второму) массиву, можете ли вы сделать предыдущий? Попросил меня закодировать мою логику.

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

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

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

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