Рубрики

Интервью Microsoft | Комплект 26

Раунд 1:
Вопросы о предыдущей работе, шаблоны дизайна, использованные в предыдущей работе.

Учитывая два целых числа, представленных в формате связанного списка, и теперь добавьте эти два списка и поместите его в третий список, в любой момент времени узел может иметь только одну цифру.
С обсуждениями это было похоже на рассмотрение переноса вперед и все аналогично некоторым из двух целых чисел, представленных в виде связанного списка. Интервью попросили сначала рассказать о подходе, а затем о кодировании.

// Approach 1
// 1 2 3
// 12 8 9
// 14 1 2 

Версия 1:

private static void Add(Node head1, Node head2)

{

    int res = 0;

    if (head1 != null)

    {

        count++;

        Add(head1.Next, head2.Next);

        count--;

        res = head1.Data + head2.Data + carryFwd;

        carryFwd = res / 10;

        Node newNumNode =null;

        newNumNode = new Node() { Data = res % 10 };

        if (head3 == null)

        {

            head3 = newNumNode;

        }

        else

        {

            newNumNode.Next = head3;

            head3 = newNumNode;

        }

    // доволен этой логикой, куда войдет список

    // обратное направление что-то вроде вставки в голову

    // позиция каждый раз, когда создается новый узел

}

Версия 2: попросил меня взять пример и доказать, что решение верное
Один из моих тестов был неудачным, если последние цифры также дают перенос

    static int[] aa = new int[3];

    static int carryFwd = 0;

    static Node head3 = null;

    static int count;

    private static void Add(Node head1, Node head2)

    {

        int res = 0;

        if (head1 != null)

        {

            count++;

            Add(head1.Next, head2.Next);

            count--;

            res = head1.Data + head2.Data + carryFwd;

            carryFwd = res / 10;

            Node newNumNode =null;

            if (count == 0)

            {

                newNumNode = new Node() { Data = res };

            }

            else

            {

                newNumNode = new Node() { Data = res % 10 };

            }

            if (head3 == null)

            {

                head3 = newNumNode;

            }

            else

            {

                newNumNode.Next = head3;

                head3 = newNumNode;

            }

        }

    }

}

Версия 3:
Это сохранит сумму последних цифр в одном узле, это не то, что я ожидал, когда сумма состоит из двух цифр, поэтому, пожалуйста, исправьте код

private static void Add(Node head1, Node head2)

{

    int res = 0;

    if (head1 != null)

    {

        count++;

        Add(head1.Next, head2.Next);

        count--;

        res = head1.Data + head2.Data + carryFwd;

        carryFwd = res / 10;

        Node newNumNode =null;

        newNumNode = new Node() { Data = res % 10 };

        if (head3 == null)

        {

            head3 = newNumNode;

        }

        else

        {

            newNumNode.Next = head3;

            head3 = newNumNode;

        }

        if(carryFwd ==1)

        {

           newNumNode = new Node() { Data = carrFwd};

           newNumNode.Next = head3;

           head3 = newNumNode;

        }

    }

Версия 4:
Можете ли вы оптимизировать больше здесь …? Какое максимальное значение при добавлении двух цифр …? Каковы возможные значения для переноса …? Спина к спине вопросы
Таким образом, в моей последней версии была удалена переменная count, и последнее условие переноса было перенесено за пределы функции. Он создал больше веселья здесь, поэтому он копает так глубоко.

    public class Node

    {

        public int Data { get; set; }

        public Node Next { get; set; }

    }

}

Теперь напишите контрольные примеры для этой проблемы.
Около 15 тестовых случаев означает тестовые входы. Я написал, посмотрев на мое решение.
Вопрос здесь заключается в том, чтобы написать тестовые примеры для вашего решения или для проблемы, подумайте, что это не ваш код, которому вы дали проблему, и напишите тестовые примеры.
Затем я добавил некоторые тестовые примеры, игнорируя мое предположение о равной длине списка.
Когда меня попросили написать больше, я был рад, когда написал тест с размером связанного списка 10000000, поскольку мое решение рекурсивное, я могу получить исключение переполнения стека.
С этим ответом он ударил меня множеством вопросов.

Интервьюер:
Тогда почему вы выбираете рекурсию? Мне нужен альтернативный подход, который недоволен одним альтернативным

  // Approach 2
  /*
   * Reverse list 1:
   * Reverse list 2:
   * Add the lists with remainder and dividends
   * Reverse list 3:
  */

  // Approach 3
  /*
   * make the linked list to array and use the indices to 
     traverse and do the addition
   * No program is asked for it
  */

  // Approach 4
  /*
   * mConvert the entire linked list to an integer and then
     add both the integers and then prepare a linked list 
     with the result 
   * but the issue if the result is out of integer boundary
  */ 

Когда я сказал подход 4, он спросил меня

Интервьюер: «Вы думаете, почему этот парень сохраняет целое число в связанном списке, а затем спрашивает меня о добавлении таких списков…?»
Я: да
Интервьюер: тогда ответь себе, что заставляет меня делать это, давай поменяемся ролями
Я: рассказал некоторые сценарии, такие как
1. хотите иметь целочисленные индексы и динамически расти (чтобы массивы не были дружественными)
2. Если я хочу иметь счетчик, значение которого больше диапазона целых чисел, я могу использовать эту или другую структуру данных.

Опрашивающий: Теперь давайте снова вернемся к вопросу и затем исправим ваш код, игнорируя ваше предположение о равной длине списков.
Я: вышеупомянутые подходы 3 и 4 могут решить
Интервьюер: но это альтернативные подходы для решения любых способов исправить одно и то же решение вместо того, чтобы идти с альтернативным?
Я: Может быть, я дополню меньший список нулями, а затем сначала использую дополнительные издержки своего алгоритма, но это работает.
Интервьюер: Хорошо. Вернемся к вашему решению. Рекурсия. Почему вы запрыгнули и начали с рекурсии, когда у вас есть много альтернатив …?
Я: Я обычно думаю о рекурсии, когда кто-то задает вопрос в связанном списке, который иногда легко решить, поскольку он однонаправлен.
Интервьюер: можете ли вы подробнее рассказать, как рекурсия облегчит логику разработчика?
Я: Он использует внутреннее дерево, с помощью которого я могу выполнять операции в обратном направлении в связанном списке
Видж: Какое дерево оно поддерживает?
Я: Имя — это некое RecursionTree, но на самом деле это не дерево.
Интервьюер: Тогда что это
Я: некоторая структура данных
Интервьюер: вне всякого сомнения, что это за структура данных
Я: Я надеюсь, что это стек, так как он работает в режиме LIFO, поэтому я могу легко выполнить обратную операцию. Вот почему один из моих тестов проверяет исключение переполнения стека, так как я использовал рекурсию, когда у меня большие данные.
Интервьюер: что такое LIFO
Я: объяснил про LIFO и сравнил с FIFO.

Интервьюер: Есть вопросы ко мне …?
Я: Если это не является конфиденциальным и очевидным, скажите мне, какова основная логика или алгоритмы, используемые в Bing, поскольку мой менеджер сказал, что это для команды Bing
Опрашивающий: хорошо, если вы хотите написать алгоритм поиска, каков ваш подход?
Я: Я пойду с некоторыми эвристическими поисками, такими как поиск типа Best-First алгоритма A * или решение задачи TSP (Traveling sales person).
Интервьюер: если это так, любой может написать поисковик 🙂 мы также используем некоторые эвристические методы, но никогда не будем похожи на прямое A * algo
И некоторое обсуждение Google против Bing, а затем это все с моей стороны, и вы можете стать частью команды релевантности Bing, как только мы поговорим с другим парнем.

Раунд 2: длится 1:30 мин
Интервьюер: начну прямо с вопроса, не теряя времени.
Для данного массива + ves и -ves найдите подмассив, максимум которого max среди всех подмассивов любой длины в данном массиве.
Сначала расскажите подход, а затем напишите код
Я: Через некоторое время рассказал о подходе со сложностью O (n), затем он попросил меня написать код

int len = sizeof(arr)/sizeof(arr[0]);

int currMax = a[0], finalMax = arr[0];

for (int i=1;i<=len;i++) { 

  currMax += a[i]; i

  if(currMax > finalMax)

      finalMax = currMax;

  if(currMax<0)

      currMax =0;

}

Интервьюер: Возьмите несколько цифр и докажите, что ваше решение верное
Я: Показанный на примере мне нужно пройти по всему списку, пока я не получу ответ.
Интервьюер: Это терпит неудачу в любом сценарии?
Я: нет никогда
Опрашивающий: Он потерпит неудачу, если все числа в массиве — -ves
Я: но изначально вопрос был массив это сочетание + ve и -ve
Интервьюер: Хорошо, тогда позвольте мне изменить вопрос и подумать, что у него есть все -весы, тогда ваш код потерпит неудачу, если да, то где?
Я: да, это будет с условием currMax
Интервьюер: затем исправить
Я: потребовалось много времени, чтобы исправить, а затем попросил меня доказать правильность
Я не смог доказать свое решение, потому что где-то проиграл, пока отслеживал большой список, но решение было правильным, поэтому
Интервьюер: он попросил меня изменить инициализацию и исправить это подсказка
Я: Я не мог исправить, потому что придерживался своего решения, но я дал альтернативный подход, как
Я умножу все -ve числа на -1 и сделаю список заполненным + ves, а затем найду минимум подмассива вместо max, как только получу, я сделаю это -ve числом до возврата или печати
Интервьюер: очень заинтересован в том, что является возвращаемым значением функции, которую я написал; и он сказал, что вы идете к альтернативному решению вместо исправления существующего решения
Интервьюер: хорошо, давайте перейдем к другому вопросу, если дерево найдет предка
Я: имеется в виду родитель, прародитель или прародитель
Интервьюер: это имеет значение для вас? И какой у тебя подход, скажем, к прародителю?
Я: Я сказал, может быть, я пойду со стеком и на основе вашего варианта я буду смотреть узел из стека
Интервьюер: Хорошо, вместо этого мы перейдем к другому вопросу.

Интервьюер: Я нарисую дерево на бумаге и дам вам время. Я запомню дерево в структуре данных, и как только вы скажете «да», я уничтожу или заберу свою бумагу, а затем посчитаю, что структура данных является входной. к вашему алгоритму, и они построят мое дерево обратно
Я: Я не мог понять проблему, задавал слишком много вопросов, что он на самом деле хочет, я построю дерево, используя дерево ur, а затем вызову ту же функцию, чтобы воссоздать
Интервьюер: как вы создаете то, что вы вводите, какова структура данных?
Я: Я сказал Node бла-бла … задал слишком много вопросов, тогда я понимаю, что он хочет
Таким образом, мой подход состоял в том, чтобы я представлял ваше дерево в двух массивах, один из которых будет Inorder, а другой будет pre / post, здесь я перейду к Pre, и как только у меня будут эти два массива, я могу перейти к алгоритму построения, предоставив эти входные данные. ,
Интервьюер: расскажите мне подход, как вы строите, если вы эти два массива
Я: Я сказал, комбинируя эти два, как мы можем пойти и построить как из inorder, мы можем получить корневой элемент и найти тот корень во втором массиве, а затем разделить массив, который совпадает с левым и правым от дерева для корня и продолжить далее ; это мне нужно сделать вручную для данного дерева, чтобы доказать мое решение; и после расщепления он задал пару вопросов о том, куда пойдут вложенные массивы и как запомнишь то, что осталось n справа; вручную я объяснил все это на примере и сказал, что не знаю, какое условие нужно проверить, когда я пишу это как программу
Интервьюер: доволен подходом и спросил, что в In / Pre / Post почему вы выбрали только эти два
Я: Мне нужен Inorder, и вы можете сказать мне, какой из них вы хотите, чтобы я взял до или после
Интервьюер: ваше дело, а также структуру данных и написание программы
Я: Я не смог поместить свою логику в код, так как я не мог проверить правильные условия обычным способом, а также рекурсию, но не мог сделать конкретный код вообще.
Интервьюер: у нас заканчивается время, поэтому мы остановимся здесь.

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

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

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

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

Интервью Microsoft | Комплект 26

0.00 (0%) 0 votes