Interview - Find the pole of magnitude in an array

Question

Magnitude Pole: An element in an array whose left hand elements are less than or equal to it, and whose right side element is greater than or equal to it.

input example

3,1,4,5,9,7,6,11 

desired result

 5,11 

I was asked this question in an interview, and I should return the index of the element and return only the first element that satisfies the condition.

My logic

• Let's take two MultiSets (so that we can also consider the duplicate), one for the right side of the element and one for the left side of the element (pole).
• Start with the 0th element and put all the elements in the “correct set”.
• The basic condition is if this 0th element is less than or equal to all elements in the "correct set", then returns its index.
• Else put this in the “left set” and started with the item at index 1.
• Turn the array and each time select the maximum value from the "left set" and the minimum value from the "right set" and compare.
• At any moment in time for any element, the whole value to the left of it is in the “left set”, and the value to the right is in the “right set”

code

 int magnitudePole (const vector<int> &A) { multiset<int> left, right; int left_max, right_min; int size = A.size(); for (int i = 1; i < size; ++i) right.insert(A[i]); right_min = *(right.begin()); if(A[0] <= right_min) return 0; left.insert(A[0]); for (int i = 1; i < size; ++i) { right.erase(right.find(A[i])); left_max = *(--left.end()); if (right.size() > 0) right_min = *(right.begin()); if (A[i] > left_max && A[i] <= right_min) return i; else left.insert(A[i]); } return -1; } 

My questions

• They told me that my logic is wrong, I can’t understand why this logic is wrong (although I checked some cases and it returns the right index)
• For my own curiosity, how to do this without using any set / multiset in O (n) time.

Answer 1

For the O (n) algorithm:

• Count the largest element from n [0] to n [k] for all k from [0, length (n)), save the answer in the maxOnTheLeft array. It costs O (n);
• Count the smallest element from n [k] to n [length (n) -1] for all k from [0, length (n)), save the response in the minOnTheRight array. It costs O (n);
• Scroll through all this and find any n [k] with maxOnTheLeft <= n [k] <= minOnTheRight. It costs O (n).

And you code (at least) is wrong here:

 if (A[i] > left_max && A[i] <= right_min) // <-- should be >= and <= 

Answer 2

• Create two bool [N] called NorthPole and SouthPole (just to be humorous.
• step forward through A [] tracking the maximum element found so far and set SouthPole [i] true if A [i]> Max (A [0..i-1])
• step back through A [] and set NorthPole [i] true if A [i] Minimum (A [g + 1..N-1)
• go through NorthPole and SouthPole to find the first item with true.

O (N) at each step above, like visiting each node once, so O (N) as a whole.

Answer 3

for Java:

 public int magnitude(int[] A) { int length = A.length; // the sense of maxes is : what the maximum number from the beginning of the array till the current position int[] maxes = new int[A.length]; // the sense of mins is : what the minimum number from the current position till the end of the array int[] mins = new int[A.length]; int max = maxes[0] = Integer.MIN_VALUE; int min = mins[length - 1] = Integer.MAX_VALUE; // mins and maxes list are built incrementally for (int i = length - 1; i >= 0; --i) { if (A[i] < min) { min = A[i]; } mins[i] = min; } for (int i = 0; i < length; i++) { if (A[i] > max) { max = A[i]; } maxes[i] = max; } for (int i = 0; i < length; i++) { if (A[i] >= maxes[i] && A[i] <= mins[i]) { return i; } } return -1; } 

Answer 4

Your logic seems perfectly correct (did not check the implementation, though) and can be implemented to give an O (n) time algorithm! Good thinking work in terms of sets.

Your right set can be implemented as a stack that supports min, and your left set can be implemented as a stack that supports max, and this gives the O (n) time algorithm.

Having a stack supporting max / min is a well-known interview question, and it can be done so that each operation (push / pop / min / max - O (1)).

To use this for your logic, the pseudocode will look something like this.

 foreach elem in a[n-1 to 0] right_set.push(elem) while (right_set.has_elements()) { candidate = right_set.pop(); if (left_set.has_elements() && left_set.max() <= candidate <= right_set.min()) { break; } else if (!left.has_elements() && candidate <= right_set.min() { break; } left_set.push(candidate); } return candidate 

Answer 5

I saw this problem on Codility, solved it using Perl:

 sub solution { my (@A) = @_; my ($max, $min) = ($A[0], $A[-1]); my %candidates; for my $i (0..$#A) { if ($A[$i] >= $max) { $max = $A[$i]; $candidates{$i}++; } } for my $i (reverse 0..$#A) { if ($A[$i] <= $min) { $min = $A[$i]; return $i if $candidates{$i}; } } return -1; } 

Answer 6

What about the following code? I think its effectiveness is not very good in the worst case, but the expected efficiency will be good.

  int getFirstPole(int* a, int n) { int leftPole = a[0]; for(int i = 1; i < n; i++) { if(a[j] >= leftPole) { int j = i; for(; j < n; j++) { if(a[j] < a[i]) { i = j+1; //jump the elements between i and j break; } else if (a[j] > a[i]) leftPole = a[j]; } if(j == n) // if no one is less than a[i] then return i return i; } } return 0; } 

Answer 7

• Create an ints array called mags and an int variable called maxMag .
• For each element in the source array, check if it is greater than or equal to the maxMag element.
• If there is: add an element to the mags array and set maxMag = element .
• If it is not: loop through the mags array and remove all the elements less.

Result: array of poles of magnitude

Answer 8

An interesting question: I have my own solution in C #, which I cited below, read the comments to understand my approach.

 public int MagnitudePoleFinder(int[] A) { //Create a variable to store Maximum Valued Item ie maxOfUp int maxOfUp = A[0]; //if list has only one value return this value if (A.Length <= 1) return A[0]; //create a collection for all candidates for magnitude pole that will be found in the iteration var magnitudeCandidates = new List<KeyValuePair<int, int>>(); //add the first element as first candidate var a = A[0]; magnitudeCandidates.Add(new KeyValuePair<int, int>(0, a)); //lets iterate for (int i = 1; i < A.Length; i++) { a = A[i]; //if this item is maximum or equal to all above items ( maxofUp will hold max value of all the above items) if (a >= maxOfUp) { //add it to candidate list magnitudeCandidates.Add(new KeyValuePair<int, int>(i, a)); maxOfUp = a; } else { //remote all the candidates having greater values to this item magnitudeCandidates = magnitudeCandidates.Except(magnitudeCandidates.Where(c => c.Value > a)).ToList(); } } //if no candidate return -1 if (magnitudeCandidates.Count == 0) return -1; else //return value of first candidate return magnitudeCandidates.First().Key; }