DsAlgoPractice

Thi project helped me crack interviews in the big companies. It contains solutions to Codility problems with a 100% efficiency score. Completed ones have been checked below. This project was generated using Nx.

Run this project by running the tests: npx nx test codility --watch

Codility Solutions

Lessons - https://app.codility.com/programmers/lessons/

Iterations

• BinaryGap Easy (Find longest sequence of zeros in binary representation of an integer)

Arrays

• CyclicRotation Easy (Rotate an array to the right by a given number of steps)
• OddOccurrencesInArray Easy (Find value that occurs in odd number of elements)

Time Complexity

• FrogJmp Easy (Count minimal number of jumps from position X to Y)
• PermMissingElem Easy (Find the missing element in a given permutation)
• TapeEquilibrium Easy (Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|)

Counting Elements

• FrogRiverOne Easy (Find the earliest time when a frog can jump to the other side of a river)
• PermCheck Easy (Check whether array A is a permutation)
• MaxCounters Medium (Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum)
• MissingInteger Medium (Find the smallest positive integer that does not occur in a given sequence)

Prefix Sums

• PassingCars Easy (Count the number of passing cars on the road)
• CountDiv Medium (Compute number of integers divisible by k in range [a..b])
• GenomicRangeQuery Medium (Find the minimal nucleotide from a range of sequence DNA)
• MinAvgTwoSlice Medium (Find the minimal average of any slice containing at least two elements)

Sorting

• Distinct Easy (Compute number of distinct values in an array)
• MaxProductOfThree Easy (Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R))
• Triangle Easy (Determine whether a triangle can be built from a given set of edges)
• NumberOfDiscIntersections Medium (Compute the number of intersections in a sequence of discs)

Stacks and Queues

• Brackets Easy (Determine whether a given string of parentheses (multiple types) is properly nested)
• Fish Easy (N voracious fish are moving along a river. Calculate how many fish are alive)
• Nesting Easy (Determine whether a given string of parentheses (single type) is properly nested)
• StoneWall Easy (Cover "Manhattan skyline" using the minimum number of rectangles)

Leader

• Dominator Easy (Find an index of an array such that its value occurs at more than half of indices in the array)
• EquiLeader Easy (Find the index S such that the leaders of the sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N - 1] are the same)

Maximum slice problem

• MaxProfit Easy (Given a log of stock prices compute the maximum possible earning)
• MaxSliceSum Easy (Find a maximum sum of a compact subsequence of array elements)
• MaxDoubleSliceSum Medium (Find the maximal sum of any double slice)

Prime and composite numbers

• CountFactors Easy (Count factors of given number n)
• MinPerimeterRectangle Easy (Find the minimal perimeter of any rectangle whose area equals N)
• Flags Medium (Find the maximum number of flags that can be set on mountain peaks)
• Peaks Medium (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])

Sieve of Eratosthenes

• CountNonDivisible Medium (Calculate the number of elements of an array that are not divisors of each element)
• CountSemiprimes Medium (Count the semiprime numbers in the given range [a..b])

Euclidean algorithm

• ChocolatesByNumbers Easy (There are N chocolates in a circle. Count the number of chocolates you will eat)
• CommonPrimeDivisors Medium (Check whether two numbers have the same prime divisors)

Fibonacci numbers

• FibFrog Medium (Count the minimum number of jumps required for a frog to get to the other side of a river)
• Ladder Medium (Count the number of different ways of climbing to the top of a ladder)

Binary search algorithm

• MinMaxDivision Medium (Divide array A into K blocks and minimize the largest sum of any block)
• NailingPlanks Medium (Count the minimum number of nails that allow a series of planks to be nailed)

Caterpillar method

• AbsDistinct Easy (Compute number of distinct absolute values of sorted array elements)
• CountDistinctSlices Easy (Count the number of distinct slices (containing only unique numbers))
• CountTriangles Easy (Count the number of triangles that can be built from a given set of edges)
• MinAbsSumOfTwo Medium (Find the minimal absolute value of a sum of two elements)

Greedy algorithms

• MaxNonoverlappingSegments Easy (Find a maximal set of non-overlapping segments)
• TieRopes Easy (Tie adjacent ropes to achieve the maximum number of ropes of length >= K)

Dynamic programming

• NumberSolitaire Medium (In a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6)
• MinAbsSum Hard (Given array of integers, find the lowest absolute sum of elements)

External problems

• MergeSort
• QuickSort
• BowlingGameScorer