Олька (olgak) wrote in rabota_il,
Олька
olgak
rabota_il

Вопросы в Google. Обсудим?

Базовая телефонная проверка:

1. В какую степень нужно возвести двойку, чтобы получилось 2 гигабайта (быстро, без калькулятора)?

2. Какой оператор C++ нужно использовать для освобождения массива, созданного с помощью ”new char[10]”?

3. Расположите процессы в порядке убывания их скорости, от самого быстрого до самого медленного:
a. чтение из регистра процессора
b. переключение контекста
c. считывание с диска
d. считывание из оперативной памяти

Алгоритмы и структуры данных:

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

2. Напишите функцию, которая определит, является ли её аргумент степенью двойки. А теперь без циклов.

3. Напишите функцию, которая найдёт K-й наименьший элемент в бинарном дереве (binary search tree).

4. Расположите алгоритмы в порядке убывания вычислительной сложности:
a. перемножение двух матриц
b. сортировка вставкой (insertion sort)
c. двоичный поиск (binary search)
d. heap sort

C/C++:

1. Когда лучше использовать C, а когда - C++?

2. Как бы вы реализовали Unix-утилиту "tail" (она возвращает N последних строк в файле). Какую структуру данных использовали бы? Есть ли структура данных, которая поддерживала бы заданное количество элементов автоматически? Как бы вы реализовали это в C++? Какие C-функции по перемещению файлового указателя (file pointer) и определения размера файла вы знаете?

3. В чем разница между malloc и calloc?

4. Зачем нужны виртуальные деструкторы?

5. Как бы вы убили все HTTPD процессы на Unix-машине? Как бы вы скормили список параметров Unix-утилите вроде ”kill”?

6. Что напечатает нижеследующая программа?

int *f(int n)
{
int r = n + 1;
return &r;
}

int main()
{
int *n1 = f(1);
int *n2 = f(2);
return printf(”%d”, *n1);
}

Алгоритмы и стуктуры данных:

1. Назовите самую интересную и значимую проблему из решенных вами.

2. Сортированный массив циклически сдвинули неизвестное число раз. Как найти элемент в таком массиве? Как это сделать за логарифмическое время?

3. Какие структуры данных можно использовать для хранения разного рода словарей? Когда вы использовали бы ту или иную? Можете ли вы сконструировать структуру данных, имеющую среднее время выборки O(1), а наихудшее - O(log n)?

4. Есть прямоугольная матрица, где числа в каждой строке и каждом столбце упорядочены (например, по возрастанию). Как бы вы искали число в такой матрице? Можете ли вы сделать это за линейное время? А за логарифмическое?

Очные интервью ("программирование у доски"):

1. Как бы вы нашли одинаковые элементы в N сортированных связанных списках?

2. Представьте, что есть массив из N=1000 элементов. Число N растёт, увеличиваясь на единицу на каждом шаге. После каждого шага в массиве должно остаться ровно k=1000 помеченных элементов и N-k непомеченных. Каждый из N элементов имеет одинаковую вероятность быть помеченным. Не зная финального значения N (допустим, что N растет бесконечно), как можно эффективно обеспечивать выполнение вышеуказанных правил о пометке на каждом шаге? Определите сложность предлагаемых решений.

3. Представьте, что у вас есть строка ”putinsayshewantstoboosteconomy” (без пробелов). Спроектируйте алгоритм расстановки пробелов в нужные места (т.е. извлечения отдельных слов из текста)? Какая структура данных особенно эффективна для этой цели? Оцените максимум и минимум требуемого места. Как выбрать из нескольких возможных вариантов разбиения? Где можно получить необходимую для этого информацию, и как?

4. Если у вас есть строка из N символов, сколько есть способов разбить её на отдельные "слова"?

5. Объясните простыми словами самое крутое, что вы сделали на вашей предыдущей (нынешней) работе.

6. Пользователь ввел поисковый запрос из N ключевых слов. У вас есть N списков (по одному на каждое ключевое слово), в которых хранятся смещения от начала документа, где это слово встречается. Списки отсортированы. Спроектируйте эффективный алгоритм поиска наименьшего фрагмента документа, содержащего каждое из ключевых слов хотя бы 1 раз? Фактически требуется найти N чисел, по одному из каждого списка, так, чтобы разница между максимальным и минимальным числом была наименьшей. Порядок слов не имеет значения, допускается многократный повтор любого слова в пределах найденного (минимального) фрагмента. Оцените сложность алгоритма. Реализуйте его.

7. Какие вопросы вы задали бы пользователю, если бы проектировали систему кеширования? Какие схемы кеширования (caching policies) вы можете предложить? Как бы вы реализовали каждую из них? Какие методы вы имели бы в классе, реализующем такую систему?


From there: http://sarov.ws/forum/index.php?s=b9b15aaba0b0445c9fb0e7d5467eb0b5&showtopic=946&pid=6479&st=0&#entry6479
Subscribe

Recent Posts from This Community

  • Product Designer in Jerusalem

    Product Designer in Jerusalem. Our client, a American-based company in Jerusalem, develops IT and innovative solutions in financing sector. We are…

  • Тиум мас

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

  • (без темы)

    Порекомендуйте, пожалуйста, хорошую уборщицу в Тель-Авиве (Яффо).

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 5 comments