## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
7
of 7 vote

Merge Sort modification which sorts initial array "a" in decreasing order, but in spite of modifying given array it modifies an array of indexes "b", which allows to track surpassers in the third array "c". Array "t" is a temp buffer used for merging purposes as required by Merge Sort algorithm.
Time: O(n log n).
Space: O(n).

``````class MaxSurpasser {
int[] a, b, c, t;

private MaxSurpasser(int[] a) {
this.a = a;
this.b = new int[a.length];
this.c = new int[a.length];
this.t = new int[a.length];
for (int i = 0; i < b.length; i++){
b[i] = i;
}
}

public static int find(int[] a) {
return new MaxSurpasser(a).search();
}

private int search() {
mergeSort(0, a.length - 1);
int max = 0;
for (int i = 0; i < a.length; i++) {
if (c[i] > max) {
max = c[i];
}
}
return max;
}

private void mergeSort(int l, int r) {
if (l >= r) {
return;
}
int m = (l + r) / 2;
mergeSort(l, m);
mergeSort(m + 1, r);
int i = l;
int j = m + 1; int acc = 0;
for (int s = l; s <= r; s++) {
if (j > r || i <= m && a[b[i]] >= a[b[j]]) {
t[s] = b[i];
c[b[i]] += acc;
i++;
} else {
t[s] = b[j];
acc++;
j++;
}
}
for (int s = l; s <= r; s++) {
b[s] = t[s];
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm just curious as a guy studying for the google interview, did you just come up with this idea in one-shot?

Comment hidden because of low score. Click to expand.
2
of 2 votes

thewhatwhat, it's just a modification of a well known "count number of inversions algorithm"

Comment hidden because of low score. Click to expand.
0
of 0 votes

This is similar as computing inversion count of an array which basically counts smaller (or equal) elements on the right. So, surpasser of a position = n-i-1-inversion_count at that position.

Comment hidden because of low score. Click to expand.
1
of 1 vote

IMHO, this is the only viable solution I have seen for 1 hour interview in terms of code size, logic complexity. BST (too much coding), binary indexed tree (un-intuitive logic and still fair amount of coding) are not appropriate for an interview.

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void surpass(int[] a){

int max = 0; int result[] = new int[a.length];
for(int i=1; i<a.length; i++){
for(int j=0; j<i; j++){
if(a[i] > a[j]){
result[j] +=1;
max = Math.max(max, result[j]);
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

not what the question asks. Question was for the maximal. And your approach would not be O(n) memory- you use the same amount of memory that was already consumed by the problem as part of the parameters.

Comment hidden because of low score. Click to expand.
0
of 0 votes

@Zortlord : my mistake.. updated now :)

``````public static void surpass(int[] a){

int max = 0; int result[] = new int[a.length];
for(int i=1; i<a.length; i++){
for(int j=0; j<i; j++){
if(a[i] > a[j]){
result[j] +=1;
max = Math.max(max, result[j]);
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

This is O(N^2) algo.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args){
int[] array = new int[]{2,7,5,5,2,7,0,8,1};
System.out.println(getMaxSurpasser(array, 0));
}

public static int getMaxSurpasser(int [] array, int index){
if(array.length <= index){
return -1;
}
int element = array[index];
int surpasserCount = 0;
for(int i=index + 1; i<array.length; i++){
if(array[i] > element){
surpasserCount ++;
}
}
int nextSurpasserCount = getMaxSurpasser(array, index + 1);
return surpasserCount > nextSurpasserCount ? surpasserCount : nextSurpasserCount;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution takes O(n*n) time and O(n) space. Seems to be not optimal.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args){
int[] array = new int[]{2,7,5,5,2,7,0,8,1};
System.out.println(getMaxSurpasser(array, 0));
}

public static int getMaxSurpasser(int [] array, int index){
if(array.length <= index){
return -1;
}
int element = array[index];
int surpasserCount = 0;
for(int i=index + 1; i<array.length; i++){
if(array[i] > element){
surpasserCount ++;
}
}
int nextSurpasserCount = getMaxSurpasser(array, index + 1);
return surpasserCount > nextSurpasserCount ? surpasserCount : nextSurpasserCount;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Time: O(n log n)
Space: O(n)

``````int maxSurpasser(vector<int> input)
{
vector<int> copied(input.begin(), input.end());
sort(copied.begin(), copied.end());

int maxSurpasser = -1;

for (int const& i : input)
{
auto begin = std::lower_bound(copied.begin(), copied.end(), i);
auto end = std::upper_bound(begin, copied.end(), i);

maxSurpasser = max(maxSurpasser, copied.end() - end);
copied.erase(begin, end);
}

return maxSurpasser;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

The idea is good but the time complexity is not O(n log n) because the time complexity of vector's erase operation is O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class SurPasser {
public static void main(String[] args) {
int a[] = { 2, 7, 5, 5, 2, 7, 0, 8, 1 };
findSurPasser(a);
}

private static void findSurPasser(int[] a) {
int n = a.length;
int sp[] = new int[n];
for (int i = 0; i < n; i++)
sp[i] = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] < a[j])
sp[i] = sp[i] + 1;
}
}
int max = 0;
for (int i = 0; i < n; i++)
if (max < sp[i])
max = sp[i];
System.out.println(max);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a bst inserting elements going from i=0 to N.
Now in this bst find the right subtree which has max number of elements.
complexity: nlogn (avg) worst n2

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````public static int surpasser(int[] arr){
if(arr==null){
throw new NullPointerException();
}

int flagList[arr.length];
int maxS = 0;
flagList[0] = 1;
for (int i=0;i<arr.length;i++){
if(flagList[i]){
int localS = 0;
for (int j=i+1;j<arr.length;j++){
if(arr[i]<arr[j]){
localS++;
flagList[j]=0;
}
else if(arr[i]==arr[j]){
flagList[j]=0;
}
else {
flagList[j]=1;
}
}
if(maxS < localS){
maxS = localS;
}
}
}
return globalS;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

clarification...
1. sorry for the duplicated replies...
2. this is basically a modified version of zortlord's answer above, with an additional list of "what elements to search" (flagList). Basically, when counting the surpassers for an element x, if any compared element y is not smaller than x, you don't need to count the surpassers for y.
3. further, if x has with k surpassers, then there's no need to calculate the number of surpassers for the last k elements in the array.
So the worst case time complexity will be O(n^2), with memory O(n) I think...

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int surpasser(int[] arr){
if(arr==null){
throw new NullPointerException();
}

int flagList[arr.length];
int maxS = 0;
flagList[0] = 1;
for (int i=0;i<arr.length;i++){
if(flagList[i]){
int localS = 0;
for (int j=i+1;j<arr.length;j++){
if(arr[i]<arr[j]){
localS++;
flagList[j]=0;
}
else if(arr[i]==arr[j]){
flagList[j]=0;
}
else {
flagList[j]=1;
}
}
if(maxS < localS){
maxS = localS;
}
}
}
return globalS;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int surpasser(int[] arr){
if(arr==null){
throw new NullPointerException();
}

int flagList[arr.length];
int maxS = 0;
flagList[0] = 1;
for (int i=0;i<arr.length;i++){
if(flagList[i]){
int localS = 0;
for (int j=i+1;j<arr.length;j++){
if(arr[i]<arr[j]){
localS++;
flagList[j]=0;
}
else if(arr[i]==arr[j]){
flagList[j]=0;
}
else {
flagList[j]=1;
}
}
if(maxS < localS){
maxS = localS;
}
}
}
return globalS;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

//defacto binary insetion
public int surpasser(int [] input){

int i = input.length -1;

TreeNode root = new TreeNode(input[i]);
int globalSurpasser =0;
while(i>=0){
int localSurpasser = 0;
boolean foundPlace = false;
while(!foundPlace){
if(input[i]<root.value){
if (root.left != null) {
root = root.left;
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
}
else {
root.left = new TreeNode(input[i]);
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
foundPlace = true;
}
}

else if(input[i]>root.value){
if (root.right != null) {
root = root.right;
}
else{
root.right = new TreeNode(input[i]);
foundPlace = true;
}
}
}

}

return globalSurpasser;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int surpasser(int [] input){

int i = input.length -1;

TreeNode root = new TreeNode(input[i]);
int globalSurpasser =0;
while(i>=0){
int localSurpasser = 0;
boolean foundPlace = false;
while(!foundPlace){
if(input[i]<root.value){
if (root.left != null) {
root = root.left;
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
}
else {
root.left = new TreeNode(input[i]);
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
foundPlace = true;
}
}

else if(input[i]>root.value){
if (root.right != null) {
root = root.right;
}
else{
root.right = new TreeNode(input[i]);
foundPlace = true;
}
}
}

}

return globalSurpasser;

}

Comment hidden because of low score. Click to expand.
0
of 2 vote

time O(nlogn)
space O(n)

Just insert from left to right of the array in a binary tree...as you traverse just count number of left turns...

``````public int surpasser(int [] input){

int i = input.length -1;

TreeNode root =   new TreeNode(input[i]);
TreeNode rootTree = root;
int globalSurpasser =0;
i--;
while(i>=0){
int localSurpasser = 0;

boolean foundPlace = false;
while(!foundPlace){
if(input[i]<root.value){
if (root.left != null) {
root = root.left;
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
}
else {
root.left = new TreeNode(input[i]);
localSurpasser++;
if (localSurpasser > globalSurpasser) {
globalSurpasser = localSurpasser;
}
foundPlace = true;
}
}

else if(input[i]>root.value){
if (root.right != null) {
root = root.right;
}
else{
root.right = new TreeNode(input[i]);
foundPlace = true;
}
}
}
i--;
}

return globalSurpasser;

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi
Consider [0,8,1]; bst will have 1 as a tree. For 0, we have only 1 left turn, but surpasser of 0 is 2. I think just counting left turn is not enough..

Comment hidden because of low score. Click to expand.
1
of 1 vote

When you are inserting elements in your tree, you have to update how many elements are in the left and right subtree for all elements you traverse through while you insert the new values.
i.e
struct Node
{
Node* left, *right;
int value, leftSize, rightSize;
}

Then using those values you can work out how many elements are larger than your current value:

start with sum = root->rightSize
curNode = root;

if turning left:
sum += curNode->rightSize + 1
curNode = curNode->left;
if turning right:
sum -= (curNode->leftSize + 1)
curNode = curNode->right;

when you hit the element in question sum will be the number of elements larger than it in th BST

Comment hidden because of low score. Click to expand.
0
of 0 votes

your code does not work if you run it, have you test it before posting?

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is O(n*logn) average and O(n^2) worst case time complexity and O(n) space: using Binary search tree where each node maintain a bit of information of number of nodes on its right, denoted as num_right

From right to left of the array: take an element a[i] to add to the tree by traverse from root, find the suitable place to add a[i], like BST insert, and do the following extra work at each node k:
- if need to go right child of k: (node k).num_right++
- if need to go left of k: surpassers[i] += (node k).num_right+1

Since each step take O(h), average is O(logn) and worst case is O(n), so in the end it is O(nlogn) avg and O(n^2) worst case

-

Comment hidden because of low score. Click to expand.
0
of 0 votes

If we use self balanced binary search tree, we can ensure the O(n*logn) time complexity. It's more complicated though.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Using a BST adds storage as auxiliary info, where the elements are already known in the input. Hence, using a BST does not optimize the algo.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it would be simplest to sort the array: bound below by nlogn due to comparison. Then, the max surpasser is found by iterating from index 0 and subtracting by one until a new element is found: O(n). The total running time would be O(nlogn).

Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction: subtract one when a new element is found, iterating from index 0

Comment hidden because of low score. Click to expand.
0
of 0 votes

Curiously, is it possible to do better than O(nlogn) and constant space? If the input is immutable, then the problem is more complex

Comment hidden because of low score. Click to expand.
0
of 0 votes

> the max surpasser is found by iterating from index 0 and subtracting by one until a new element is found

@Yev, What is the start value of max surpasser in above step?

Comment hidden because of low score. Click to expand.
0
of 0 votes

@Yev: Can you illustrate your solution using this example: 1,3,6,2,8,3

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time Complexity: O(n)
Space Complexity: O(n)

``````public class surpass {

public static void main(String a[])   {
int[] aa = {2,7, 5, 5, 2, 7, 0, 8, 1};
System.out.print(maxSurpass(aa)) ;
}

public static int maxSurpass(int[] a) {
int max = 0;

Node[] surpass  = new Node[a.length];
for (int i = 0; i < a.length ; i ++) {
if (surpass[i] == null)
surpass[i] = new Node(a[i]);
for ( int j = 0; j < i; j++)
if (surpass[j].getData() < a[i])
surpass[j].incrementSurpass();
}

for (int j=0; j < surpass.length; j++)
if (surpass[j].getSurpass().get() > max)
max = surpass[j].getSurpass().get();

return max;
}

}

class Node {
private int data;
private Node next;
private Node previous;
private AtomicInteger surpass;

Node(int d){
this.data = d;
this.surpass = new AtomicInteger(0);
}

Node(int d, Node n) {
this.data = d;
this.next = n;
}

Node(int d, Node n, Node p) {
this.data = d;
this.next = n;
this.previous = p;
}

public void incrementSurpass() {
this.surpass.getAndIncrement();
}

public void decrementSurpass() {
this.surpass.getAndDecrement();
}

public int getData() {
return data;
}
public Node getNext() {
return next;
}
public Node getPrevious() {
return previous;
}
public AtomicInteger getSurpass() {
return surpass;
}

public String toString() {
return "[ Data: "+ getData() + "; surpass: " + getSurpass().get() + "]";
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

this is n^2, not O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Time Complexity: O(n)
Space Complexity: O(n)

``````package ds;

import java.util.concurrent.atomic.AtomicInteger;

public class surpass {

public static void main(String a[])   {
int[] aa = {2,7, 5, 5, 2, 7, 0, 8, 1};
System.out.print(maxSurpass(aa)) ;
}
public static int maxSurpass(int[] a) {
int max = 0;
Node[] surpass  = new Node[a.length];
for (int i = 0; i < a.length ; i ++) {
if (surpass[i] == null)
surpass[i] = new Node(a[i]);
for ( int j = 0; j < i; j++)
if (surpass[j].getData() < a[i])
surpass[j].incrementSurpass();
}
for (int j=0; j < surpass.length; j++)
if (surpass[j].getSurpass().get() > max)
max = surpass[j].getSurpass().get();
return max;
}
}

class Node {
private int data;
private Node next;
private AtomicInteger surpass;
Node(int d){
this.data = d;
this.surpass = new AtomicInteger(0);
}
Node(int d, Node n) {
this.data = d;
this.next = n;
}
public void incrementSurpass() {
this.surpass.getAndIncrement();
}
public int getData() {
return data;
}
public Node getNext() {
return next;
}
public AtomicInteger getSurpass() {
return surpass;
}
public String toString() {
return "[ Data: "+ getData() + "; surpass: " + getSurpass().get() + "]";
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

why is the time complexity is O(n) while doing loop inside loop.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Copying an answer from SO:

Solution 1

I don't know if this is the same as Rem's solution, but you could solve this quite easily with a binary search tree.

Initialize an empty binary search tree and then iterate in reverse order through the array.

Insert each element in the binary search tree and then perform a count of all the elements in the tree above the value of the element. (If each subtree stores the number of elements it contains, then these operations can both be done in O(logn) if an appropriate balanced tree is used.)

The max number of successors is given by the largest count observed.

Comment hidden because of low score. Click to expand.
0
of 0 votes

The sample code on SO is overly simplified. The actually implementation is much more complicated if you need to implement index sort, consider duplicate numbers. However, BIT is still a great idea and may possibly still easier to code compared with other solutions.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is almost the same as hieu.pham's solution above using BST and adding # of right nodes as an additional tree node property. One additional detail is handling of equal values. A value should be inserted to the left of a node with the same value and its surpasser should be increased by numRight of the node instead of (numRIght + 1).

Here is a C++ implementation.

``````#include <iostream>
#include <vector>
using namespace std;

struct TreeNode {
TreeNode *left;
TreeNode *right;
int data;
unsigned numRight;

TreeNode(int value) : left(NULL), right(NULL), data(value), numRight(0) {}
};

class BST {
private:
TreeNode *root;

unsigned InsertToSubTree(int value, TreeNode *subRoot) {
if (value <= subRoot->data) {
auto countMe = value < subRoot->data ? 1 : 0;

if (subRoot->left == NULL) {
subRoot->left = new TreeNode(value);

return (subRoot->numRight + countMe);
}

return (InsertToSubTree(value, subRoot->left) + subRoot->numRight + countMe);
}
else {
subRoot->numRight++;
if (subRoot->right == NULL) {
subRoot->right = new TreeNode(value);
return 0;
}

return InsertToSubTree(value, subRoot->right);
}
}

public:
BST() : root(NULL) {}

unsigned FindSurpasser(int value) {
if (root == NULL) {
root = new TreeNode(value);
return 0;
}

return InsertToSubTree(value, root);
}
};

int main()
{
std::vector<int> input { 2, 7, 5, 5, 2, 7, 0, 8, 1 };
BST bTree;

unsigned maxSurpasser = 0;

for (unsigned i = input.size(); i-- > 0; ) {
unsigned surPasser = bTree.FindSurpasser(input[i]);
cout << "input " << input[i] << " surPasser " << surPasser << endl;
maxSurpasser = max(surPasser, maxSurpasser);
};

cout << maxSurpasser << endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

And no one thinks that this might not be an actual google interview question? O(n^2) is fine but anyone trying to do O(nlgn) on phone, good luck....I would urge to search web for "surpasser count"

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void maxSurpasserOfArray(int iArr[SIZE])
{
int resArr[SIZE]={0};
int max =0;
for(int i=0;i<9;i++)
{
for(int j=i+1;j<SIZE;j++)
{
if(iArr[i]<iArr[j])
resArr[i] = resArr[i]+1;
}
if(max<resArr[i])
max = resArr[i];
}
cout << "\n max surpasser is "<< max;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

there are a data structure named Binary Indexed Tree(BIT), it can solve this problem well. ps. if the data range is so large, we can hash each different num to a continuous sequence.

Comment hidden because of low score. Click to expand.
0
of 2 vote

Quick and easy idea:
Remember where each element was.
Sort the array (descending). For each element, see how many spaces to the right it moved in the sort.

Comment hidden because of low score. Click to expand.
0
of 0 votes

This won't work. Consider:

``[10, 3, 4, 5, 2]``

When sorted, it becomes:

``[2, 3, 4, 5, 10 ]``

The value 4 doesn't move at all. By your logic, there are no surpassers for 4. However, 5 is a surpasser for 4.

Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem can be with not unique values:

``[10, 3, 4, 5, 2, 4]``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````maxVal = 0;
function insert(cNode, val, vishnu, parentNode, dir){
if(!cNode){
parentNode[dir] = {val: val, cnt: vishnu};
maxVal = Math.max(maxVal, vishnu);
return;
}

if(val <= cNode.val){
insert(cNode.left, val, cNode.cnt + 1, cNode, 'left');
return;
}

cNode.cnt++;
insert(cNode.right, val, vishnu, cNode, 'right');
}

var p = {left: null};
[6,1,5,2,4,3].forEach(function(val){

insert(p.left, val, 0, p, 'left');
});

console.log(maxVal);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````maxVal = 0;
function insert(cNode, val, surpasser, parentNode, dir){
if(!cNode){
parentNode[dir] = {val: val, cnt: surpasser};
maxVal = Math.max(maxVal, surpasser);
return;
}

if(val <= cNode.val){
insert(cNode.left, val, cNode.cnt + 1, cNode, 'left');
return;
}

cNode.cnt++;
insert(cNode.right, val, surpasser, cNode, 'right');
}

var p = {left: null};
[3,2,4,1,2,3,5].reverse().forEach(function(val){
insert(p.left, val, 0, p, 'left');
});

console.log(maxVal);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can solve this problem with reverse merge sort.

``````public static class Solution {

int max;
Map<Integer, Integer> map;

int getSurpasser(int[] nums) {
max = 0;
map = new HashMap<Integer, Integer>();

mergeSort(nums, 0, nums.length - 1);

return max;
}

void mergeSort(int[] a, int lo, int hi) {
if (lo >= hi) return;

int mid = lo + (hi - lo) / 2;

mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);

reverseMerge(a, lo, mid, hi);
}

void reverseMerge(int[] a, int lo, int mid, int hi) {
if (lo >= hi)
return;

// make a copy of a[]
int[] c = new int[a.length];
System.arraycopy(a, 0, c, 0, a.length);

// reverse merge
for (int k = hi, i = mid, j = hi; k >= lo; k--) {
if (i < lo)            a[k] = c[j--];
else if (j < mid + 1)  a[k] = c[i--];
else if (c[i] >= c[j]) a[k] = c[j--];
else {
// We need to avoid duplicates
if (i == mid || c[i] != c[i + 1]) {
int count = map.containsKey(c[i]) ? map.get(c[i]) : 0;
count += j - mid;
map.put(c[i], count);
max = Math.max(max, count);
}

a[k] = c[i--];
}
}

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static int findMaxSurpass(int[] arr)
{
int[] indexArr = new int[arr.Length];
int[] surpassArr = new int[arr.Length];

for(int i =0; i < arr.Length; i++)
{
indexArr[i] = i;
}
mergeSort(arr, 0, arr.Length - 1, indexArr, surpassArr);
int max = 0;
for (int i = 0; i < surpassArr.Length; i++)
{
if(surpassArr[i] > max)
{
max = surpassArr[i];
}
}
return max;
}

public static void mergeSort(int[] arr, int left,int right,int[] indexArr, int[] surpassArr)
{
if(left < right)
{
int mid = (left + right) / 2;
mergeSort(arr, left, mid, indexArr, surpassArr);
mergeSort(arr, mid + 1, right, indexArr, surpassArr);

int i = left;
int j = mid + 1;
int k = left;

int[] temp = new int[arr.Length];
while(i <= mid && j <= right)
{
if(arr[indexArr[i]] < arr[indexArr[j]])
{
surpassArr[indexArr[i]] += right - j +1;
temp[k++] = indexArr[i++];
}
else
{
temp[k++] = indexArr[j++];
}
}

while (i <= mid)
{
temp[k++] = indexArr[i++];
}
while (j <= right)
{
temp[k++] = indexArr[j++];
}

for(int l = left; l <= right;l++)
{
indexArr[l] = temp[l];
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findMaxSurpass(int[] arr)
{
int[] indexArr = new int[arr.Length];
int[] surpassArr = new int[arr.Length];

for(int i =0; i < arr.Length; i++)
{
indexArr[i] = i;
}
mergeSort(arr, 0, arr.Length - 1, indexArr, surpassArr);
int max = 0;
for (int i = 0; i < surpassArr.Length; i++)
{
if(surpassArr[i] > max)
{
max = surpassArr[i];
}
}
return max;
}

public static void mergeSort(int[] arr, int left,int right,int[] indexArr, int[] surpassArr)
{
if(left < right)
{
int mid = (left + right) / 2;
mergeSort(arr, left, mid, indexArr, surpassArr);
mergeSort(arr, mid + 1, right, indexArr, surpassArr);

int i = left;
int j = mid + 1;
int k = left;

int[] temp = new int[arr.Length];
while(i <= mid && j <= right)
{
if(arr[indexArr[i]] < arr[indexArr[j]])
{
surpassArr[indexArr[i]] += right - j +1;
temp[k++] = indexArr[i++];
}
else
{
temp[k++] = indexArr[j++];
}
}

while (i <= mid)
{
temp[k++] = indexArr[i++];
}
while (j <= right)
{
temp[k++] = indexArr[j++];
}

for(int l = left; l <= right;l++)
{
indexArr[l] = temp[l];
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Start inserting elements in a BST from rightmost element of array (i.e) last element.

for each node, keep these fields,
int ans, key, num_greater
node *left, *right

num_greater will contain number of elements greater than then the node value at that instance.
for each node, keep updating num_greater, if some element goes in right subtree of that node.

when inserting each node, its ans will start from 0 at root, and ans will keep on getting updated depending on whether we go into right subtree or left subtree, till we reach a leaf and insert the key.

if we go right, ans will remain same,
if we go left, ans will increment by (node->num_greater) + (node->key > key ? 1 : 0)

when you insert your node, you will have surpasser for that key.
you can keep a maximum answer and after inserting all elements you will have your answer,

BST worst case time will be n2

you can use AVL tree for worst case time of nlogn

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void sort(int *src, int *dest, int lo, int hi, int *a, int *sp) {
if (hi <= lo) {
return;
}
int mid = lo + ((hi - lo) >> 1);
sort(dest, src, lo, mid, a, sp);
sort(dest, src, mid + 1, hi, a, sp);

int pos = hi;
int i = mid, j = hi;
while (i >= lo && j > mid) {
if (a[src[i]] < a[src[j]]) {
dest[pos--] = src[j--];
}
else {
sp[src[i]] += hi - j;
dest[pos--] = src[i--];
}
}

while (i >= lo) {
sp[src[i]] += hi - mid;
dest[pos--] = src[i--];
}
while (j > mid)
dest[pos--] = src[j--];
}

int maxSurpasser(int *a, int n) {
int *index = new int[n];
int *sp = new int[n];
int *buf = new int[n];
memset(sp, 0, sizeof(int) * n);
for (int i = 0; i < n; ++i)
index[i] = i;
memcpy(buf, index, sizeof(int) * n);

sort(buf, index, 0, n - 1, a, sp);

int ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, sp[i]);

return ans;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Quite long solution using tree with cached size of the right subtree for each node. Complexity: time O(n log n), space: O(n)

``````public int getMaxSupessor(int[] array) {
Tree tree = new Tree();
int maxSupessor = Integer.MIN_VALUE;
for(int i=array.length-1; i>=0; i--) {
tree.add(array[i]);
maxSupessor = Math.max(maxSupessor, tree.getSupessor(array[i]));
}
return maxSupessor;
}

public class Tree {
private Node root;

public void add(int value) {
if (root == null)
root = new Node(value);
add(value, root);
}

private void add(int value, Node node) {
if (value == node.value) {
node.count++;
return;
}

if (value < node.value) {
if (node.left == null)
node.left = new Node(value);
else
add(value, node.left);
} else {
node.rightSize++;
if (node.right == null)
node.right = new Node(value);
else
add(value, node.right);
}
}

public int getSupessor(int value) {
return getSupessor(value, root);
}

private int getSupessor(int value, Node node) {
if (node == null)
return 0;
if (value < node.value)
return node.count + node.rightSize + getSupessor(value, node.left);
if (node.value < value)
return getSupessor(value, node.right);
return node.rightSize;
}
}

public class Node {
public int value;
public Node left;
public Node right;
public int count;
public int rightSize;

public Node(int value) {
count = 1;
rightSize = 0;
this.value = value;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I create a map of potentially approritate items
value -> surpasser

we go from left to right,
if next item can be used as potential only if it is less than minimum in array of potentials.
Otherwise we increase counter of all potential which are less than item.

Best case: n
Worst case: n*n

``````int get_maximum_surpasser()
{
int array_size = 0;
int * vals= input_array( array_size );

if( array_size == 0 )
{
return 0;
}

std::set<map> potential;
int minimal_preferred = vals[0];
potential.insert( std::pair<int,int>( minimal_preferred, 0 ) );

for( int i = 1; i < array_size; ++i )
{
for( auto it = potential.begin(); it != potential.end(); ++it )
{
if( it->first < vals[i] )
it->second ++;
else
break;
}
if( vals[i] < minimal_preferred )
{
minimal_preferred = vals[i];
potential.insert( std::pair<int,int>( minimal_preferred, 0 ) );
}
}

int max = 0;
for( auto it = potential.rbegin(); it != potential.rend(); ++it )
{
if( it->second > max )
max = it->second();
}
}``````

What do you think about this?

Comment hidden because of low score. Click to expand.
0
of 0 vote

c# implementation.
Time: O(nlogn).
Space: O(n).

``````static private int GetGreatestNumberOfSurpassers( int[] arr ) {

var initIndexes = new Dictionary<int, Queue<int>>();

for ( int i = 0; i < arr.Length; i++ ) {
var currElm = arr[ i ];
if ( initIndexes.ContainsKey( currElm ) ) {
initIndexes[ currElm ].Enqueue( i );
continue;
}
var queue = new Queue<int>();
queue.Enqueue( i );
initIndexes[ currElm ] = queue;
}

Array.Sort( arr ); arr = arr.Reverse().ToArray(); // Merge Sort

int res = 0;
for ( int i = 0; i < arr.Length; i++ ) {
var curr = i - initIndexes[ arr[ i ] ].Dequeue();
if ( curr > res ) {
res = curr;
}
}
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````var countSurpasser = function(ar) {

var result = [];

for(var i = 0; i < ar.length; i++) {
count = 0
for(j = i + 1; j < ar.length; j++) {
if(ar[j] > ar[i]) {
count++;
}
}
result.push(count);
}
return result;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using partition approach.

Speed O (n log n)
Space O (n)

``````public int findMaxSurpasser(int[] a) {
// partition from i to j. Complexity: O (log n)
// keep track of max surpasser.
// last element will be 0 so don't loop for that. (optimization)
if (a.length < 2) return 0;
int max = 0;
for (int i = 0; i < a.length-1; i++) {
int[] sortingA = new int[a.length-i];
System.arraycopy(a,i,sortingA,0, sortingA.length);
// position of the pivot
int pos = partition(sortingA);
// count # of elements on right of pivot
int diff = sortingA.length - pos - 1;
max = Math.max(max, diff);
}
return max;
}

public int partition(int[] a) {
int pivot = a[0];
int i = 1;
for (int j = 1; j < a.length; j++) {
if (a[j] <= pivot) {
swap(a, i, j);
i++;
}
}
swap(a, i-1, 0);
return i-1;
}

public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using partition approach.

Time : O (n log n)
Space : O (n)

``````public int findMaxSurpasser(int[] a) {
// partition from i to j. Complexity: O (log n)
// keep track of max surpasser.
// last element will be 0 so don't loop for that. (optimization)
if (a.length < 2) return 0;
int max = 0;
for (int i = 0; i < a.length-1; i++) {
int[] sortingA = new int[a.length-i];
System.arraycopy(a,i,sortingA,0, sortingA.length);
// position of the pivot
int pos = partition(sortingA);
// count # of elements on right of pivot
int diff = sortingA.length - pos - 1;
max = Math.max(max, diff);
}
return max;
}

public int partition(int[] a) {
int pivot = a[0];
int i = 1;
for (int j = 1; j < a.length; j++) {
if (a[j] <= pivot) {
swap(a, i, j);
i++;
}
}
swap(a, i-1, 0);
return i-1;
}

public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is one of those things where it cannot really be simplified. O(n^2) complexity and O(1) memory:

``````public static int surpasser(int[] arr){
if(arr == null){
throw new NullPointerException();
}

int maxSurpasser = 0;
for(int i = 0; i < arr.length; i++){
int localSurpasser = 0;
for(int j = i+1; j < arr.length; j++){
if(arr[i] < arr[j]){
localSurpasser++;
}
}
if(localSurpasser > maxSurpasser){
maxSurpasser = localSurpasser;
}
}
return maxSurpasser;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

not true. There are O(nlogn) solutions.

Comment hidden because of low score. Click to expand.
-1
of 7 vote

this can be done in nlogn.
1.Store the position of each element for that we can use an object with
{
val: value
position: array_index
}

for each element in the array
2.Then sort the object array created above with value.
3.Subtract the old position from the new position for each element. i.e (old position - new position) remember don't take absolute value .
and the maximum of this is the maximum surpasser of the array

Comment hidden because of low score. Click to expand.
2
of 2 votes

[2,7,5,5,2,7,0,8,1]
sort = [0,1,2,2,5,5,7,7,8]
old_pos =[6,8,0,4,2,3,1,5,7]
new_pos = [0,1,2,3,4,5,6,7,8]
old_pos - new_pos = [6,7,-1,1,-2,-2,-5,-2,-1]

Max = 6
??

Comment hidden because of low score. Click to expand.
0
of 0 votes

duplicates would a problem with this approach imagine a array with all same element like 1,1,1,1,1,1,1,1

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More