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

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

Ответы на задачки из прошлого выпуска уже опубликованы. Сверяйтесь.

Вопросы

1. Fill the Jug

There are two empty jugs each of 4 and 3 liters respectively, without any measuring marks. How many minimum steps are required to have 2 liters of water into the 4 litre jug (the jugs can be filled any number of times with water, and they can be emptied any number of times).

2. Geek and Cashier

A Geek asks a cashier to pay Rs 200 for a cool program written by him. He asks the cashier to pay only in the following way:

• Few 1 Rs Notes. Let x.
• Few 2 Rs Notes. Must ten times of 1 Rs Notes, i.e., 10x.
• Rest of the money as 5 Rs Notes(Minimum number Rs 5 notes should be used)

How does the Geek’s Cashier plan to pay?

Задачи

1. Reverse words in a given string

Given a String of length S, reverse the whole string without reversing the individual words in it. Words are separated by dots.

Input:
The first line contains T denoting the number of testcases. T testcases follow. Each case contains a string S containing characters.

Output:
For each test case, in a new line, output a single line containing the reversed String.

Constraints:
1 <= T <= 100
1 <= |S| <= 2000

Example:
Input:
2
i.like.this.program.very.much
pqr.mno

Output:
much.very.program.this.like.i
mno.pqr

2. Kadane’s Algorithm

Given an array arr of N integers. Find the contiguous sub-array with maximum sum.

Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A1, A2, …, AN denoting the elements of the array.

Output:
Print the maximum sum of the contiguous sub-array in a separate line for each test case.

Constraints:
1 ≤ T ≤ 110
1 ≤ N ≤ 106
-107 ≤ A[i] <= 107

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

Explanation:
Testcase 1: Max subarray sum is 9 of elements (1, 2, 3, -2, 5) which is a contiguous subarray.

3. Ugly Numbers

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers. By convention, 1 is included. Write a program to find Nth Ugly Number.

Input:
The first line of input contains an integer T denoting the number of test cases. T testcases follow. For each testcase there is one line of input that contains the number N.

Output:
Print the Nth Ugly Number.

Constraints:
1 ≤ T ≤ 104
1 ≤ N ≤ 104

Example:
Input:
2
10
4
Output:
12
4

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