Ac0olA Mar 5 2020 at 21:59

Выпуск#32: ITренировка — актуальные вопросы и задачи от ведущих компаний

5 min

2.6K

Spice IT Recruitment corporate blogEntertaining tasksProgramming*

Привет, дорогие читатели. Мы вновь и вновь радуем Вас новой подборкой интересных вопросов и задачек с собеседований в ведущие IT-компании!

Кстати, ответы на задачки из прошлого выпуска уже опубликованы!

Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства Spice IT.

На этой неделе мы собрали задачи с собеседований в индийскую компанию MakeMyTrip.

Вопросы

1. 10 Coins Puzzle

You are blindfolded and 10 coins are place in front of you on table. You are allowed to touch the coins, but can’t tell which way up they are by feel. You are told that there are 5 coins head up, and 5 coins tails up but not which ones are which.

Can you make two piles of coins each with the same number of heads up? You can flip the coins any number of times.

Перевод

Вам завязывают глаза и кладут 10 монет на стол перед вами. Вы можете трогать монеты, но на ощупь вы не можете определить, какой из сторон вверх лежат монеты. Вам говорят, что есть 5 монет, лежащих аверсом («решкой») вверх и 5 монет, лежащих реверсом («орлом») вверх, но какие именно — не сказано.

Можете ли вы сделать две кучки монет с одинаковым количеством монет, лежащих аверсом вверх? Вы можете перевернуть монеты любое количество раз.

2. Newspaper Puzzle

A newspaper made of 16 large sheets of paper folded in half. The newspaper has 64 pages altogether. The first sheet contains pages 1, 2, 63, 64.

If we pick up a sheet containing page number 45. What are the other pages that this sheet contains?

Перевод

Газета состоит из 16 больших листов бумаги, сложенных пополам. Всего в газете 64 страницы. Первый лист содержит страницы 1, 2, 63, 64.

* газета сложена пополам

Если мы возьмем лист, содержащий номер страницы 45. Какие еще страницы содержит этот лист?

Задачи

1. Transpose of Matrix

Write a program to find transpose of a square matrix mat[][] of size N*N. Transpose of a matrix is obtained by changing rows to columns and columns to rows.

Input:
The first line of input contains an integer T, denoting the number of testcases. Then T test cases follow. Each test case contains an integer N, denoting the size of the square matrix. Then in the next line are N*N space separated values of the matrix.

Output:
For each test case output will be the space separated values of the transpose of the matrix

Constraints:
1 <= T <= 15 1 <= N <= 20 -103 <= mat[i][j] <= 103

Example:
Input:
2 4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 2 1 2 -9 -2

Output:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 -9 2 -2

Explanation:
Testcase 1: The matrix after rotation will be: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4.

Перевод

Напишите программу, чтобы найти транспонирование квадратной матрицы mat[][] размера N*N. Транспонирование матрицы получается путем изменения строк на столбцы и столбцов на строки.

Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестовых наборов. Затем следуют T тестовых наборов. Каждый тестовый набор содержит целое число N, обозначающее размер квадратной матрицы. Затем в следующей строке через пробел записываются N*N значений матрицы.

Выход:
Для каждого теста выходными данными будут разделенные пробелами значения транспонирования матрицы

Ограничения:

1 < = T <= 15

1 < = N <= 20

-103 < = mat[i] [j] < = 103

Пример:
Ввод:

2

4

1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4

2

1 2 -9 -2

Выход:

1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

1 -9 2 -2

Объяснение:
Тест 1: матрица после транспонирования будет: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4.

2. Trailing zeroes in factorial

For an integer n find number of trailing zeroes in n!.

Input:
The first line contains an integer 'T' denoting the total number of test cases. In each test cases, it contains an integer 'N'.

Output:
In each seperate line output the answer to the problem.

Constraints:
1 <= T <= 100 1 <= N <= 1000

Example:
Input:
1 9
Output:
1

Перевод

Для целого числа n найдите количество нулей на конце числа n!.

Ввод:
Первая строка содержит целое число 'T', обозначающее общее число тестов. В каждом тесте содержится целое число 'N'.

Выход:
В каждой отдельной строке выведите ответ на задачу.

Ограничения:

1 < = T <= 100

1 < = N < = 1000

Пример:
Ввод:

1

9

Выход:
1

3. Steps by Knight

Given a square chessboard of N x N size, the position of Knight and position of a target is given. We need to find out minimum steps a Knight will take to reach the target position.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the square chessboard. The next line contains the X-Y coordinates of the knight. The next line contains the X-Y coordinates of the target.

Output:
Print the minimum steps the Knight will take to reach the target position.

Constraints:
1<=T<=100 1<=N<=20 1<=knight_pos,targer_pos<=N

Example:
Input:
2 6 4 5 1 1 20 5 7 15 20

Output:
3 9

Перевод

На квадратной шахматной доске размером N x N задается положение коня и положение цели. Нам нужно выяснить, какие минимальные шаги сделает конь, чтобы достичь цели.

Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестов. Затем следуют T тестов. Каждый тест содержит целое число n, обозначающее размер квадратной шахматной доски. Следующая строка содержит координаты X-Y коня. Следующая строка содержит координаты X-Y цели.

Выход:
Выведите минимальные шаги, которые конь сделает, чтобы достичь целевой позиции.

Ограничения:

1<=T<=100

1<=N<=20

1<=knight_pos,targer_pos<=N

Пример:
Ввод:

Выход:

3

9

Ответы

Вопрос 1

ОТВЕТ: Да.
Объяснение:
Сделайте 2 кучки с равным количеством монет. Теперь переверните все монеты в одной из кучек.

Давайте рассмотрим простой случай:
А — аверс, Р — реверс.
Кучка 1: А Р Р Р Р
Кучка 2: А А А А Р

Перевернём все монеты в кучке 1.
Кучка 1: Р А А А А
Кучка 2: А А А А Р

В обоих кучках получилось равное количество аверсов.

Вопрос 2

На обратной стороне 45-ой страницы расположена страница 46. Страницы таковы, что для каждой страницы P, 65-p будет также на той же странице.

Поэтому,
65-45 = 20
65-46 = 19

Итак, четыре страницы на этом листе — 19, 20, 45, 46.

Задача 1

O(1) решение:

import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
 {
	public static void main (String[] args)
	 {
	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	 try{
	     int testCases = Integer.parseInt(br.readLine());
	     while(testCases-->0){
	         int size = Integer.parseInt(br.readLine());
	         int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
	         int num = 0;
	         int i=0;
	         int total = size*size;
	         
	         while(num<total && i<size){
	             if(num >= size*(size-1)) { 
	                System.out.print(arr[num] + " ");
	                i++;
	                num = i;
	             }
	             else {
	             System.out.print(arr[num] + " ");
	             num+=size;
	             }
	         }
	         System.out.println();
	     }
	 }
	 catch (Exception e){
	     e.printStackTrace();
	 }
	 }
}

Задача 2

import math
for _ in range(int(input())):
n=math.factorial(int(input()))
print(len(str(n))-len(str(n).rstrip("0")))

Задача 3

#include<bits/stdc++.h>
using namespace std;

void bfs(bool visited[20][20],int n,int x,int y,int X,int Y,int& count){
    queue<pair<int,int>>q;
    visited[x-1][y-1]=true;
    q.push(make_pair(x,y));
    q.push(make_pair(0,0));
    while(q.size()>1){
        x=q.front().first;
        y=q.front().second;
        if(q.front().first==0 && q.front().second==0){
            q.pop();
            count++;
            q.push(make_pair(0,0));
            continue;
        }
        if(q.front().first==X && q.front().second==Y){
            return;
        }
        if(x>2 && y>1 && visited[x-3][y-2]==false){
            visited[x-3][y-2]=true;
            q.push(make_pair(x-2,y-1));
        }
        if(x>2 && y<n && visited[x-3][y]==false){
            visited[x-3][y]=true;
            q.push(make_pair(x-2,y+1));
        }
        if(x>1 && y<n-1 && visited[x-2][y+1]==false){
            visited[x-2][y+1]=true;
            q.push(make_pair(x-1,y+2));
        }
        if(x<n && y<n-1 && visited[x][y+1]==false){
            visited[x][y+1]=true;
            q.push(make_pair(x+1,y+2));
        }
        if(x<n-1 && y<n && visited[x+1][y]==false){
            visited[x+1][y]=true;
            q.push(make_pair(x+2,y+1));
        }
        if(x<n-1 && y>1 && visited[x+1][y-2]==false){
            visited[x+1][y-2]=true;
            q.push(make_pair(x+2,y-1));
        }
        if(x<n && y>2 && visited[x][y-3]==false){
            visited[x][y-3]=true;
            q.push(make_pair(x+1,y-2));
        }
        if(x>1 && y>2 && visited[x-2][y-3]==false){
            visited[x-2][y-3]=true;
            q.push(make_pair(x-1,y-2));
        }
        q.pop();
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int x,y,X,Y;
        cin>>x>>y>>X>>Y;
        int count=0;
        bool visited[20][20]={false};
        bfs(visited,n,x,y,X,Y,count);
        cout<<count<<'\n';
    }
	return 0;
}

Tags:

Hubs:

Выпуск#32: ITренировка — актуальные вопросы и задачи от ведущих компаний

Вопросы

Задачи

Ответы

Articles

Information