Array Of Integers
August 28, 2018
Today’s exercise is an interview question from Amazon:
You are given an array of integers, not necessarily unique. Your goal is to transform the array of integers so that the smallest number does not differ from the largest number by more than two times by removing integers from the array; thus, if x is the smallest element in the array, and y is the largest, then y ≤ 2x. You need only find the number of items to be removed from the array, not make a list of the items. As an example, given the array [4,5,3,8,3,7], you can remove the 2 smallest integers, leaving [4,5,7,8], so that 8 ≤ 2 × 4, or you can remove the 2 largest integers, leaving [3,4,5,6], so that 5 ≤ 2 × 3.
Your task is to write a function to determine how many items to remove from the array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python, a rather inefficient solution (2^n). For each subset of the list, determine whether it satisfies the constraint. @Programmingpraxis: i don’t believe your code handles [1,5,5,20] correctly.
Klong version – Uses same logic as @ProgrammingPraxis, except:
If the counts of lesser and greater numbers are equal and are greater than half the length of the list, then return counts plus the result of e2(new list composed of the original list without the lesser and greater numbers).
e::{:[0=#x; "No solution" :|1=#x; 0; e2(x)]} e2::{[hi l2 len lo n1 n2]; lo::(l2::x@<x)@0; hi::l2@((len::#l2)-1); n1::(+/{x<hi%2}'l2); n2::(+/{x>(lo*2)}'l2); :[n1<n2; n1:| n2<n1; n2:| n1<len%2; n1; e2((2*(len-n1))+(-len-n1)_(len-n2)_l2)]}Examples:
[] –> No solution
[4][ –> 0]
[2 2][ –> 0]
[1 3 5][ –> 1]
[1 5 5 20][ –> 0]
[4 5 3 8 3 7][ –> 2]
“done”
Klong version 2 (Version 1 was wrong)
e::{:[0=#x; "No solution" :|1=#x; 0; e2(x)]} e2::{[hi l2 len lo n1 n2]; lo::(l2::x@<x)@0; hi::l2@((len::#l2)-1); n1::(+/{x<hi%2}'l2); n2::(+/{x>(lo*2)}'l2); :[n1<n2; n1:| n2<n1; n2:| n1<len%2; n1; e2((-len-n1)_(len-n2)_l2)+(2*(len-n1))]}Examples:
{.w(x); .p(” –> “,,/:~e(x))}'[[] [4] [2 2] [1 3 5] [1 5 5 20] [4 5 3 8 3 7]];”done”
[] –> No solution
[4][ –> 0]
[2 2][ –> 0]
[1 3 5][ –> 1]
[1 5 5 20][ –> 2]
[4 5 3 8 3 7][ –> 2]
“done”
Although it’s not explicitly stated in the problem, I interpret that the goal is to find the minimum number of elements that can be removed to satisfy the condition. Otherwise, the solution could always be to remove all but one element.
@bookofstevegraham, I’m not familiar with klong, but it sounds like your algorithm may not handle the case where the number of high elements that needs to be dropped differs from the number of low elements to drop. For example, what does your algorithm return for [1, 2, 20, 21, 22, 200]? Under the interpretation of the question I gave in my last paragraph, the expected answer would be 3 (remove elements 1, 2, and 200).
Here’s an O(n log n) solution in C. It sorts the list and finds the longest contiguous valid group.
#include <stdio.h> #include <stdlib.h> int compar(const void* a, const void* b) { int x = *(int*)a; int y = *(int*)b; return (x < y) ? -1 : (x > y); } int drop_count(int* array, int n) { int result = n - 1; qsort(array, n, sizeof(int), compar); int j = 0; for (int i = 0; i < n; ++i) { int lower = array[i]; while (j+1 < n && array[j+1] <= 2 * lower) ++j; int tmp = n - j + i - 1; if (tmp < result) result = tmp; } return result; } int main(int argc, char* argv[]) { int array[argc - 1]; for (int i = 1; i < argc; ++i) { array[i-1] = atoi(argv[i]); } int result = drop_count(array, argc - 1); printf("%d\n", result); return EXIT_SUCCESS; }Example:
As I am a beginner, this is my simple code, If any body wants to give feed back it is acceptable.
a = [4,5,3,8,3,7]
count1, count2 = 0, 0
maxi = max(a)
mini = min(a)
print(maxi, mini)
value1 = 2 * mini
value2 = maxi // 2
print(value1, value2)
for i in a:
if i > value1:
count1 += 1
if i < value2:
count2 += 1
print(‘Remove {} Largest integers’.format(count1))
print(‘OR’)
print(‘Remove {} Smallest integers’.format(count2))
@Daniel: O(n log n) for qsort. However, I think your for + while loop has iterations: 1+2+3+…+n = 1/2n * (n+1) = O(n^2).
@Rutger, I thought the for + while loop is O(n) since both indices i and j are making a single pass across the list in total (unlike a conventional nested for loop, the inner index j is strictly increasing).
Is your analysis considering this? The 1+2+…+n that you wrote seems like it would arise from an ordinary nested for loop over i from 0 to n and j from 0 to i.
If possible, can you please provide more details? Thanks.
Klong version 3 — @Daniel – Good call. Thanks. It did not perform as it should have. Made appropriate changes.
e::{:[0=#x; "No solution" :|1=#x; 0; e2(x)]} e1::{:[x>y%2; y-x; x]} e2::{[hi l2 len lo n1 n2]; lo::(l2::x@<x)@0; hi::l2@((len::#l2)-1); n1::(+/{x<hi%2}'l2); n2::(+/{x>(lo*2)}'l2); :[n1<len%2; :[n2<len%2; :[n1<n2; n1; n2]; n1]; e3(e1(n1; len); e1(n2; len); l2)]} e3::{[z1]; z1::z; e2((-x)_y_z)+x+y}Examples::monad
[] –> No solution
[4][ –> 0]
[2 2][ –> 0]
[1 3 5][ –> 1]
[1 5 5 20][ –> 2]
[4 5 3 8 3 7][ –> 2]
[1 2 20 21 22 200][ –> 3]
“done”
@ProgrammingPraxis: Ran your program on Gambit Scheme with the following tests and it didn’t seem to work for:
(display (f ‘(1 5 5 20))) (newline)
1
>
(display (f ‘(1 2 20 21 22 200))) (newline)
1
>
Here’s an O(n) Haskell version. It makes two passes over the array: first to find the minimum and maximum values, then to count the number of values that are greater than twice the minimum and those that are less than half the maximum. It returns the minimum of these two counts.
{-# LANGUAGE OverloadedLists #-} {-# OPTIONS_GHC -fno-warn-type-defaults #-} import qualified Control.Foldl as F import qualified Data.Vector as V -- The minimum number of numbers to remove from an array so that the smallest -- remaining value is less than or equal to twice the largest remaining value. rem2x :: (Ord a, Num a) => V.Vector a -> Int rem2x xs | V.length xs == 0 = 0 | otherwise = let (Just min', Just max') = foldp F.minimum F.maximum xs (highs, lows) = foldp (count (`gt2` min')) (count (max' `gt2`)) xs in min highs lows where foldp f g = F.fold ((,) <$> f <*> g) count f = F.handles (F.filtered f) F.length x `gt2` y = x > 2 * y main :: IO () main = do print $ rem2x [4, 5, 3, 8, 3, 7] print $ rem2x [1, 5, 5, 20] print $ rem2x [1, 2, 20, 21, 22, 200] print $ rem2x [1, 2] print $ rem2x [4] print $ rem2x []@Globules, for [1,5,5,20], it’s possible to remove two elements (1 and 20), but your solution seemingly removes three. While removing three is still valid based on a strict reading of the question, the goal is presumably be to remove as few elements as possible (otherwise, the solution could always be to remove all but one element). For [1, 2, 20, 21, 22, 200], your solution seemingly removes 4 elements, but it’s possible to remove three (1, 2, and 200).
@Rutger, I’ve given more thought to your earlier comment.
Using the same approach that you used, I think the number of iterations is (1+x1) + (1+x2) + (1+x3) + … + (1+xN), where the 1s are from the outer loop and x’s are from the inner loop. The inner loop executes N times in total, so the sum across x’s is N and the preceding sum would be 2N, making the loop part of the code O(n), and the entire algorithm O(n log n).
An alternative way to think of the approach I used is that the array is first sorted, and then a sliding window slides over the array by incrementally moving the front and end of the window. Each incremental movement of the front or end of the window is one unit toward the end of the array, resulting in 2N movements (N movements of the front and N movements of the back).
Additionally, the for + while loop can be seen as O(n) by considering how many times the body of the for loop and the while loop each execute. The body of the for loop executes N times, and the body of the while loop also executes N times. Both of these execute N times in total (as opposed to being executed N times on each iteration).
Interesting drill. Here is my take on it using Julia v. 1.0:
Code:
function aoi_engine(x_::Array{<:Integer, 1}, go_with_small_values::Bool = true)
n_ = length(x_)
x = copy(x_)
m, M = extrema(x)
n = length(x)
end
function aoi(z::Array{<:Integer, 1})
c1 = aoi_engine(z)
c2 = aoi_engine(z, false)
end
Note: as a bonus, this code yields not only the number of elements that need to be removed, but also the strategy used for keeping that to a minimum
Example:
julia> x = [9, 10, 2, 5, 1, 7, 6, 2, 10, 2];
julia> aoi(x)
(4, “small”) # output
So, we need to remove the 4 smallest elements in order to get an array that satisfies the given condition.
Should we want to explore the other strategy, we can do so as follows:
julia> aoi_engine(x, false)
6 # output
As expected, this yields a larger number. In other words, should we wish to start from the higher values of the array, we’d need to remove 6 elements before the given condition is satisfied.
I imagine that this drill aims to create a heuristic for removing outliers or elements that could potentially act as outliers. Is that the case?
@Daniel You’re right, I didn’t pay close enough attention to the wording of the problem. So much for working at Amazon…
Klong version 4 – Found a list — [2 3 4 9 19] — which my earlier program did not process correctly
e::{:[0=#x; "No solution" :|1=#x; 0; e2(x)]} e1::{:[x>y%2; y-x; x]} e2::{[hi l2 len lo n1 n2]; lo::(l2::x@<x)@0; hi::l2@((len::#l2)-1); n1::(+/{x<hi%2}'l2); n2::(+/{x>(lo*2)}'l2); :[n1<len%2; :[n2<len%2; n1&n2; n1]; :[n2<len%2; n2; e3(e1(n1; len); e1(n2; len); l2)]]} e3::{[z1]; z1::z; e2((-x)_y_z)+x+y} {.w(x," --> ",e(x)); .p("")}'[[] [4] [2 2] [1 3 5] [1 5 5 20] [2 3 4 9 19] [4 5 3 8 3 7] [1 2 20 21 22 200]];"done"steve@steve-VirtualBox:~/klong$ rlwrap ./kg
Klong 20180213
]l lib/arrayofintegers
loading “./lib/arrayofintegers.kg”
[” –> No solution”]
[4 ” –> ” 0]
[2 2 ” –> ” 0]
[1 3 5 ” –> ” 1]
[1 5 5 20 ” –> ” 2]
[2 3 4 9 19 ” –> ” 2]
[4 5 3 8 3 7 ” –> ” 2]
[1 2 20 21 22 200 ” –> ” 3]
Heres a C++ solutionm runs in O(n log n), returns the minimum number of elements to remove.
#define bsearch(a,n) (upper_bound(begin(a),end(a),n)-begin(a))
int minRemove(vector<int> arr) {
sort(begin(arr), end(arr));
int i=0, s=(int)arr.size(), m=s+1, bi;
while (i < s){
if (i >= m) break;
bi = bsearch(arr, 2*arr[i]);
m = min(m, i+s-bi);
i+=1;
}
return m;
}
int main() {
vector<int> a = {3,4,4,5,5,6};
vector<int> b = {3,4,4,5,7,8,9};
cout << minRemove(a) << endl;
cout << minRemove(b) << endl;
}
/*
0
2
*/
Here’s a single loop version of Daniel’s solution that makes it clear that we go round the loop at most 2n times:
#include <iostream> #include <vector> #include <algorithm> #include <stdlib.h> int drop_count(std::vector<int> a) { std::sort(a.begin(), a.end()); int i = 0, j = 0, maxlen = 0; while(j < a.size()) { if (a[j] <= 2*a[i]) { std::cout << i << " " << j+1 << "\n"; maxlen = std::max(maxlen,j-i+1); j++; // Try extending a solution } else { i++; // Try next starting point } } return maxlen; } int main(int argc, char* argv[]) { std::vector<int> a; for (int i = 1; i < argc; ++i) { a.push_back(atoi(argv[i])); } std::cout << drop_count(a) << "\n"; }