## 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

xis the smallest element in the array, andyis the largest, theny≤ 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.

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).

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)

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

minimumnumber 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.

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

iandjare making a single pass across the list in total (unlike a conventional nested for loop, the inner indexjis strictly increasing).Is your analysis considering this? The

1+2+…+nthat you wrote seems like it would arise from an ordinary nested for loop overifrom 0 to n andjfrom 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.

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.

@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

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

*/