There is a forum that has a limit of K characters per entry. In this task your job is to implement an algorithm for cropping messages that are too long. You are given a message, consisting of English alphabet letters and spaces, that might be longer than the limit. Your algorithm should crop a number of words from the end of the message, keeping in mind that:
- it may not crop away part of a word;
- the output message may not end with a space;
- the output message may not exceed the K-character limit;
- the output message should be as long as possible.
This means that, in some cases, the algorithm may need to crop away the entire message, outputting an empty string.
For example, given the text:
"Codility We test coders"
With K = 14 the algorithm should output:
"Codility We"
Note that:
- the output "Codility We te" would be incorrect, because the original message is cropped through the middle of a word;
- the output "Codility We " would be incorrect, because it ends with a space;
- the output "Codility We test coders" would be incorrect, because it exceeds the K-character limit;
- the output "Codility" would be incorrect, because it is shorter than the correct output.
Write a function
class Solution { public String solution(String message, int K); }
which, given a message and an integer K, returns the message cropped to no more than K characters, as described above.
Examples:
1. Given message = "Codility We test coders" and K = 14, the function should return "Codility We".
2. Given message = "Why not" and K = 100, the function should return "Why not".
3. Given message = "The quick brown fox jumps over the lazy dog" and K = 39, the function should return "The quick brown fox jumps over the lazy".
4. Given message = "To crop or not to crop" and K = 21, the function should return "To crop or not to".
Assume that:
- K is an integer within the range [1..500];
- message is a non-empty string containing at most 500 English alphabet letters and spaces. There are no spaces at the beginning or at the end of message; also there can't be two or more consecutive spaces in message.
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.
An industrial company has N factories, each producing some pollution every month. The company has decided to reduce its total fume emissions by equipping some of the factories with one or more filters.
Every such filter reduces the pollution of a factory by half. When a second (or subsequent) filter is applied, it again reduces by half the remaining pollution emitted after fitting the existing filter(s). For example, a factory that initially produces 6 units of pollution will generate 3 units with one filter, 1.5 units with two filters and 0.75 units with three filters.
You are given an array of N integers describing the amount of pollution produced by the factories. Your task is to find the minimum number of filters needed to decrease the total sum of pollution by at least half.
Write a function:
class Solution { public int solution(int[] A); }
which, given an array of integers A of length N, returns the minimum number of filters needed to reduce the total pollution by at least half.
Examples:
1. Given A = [5, 19, 8, 1], your function should return 3. The initial total pollution is 5 + 19 + 8 + 1 = 33. We install two filters at the factory producing 19 units and one filter at the factory producing 8 units. Then the total pollution will be 5 + ((19 / 2) / 2) + (8 / 2) + 1 = 5 + 4.75 + 4 + 1 = 14.75 which is less than 33 / 2 = 16.5, so we have achieved our goal.
2. Given A = [10, 10], your function should return 2, because we may install one filter at each factory.
3. Given A = [3, 0, 5], your function should return 2, because it is sufficient to install one filter at each factory producing a non-zero amount of pollution.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..30,000];
- each element of array A is an integer within the range [0..70,000].
A group of friends is going on holiday together. They have come to a meeting point (the start of the journey) using N cars. There are P[K] people and S[K] seats in the K-th car for K in range [0..N-1]. Some of the seats in the cars may be free, so it is possible for some of the friends to change the car they are in. The friends have decided that, in order to be ecological, they will leave some cars parked at the meeting point and travel with as few cars as possible.
Write a function:
class Solution { public int solution(int[] P, int[] S); }
that, given two arrays P and S, consisting of N integers each, returns the minimum number of cars needed to take all of the friends on holiday.
Examples:
1. Given P = [1, 4, 1] and S = [1, 5, 1], the function should return 2. A person from car number 0 can travel in car number 1 instead. This way, car number 0 can be left parked at the meeting point.
2. Given P = [4, 4, 2, 4] and S = [5, 5, 2, 5], the function should return 3. One person from car number 2 can travel in car number 0 and the other person from car number 2 can travel in car number 3.
3. Given P = [2, 3, 4, 2] and S = [2, 5, 7, 2], the function should return 2. Passengers from car number 0 can travel in car number 1 and passengers from car number 3 can travel in car number 2.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of arrays P and S is an integer within the range [1..9];
- every friend had a seat in the car they came in; that is, P[K] ≤ S[K] for each K within the range [0..N-1].