#InterviewPrep: Codility Lessons 1–2 (using Kotlin)
👋 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
- How to convert int to binary?
- 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 0
s.
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! 🚶