Coding Challenge Array Exercises
Jan 10th, 2020 - written by Kimserey with .
Coding exercises are hard, no matter what level of experience you have and which point of your career you are at, it is a very different skills to succeed coding exercises versus building real life application. Nonetheless some of them are quite interesting and highlight techniques that can vastly change the performance of a program. In today’s post we look at optimization techniques used in arrays on common problems.
Minimum Swaps by one position
Problem
We are given an array from 0 to n-1 shuffled in such a way that elements were swapped in pairs. Each element is only allowed to move forward the array two times. Find how many swaps are required to reach the state of the shuffled array.
1
2
3
4
5
6
7
8
9
10
11
12
Example:
1 0 2 5 4 3
Solution:
4
Explanation:
- 0 1 2 3 4 5: Initial
- 1 0 2 3 4 5: Move forward 1
- 1 0 2 3 5 4: Move forward 5
- 1 0 2 5 3 4: Move forward 5
- 1 0 2 5 4 3: Move forward 4
Explanation
We iterate through the array and execute a first check verifying that the current value held at the index does not differ from more than two, if it does it means that the array violates the constraint of maximum two moves.
When we iterate through the array, at each index, any value superior to the value held at the index in front position are considered as swaps.
1
2 0 1: Has two swaps
A first implementation of our algorithm would be:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def get_min_swap(q):
res = 0
for i, v in enumerate(q):
diff = v - i
if diff > 2:
print("Too many swaps")
return
for j in range(0, i):
if q[j] > v:
res += 1
print(res)
We have reduced the inner iteration by restricting the range from [0, i]. But we can do better, in fact we can recognize that at any time, a value can only go ahead by a single position.
The first swap will put the value behind at the same position and the second swap will put the value in front by one position.
Therefore we can deduce that for any value, the maximum position a value behind can get ahead is by one position.
We can therefore reduce the range to [v - 1, i].
All swaps have to be contained between [v - 1, i] where i is where the value is at the moment.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def get_min_swap(q):
res = 0
for i, v in enumerate(q):
diff = v - i
if diff > 2:
print("Too many swaps")
return
for j in range(max(v - 1, 0), i):
if q[j] > v:
res += 1
print(res)
And we will have achieve the best algorithm.
Minimum Swaps to sort
Problem
We are given an array of shuffled incremental integer starting from zero. We want to know the minimum swaps needed to sort the array.
1
2
3
4
5
6
7
8
9
10
11
12
Example:
5 4 1 0 2 3
Solution:
4
Steps:
5 4 1 0 2 3: 5<>0
0 4 1 5 2 3: 4<>1
0 1 4 5 2 3: 4<>2
0 1 2 5 4 3: 3<>5
0 1 2 3 4 5: end
Explanation
Each position in the array should contain it’s own value. Therefore to sort the array we go through each position and swap any wrong value to the position where the right value was held. In order to swap a value we need to retrieve the index where the value is held. For an O(1) retrieval we construct a reverse array containing the values as indices and the indices as values. Then when we iterate and find a misplaced value, we retrieve the index of the correct value and swap it with the currently misplaced value.
With that we achieve an O(n) complexity
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def minmum_swap(arr):
# Array of indexes for each value,
# for quick lookup.
indexes = [0] * len(arr)
for pos, val in enumerate(arr):
indexes[val] = pos
swaps = 0
for i in range(len(arr)):
# Check if value is at the wrong position
if arr[i] != i:
tmp = arr[i]
# Sets the current index to the array.
arr[i] = i
# Find the previous value index from indexes
# and set the tmp value to where the index was.
arr[indexes[i]] = tmp
# Modify the indexes array accordingly
indexes[tmp] = indexes[i] # Apply the swap
indexes[i] = i # Set the correct value
swaps += 1
return swaps
Variation
Problem
For this last exercise, we want to find the highest value when the arrays are added.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Example:
3 5 - 10
1 4 - 5
6 8 - 2
Solution:
15
Steps:
00 00 00 10 10 10 00 00 00: 3 5 - 10
00 05 05 05 05 00 00 00 00: 1 4 - 5
00 00 00 00 00 00 02 02 02: 6 8 - 2
Resulting 0 5 5 15 15 10 2 2 2 with a max of 15.
Explanation
By drawing the result, we can see that the result is given by the variation of level. Each value can be derived by the variation of each range given.
For example the first range, 3 5 - 10 would represent 0 0 0 10 10 10 0 0 0, which can also be represented as its slope 0 0 0 10 0 0 -10 0 0.
At index 3, the values increase by 10, and at index 6, decrease by 10, resulting in 0 0 0 10 10 10 0 0 0.
If we continue with this logic with each range, we end up with an array aggregating all variation and representing the actual result.
1
2
0 +5 0 +10 0 -5 -10+2 0 0
0 5 5 15 15 10 2 2 2
And we can implement it with the following function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# queries contain the range plus the value
def array_manipulation(n, queries):
res = [0] * (n)
for q in queries:
x, y, incr = q[0], q[1], q[2]
# Add the increment variation at x
res[x] += incr
if y < len(res):
# Remove the increment variation at y+1
res[y + 1] -= incr
# Construct the final result by adding every value
# of the variation and constructing the actual
# increment result.
mx = 0
x = 0
for i in res:
x = x + i
if mx < x:
mx = x
return mx
And that concludes today’s post!
Conclusion
Today we looked into three array exercises, each one of the exercises had different constraint which made a solution slightely different. In all of the exercise the only criteria which mattered was the complexity. In the first exercise, we reduced the complexity by reducing the domain of values to look at when we identified the maximum space a swap could occur in. In the second exercise, we reduced the complexity by building a reserve array of indexes which would then allow us to retrieve values in the array for at a constant complexity. Lastly the third exercise, we reduced the complexity by constructing an array which will allow us to represent the result in a single step. I hope you liked this post and I see you on the next one!