Рубрики

Интервью Microsoft | 14

Меня зовут Рави Чандра. Сегодня я посетил интервью с Microsoft в Бангалоре. Я был направлен консультантом. Интервью были проведены для различных должностей в различных командах в центре развития Хайдарабада.

Я не смог очистить первый раунд. Но позвольте мне поделиться с читателями geeksforgeeks вопросом, с которым я столкнулся.

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

Изначально я дал решение для hashmap. Но он сказал, что операции с хэш-картой являются дорогостоящими из-за коллизий и т. Д., И попросил меня предоставить лучшее решение. Я предложил линейный поиск. Но он хочет лучший алгоритм поиска.

К сожалению, лучший ответ поразил меня, когда я вышел из комнаты для интервью.

Это решение таково. Предположим, что каждая запись контакта имеет уникальное значение индекса. Давайте сохраним два отсортированных массива индексов, один на основе телефонных номеров и один на основе имен. Таким образом, используемое пространство меньше, и поиск выполняется в O (log n).

Вот некоторые мысли модераторов:

Поскольку телефон имеет ограниченные возможности, количество контактов также ограничено, обычно от 500 до 1000 контактов. И длина контакта будет ограничена, допустим, это 64 символа.

Телефон содержит как минимум два типа памяти: флэш-память и оперативную память. Flash хранит программное обеспечение и постоянные данные. ОЗУ используется для обработки.

Существуют различные структуры данных для реализации эффективного поиска. Количественно, согласно нашему гипотетическому телефону с 1000 контактами, каждый из которых имеет длину 64 символа, нам нужно [1000 * 64 * Nodesize] для дерева (приближение). Это порядка нескольких килобайтных байтов. Где, как у нас обычно есть оперативная память в несколько мегабайт.

Если Trie кажется дорогостоящим для запланированной оперативной памяти, мы можем использовать троичный или сжатый Trie. Или даже мы можем использовать основанный на основаниях поиск, как кто-то указал.

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

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

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

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

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

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

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

Интервью Microsoft | 14

0.00 (0%) 0 votes