Рубрики

Google Интервью Опыт | Комплект 2 (Вопросы по размещению)

MCQ Вопросы: 20 (+4, -1)
Субъективный вопрос: 1

1) даны четыре матрицы
P = 20 × 10
Q = 10 × 5
R = 5 × 10
S = 10 × 10
Найти минимум нет. умножения требуется для PxQxRxS?
а) 4000
б) 2500
в) 3000
г) ни один из них

2) Даны два массива n-размера. n1 в порядке убывания и n2 в порядке возрастания. Если c1 — временная сложность для n1 с использованием быстрой сортировки, а c2 — временная сложность для n2 с использованием быстрой сортировки. Потом —
а) с1> с2
b) c1 3) Если существует N отсортированный массив, то какова временная сложность нахождения 2 нет, имеющих сумму меньше 1000.
а) О (1)
б) О (п ^ 2)
против)
г) О (логн)

4) Есть какой-то процесс. В каком из алгоритмов планирования использование ЦП является минимальным. Если время ввода-вывода составляет 90 мс, а время загрузки процессора — 10 мс (вопрос очень длинный, чтобы запомнить)

5)

int func(int x, int *y, int **z)
{
  int p, q;
  x += 2;
  p = *y++;
  q = **z++;
  q = **z++; //Not a repeated line.
}
void main()
{
  int a = 5, *b, **c;
  b = &a;
  c = &b;
  printf(“%d”,a);
}

6) Найдите наименее значащую цифру 2 ^ 3 * google, где google = 10 ^ 100.
а) 2
б) 4
в) 6
г) 8

7) Пусть w (n) и A (n) обозначают соответственно время выполнения в наихудшем и среднем случаях алгоритма, выполняемого на входе размера n. что из перечисленного ВСЕГДА ИСТИНА?
а) A (n) = Омега (W (n))
б) A (n) = тета (W (n))
в) A (n) = O (W (n))
d) A (n) = o (W (n))

8) Рассмотрим полный неориентированный граф с множеством вершин {0, 1, 2, 3, 4}. Запись Wij в матрице W ниже — это вес ребра {i, j}.

    0 1 8 1 4
    1 0 12 4 9
W = 8 12 0 7 3
    1 4 7 0 2
    4 9 3 2 0

Каков минимально возможный вес остовного дерева T в этом графе, чтобы вершина 0 была листовым узлом в дереве T?
а) 7
б) 8
в) 9
г) 10

9) В графе, приведенном в вопросе 8, каков минимально возможный вес пути P от вершины 1 до вершины 2 в этом графе, чтобы P содержало не более 3 ребер?
а) 7
б) 8
в) 9
г) 10

10) Хеш-таблица длиной 10 использует открытую адресацию с хеш-функцией h (k) = k mod 10 и линейное зондирование. После вставки 6 значений в пустую хеш-таблицу таблица выглядит так, как показано ниже.

|0|   | 
|1|   |
|2| 42|
|3| 23|
|4| 34|
|5| 52|
|6| 46|
|7| 33|
|8|   |
|9|   |

Какой из следующих вариантов дает возможный порядок, в котором значения ключей могли быть вставлены в таблицу?
а) 46, 42, 34, 52, 23, 33
б) 34, 42, 23, 52, 33, 46
в) 46, 34, 42, 23, 52, 33
г) 42, 46, 33, 23, 34, 52

11) Сколько разных последовательностей вставки значений ключей, использующих одну и ту же хеш-функцию вопроса 10 и линейное зондирование, приведут к хеш-таблице, показанной выше?
а) 10
б) 20
в) 30
г) 40

12) Рекуррентное соотношение, определяющее оптимальное время задачи Ханойской башни с n дисками, имеет вид
а) T (n) = 2T (n — 2) + 2
б) T (n) = 2T (n — 1) + n
c) T (n) = 2T (n / 2) + 1
г) T (n) = 2T (n — 1) + 1

13) Для трех семафоров S0, S1 и S2 инициализируются как S0 = 1, S1 = 0, S2 = 0 и обрабатывают P0, P1 и P2.

P0 : while(true)
P0, P1 and P2.
P0 : while(true)
{
  wait(S0);
  printf(“ 0 “);
  Release(S1);
  Release(S2);
}
P1: while(true)
{
  Wait(S1);
  Release(S2);
}
P2: while(true)
{
  Wait(S2);
  Release(S0);
} 

Узнайте, сколько раз процесс P0 выполняет оператор printf.
а) как минимум дважды
б) ровно один раз
в) ровно в два раза
г) ровно трижды

14) Учитывая следующую программную конструкцию

{
 if ( a == b ) { S1; exit(); }
 else if ( c==d ) { S2; }
 else { S3; exit(); }
 S4;
} 

Учитывая 4 теста, выясните, какой из следующих пунктов охватывает все 4 утверждения
T1: a, b, c и d одинаковы.
T2: a, b, c и d все различны.
T3: a == b и c! = D.
T4: a! = B и c == d.
а) Т1, Т2 и Т3;
б) Т1, Т4.
в) Т2, Т4.
г) Т1, Т2 и Т4.

15) Какие из следующих утверждений верны?
I. Самое короткое оставшееся время первого планирования может вызвать голод
II. Упреждающее планирование может вызвать голод
III. Round Robin лучше, чем FCFS с точки зрения времени отклика
а) я только
б) только я и III
в) только II и III
г) I, II и III

16) Последовательности доступа к логическим страницам:
1 2 3 2 4 1 3 2 4 1
Реализованы оптимальные методы замены LRU, FIFO Page.
Тогда нет. ошибок страницы в:
а) Оптимальный 17) Найти нет. сбоев страниц для техники замены оптимальных страниц в данной последовательности вопросов №. 16.
а) 5
б) 6
в) 7
г) 8

18) С учетом простого графа из 6 узлов (заметьте, это простой граф), укажите, какой из следующих пунктов является набором допустимых степеней графа.
а) 4,4,1,1,1,1
б) 4,4,2,1,1,1
в) 4,4,2,2,1,1
г) нет

19)

gcd(n,m)
{
  if (n%m == 0)
    return n;
  n = n%m;
  return gcd ( m, n);
} 

Какова сложность вычисления gcd (n, m) в худшем случае?
а) O (lgn)
б) О (ЛГМ)
в) O (LG (LGG))
d) O (lg (lgm))

20)

void f(char * x)
{
  x++;
  *x = 'a';
}
int main()
{
  char * str = "hello";
  f(str);
  cout 

a) hello
b) hallo
c) allo
d) empty string

SECTION B – Subjective Question
A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. Find all the distinct tours of a knight placed on (x,y) of a NxN chessboard.
X,Y Knight can go to 8 positions.(default rule). Write a running code.

These questions are contributed by Harshit Gupta. If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

All Practice Problems for Google !

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

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

Google Интервью Опыт | Комплект 2 (Вопросы по размещению)

0.00 (0%) 0 votes