Add task descriptions

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

Hide file tree

Showing 12 changed files with 417 additions and 2 deletions.
diff --git a/CodilityLessonsTests/Lesson5_CountDiv.swift b/CodilityLessonsTests/Lesson5_CountDiv.swift
@@ -8,6 +8,26 @@
 
 import XCTest
 
+/*
+ CountDiv
+ Compute number of integers divisible by k in range [a..b].
+
+
+ Write a function:
+
+ public func solution(_ A : Int, _ B : Int, _ K : Int) -> Int
+ that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:
+
+ { i : A ≤ i ≤ B, i mod K = 0 }
+ For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.
+
+ Write an efficient algorithm for the following assumptions:
+
+ A and B are integers within the range [0..2,000,000,000];
+ K is an integer within the range [1..2,000,000,000];
+ A ≤ B.
+*/
+
 class Lesson5_CountDiv: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson5_GenomicRangeQuery.swift b/CodilityLessonsTests/Lesson5_GenomicRangeQuery.swift
@@ -8,6 +8,48 @@
 
 import XCTest
 
+/*
+ GenomicRangeQuery
+ Find the minimal nucleotide from a range of sequence DNA.
+
+
+ A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?
+
+ The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).
+
+ For example, consider string S = CAGCCTA and arrays P, Q such that:
+
+ P[0] = 2    Q[0] = 4
+ P[1] = 5    Q[1] = 5
+ P[2] = 0    Q[2] = 6
+ The answers to these M = 3 queries are as follows:
+
+ The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
+ The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
+ The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.
+ Write a function:
+
+ public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int]
+ that, given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.
+
+ Result array should be returned as an array of integers.
+
+ For example, given the string S = CAGCCTA and arrays P, Q such that:
+
+ P[0] = 2    Q[0] = 4
+ P[1] = 5    Q[1] = 5
+ P[2] = 0    Q[2] = 6
+ the function should return the values [2, 4, 1], as explained above.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [1..100,000];
+ M is an integer within the range [1..50,000];
+ each element of arrays P, Q is an integer within the range [0..N − 1];
+ P[K] ≤ Q[K], where 0 ≤ K < M;
+ string S consists only of upper-case English letters A, C, G, T.
+*/
+
 class Lesson5_GenomicRangeQuery: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson5_MinAvgTwoSlice.swift b/CodilityLessonsTests/Lesson5_MinAvgTwoSlice.swift
@@ -8,6 +8,51 @@
 
 import XCTest
 
+/*
+ MinAvgTwoSlice
+ Find the minimal average of any slice containing at least two elements.
+
+
+ A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).
+
+ For example, array A such that:
+
+ A[0] = 4
+ A[1] = 2
+ A[2] = 2
+ A[3] = 5
+ A[4] = 1
+ A[5] = 5
+ A[6] = 8
+ contains the following example slices:
+
+ slice (1, 2), whose average is (2 + 2) / 2 = 2;
+ slice (3, 4), whose average is (5 + 1) / 2 = 3;
+ slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.
+ The goal is to find the starting position of a slice whose average is minimal.
+
+ Write a function:
+
+ public func solution(_ A : inout [Int]) -> Int
+ that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.
+
+ For example, given array A such that:
+
+ A[0] = 4
+ A[1] = 2
+ A[2] = 2
+ A[3] = 5
+ A[4] = 1
+ A[5] = 5
+ A[6] = 8
+ the function should return 1, 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 Lesson5_MinAvgTwoSlice: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson5_PassingCars.swift b/CodilityLessonsTests/Lesson5_PassingCars.swift
@@ -8,6 +8,50 @@
 
 import XCTest
 
+/*
+ PassingCars
+ Count the number of passing cars on the road.
+
+
+ A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.
+
+ Array A contains only 0s and/or 1s:
+
+ 0 represents a car traveling east,
+ 1 represents a car traveling west.
+ The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.
+
+ For example, consider array A such that:
+
+ A[0] = 0
+ A[1] = 1
+ A[2] = 0
+ A[3] = 1
+ A[4] = 1
+ We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).
+
+ Write a function:
+
+ public func solution(_ A : inout [Int]) -> Int
+ that, given a non-empty array A of N integers, returns the number of pairs of passing cars.
+
+ The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.
+
+ For example, given:
+
+ A[0] = 0
+ A[1] = 1
+ A[2] = 0
+ A[3] = 1
+ A[4] = 1
+ 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 that can have one of the following values: 0, 1.
+*/
+
 class Lesson5_PassingCars: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson6_Distinct.swift b/CodilityLessonsTests/Lesson6_Distinct.swift
@@ -8,6 +8,29 @@
 
 import XCTest
 
+/*
+ Distinct
+ Compute number of distinct values in an array.
+
+
+ Write a function
+
+ public func solution(_ A : inout [Int]) -> Int
+
+ that, given an array A consisting of N integers, returns the number of distinct values in array A.
+
+ For example, given array A consisting of six elements such that:
+
+ A[0] = 2    A[1] = 1    A[2] = 1
+ A[3] = 2    A[4] = 3    A[5] = 1
+ the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.
+
+ 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 [−1,000,000..1,000,000].
+*/
+
 class Lesson6_Distinct: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson6_MaxProductOfThree.swift b/CodilityLessonsTests/Lesson6_MaxProductOfThree.swift
@@ -8,6 +8,50 @@
 
 import XCTest
 
+/*
+ MaxProductOfThree
+ Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).
+
+
+ A non-empty array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).
+
+ For example, array A such that:
+
+ A[0] = -3
+ A[1] = 1
+ A[2] = 2
+ A[3] = -2
+ A[4] = 5
+ A[5] = 6
+ contains the following example triplets:
+
+ (0, 1, 2), product is −3 * 1 * 2 = −6
+ (1, 2, 4), product is 1 * 2 * 5 = 10
+ (2, 4, 5), product is 2 * 5 * 6 = 60
+ Your goal is to find the maximal product of any triplet.
+
+ Write a function:
+
+ public func solution(_ A : inout [Int]) -> Int
+
+ that, given a non-empty array A, returns the value of the maximal product of any triplet.
+
+ For example, given array A such that:
+
+ A[0] = -3
+ A[1] = 1
+ A[2] = 2
+ A[3] = -2
+ A[4] = 5
+ A[5] = 6
+ the function should return 60, as the product of triplet (2, 4, 5) is maximal.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [3..100,000];
+ each element of array A is an integer within the range [−1,000..1,000].
+*/
+
 class Lesson6Task2: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson6_NumberOfDiscIntersections.swift b/CodilityLessonsTests/Lesson6_NumberOfDiscIntersections.swift
@@ -8,6 +8,43 @@
 
 import XCTest
 
+/*
+ NumberOfDiscIntersections
+ Compute the number of intersections in a sequence of discs.
+
+
+ We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].
+
+ We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).
+
+ The figure below shows discs drawn for N = 6 and A as follows:
+
+ A[0] = 1
+ A[1] = 5
+ A[2] = 2
+ A[3] = 1
+ A[4] = 4
+ A[5] = 0
+
+
+ There are eleven (unordered) pairs of discs that intersect, namely:
+
+ discs 1 and 4 intersect, and both intersect with all the other discs;
+ disc 2 also intersects with discs 0 and 3.
+ Write a function:
+
+ public func solution(_ A : inout [Int]) -> Int
+
+ that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
+
+ Given array A shown above, the function should return 11, 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 [0..2,147,483,647].
+*/
+
 class Lesson6_NumberOfDiscIntersections: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson6_Triangle.swift b/CodilityLessonsTests/Lesson6_Triangle.swift
@@ -8,6 +8,44 @@
 
 import XCTest
 
+/*
+ Triangle
+ Determine whether a triangle can be built from a given set of edges.
+
+
+ An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:
+
+ A[P] + A[Q] > A[R],
+ A[Q] + A[R] > A[P],
+ A[R] + A[P] > A[Q].
+ For example, consider array A such that:
+
+ A[0] = 10    A[1] = 2    A[2] = 5
+ A[3] = 1     A[4] = 8    A[5] = 20
+ Triplet (0, 2, 4) is triangular.
+
+ Write a function:
+
+ public func solution(_ A : inout [Int]) -> Int
+
+ that, given an array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.
+
+ For example, given array A such that:
+
+ A[0] = 10    A[1] = 2    A[2] = 5
+ A[3] = 1     A[4] = 8    A[5] = 20
+ the function should return 1, as explained above. Given array A such that:
+
+ A[0] = 10    A[1] = 50    A[2] = 5
+ A[3] = 1
+ the function should return 0.
+
+ 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 Lesson6_Triangle: XCTestCase {
 
     func test() {

diff --git a/CodilityLessonsTests/Lesson7_Brackets.swift b/CodilityLessonsTests/Lesson7_Brackets.swift
@@ -8,6 +8,31 @@
 
 import XCTest
 
+/*
+ Brackets
+ Determine whether a given string of parentheses (multiple types) is properly nested.
+
+
+ A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:
+
+ S is empty;
+ S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
+ S has the form "VW" where V and W are properly nested strings.
+ For example, the string "{[()()]}" is properly nested but "([)()]" is not.
+
+ Write a function:
+
+ public func solution(_ S : inout String) -> Int
+ that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.
+
+ For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.
+
+ Write an efficient algorithm for the following assumptions:
+
+ N is an integer within the range [0..200,000];
+ string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".
+*/
+
 class Lesson7_Brackets: XCTestCase {
 
     func test() {