Рубрики

Microsoft Интервью опыт | Комплект 108 (в кампусе)

Раунд 1: Способность
Раунд 2: 2 вопроса из структуры данных

Раунд 3: Групповой облет

  1. Найдите наименьшего общего предка двух узлов в двоичном дереве.
    Определите, соответствует ли текущее корневое значение одному из ключевых значений. Если это так, этот корень возвращается. В противном случае процедура повторяется для левого и правого поддеревьев. Узлом, который имеет один ключ в левом поддереве, а другой ключ в правом поддереве, является LCA. Если оба ключа лежат в левом поддереве, первым узлом, значение которого совпадает с одним из значений ключа, является LCA. Аналогично для правильного поддерева. Временная сложность O (n). Интервьюер попросил оптимизации. Я предложил лучший подход для BST.
  2. По двум отсортированным массивам (с повторяющимися элементами) найдите k-е минимальное число из обоих массивов.
  3. Поддерживать индекс для каждого массива, оба инициализируются первым элементом соответствующего массива. Выполните цикл k раз и в каждой итерации найдите минимальный элемент среди текущих индексов и увеличьте индекс массива, содержащего минимум. Если элементы равны, увеличивайте оба индекса. Временная сложность O (k).

Раунд 4:

  1. Учитывая узел в BST, удалите его. Родительская ссылка не является частью структуры узла.
    Если узел является листовым, удалите узел.
    Если у узла есть один дочерний элемент, замените значение этого узла дочерним значением и рекурсивно удалите дочерний элемент.
    Если узел имеет двух дочерних элементов, найдите преемника inorder, замените значение текущего узла значением преемника inorder и рекурсивно удалите преемник inorder.
    Временная сложность составляет O (ч). Интервьюер предложил возможную оптимизацию для одного дочернего случая, чтобы рекурсивное удаление не требовалось для одного ребенка. Нам нужно только скопировать его левый и правый дочерние указатели на узел, который мы пытаемся удалить.
    Связанная статья : GeeksforGeeks Ссылка
  2. Головоломка — есть девять монет, одна из которых неисправна (отличается по весу от других). Найдите максимальное количество итераций, чтобы найти дефектную.
    Я предложил подход «разделяй и властвуй», максимум 5 итераций.

Раунд 5:

  1. Обсуждение проекта
  2. Программа работает в бесконечном цикле в системе. Если мы попытаемся запустить другую хорошую программу во время выполнения этого бесконечного цикла, будет ли хорошая программа работать?

    Я ответил, что программа запустится, но загрузка ЦП будет снижена.

  3. Напишите код для реализации функции strtok () в C.
  4. Поддерживать индекс для представления начала следующего токена, инициализированный равным 0. Поиск строки линейно, если найдено совпадение для шаблона, сохраните подстроку из индекса начала в предыдущую позицию шаблона в строковом массиве и обновите начало Индекс для следующего токена. Временная сложность O (n).
    Интервьюер хотел узнать, почему я использовал malloc () вместо статического размещения.

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

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

Напишите свой опыт интервью или отправьте его по электронной почте на адрес contrib@geeksforgeeks.org

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

Microsoft Интервью опыт | Комплект 108 (в кампусе)

0.00 (0%) 0 votes