Рубрики

Часто задаваемые вопросы об алгоритме интервью | Комплект 1

Что такое алгоритм?
Неформально, алгоритм — это любая четко определенная вычислительная процедура, которая принимает какое-либо значение или набор значений в качестве входных данных и создает некоторое значение или набор значений в качестве выходных данных. Таким образом, алгоритм представляет собой последовательность вычислительных шагов, которые преобразуют входные данные в выходные. (Источник: Введение в алгоритмы, 3-е издание, CLRS )

Какова временная сложность бинарного поиска?
Временная сложность бинарного поиска составляет O (Logn). См. Бинарный поиск для более подробной информации.

Можно ли использовать бинарный поиск для связанных списков?
Поскольку произвольный доступ не разрешен в связанном списке, мы не можем достичь среднего элемента за O (1) раз. Поэтому бинарный поиск невозможен для связанных списков. Есть и другие способы, см., Например, список пропусков.

Как определить, перекрываются ли два заданных прямоугольника?
Два прямоугольника не перекрываются, если выполняется одно из следующих условий.
1) Один прямоугольник выше верхнего края другого прямоугольника.
2) Один прямоугольник находится слева от левого края другого прямоугольника.
См. Найти, если два прямоугольника перекрываются для более подробной информации.

Как найти угол между часовой и минутной стрелками в данный момент времени?
Идея состоит в том, чтобы взять за точку отсчета 12. Найдите угол, смещенный часовой и минутной стрелками, вычтите два угла, чтобы найти угол между ними. Смотрите угол между часовой и минутной стрелками для более подробной информации

Когда происходит наихудший случай быстрой сортировки?
В быстрой сортировке мы выбираем элемент pivot, а затем разделяем данный массив вокруг элемента pivot, помещая элемент pivot в правильную позицию в отсортированном массиве.
Худший случай быстрой сортировки происходит, когда одна часть после раздела содержит все элементы, а другая часть пуста. Например, если входной массив отсортирован и если последний или первый элемент выбран в качестве основного, то происходит худшее. Смотрите http://quiz.geeksforgeeks.org/quick-sort/ для более подробной информации.

Сортированный массив вращается в некоторой неизвестной точке, как эффективно искать элемент в нем.
Простым подходом является линейный поиск, но мы можем искать в O (Logn) время, используя Binary Search . См. Поиск элемента в отсортированном и развернутом массиве для получения дополнительной информации.
Другие варианты этой проблемы, такие как поиск минимального или максимального элемента в отсортированном и повернутом массиве .

Учитывая большую строку символов, как эффективно найти в ней первого уникального символа?
Эффективным решением является использование символа в качестве индекса в массиве count. Проследить заданную строку и сохранить индекс первого вхождения каждого символа, а также сохранить количество вхождений. Затем просмотрите массив count и найдите наименьший индекс с count как 1. См. Найти первый уникальный символ для более подробной информации.

Как посчитать инверсии в отсортированном массиве?
Два элемента arr [i] и arr [j] в массиве arr [] образуют инверсию, если a [i]> a [j] и i <j. Как посчитать все инверсии в несортированном массиве. См. Инверсии числа в массиве для всех подходов.

Учитывая большой массив, как эффективно найти в нем k-й по величине элемент?
Для этого может быть много решений. Лучшее решение — использовать минимальную кучу. Мы строим Min Heap MH из первых k элементов. Для каждого элемента, после k-го элемента (от arr [k] до arr [n-1]), сравните его с корнем MH, если элемент больше, чем корень, сделайте его корнем и вызовите heapify для MH, иначе проигнорируйте его , Наконец, MH имеет k самых больших элементов, а корень MH — это k-й по величине элемент. Смотрите k самых больших (или самых маленьких) элементов для более подробной информации.

Дан массив размером n с диапазоном чисел от 1 до n + 1. Массив не содержит дубликатов, отсутствует один номер, найдите отсутствующий номер.
Там может быть много способов решить это. Лучше всего использовать XOR. См. Поиск недостающего номера для деталей. Существует много вариантов этой проблемы, например, найти два повторяющихся числа , найти пропущенное и повторяющееся число и т. Д.

Как написать эффективный метод для расчета х поднять до степени п?
Идея состоит в том, чтобы использовать делить завоевателя здесь, чтобы сделать это за O (Logn) время. См. Написать программу на C для вычисления pow (x, n) для более подробной информации.

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

Дан ряд из n монет значений v1. , , vn, где n четное. Мы играем в игру против оппонента, чередуя ходы. В каждом ходу игрок выбирает первую или последнюю монету из ряда, навсегда удаляет ее из ряда и получает ценность монеты. Определите максимально возможную сумму денег, которую мы можем определенно выиграть, если будем двигаться первым.
Это также вопрос динамического программирования. Посмотрите Оптимальную Стратегию для Игры для получения дополнительной информации.

Вам дан массив отсортированных слов на произвольном языке, вам нужно найти порядок (или приоритет символов) в языке. Например, если заданы массивы {«baa», «abcd», «abca», «cab», «cad»}, то порядок символов «b», «d», «a», «c». Обратите внимание, что слова сортируются и в данном языке «baa» предшествует «abcd», поэтому «b» перед «a» в выводе. Точно так же мы можем найти другие заказы.
Это можно решить, выполнив два шага: сначала создайте граф, обработав заданный набор слов, затем выполните топологическую сортировку созданного графа. См. Это для получения дополнительной информации.

Вам также может понравиться

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

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

Часто задаваемые вопросы об алгоритме интервью | Комплект 1

0.00 (0%) 0 votes