Выпуск#32: 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.

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?

Задачи

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.

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

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

Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!