Issue # 39: IT training - current issues and challenges from leading companies

Greetings! We filmed a new issue with tasks aimed at increasing brain neuroplasticity.

Inspired by job interviews at American Walmart. Well, are you ready to move the gyrus?

Answers to problems from the previous issue have already been published. Check.

Questions

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 liter jug (the jugs can be filled any number of times with water, and they can be emptied any number of times).

Transfer

There are two jugs (initially empty) each of 4 and 3 liters, respectively, without any dimensional signs. How many minimum steps are required in order to pour 2 liters of water into a 4-liter jug (jugs can be filled with water and 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?

Transfer

Geek asks the cashier to pay 200 rupees for a cool program written by himself. He asks the cashier to pay only as follows:

A few banknotes of 1 Rupee. Let X.
A few banknotes of 2 Rupees. You need ten times more than 1 rupee banknote, that is 10x.
The remaining money in the form of banknotes of 5 rupees (the minimum number of banknotes of 5 rupees should be used)

How is the cashier going to pay?

Tasks

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

Transfer

Given a string of length S. Turn the entire line without interchanging individual words in it. Words are separated by dots.

Input:

The first line contains Tdenoting the number of test sets. Each test contains an S string containing characters.

Conclusion:

For each test case, in a new line print one line containing an inverted line.

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

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

Conclusion:
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.

Transfer

Dan array arr of N integers. Find the adjacent sub-array with the maximum sum.

Input:

The first line of input contains an integer T, indicating the number of tests. Description of tests t as follows. The first line of each test case contains a single integer N, indicating the size of the array. The second line contains N integers, separated by spaces A1, A2, ..., Denoting the elements of the array.

Conclusion:

Print the maximum amount of the adjacent subtree in a separate line for each test.

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

Example:
Enter
2 5 1 2 3 -2 5 4 -1 -2 -3 -4
Conclusion
9 -1

Explanation:
Example 1: maximum subarray is the sum of 9 elements (1, 2, 3, -2, 5) which is a continuous 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

Transfer

Ugly numbers are numbers for which the only prime factors are 2, 3, or 5. Sequence: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. By agreement, the unit is included. Write a program to find the nth ugliest number.

Input:

The first line of input contains an integer T, indicating the number of tests. For each test case, there is one input line containing the number N.

Conclusion:

Print the Nth “ugly” number.

Limitations:
1 ≤ T ≤ 104 1 ≤ N ≤ 104

Example:
Input:
2 10 4
Conclusion:
12 4

Answers to the tasks will be given during the next week - have time to solve it. Good luck