#InterviewPrep: Codility Lessons 1–2 (using Kotlin)

Photo by Mark Basarab on Unsplash

👋 Hello! It’s been some time, and I thought you’d like to take another look at some of your past memories. Time to dive back into Codility!

Lesson 1: Iterations

BinaryGap

Find longest sequence of zeros in binary representation of an integer.

+--------+-----------------------+------------+--------+
| Number | Binary Representation | Binary Gap | Result |
+--------+-----------------------+------------+--------+
|      9 |                  1001 | 2          |      2 |
|    529 |            1000010001 | 4 & 3      |      4 |
|     20 |                 10100 | 1          |      1 |
|     15 |                  1111 | 0          |      0 |
|     32 |                100000 | 0          |      0 |
|   1041 |           10000010001 | 5 & 3      |      5 |
+--------+-----------------------+------------+--------+

Write a function:

class Solution { public int solution(int N); }

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn’t contain a binary gap.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..2,147,483,647].

Intuition

1. How to convert int to binary?
2. Can’t we just count every ‘0’ inside looping?

Approach

Integer.toBinaryString(int i) ⇒ returns a string representation of the integer argument as an unsigned integer in base 2.

The unsigned integer value is the argument plus 2³² if the argument is negative; otherwise it is equal to the argument. This value is converted to a string of ASCII digits in binary (base 2) with no extra leading 0s.

String is basically just an array of char so, we can just count every 0

Code

import kotlin.math.*

fun solution(N: Int): Int {
    val binaryRep = Integer.toBinaryString(N)
    if (binaryRep.length <= 2) return 0 // 00, 01, 10, 11 has no gap
    else {
        var totalGap = 0
        var binaryGap = 0 
        for (c in binaryRep) {
            if (c == '1') {
                totalGap = Math.max(binaryGap, totalGap) // keep the longest binary gap
                binaryGap = 0
            } else {
                binaryGap++ // count every 0
            }
        }
        return totalGap
    }
}

• Time Complexity: O(log N) because we are converting the integer N to its binary representation, which requires iterating through the digits of N.
• Space complexity is O(1) because we are using a constant amount of extra space regardless of the input size.

Lesson 2: Arrays

CyclicRotation

Rotate an array to the right by a given number of steps.

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

class Solution { public int[] solution(int[] A, int K); }

that, given an array A consisting of N integers and an integer K, returns the array A rotated K times.

A = [3, 8, 9, 7, 6]
K = 3

Output
[9, 7, 6, 3, 8]

Explanation
Rotation 1 => [3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
Rotation 2 => [6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
Rotation 3 => [7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

Assume that:

• N and K are integers within the range [0..100];each element of array A is an integer within the range [−1,000..1,000].

Intuition

Output: [9, 7, 6, 3, 8] with index: [2, 3, 4, 0, 1]

How about splitting the array?

• Left side [9, 7, 6] => index: [2, 3, 4]
• Right side [3, 8]=> index: [0, 1]

Approach

Let say for the left side, we can put the numbers from k..nums.size-1 and for the right side, 0..nums.size-1-k

But, we can’t purely rely on the k since it can be k > nums.size. So, rotation = k % nums.size

val rotation = k % nums.size
val l = nums.size - rotation
val r = l - 1
return nums.slice(l until nums.size) + nums.slice(0..r)

Code

fun solution(A: IntArray, K: Int): IntArray {
    if (A.isEmpty() || A.size == K || K == 0) return A

    val r = K%A.size

    val L = A.size - r
    val R = L - 1

    return (A.slice(L until A.size) + A.slice(0..R)).toIntArray()
}

• Time complexity: O(N) Where n is the number of elements in the input array nums. This is because we are iterating through the array twice, once to copy the elements to a new array and once to update the original array with the rotated elements.
• Space complexity: O(N) We are creating a copy of the input array nums with the same size, which requires additional space.

See different approach: LeetCode — Rotate Array

OddOccurrencesInArray

Find value that occurs in odd number of elements.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

A = [9, 3, 9, 3, 9, 7, 9]

Output
7

Explanation
[9, 9] => [0, 2]
[3, 3] => [1, 3]
[9, 9] => [4, 6]
[7] => [5], therefore, output = 7

Assume that:

• N is an odd integer within the range [1..1,000,000];
• each element of array A is an integer within the range [1..1,000,000,000];
• all but one of the values in A occur an even number of times.

Intuition

• How do I know if there is an unpaired element in an array?
• How about iterating thru array, and only store an unpaired element?
• So, we need to check if A[i].isExist() then we can remove it from the storage

Approach

Let’s use Map<Int, Int> , iterate through the array and we check if A[n] != null then we can map.remove(n)

Code

fun solution(A: IntArray): Int {
    val a = mutableMapOf<Int, Int>()
    
    for (n in A) {
        if (a[n] == null) {
            a[n] = 1
        } else {
            a.remove(n)
        }
    }
    
    return a.keys.first()
}

Correctness: 100%, Performance: 75%, Overall 88% 💢

Let’s go back to…

Intuition

• N is an odd integer within the range [1..1,000,000];
• each element of array A is an integer within the range [1..1,000,000,000];
• all but one of the values in A occur an even number of times.

How about using logical operator xor?

1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 0 = 0

Approach

A = [9, 3, 9] => expected value: 3
9 = 1001
3 = 0011

=> 1001(9) XOR 0011(3) = 1010(10) XOR 1001(9) = 0011(3)
=> 9 XOR 3 XOR 9 = 3

With that being said, we can get unpaired element with exclusive-or.

Code

fun solution(A: IntArray): Int {
    var num = 0
    for (a in A) {
        num = num.xor(a)
    }
    return num
}

• Time complexity: O(N) where n is the length of the input array A. This is because the solution iterates through each element in the array once to calculate the XOR operation.
• Space Complexity: O(1) because it only uses a constant amount of extra space regardless of the size of the input array.

That wraps it up for today! Hope it was beneficial. Catch you in the next piece! 🚶