Add task descriptions

omalovichko · Feb 20, 2019 · 83de893 · 83de893
1 parent 283c6c9
commit 83de893
Show file tree

Hide file tree

Showing 20 changed files with 790 additions and 0 deletions.
diff --git a/CodilityLessonsTests/Lesson10_CountFactors.swift b/CodilityLessonsTests/Lesson10_CountFactors.swift
@@ -8,6 +8,28 @@
 
 import XCTest
 
+/*
+ CountFactors
+ Count factors of given number n.
+
+
+ A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M.
+
+ For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).
+
+ Write a function:
+
+ public func solution(_ N : Int) -> Int
+
+ that, given a positive integer N, returns the number of its factors.
+
+ For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [1..2,147,483,647].
+*/
+
 class Lesson10_CountFactors: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson10_MinPerimeterRectangle.swift b/CodilityLessonsTests/Lesson10_MinPerimeterRectangle.swift
@@ -8,6 +8,36 @@
 
 import XCTest
 
+/*
+ MinPerimeterRectangle
+ Find the minimal perimeter of any rectangle whose area equals N.
+
+
+ An integer N is given, representing the area of some rectangle.
+
+ The area of a rectangle whose sides are of length A and B is A * B, and the perimeter is 2 * (A + B).
+
+ The goal is to find the minimal perimeter of any rectangle whose area equals N. The sides of this rectangle should be only integers.
+
+ For example, given integer N = 30, rectangles of area 30 are:
+
+ (1, 30), with a perimeter of 62,
+ (2, 15), with a perimeter of 34,
+ (3, 10), with a perimeter of 26,
+ (5, 6), with a perimeter of 22.
+ Write a function:
+
+ public func solution(_ N : Int) -> Int
+
+ that, given an integer N, returns the minimal perimeter of any rectangle whose area is exactly equal to N.
+
+ For example, given an integer N = 30, the function should return 22, as explained above.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [1..1,000,000,000].
+*/
+
 class Lesson10_MinPerimeterRectangle: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson10_Peaks.swift b/CodilityLessonsTests/Lesson10_Peaks.swift
@@ -8,6 +8,80 @@
 
 import XCTest
 
+/*
+ Peaks
+ Divide an array into the maximum number of same-sized blocks, each of which should contain an index P such that A[P - 1] < A[P] > A[P + 1].
+
+
+ A non-empty array A consisting of N integers is given.
+
+ A peak is an array element which is larger than its neighbors. More precisely, it is an index P such that 0 < P < N − 1,  A[P − 1] < A[P] and A[P] > A[P + 1].
+
+ For example, the following array A:
+
+ A[0] = 1
+ A[1] = 2
+ A[2] = 3
+ A[3] = 4
+ A[4] = 3
+ A[5] = 4
+ A[6] = 1
+ A[7] = 2
+ A[8] = 3
+ A[9] = 4
+ A[10] = 6
+ A[11] = 2
+ has exactly three peaks: 3, 5, 10.
+
+ We want to divide this array into blocks containing the same number of elements. More precisely, we want to choose a number K that will yield the following blocks:
+
+ A[0], A[1], ..., A[K − 1],
+ A[K], A[K + 1], ..., A[2K − 1],
+ ...
+ A[N − K], A[N − K + 1], ..., A[N − 1].
+ What's more, every block should contain at least one peak. Notice that extreme elements of the blocks (for example A[K − 1] or A[K]) can also be peaks, but only if they have both neighbors (including one in an adjacent blocks).
+
+ The goal is to find the maximum number of blocks into which the array A can be divided.
+
+ Array A can be divided into blocks as follows:
+
+ one block (1, 2, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2). This block contains three peaks.
+ two blocks (1, 2, 3, 4, 3, 4) and (1, 2, 3, 4, 6, 2). Every block has a peak.
+ three blocks (1, 2, 3, 4), (3, 4, 1, 2), (3, 4, 6, 2). Every block has a peak. Notice in particular that the first block (1, 2, 3, 4) has a peak at A[3], because A[2] < A[3] > A[4], even though A[4] is in the adjacent block.
+ However, array A cannot be divided into four blocks, (1, 2, 3), (4, 3, 4), (1, 2, 3) and (4, 6, 2), because the (1, 2, 3) blocks do not contain a peak. Notice in particular that the (4, 3, 4) block contains two peaks: A[3] and A[5].
+
+ The maximum number of blocks that array A can be divided into is three.
+
+ Write a function:
+
+ public func solution(_ A : inout [Int]) -> Int
+
+ that, given a non-empty array A consisting of N integers, returns the maximum number of blocks into which A can be divided.
+
+ If A cannot be divided into some number of blocks, the function should return 0.
+
+ For example, given:
+
+ A[0] = 1
+ A[1] = 2
+ A[2] = 3
+ A[3] = 4
+ A[4] = 3
+ A[5] = 4
+ A[6] = 1
+ A[7] = 2
+ A[8] = 3
+ A[9] = 4
+ A[10] = 6
+ A[11] = 2
+ the function should return 3, as explained above.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [1..100,000];
+ each element of array A is an integer within the range [0..1,000,000,000].
+*/
+
 class Lesson10_Peaks: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson15_AbsDistinct.swift b/CodilityLessonsTests/Lesson15_AbsDistinct.swift
@@ -8,6 +8,45 @@
 
 import XCTest
 
+/*
+ AbsDistinct
+ Compute number of distinct absolute values of sorted array elements.
+
+
+ A non-empty array A consisting of N numbers is given. The array is sorted in non-decreasing order. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.
+
+ For example, consider array A such that:
+
+ A[0] = -5
+ A[1] = -3
+ A[2] = -1
+ A[3] =  0
+ A[4] =  3
+ A[5] =  6
+ The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.
+
+ Write a function:
+
+ public func solution(_ A : inout [Int]) -> Int
+ that, given a non-empty array A consisting of N numbers, returns absolute distinct count of array A.
+
+ For example, given array A such that:
+
+ A[0] = -5
+ A[1] = -3
+ A[2] = -1
+ A[3] =  0
+ A[4] =  3
+ A[5] =  6
+ the function should return 5, as explained above.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [1..100,000];
+ each element of array A is an integer within the range [−2,147,483,648..2,147,483,647];
+ array A is sorted in non-decreasing order.
+*/
+
 class Lesson15_AbsDistinct: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson16_MaxNonoverlappingSegments.swift b/CodilityLessonsTests/Lesson16_MaxNonoverlappingSegments.swift
@@ -8,6 +8,45 @@
 
 import XCTest
 
+/*
+ MaxNonoverlappingSegments
+ Find a maximal set of non-overlapping segments.
+
+
+ Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in arrays A and B. For each I (0 ≤ I < N) the position of segment I is from A[I] to B[I] (inclusive). The segments are sorted by their ends, which means that B[K] ≤ B[K + 1] for K such that 0 ≤ K < N − 1.
+
+ Two segments I and J, such that I ≠ J, are overlapping if they share at least one common point. In other words, A[I] ≤ A[J] ≤ B[I] or A[J] ≤ A[I] ≤ B[J].
+
+ We say that the set of segments is non-overlapping if it contains no two overlapping segments. The goal is to find the size of a non-overlapping set containing the maximal number of segments.
+
+ For example, consider arrays A, B such that:
+
+ A[0] = 1    B[0] = 5
+ A[1] = 3    B[1] = 6
+ A[2] = 7    B[2] = 8
+ A[3] = 9    B[3] = 9
+ A[4] = 9    B[4] = 10
+ The segments are shown in the figure below.
+
+
+
+ The size of a non-overlapping set containing a maximal number of segments is 3. For example, possible sets are {0, 2, 3}, {0, 2, 4}, {1, 2, 3} or {1, 2, 4}. There is no non-overlapping set with four segments.
+
+ Write a function:
+
+ public func solution(_ A : inout [Int], _ B : inout [Int]) -> Int
+ that, given two arrays A and B consisting of N integers, returns the size of a non-overlapping set containing a maximal number of segments.
+
+ For example, given arrays A, B shown above, the function should return 3, as explained above.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [0..30,000];
+ each element of arrays A, B is an integer within the range [0..1,000,000,000];
+ A[I] ≤ B[I], for each I (0 ≤ I < N);
+ B[K] ≤ B[K + 1], for each K (0 ≤ K < N − 1).
+*/
+
 class Lesson16_MaxNonoverlappingSegments: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson16_TieRopes.swift b/CodilityLessonsTests/Lesson16_TieRopes.swift
@@ -8,6 +8,60 @@
 
 import XCTest
 
+/*
+ TieRopes
+ Tie adjacent ropes to achieve the maximum number of ropes of length >= K.
+
+
+ There are N ropes numbered from 0 to N − 1, whose lengths are given in an array A, lying on the floor in a line. For each I (0 ≤ I < N), the length of rope I on the line is A[I].
+
+ We say that two ropes I and I + 1 are adjacent. Two adjacent ropes can be tied together with a knot, and the length of the tied rope is the sum of lengths of both ropes. The resulting new rope can then be tied again.
+
+ For a given integer K, the goal is to tie the ropes in such a way that the number of ropes whose length is greater than or equal to K is maximal.
+
+ For example, consider K = 4 and array A such that:
+
+ A[0] = 1
+ A[1] = 2
+ A[2] = 3
+ A[3] = 4
+ A[4] = 1
+ A[5] = 1
+ A[6] = 3
+ The ropes are shown in the figure below.
+
+
+
+ We can tie:
+
+ rope 1 with rope 2 to produce a rope of length A[1] + A[2] = 5;
+ rope 4 with rope 5 with rope 6 to produce a rope of length A[4] + A[5] + A[6] = 5.
+ After that, there will be three ropes whose lengths are greater than or equal to K = 4. It is not possible to produce four such ropes.
+
+ Write a function:
+
+ public func solution(_ K : Int, _ A : inout [Int]) -> Int
+
+ that, given an integer K and a non-empty array A of N integers, returns the maximum number of ropes of length greater than or equal to K that can be created.
+
+ For example, given K = 4 and array A such that:
+
+ A[0] = 1
+ A[1] = 2
+ A[2] = 3
+ A[3] = 4
+ A[4] = 1
+ A[5] = 1
+ A[6] = 3
+ the function should return 3, as explained above.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [1..100,000];
+ K is an integer within the range [1..1,000,000,000];
+ each element of array A is an integer within the range [1..1,000,000,000].
+*/
+
 class Lesson16_TieRopes: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson17_NumberSolitaire.swift b/CodilityLessonsTests/Lesson17_NumberSolitaire.swift
@@ -8,6 +8,57 @@
 
 import XCTest
 
+/*
+ NumberSolitaire
+ In a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6.
+
+
+ A game for one player is played on a board consisting of N consecutive squares, numbered from 0 to N − 1. There is a number written on each square. A non-empty array A of N integers contains the numbers written on the squares. Moreover, some squares can be marked during the game.
+
+ At the beginning of the game, there is a pebble on square number 0 and this is the only square on the board which is marked. The goal of the game is to move the pebble to square number N − 1.
+
+ During each turn we throw a six-sided die, with numbers from 1 to 6 on its faces, and consider the number K, which shows on the upper face after the die comes to rest. Then we move the pebble standing on square number I to square number I + K, providing that square number I + K exists. If square number I + K does not exist, we throw the die again until we obtain a valid move. Finally, we mark square number I + K.
+
+ After the game finishes (when the pebble is standing on square number N − 1), we calculate the result. The result of the game is the sum of the numbers written on all marked squares.
+
+ For example, given the following array:
+
+ A[0] = 1
+ A[1] = -2
+ A[2] = 0
+ A[3] = 9
+ A[4] = -1
+ A[5] = -2
+ one possible game could be as follows:
+
+ the pebble is on square number 0, which is marked;
+ we throw 3; the pebble moves from square number 0 to square number 3; we mark square number 3;
+ we throw 5; the pebble does not move, since there is no square number 8 on the board;
+ we throw 2; the pebble moves to square number 5; we mark this square and the game ends.
+ The marked squares are 0, 3 and 5, so the result of the game is 1 + 9 + (−2) = 8. This is the maximal possible result that can be achieved on this board.
+
+ Write a function:
+
+ public func solution(_ A : inout [Int]) -> Int
+
+ that, given a non-empty array A of N integers, returns the maximal result that can be achieved on the board represented by array A.
+
+ For example, given the array
+
+ A[0] = 1
+ A[1] = -2
+ A[2] = 0
+ A[3] = 9
+ A[4] = -1
+ A[5] = -2
+ the function should return 8, as explained above.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [2..100,000];
+ each element of array A is an integer within the range [−10,000..10,000].
+*/
+
 class Lesson17_NumberSolitaire: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson8_Dominator.swift b/CodilityLessonsTests/Lesson8_Dominator.swift
@@ -8,6 +8,38 @@
 
 import XCTest
 
+/*
+ Dominator
+ Find an index of an array such that its value occurs at more than half of indices in the array.
+
+
+ An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.
+
+ For example, consider array A such that
+
+ A[0] = 3    A[1] = 4    A[2] =  3
+ A[3] = 2    A[4] = 3    A[5] = -1
+ A[6] = 3    A[7] = 3
+ The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.
+
+ Write a function
+
+ public func solution(_ A : inout [Int]) -> Int
+ that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.
+
+ For example, given array A such that
+
+ A[0] = 3    A[1] = 4    A[2] =  3
+ A[3] = 2    A[4] = 3    A[5] = -1
+ A[6] = 3    A[7] = 3
+ the function may return 0, 2, 4, 6 or 7, as explained above.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [0..100,000];
+ each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
+*/
+
 class Lesson8_Dominator: XCTestCase {
 
     func test() {