## Google Interview Question for Software Engineer / Developers

Team: Autocomplete
Country: United States
Interview Type: Written Test

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

it's very similar to merge sort, we have to maintain another array with the same size that keeps the current "qaz" of each number, assume the initial array is 33 , 48 , 26 , 58 , 41 , 59
I just explain the last step of the merge sort
First half: 26(0), 33(1), 48(0)
Second half: 41(1), 58(1), 59(0)
Update "qaz" of the first half before merging the two sorted arrays,
-traverse both arrays from end to the beginning,
-move the pointer which is pointing to the bigger number,
-when moving the pointer of the second array, increase added_qaz
-when moving the pointer to the first array, apply (add) qaz before moving
-when the loop ends, increase qaz of the numbers in the first half from where the pointer is to the beginning
void UpdateQAZ(int low, int mid, int high)
{
int i,j;

i = mid;
j = high;

while ( ( i >= 0 ) && ( j > mid ) )
{
if ( A[ j ] > A[ i ] )
{
j--;
}
else
{
i--;
}
}

if ( j <= mid )
{
for ( x = i ; x >=low ; x-- )
{
}
}
}
Trace:
low = 0, mid = 2, high=5, added_qaz = 0
iterations:
1. i = 2, j = 5, added_qaz = 1
2. i = 2, j = 4, added_qaz = 2
3. i = 2, j = 3, added_qaz = 2, increase qaz of 48 by 2
4. i = 1, j = 3, added_qaz = 3
5. i = 1, j =2 : loop ends
Second loop:
x = 1 => , increase qaz of 33 by 3
x = 0 => , increase qaz of 26 by 3

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

Here is code:

``````void UpdateQAZ(int low, int mid, int high)
{
int i,j;

i = mid;
j = high;

while ( ( i >= 0 ) && ( j > mid ) )
{
if ( A[ j ] > A[ i ] )
{
j--;
}
else
{
i--;
}
}

if ( j <= mid )
{
for ( x = i ; x >=low ; x-- )
{
}
}
}``````

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

koosha.nejad -- send me a message to my email : geniucode@gmail.com

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

I think alllowing i to be less than low would cause numbers in the second half to be double counted. Should the loop have the following instead or if not could someone explain why?

``while ( ( i >= low ) && ( j > mid ) )``

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

Modified the MergeSort algorithm for this problem - Time Complexity - O(nlogn)

``````#include<utility>
#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

unordered_map<int, int> q;

unordered_map<int, int> initializeQAZ(vector<int> &A, int vsize)
{
unordered_map<int, int> qaz;
for(int i = 0; i < vsize; i++)
{
qaz[A[i]] = 0;
}
return qaz;
}

vector<int> merge_sort(vector<int> &l, vector<int> &r)
{
vector<int> result;
unsigned left_it = 0, right_it = 0;
while(left_it < l.size() && right_it < r.size())
{
if(l[left_it] < r[right_it])
{
result.push_back(l[left_it]);
q[l[left_it]] += (r.size() - right_it);
left_it++;
}
else
{
result.push_back(r[right_it]);
right_it++;
}
}
while(left_it < l.size())
{
result.push_back(l[left_it]);
left_it++;
}
while(right_it < r.size())
{
result.push_back(r[right_it]);
right_it++;
}
return result;
}

vector<int> mergeSort(vector<int> &A)
{
if(A.size() == 1)
return A;

vector<int>::iterator middle = A.begin() + A.size()/2;
vector<int> leftV(A.begin(), middle);
vector<int> rightV(middle, A.end());

leftV = mergeSort(leftV);
rightV = mergeSort(rightV);

return merge_sort(leftV, rightV);
}

int main(int argc, char** argv)
{
int B[] = {33, 25, 26, 58, 41, 59};
vector<int> A(B, B + sizeof(B) / sizeof(B));
q = initializeQAZ(A, A.size());
vector<int> sortedA = mergeSort(A);
for(int i = 0; i < A.size(); i++)
{
cout << A[i] << "  ";
}
cout << endl;
for(int i = 0; i < sortedA.size(); i++)
{
cout << sortedA[i] << "  ";
}

cout << endl;
for(int i = 0; i < A.size(); i++)
{
cout << A[i] << "  " << q[A[i]] << endl;
}
return 0;
}``````

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

This is another MergeSort-like solution in Java, that just tries to be easier to read.
It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

``````public class QAZ {

public static void main(String[] args) {
int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
System.out.println(getMaxQAZ(array));
}

public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length).qaz;
}

private static QAZResult getMaxQAZ(int[] array, int start, int end) {

if (end - start <= 3) {
return getLastLocalMaxQAZ(array, start, end);
}

int middle = (end + start) / 2;

QAZResult leftResult = getMaxQAZ(array, start, middle);

QAZResult rightResult = getMaxQAZ(array, middle, end);

if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}

for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}

return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;

}

private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){

int minVal = array[start];
int qaz = 0;
for (int i = start + 1; i < end; i++) {
if (array[i -1] < array[i]) {
qaz++;
} else {
minVal = array[i];
}
}
return new QAZResult(minVal, qaz);
}
}

class QAZResult {
int minVal;
int qaz;

public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}``````

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

Does this work for {7, 8, 2, 3, 4, 5}? The Answer Should be 3, but i believe your program produces 4?

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

If input is {4, 33 , 25 , 26 , 58 , 41 , 59 }, your code returns 4. Right answer should be 6.

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

This is really easy and nice approach with small flaw in it. Better to keep the granularity to 2 while dividing, the merging works perfect. Here is the updated code:

``````public class HelloWorld {

public static void main(String[] args) {
int[] array = {7, 8, 2, 3, 4, 5 };
System.out.println(getMaxQAZ(array));
}

public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length-1).qaz;
}

private static QAZResult getMaxQAZ(int[] array, int start, int end) {
if (end <= start) {
return new QAZResult(array[end], 0);
}

if (end == start+1) {
if (array[start] < array[end]) {
return new QAZResult(array[start], 1);
}

return new QAZResult(array[end], 0);
}

int middle = (end + start) / 2;

QAZResult leftResult = getMaxQAZ(array, start, middle);

QAZResult rightResult = getMaxQAZ(array, middle+1, end);

if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}

for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}

return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;
}
}

class QAZResult {
int minVal;
int qaz;

public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}``````

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

To pavelkushtia,
This is not a correct solution!
What Anselmo said about "It is based on the observation that the element that holds the max QAZ is a local minimum of the array" is not correct.
For example, for array = { 25, 33, 26, 58, 41, 59, 4 }. The minimum of array is 4. the QAZ of 4 is 0. Obviously, the QAZ of this array is from 25, which is 5.
You should try this test case in your code and see the result.

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

Allen,
my code had a couple of minor bugs that Pavelkushtia noticed and fixed brilliantly (thanks Pavel!).

But the implant of my solution, I believe, is substantially correct and the observation about local minimums is correct as well.

A local minimum of a function is a different concept than absolute minimum. In the array you posted: { 25, 33, 26, 58, 41, 59, 4 }, 4 is a local and absolute minimum, but 25 is another local minimum.

A local minimum needs to be smaller or equal to the values besides it, is any, that's it.

Now think again, and you will see that the max QAZ holder needs to be a local minimum.

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

Hi Anselmo,
Can you fix the code? I ran the code. I don't think either your code or pavelkushtia's code for { 25, 33, 26, 58, 41, 59, 4 } is correct.

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

modified merge sort is nice solution.

I do have 1 more algo which is having complexity : O(nlogn).

say array is
A [] = { 33 , 25 , 26 , 58 , 41 , 59}

step 1 : create ArrayList of size = A.length
step 2 : sort ArrayList in ascending order O(nlog(n))

ArrayList => { 25 , 26 , 33, 41, 58 , 59 }

step 3 : choose 1st element of A[] ie 33
=> qaz(33) => total elements in ArrayList after 33
=> qaz(33) = 3

remove element 33 from ArrayList
now ArrayList = {25 , 26 , 41, 58 , 59 }

step 4: choose next element from A[] ie 25
=> qaz(25) = total elements in ArrayList after 25
=> qaz(25) = 4

remove element 25 from ArrayList
now ArrayList = {26 , 41, 58 , 59 }

step 5: choose next element from A[] ie 26
=> qaz(26) = total elements in ArrayList after 26
=> qaz(26) = 3

remove element 26 from ArrayList
now ArrayList = {41, 58 , 59 }

step 6: choose next element from A[] ie 58
=> qaz(58) = total elements in ArrayList after 58
=> qaz(58) = 1

remove element 58 from ArrayList
now ArrayList = {41 , 59 }

step 7: choose next element from A[] ie 41
=> qaz(41) = total elements in ArrayList after 41
=> qaz(41) = 1

remove element 41 from ArrayList
now ArrayList = { 59 }

last step: choose next element from A[] ie 59
=> qaz(59) = total elements in ArrayList after 59
=> qaz(59) = 0

remove element 59 from ArrayList
now ArrayList = {}

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

are you physically removing items from ArrayList ? if yes, then it'd be O(n), if No, then finding number of elements after a certain element is again O(n),
your algorithm works, but I'm afraid it's O(n^2)

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

thanks Koosha ,
As the array list is already sorted, we can use binary search ( O(logn) ) for finding the index of element to be removed.

once the index of element is known then deletion is O(1) .

Similarly Binary search can be used for finding number of elements after a certain element .

Hence the over all complexity would be O(nlogn) only!

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

How the delete operation can take O(1)?
Doesn't the delete required to shifts any elements after the index to the left ?

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

@Boris : sorted elements are stored in ArrayList , but not in array. And arrayList tooks O(1) for delete operation

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

If I'm not mistaken, you are removing the element logically, which takes O(1); in the case when you remove 33 from { 25 , 26 , 33, 41, 58 , 59 } , you will have
{ 25 , 26 , NULL, 41, 58 , 59 }, now finding elements after 25 (step 4) will be O(n)

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

yes koosha you are correct.

Is there any method in O(logn) to determine number of elements after specific element in sorted list excluding ones that are already processed?

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

I don't think so

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

You should think the difference between array and list.
array - can use binary search but delete costs O(n)
list - the time complexity of binary search for the linked list is not nLogn since it takes O(n/2) to find mid of the list.

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

``````I think this is the right idea or approach especially during a 40 min interview. The merge-sort like solutions are great but i doubt many people can code those cleanly under duress and mistake-free.
Here is what I came up with to correct the slow search:

MAX-QAZ ( int[] array )

1. maxQaz = 0

2. Q = PRIORITY-QUEUE

3. for i = array.length - 1 to 0                   // starts from the back

4.       index pos = Q.insert ( array[i] )     // this Q returns the index of the element

5.       qaz = Q.size -  pos

6.        if qaz > maxQaz

7.                 maxQaz = qaz

8.  return maxQaz``````

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

``````MAXIMUM-QUAZ ( int[] array )

1. MaxQaz = 0

2. Q = PRIORITY-QUEUE

3. for i = array.length - 1 to 0

4.     index = Q.insert ( array [ i ] )   // return index of newly inserted element

5.     qaz = Q.size - index

6.     if ( qaz > MaxQaz )

7.         MazQaz = qaz

8. return MazQaz``````

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

``````MAXIMUM-QUAZ ( int[] array )

1. MaxQaz = 0

2. Q = PRIORITY-QUEUE

3. for i = array.length - 1 to 0

4.     index = Q.insert ( array [ i ] )   // return index of newly inserted element

5.     qaz = Q.size - index

6.     if ( qaz > MaxQaz )

7.         MazQaz = qaz

8. return MazQaz``````

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

``````MAXIMUM-QUAZ ( int[] array )

1. MaxQaz = 0

2. Q = PRIORITY-QUEUE

3. for i = array.length - 1 to 0

4.     index = Q.insert ( array [ i ] )

5.     qaz = Q.size - index

6.     if ( qaz > MaxQaz )

7.         MazQaz = qaz

8. return MazQaz``````

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

This is another MergeSort-like solution in Java, that just tries to be easier to read.
It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

``````public class QAZ {

public static void main(String[] args) {
int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
System.out.println(getMaxQAZ(array));
}

public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length).qaz;
}

private static QAZResult getMaxQAZ(int[] array, int start, int end) {

if (end - start <= 3) {
return getLastLocalMaxQAZ(array, start, end);
}

int middle = (end + start) / 2;

QAZResult leftResult = getMaxQAZ(array, start, middle);

QAZResult rightResult = getMaxQAZ(array, middle, end);

if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}

for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}

return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;

}

private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){

int minVal = array[start];
int qaz = 0;
for (int i = start + 1; i < end; i++) {
if (array[i -1] < array[i]) {
qaz++;
} else {
minVal = array[i];
}
}
return new QAZResult(minVal, qaz);
}
}

class QAZResult {
int minVal;
int qaz;

public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}``````

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

``````MAXIMUM-QUAZ ( int[] array )

1. MaxQaz = 0

2. Q = PRIORITY-QUEUE

3. for i = array.length - 1 to 0

4.     index = Q.insert ( array [ i ] )   // return index of newly inserted element

5.     qaz = Q.size - index

6.     if ( qaz > MaxQaz )

7.         MazQaz = qaz

8. return MazQaz``````

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

Since they want O(nlogn) they probably want something to do with sorting or divide and conquer. My solution is merge sort, but you have another array storing counts :
Lets call the original array A, and the max array Max
1. Recursively cut the array in half like in merge sort
2. Merge Process:
Let's assume leftIndex is the starting index of the left side and rightIndex is the starting of the right side. Lets say endRight is the end of the right and endLeft is end of left.
1. Check to see whether the starting index of the right side or left side is bigger.
2. If the left side is bigger, update Max[leftIndex] += endLeft - rightIndex. Then do the swapping in the same way you would for both arrays.
3. If the right side is bigger, just do the swapping for both array like you would normally.

Once you are done you can just search for the biggest number in Max[], which would take O(n). So the complexity is nLgn + n, or O(nLgn).

I wonder if there is a way to do this without an extra array. You can probably keep track of the max during the merge process so you can cut out the last O(n) operation. Let me know if I made any mistakes!

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

hi, I think you are in the right way, but can you please code it ( write a code ).
if you can show us what is happening in each step.
they ask me to write a code.

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

The code is kind of big to write, but I pretty much rewrote Merge sort and added a little extra so it wasn't too bad. Obviously I had the luxury of a IDE, but the interviewer should steer you in the right direction if you make any mistakes.

``````static public int maxQaz(int[] A) {
int[] max = new int[A.length];
return mergeQazUtil(A, max, 0, A.length - 1);
}

static public int mergeQazUtil(int[] A, int[] Max, int start, int end) {
if(start == end) return 0;
int mid = (start + end)/2;
int leftRes = mergeQazUtil(A, Max, start, mid);
int rightRes = mergeQazUtil(A, Max, mid + 1, end);
int merged = merge(A, Max, start, end, mid);
return Math.max(leftRes, Math.max(rightRes, merged));
}

static public int merge(int[] A, int[] Max, int start, int end, int mid) {
int[] AHelper = new int[A.length];
int[] MaxHelper = new int[Max.length];
for(int i = 0; i < A.length; i++) {
AHelper[i] = A[i];
MaxHelper[i] = Max[i];
}
int leftStart = start, leftEnd = mid, rightStart = mid + 1, rightEnd = end;
int index = start;
int max = 0;
while(leftStart <= leftEnd && rightStart <= rightEnd) {
int curMax = 0;
//this is assuming no numbers are equal
if(AHelper[leftStart] < AHelper[rightStart]) {
MaxHelper[leftStart] += (rightEnd - rightStart) + 1;
curMax = MaxHelper[leftStart];
A[index] = AHelper[leftStart];
Max[index] = MaxHelper[leftStart];
leftStart++;
} else {
A[index] = AHelper[rightStart];
Max[index] = MaxHelper[rightStart];
rightStart++;
}
if(curMax > max) max = curMax;
index++;
}
if(index <= end) {
A[index] = AHelper[leftStart];
Max[index] = MaxHelper[leftStart];
}
return max;
}``````

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

Not enough time to complete the code, but this is the basic idea. We modify merge sort, so that whenever we add in an element from "the left side", we will add the difference between the end of the right side and the right side iterator to a hashed stored value for the element's qez.

For example, if we merge:

[11, 10, 5, 12, 20]

Our steps look like this:

[11, 10] -> [10, 11], No QEZ
[5, 12] -> QEZ of 5 is 1
[5, 12],  -> QEZ of 5 increases by 1, QEZ of 12 becomes 1

now when we merge

[10, 11] and [5, 12, 20]

 -> no QEZ change
[5,10] -> QEZ of 10 is now 2 because right pointer is pointing at 12
[5, 10, 11] -> QEZ of 11 is 2 because right pointer is pointing at 12
[5, 10, 11, 12, 20] -> No QEZ change for 12 and 20 since while loop ends the merge

Not enough time to complete the code, but the basic gist of the merge method is like this:
end refers to the location of the end of right pointer so in the case of [10, 11] and [5, 12, 20], right would be = to 2 and end would be equal to 2 + 2 = 4.
Sorry, again for incompleteness

``````merge(int[] arr, int[] new, int l, int r, int end, HashMap hm) {

boolean done = false;
int i = l;
int j = r;
int k = l;
while(!done) {

if (arr[left] >= arr[right]) {

new[k++] = arr[j++];
//handle ending case of merge here
}

else {

new[k++] = arr[j++];
hm.put(arr[k], hm.get(arr[k] + (end - j)) );
}
}

}``````

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

a recursive function which returns a TreeMap<Integer,Integer> where it contains the number and the qaz of this number.
this function divide each time the array into 2 sub-arrays and then merge them, iterate the left tree map and for each number , do a binary search to find the first larger number than this number the add to the value of this number -> rightTreeMap.size()-1-(the index of the number) and so on.

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

I think this is just O(n). Keep 2 pairs. One has smallest number and one has max qaz. Update them while traversing the array. Am I missing something?

``````#include <stdio.h>

struct Pair
{
int v;
int qaz;
Pair(int _v = 0, int _qaz = 0): v(_v), qaz(_qaz){}
};

void findMaxQaz(int v[], int len)
{
Pair smallest(v, 0);
Pair maxQaz(v, 0);

for (int i = 1; i < len; ++i)
{
if (v[i] > smallest.v)
{
smallest.qaz++;
}
else
{
smallest.qaz = 0;
smallest.v = v[i];
}
if (v[i] > maxQaz.v)
{
maxQaz.qaz++;
}
if (smallest.qaz > maxQaz.qaz)
{
maxQaz.v = smallest.v;
maxQaz.qaz = smallest.qaz;
}
}
printf("%d qaz:%d", maxQaz.v, maxQaz.qaz);
}

int main()
{
//int v[] = {2, 3, 1, 4, 5};
int v[] = {33 , 25 , 26 , 1 , 5 ,6 ,7 ,9 , 14 ,20,21,23,29};
findMaxQaz(v, sizeof(v)/sizeof(int));
return 0;
}``````

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

This looks good to me. Anyone seems problem with this solution?

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

No, there is a problem.
For {33, 34, 21, 22, 20, 23, 19, 24, 21, 22}, it gives 19 qaz:3 when correct answer is 21 qaz:4.

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

Fundamental problem in your solution. Suppose, we can find QAZ of all elements in O(n). By reversing array, finding QAZ and reversing it once again we can find QAZ in "opposite direction" in O(n). By adding this values for each elements we can figure out how many elements in array are lesser than this element, i.e. position of this element in sorted array. In O(n).
Than, applying a permutation to initial array (can be done in O(n)) we get sorted arry in O(n), which is impossible, as you know.

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

Walk the array in reverse, inserting values into a min-oriented heap as you go. The 'qaz' for each number is the number of elements beneath it in the heap when you insert it. Keep track of the max qaz after each insertion. This will be an O(n log n) algorithm.

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

Could you please elaborate? how do you take care of the following case:
1- let's say a number smaller than all the existing numbers is entered, that number will be at the top of the heap, and the qaz of that number should be zero, but your algorithm suggests something else,

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

That's why you have to walk the array in reverse, rather than forwards.

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

For every element when you traverse a heap to update values doesnt that have a higher complexity that nLogn

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

Traversing the array in reverse and inserting into heap will not give the correct answer, let's assume a number, say x, is inserted and x is NOT the smallest number so far, the qaz of x would be all the numbers greater than x, but the number of elements beneath x in the heap doesn't represent ALL the numbers that are greater than x

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

This is the exact solution I worked out. Comforting to see similar thinkers :)

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

sort the array, scan the sorted array, for each item i, let ans = max(ans, size - i - ori_i) where ori_i is the original index of the item.

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

edit: ans = max(ans, size - 1 - i + ori_i)

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

This is another MergeSort-like solution in Java, that just tries to be easier to read.
It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

``````public class QAZ {

public static void main(String[] args) {
int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
System.out.println(getMaxQAZ(array));
}

public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length).qaz;
}

private static QAZResult getMaxQAZ(int[] array, int start, int end) {

if (end - start <= 3) {
return getLastLocalMaxQAZ(array, start, end);
}

int middle = (end + start) / 2;

QAZResult leftResult = getMaxQAZ(array, start, middle);

QAZResult rightResult = getMaxQAZ(array, middle, end);

if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}

for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}

return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;

}

private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){

int minVal = array[start];
int qaz = 0;
for (int i = start + 1; i < end; i++) {
if (array[i -1] < array[i]) {
qaz++;
} else {
minVal = array[i];
}
}
return new QAZResult(minVal, qaz);
}
}

class QAZResult {
int minVal;
int qaz;

public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}``````

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

This is another MergeSort-like solution in Java, that just tries to be easier to read.
It is based on the observation that the element that holds the max QAZ is a local minimum of the array.

The recursive method returns a simple data structure that contains both the local minimum and the local max QAZ.

You recursion is applied to two half array, the left one and the right one.

For one of each you get the Max QAZ and the local minimum associated to it.

You know that merging the two sub array, the QAZ values on the right array cannot change, only the values on the left array can.

If the local minimum of the left half array is less than the one on the right, you know that this will remain the holder of the bigger QAZ, and the new QAZ value is: left QAZ + size of right half array.

In the other case, we calculate the new QAZ associated to the left local minimum in linear time (the right local minimum QAZ doesn't change), and return who has the bigger QAZ, the left or the right one.

``````public class QAZ {

public static void main(String[] args) {
int[] array = {33 , 25 , 26 , 58 , 41 , 59 };
System.out.println(getMaxQAZ(array));
}

public static int getMaxQAZ(int[] array){
if (array == null) {
return 0;
}
return getMaxQAZ(array, 0, array.length).qaz;
}

private static QAZResult getMaxQAZ(int[] array, int start, int end) {

if (end - start <= 3) {
return getLastLocalMaxQAZ(array, start, end);
}

int middle = (end + start) / 2;

QAZResult leftResult = getMaxQAZ(array, start, middle);

QAZResult rightResult = getMaxQAZ(array, middle, end);

if (leftResult.minVal < rightResult.minVal) {
return new QAZResult(leftResult.minVal, leftResult.qaz + end - middle);
}

for (int i = middle; i < end; i++) {
if (leftResult.minVal < array[i]) {
leftResult.qaz++;
}
}

return leftResult.qaz < rightResult.qaz ? leftResult : rightResult;

}

private static QAZResult getLastLocalMaxQAZ(int[] array, int start, int end){

int minVal = array[start];
int qaz = 0;
for (int i = start + 1; i < end; i++) {
if (array[i -1] < array[i]) {
qaz++;
} else {
minVal = array[i];
}
}
return new QAZResult(minVal, qaz);
}
}

class QAZResult {
int minVal;
int qaz;

public QAZResult(int minVal, int qaz) {
this.minVal = minVal;
this.qaz = qaz;
}
}``````

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

``````struct qaz_pair
{
int value;
size_t index;
};

bool operator < (const qaz_pair& lhs, const qaz_pair& rhs)
{
return lhs.value < rhs.value;
}

int qaz(const vector<int>& numbers, int number)
{
// O(n)
vector<qaz_pair> tmp;
for (const auto n : numbers )
tmp.push_back( qaz_pair{ n, tmp.size() } );

// O(nlogn)
sort(tmp.begin(), tmp.end());

qaz_pair number_pair;
number_pair.value = number;

auto found = lower_bound(tmp.begin(), tmp.end(), number_pair);
if (tmp.end() == found || found->value != number)
return -1;

// O(n)
int result = 0;
int previous = found->value;
const size_t index = found->index;
for (; tmp.end() != found ; previous = found->value, ++found )
{
if (found->index > index)
if (previous != found->value)
result++;
}

return result;
}

{
const vector<int> numbers { 33 , 25 , 26, 26 , 58 , 41, 41 , 59, 59 };

assert( -1 == qaz(numbers, 0) );
assert( -1 == qaz(numbers, 100) );

assert( 3 == qaz(numbers, 33) );
assert( 4 == qaz(numbers, 25) );
assert( 3 == qaz(numbers, 26) );
assert( 1 == qaz(numbers, 58) );
assert( 1 == qaz(numbers, 41) );
assert( 0 == qaz(numbers, 59) );
}``````

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

Here's the short code for the heap-reverse-filling approach in Java.

``````public int maxQaz(int[] arr) {
int max = 0;
TreeSet<Integer> heap = new TreeSet<>();
for (int i = arr.length-1; i >= 0; i--) {
max = Math.max(max, heap.tailSet(arr[i], false).size());
}
return max;
}``````

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

If we know for an array (having N elements) index i (0<=i<N), the number of elements which are smaller than array[i], say X, then the QAZ value of array[i] = (N-i-1)-X.
The number of elements smaller than array[i], say X, will introduce X array inversions to the right of index i. So we can just count the number of inversions at index i and calculate the QAZ value keeping track of the maximum. Since this is reduced to counting inversions we can of course use a modified merge sort algorithm but I suggest using a Fenwick tree which is much simpler to code. Complexity: O(nlogn).
Here's the code to elaborate:

``````public void solve(int[] A){
int N = A.length;
int[] bit = new int[N+1];
int[] rank = Arrays.copyOf(A, N);
Arrays.sort(rank);
for (int i = 0; i < A.length; i++) {
int idx = Arrays.binarySearch(rank, A[i]);
A[i] = idx+1;
}
int maxQAZ = Integer.MIN_VALUE;
for(int i=N-1;i>=0;i--)
{
int qaz = (N-i-1) - read(bit, A[i]-1);
maxQAZ = Math.max(maxQAZ, qaz);
update(bit, A[i],1,N);
}
System.out.println(maxQAZ);
}
private int read(int[] bit, int idx){
int sum=0;
while (idx>0)
{
sum += bit[idx];
idx -= (idx & -idx);
}
return sum;
}
private void update(int[] bit, int idx, int val, int max){
while (idx <= max)
{
bit[idx] += val;
idx += (idx & -idx);
}
}``````

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

I couldn't understand how your algorithm works, but how do you prove O(nlogn)?

for(int i=N-1;i>=0;i--) => O(N) and it calls the function "Update", to maintain O(nlogn), the complexity of the function "Update" must be equal or smaller than O(logn), How do you prove that?

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

The number of iterations in both read & update methods is the number of set bits in the "idx" parameter which is at max log N.
The line idx&(-idx) isolates the last set bit in idx.

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

Not sure you can use Binary search because the array is not sort.

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

Shorter algo based on the observation that the qaz(#i) = max(0, order of #i in the sorted array - #i).

``````int maxQaz(const vector<int> &v) {
vector<pair<int, int> > pv;
int n = v.size();
for (int i = 0; i < n; i++) {
pv.push_back(make_pair(v[i], i));
}
stable_sort(pv.begin(), pv.end());
reverse(pv.begin(), pv.end());
int ret = 0;	// when input is empty, result is 0.
for (int i = 0; i < n; i++) {
ret = max(ret, i - pv[i].second);
}
return ret;
}``````

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

As many people discussed, a O(nlogn) solution can be achieved by merge sort. Please check my analysis and solution: allenlipeng47.com/PersonalPage/index/view/126/nkey

``````package feb;

public class QAZ {

public static void main(String[] args) {
int[] arr = { 7, 8, 2, 3, 4, 5 };
int qaz = qaz(arr);
System.out.println(qaz);
}

public static int qaz(int[] arr) {
int[] eleTimes = new int[arr.length];
int[] helperQaz = new int[arr.length];
int[] helperTimes = new int[arr.length];
return qazUtil(arr, eleTimes, 0, arr.length - 1, helperQaz, helperTimes);
}

public static int qazUtil(int[] arr, int[] eleTimes, int start, int end,
int[] helperQaz, int[] helperTimes) {
if (start > end) {
return 0;
}
if (start == end) {
return 0;
}
int mid = start + (end - start) / 2;
int qazLeft = qazUtil(arr, eleTimes, start, mid, helperQaz, helperTimes);
int qazRight = qazUtil(arr, eleTimes, mid + 1, end, helperQaz,
helperTimes);
// 1. Update eleTimes in left part.
int pointerL = mid, pointerR = end;
while (pointerL >= start) {
while (arr[pointerL] < arr[pointerR] && pointerR >= mid + 1) {
pointerR--;
}
qazLeft = (eleTimes[pointerL] > qazLeft) ? eleTimes[pointerL]
: qazLeft;
pointerL--;
}
// 2. Mergesort left and right part into helperQaz, helperTimes
pointerL = start;
pointerR = mid + 1;
int helpIndex = start;
while (pointerL <= mid && pointerR <= end) {
if (arr[pointerL] < arr[pointerR]) {
helperQaz[helpIndex] = arr[pointerL];
helperTimes[helpIndex] = eleTimes[pointerL];
pointerL++;
} else {
helperQaz[helpIndex] = arr[pointerR];
helperTimes[helpIndex] = eleTimes[pointerR];
pointerR++;
}
helpIndex++;
}
while (pointerL <= mid) {
helperQaz[helpIndex] = arr[pointerL];
helperTimes[helpIndex] = eleTimes[pointerL];
pointerL++;
helpIndex++;
}
while (pointerR <= end) {
helperQaz[helpIndex] = arr[pointerR];
helperTimes[helpIndex] = eleTimes[pointerR];
pointerR++;
helpIndex++;
}
// 2.2 Copy result from helperQaz, helperTimes back to arr, eleTimes
for (int i = start; i <= end; i++) {
arr[i] = helperQaz[i];
eleTimes[i] = helperTimes[i];
}
return Math.max(qazLeft, qazRight);
}

}``````

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

How about ~20 LOC in java:

``````import java.util.*;

public class QAZ {
static int findMaxQaz(List<Integer> list) {
TreeSet<Integer> set = new TreeSet<>();
int maxQaz = -1, maxVal = -1;
Collections.reverse(list);
for (int i : list) {
int qaz = set.tailSet(i).size();
if (maxQaz < qaz) {
maxVal = i;
maxQaz = qaz;
}
}
return maxVal;
}

public static void main(String[] args) {
List<Integer> list = Arrays.asList(88, 77, 6, 5, 4, 3);
System.out.println(findMaxQaz(list));
}
}``````

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

Note that

``tailSet(...).size()``

is of

``O(log(n))``

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

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

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

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

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

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

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

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

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

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

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

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

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

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

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

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

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

Here is an interesting DP solution that achieves the O(n log n) bound.

Start at the end of the array, keeping a splay tree as an auxiliary structure and the current maximum qaz. Then as we traverse the list in reverse order, enter the numbers into the splay tree. The number just entered into the splay tree will be splayed to the root, and the tree will only contain the (now root) node and everything that appears after it in the original array. Then the qaz number of this array entry is just the amount of nodes in the right subtree of the splay tree.

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

alternate solution (not using merge sort):

Step1:
Make a second list and sort that list but keep track of where each element in the sorted list is stored within the original list.
[n log n, for the sorted list you can use a class that has a number as one class variables and "position in original list" as a second class variable]

Step 2:
Starting at the first element of the sorted list, for each element i, take

min ((n-1)-sortedListPosition, (n-1)-originalListPosition)

This is the myMaxPossibleQaz (weird name to make writing later easier),
the first item is the number of elements greater than the current element in the list as a whole,
the second item is the qaz assuming that all elements after the position of the current element in the original list are greater than the current element if all elements after element i within the original list are greater

The min of these is the highest possible qaz (given the set and the position of the current element in the original set). The highest possible qaz is lowered every time a smaller element is in front of i).

Make a list of these myMaxPossibleQaz values (or add another class variable to the objects within the sorted list) [n time].

Step 3.0

Going through each element i in the sorted list and keep track of the farthest left original position so far (this is because, any future elements in the sorted list that have an original position greater than this will definitely have a greater qaz, so we can ignore them. They will have a greater qaz because, in the original list, they appear after at least one number that they are greater than, so whatever their qaz is, the earlier number will have at least their qaz + 1)

Step 3.5
If future elements within the sorted list have an earlier position within the original list than we have seen so far then their qaz is

myMaxPossibleQaz - mySortedListPosition

This is because maxPossibleQaz is reduced by having numbers that are smaller than you appear after you in the original list, and every element so far has been smaller than the current element and after the current element in the original list.

So when iterating through the sorted list if the elements are to the right of the leftmost original position seen so far, we move on, if they are to the left, we update the leftmost seen position and calculate the qaz using the (myPossibleQaz - mySortedListPosition) formula.

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

Step 3.0 and 3.5 (well, same step, but two different cases) take n time. Calculating qaz is instant (when the qaz can possibly be larger than something we've seen so far. When it could be smaller, we ignore it).

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

Sounds interesting, have you written the code?

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

Sorry, I haven't. Have only designed it so far.

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

{{
std::pair<int,int> qaz(int* A, int len)
{
std::vector<std::pair<int,int>> VA;
for(int i = 0; i < len; ++i)
VA.push_back(std::make_pair(A[i], i));

std::sort(VA.begin(), VA.end()); O(n log n)

std::pair<int,int> B = std::make_pair(-1,-1);
for(int i = len-1; i >= 0; --i) //O(n)
{
int v = std::min(len-(VA[i].second+1), len-(i+1));
if(v > B.second)
{
B = VA[i];
B.second = v;
}
}
return B;
}
}}

I would think that replacing std::sort with a radix sort would even give a O(n) solution.

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

Iterate from end to start, in each iteration insert the current element to a binary tree. Before each insertion count how many numbers are greater than this element and that's the qaz of the current element. Dynamically update the max qaz each time.

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

Iterate from end to start, in each iteration insert the current element to a binary tree. Before each insertion count how many numbers are greater than this element and that's the qaz of the current element. Dynamically update the max qaz each time.

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

Iterate from end to start, in each iteration insert the current element to a binary tree. Before each insertion count how many numbers are greater than this element and that's the qaz of the current element. Dynamically update the max qaz each time.

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

qaz problem is just longest incrementing subsequence in diguise.
There is a solution to this problem in O(nlogn).

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

Consider { 10,11,12,13,1,14,15,16,17}

QAZ(10) = 7
longest incrementing sub sequence = { 10,11,12,13 }

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

LIS is {10, 11, 12, 13, 14, 15, 16, 17 }
in fact, the max_qaz == LIS - 1! and we can get the LIS in O(nlogn)!

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

``````# n squared qaz solution
def qaz(data):

n = len(data)

max_counter = 0

elements = []

for i in range(0,n):

candidate_counter = 0

for j in range(i + 1,n):

if data[j] > data[i]:

candidate_counter += 1

if candidate_counter > max_counter:

max_counter = candidate_counter

del elements[:]

elements.append(data[i])

elif candidate_counter == max_counter:

elements.append(data[i])

return max_counter, elements

##### This is nlogn solution in case you replace the data structure which holds the local minimums with an AVL tree.
##### I did not use an AVL tree since it is easier to understand the solution this way.
##### in the worst case we are doing a binary search ~n times to find max over all candidates which is smaller then new value in case it is bigger the min over all minimums.
##### so nlogn in the worst case. This is not optimal since deleting from an array may result linear time while deleting from AVL will result logarithmic time.
##### a tester which validates against the trivial solution runs.
##### By the way it took a day to think about and implement.could not have done it in an interview.

class QAZcandidate(object):

def __init__(self, value):

self.value = value

self.rankUP = 0

self.rankDOWN = 0

def find_max_smaller_minimum(data,key, index=0):

if len(data) == 0:

return data, index

middle = len(data)/2

element = data[middle]

if element.value > key:

return find_max_smaller_minimum(data[middle:],key,index + middle)

else:

#element.value < key
if middle > 0:

if data[middle - 1].value < key:

return find_max_smaller_minimum(data[0:middle],key,index)

else:
#we found max smaller minimum
return data[middle], middle + index

#element.value < key and its the largest minimum
else:

return data[middle], middle + index

def qaz_hard(data):

if len(data) <= 1:

return

local_minimals = []

local_minimals_last_minimal_index = 0

array_minimal_index = 0

local_minimals.append(QAZcandidate(value=data))

for i in range(1,len(data)):

if data[i] < local_minimals[local_minimals_last_minimal_index].value:
# we overwrite the previous suspected local minimal
if array_minimal_index + 1 == i:

local_minimals[local_minimals_last_minimal_index] = QAZcandidate(value=data[i])

array_minimal_index += 1

continue

else:
# new candidate for a wining local minimum
local_minimals.append(QAZcandidate(value=data[i]))

local_minimals_last_minimal_index += 1

array_minimal_index = i

continue
# data[i] > local_minimals[last_minimal_index].value
else:
# need to find maximum over all minimums which are smaller then data[i]
max_smaller_minimum_element, max_smaller_minimum_element_index = find_max_smaller_minimum(local_minimals,data[i])

# one candidate.
if max_smaller_minimum_element is local_minimals:

local_minimals[local_minimals_last_minimal_index].rankDOWN += 1

# last element
elif max_smaller_minimum_element is local_minimals[local_minimals_last_minimal_index]:

max_smaller_minimum_element.rankUP += 1

max_smaller_minimum_element.rankDOWN += 1

# element in the middle so improves position against previous elements and last minimum gains advantage against future elements
else:

max_smaller_minimum_element.rankUP += 1

local_minimals[local_minimals_last_minimal_index].rankDOWN += 1

# check if need to update winner
if max_smaller_minimum_element is not local_minimals:

prev_candidate = local_minimals[max_smaller_minimum_element_index - 1]

#we improve ranking
if max_smaller_minimum_element.rankUP >= prev_candidate.rankDOWN:

local_minimals = local_minimals[0:max_smaller_minimum_element_index - 1] + local_minimals[max_smaller_minimum_element_index:]

local_minimals_last_minimal_index -= 1
# max smaller minimum element is the first one so everybody gains
else:
pass

x = local_minimals.value

i = 0

while data[i] != x:

i += 1

counter = 0

j = i+1

while j < len(data):

if data[j] > x:

counter += 1

j += 1

return counter, local_minimals.value

if __name__ == "__main__":

import random

for i in range(0,10):

d = random.sample(range(1000), 1000)

c1, val1 = qaz(d)

c2, val2 = qaz_hard(d)

if c1 != c2:

print "error"
print str(d)
print "easy: qaz:"+str(c1)+" val:"+str(val1)
print "hard: qaz:"+str(c2)+" val:"+str(val2)

else:

print "ok"``````

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

``````# n squared qaz solution
def qaz(data):

n = len(data)

max_counter = 0

elements = []

for i in range(0,n):

candidate_counter = 0

for j in range(i + 1,n):

if data[j] > data[i]:

candidate_counter += 1

if candidate_counter > max_counter:

max_counter = candidate_counter

del elements[:]

elements.append(data[i])

elif candidate_counter == max_counter:

elements.append(data[i])

return max_counter, elements

##### This is nlogn solution in case you replace the data structure which holds the local minimums with an AVL tree.
##### I did not use an AVL tree since it is easier to understand the solution this way.
##### in the worst case we are doing a binary search ~n times to find max over all candidates which is smaller then new value in case it is bigger the min over all minimums.
##### so nlogn in the worst case. This is not optimal since deleting from an array may result linear time while deleting from AVL will result logarithmic time.
##### a tester which validates against the trivial solution runs.
##### By the way it took a day to think about and implement.could not have done it in an interview.

class QAZcandidate(object):

def __init__(self, value):

self.value = value

self.rankUP = 0

self.rankDOWN = 0

def find_max_smaller_minimum(data,key, index=0):

if len(data) == 0:

return data, index

middle = len(data)/2

element = data[middle]

if element.value > key:

return find_max_smaller_minimum(data[middle:],key,index + middle)

else:

#element.value < key
if middle > 0:

if data[middle - 1].value < key:

return find_max_smaller_minimum(data[0:middle],key,index)

else:
#we found max smaller minimum
return data[middle], middle + index

#element.value < key and its the largest minimum
else:

return data[middle], middle + index

def qaz_hard(data):

if len(data) <= 1:

return

local_minimals = []

local_minimals_last_minimal_index = 0

array_minimal_index = 0

local_minimals.append(QAZcandidate(value=data))

for i in range(1,len(data)):

if data[i] < local_minimals[local_minimals_last_minimal_index].value:
# we overwrite the previous suspected local minimal
if array_minimal_index + 1 == i:

local_minimals[local_minimals_last_minimal_index] = QAZcandidate(value=data[i])

array_minimal_index += 1

continue

else:
# new candidate for a wining local minimum
local_minimals.append(QAZcandidate(value=data[i]))

local_minimals_last_minimal_index += 1

array_minimal_index = i

continue
# data[i] > local_minimals[last_minimal_index].value
else:
# need to find maximum over all minimums which are smaller then data[i]
max_smaller_minimum_element, max_smaller_minimum_element_index = find_max_smaller_minimum(local_minimals,data[i])

# one candidate.
if max_smaller_minimum_element is local_minimals:

local_minimals[local_minimals_last_minimal_index].rankDOWN += 1

# last element
elif max_smaller_minimum_element is local_minimals[local_minimals_last_minimal_index]:

max_smaller_minimum_element.rankUP += 1

max_smaller_minimum_element.rankDOWN += 1

# element in the middle so improves position against previous elements and last minimum gains advantage against future elements
else:

max_smaller_minimum_element.rankUP += 1

local_minimals[local_minimals_last_minimal_index].rankDOWN += 1

# check if need to update winner
if max_smaller_minimum_element is not local_minimals:

prev_candidate = local_minimals[max_smaller_minimum_element_index - 1]

#we improve ranking
if max_smaller_minimum_element.rankUP >= prev_candidate.rankDOWN:

local_minimals = local_minimals[0:max_smaller_minimum_element_index - 1] + local_minimals[max_smaller_minimum_element_index:]

local_minimals_last_minimal_index -= 1
# max smaller minimum element is the first one so everybody gains
else:
pass

x = local_minimals.value

i = 0

while data[i] != x:

i += 1

counter = 0

j = i+1

while j < len(data):

if data[j] > x:

counter += 1

j += 1

return counter, local_minimals.value

if __name__ == "__main__":

import random

for i in range(0,10):

d = random.sample(range(1000), 1000)

c1, val1 = qaz(d)

c2, val2 = qaz_hard(d)

if c1 != c2:

print "error"
print str(d)
print "easy: qaz:"+str(c1)+" val:"+str(val1)
print "hard: qaz:"+str(c2)+" val:"+str(val2)

else:

print "ok"``````

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

Easy peasy.

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

Another approach is to build a binary search tree while adding the elements in the array from right to left (end to start). This works because:

1. Each time we go "down the tree" to the left all the elements in the tree above are larger than the current one so, add 1 + count the number of elements on the right side of the parent node.

2. When going "down the tree" to the right, the prev. element is small than the current one so don't count it.

3. For n elements we are traversing the tree which is max logN in height there for o(nlogn)

``````public int findMaxQaz(int[] buff) {

int max = 0;
int qaz = 0;

// create the root
TreeNode<int> root = new TreeNode(buff[buff.length-1]);
TreeNode<int> node = root;

for(int index=buff.length-2; index>=0; index--) {
if(buff[index] < node.value) {
qaz += countNodes(node.right);
qaz += 1; // for current node
if(node.left == null) {
node.left = new TreeNode<int>(buff[indedx]);
if(qaz > max)
max = qaz;
}
else
node = node.left;
}
else {
if(mode.right == null) {
node.right = node TreeNode<int>(buff[index]);
if(qaz > max)
max = qaz;
}
else
node = node.right;
}
}

return max;
}

private int countNodes(TreeNode node) {

if(null == node)
return 0;

int left = countNodes(node.left);
int right = countNodes(node.right);

return left+right+1;
}``````

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

MAXIMUM-QUAZ ( int[] array )

1. MaxQaz = 0

2. Q = PRIORITY-QUEUE

3. for i = array.length - 1 to 0

4. index = Q.insert ( array [ i ] ) // return index of newly inserted element

5. qaz = Q.size - index

6. if ( qaz > MaxQaz )

7. MazQaz = qaz

8. return MazQaz

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

Here is a O(n) in python

``````def max_qaz(arr):
qaz = {}
max_qaz = -1
for val in arr:
for k, v in qaz.items():
if val > k:
qaz[k] += 1
if qaz[k] > max_qaz:
max_qaz = qaz[k]

qaz[val] = 0
return max_qaz``````

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

``````public class id5649103830646784 {
public static void main(String arcg[]){
id5649103830646784 h = new id5649103830646784();
int[] array = {33,25,26,58,41,59};
pair[] array2 = new pair[array.length];
for(int i=0;i<array.length;i++){
array2[i] = h.new pair(array[i]);
}
h.sort(array2);
for(int i=0;i<array2.length;i++){
System.out.println(array2[i].val + ": " + array2[i].qaz);
}
}
class pair{
int val;
int qaz;
public pair(int val){
this.val = val;
qaz = 0;
}
}
private pair[] array;
private pair[] helper;
void sort(pair[] array){
this.array = array;
this.helper = new pair[array.length];
mergeSort(0,array.length-1);
}
void mergeSort(int low, int high){
if(low < high){
int mid = low+(high-low)/2;
mergeSort(low, mid);
mergeSort(mid+1, high);
merge(low,mid,high);
}
}
void merge(int low, int mid, int high){
for(int i=low;i<=high;i++) helper[i] = array[i];
int i=low, j=mid+1,k=low;
while(i<=mid && j<=high){
if(helper[i].val<=helper[j].val){
array[k] = helper[i++];
array[k].qaz += high-j+1;
}
else{
array[k] = helper[j++];
}
k++;
}
while(i<=mid) array[k++] = helper[i++];
}
}``````

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

``````public int findMaxqaz(List<Integer> input){
int size = input.size();
List<Integer> qaz = new ArrayList<>();
Map<Integer,Integer> map = new HashMap<>();
for(int i=0; i<input.size(); i++)
map.put(input.get(i), size-i);
List<Integer> sortedKeys = new ArrayList<>(map.keySet());
Collections.sort(sortedKeys);
for(int i=0; i<sortedKeys.size(); i++)
Collections.sort(qaz);
return qaz.get(qaz.size()-1);
}``````

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

``````#include <stdio.h>
#include <stdlib.h>

struct node {
int val;
int c_num;
int l_num;
struct node * left;
int r_num;
struct node * right;
};
struct node * root = NULL;

struct node * r_insert(struct node * root, int i) {
// update # left and right children to maintain counters
if (root == NULL) {
struct node * n;
n = (struct node *) malloc (sizeof(struct node));
n->val = i;
n->c_num = 1;
n->l_num = 0;
n->r_num = 0;
n->left = NULL;
n->right = NULL;
return n;
}

if (root->val < i) {
root->left = r_insert(root->left, i);
root->l_num++;
}
else if (root->val > i) {
root->right = r_insert(root->right, i);
root->r_num++;
}
else {
root->c_num++;
}

return root;
}

int r_find(struct node * root, int i) {
// TODO: Indicate error here
if (root == NULL)
return 0;

if (root->val == i)
return (root->c_num)-1;

if (root->val < i) return r_find(root->left, i);
else return root->c_num + root->l_num + r_find(root->right, i);
}

int insert_bin_src_tree(int i) {
// Insert into decending ordetr btree;
root = r_insert(root, i);

// qaz = rank in the btree's inorder traversal
return r_find(root, i);

}

// 33 , 25 , 26 , 58 , 41 , 59
// 59;
// 59, 41 59->l+59->c+41->c-1 = 1;
// 59, 41, 58: 0+0+1+0 = 1;
// 59, 41, 58, 26: 0+1+1+0+1= 3;

int qaz(int a[], int len) {
int max_qaz=0, t;

// Start from the last element; qaz = 0
for (len--; len >=0; len--) {
// Keep a binary search tree with # of children
t = insert_bin_src_tree(a[len]);
if ( t > max_qaz) max_qaz = t;
}
return max_qaz;
}

int main (void) {
int a = {33 , 25 , 26 , 58 , 41 , 59};

printf("max qaz %d\n", qaz(a, 6));
return 0;
}``````

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

Can be done using two stacks

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

Modifed merge sort. We split array on tho subarrays and calculate local quaz for both subarray (divide phase). Then in merge phase (conquer pahse) with O(n) complexity update quaz of the whole array on the basis of already calculated values in divide phase.Original array is converted to one that is sorted but original indexes are stored.

``````int[] mergeQuaz(int[] input,int l,int r, int[] qaz) {
if( l < r ) {
int mid = l + (r - l)/ 2;
int a[] = mergeQuaz(input,l,mid ,qaz);
int b[] = mergeQuaz(input,mid+1 ,r ,qa);
int indexA = 0;
int indexB = 0;
int output[] = new int[a.length + b.length];
int outIndex = 0;
while (indexA < a.length) {
if(indexB == b.length) {
qaz[a[indexA]] += b.length - indexB;
output[outIndex] = a[indexA];
indexA++;

} else {
if (input[a[indexA]]< input[b[indexB]]) {
output[outIndex] = a[indexA];
qaz[a[indexA]] += b.length - indexB;
indexB = 0;
indexA++;
} else {
output[outIndex] = b[indexB];
indexB++;
}
}
outIndex++;
}
while(indexB<b.length) {
output[outIndex] = b[indexB];
outIndex++;
indexB++;
}
return output;
}
return new int[] {l};
}``````

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

c#.
totally generic merge sort except of 1 line ( stressed in code).

``````static private Number[] MergeSort( Number[] arr ) {

if ( arr.Length == 1 ) { return arr; }

var leftHalf = new Number[ arr.Length / 2 ];
var rightHalf = new Number[ arr.Length - arr.Length / 2 ];

int t = 0;
for ( int i = 0; i < arr.Length; i++ ) {
if ( i < arr.Length / 2 ) { leftHalf[ i ] = arr[ i ]; }
else { rightHalf[ t ] = arr[ i ]; t++; }
}
return Merge( MergeSort( leftHalf ), MergeSort( rightHalf ) );
}

static private Number[] Merge( Number[] arr1, Number[] arr2 ) {

if ( arr1 == null ) { return arr2; }
if ( arr2 == null ) { return arr1; }

Number[] tail = null;

if ( arr1.Length > 1 ) { tail = new Number[ arr1.Length - 1 ]; }

if ( arr1[ 0 ].Value < arr2[ 0 ].Value ) {
for ( int i = 0; i + 1 < arr1.Length; i++ ) {
tail[ i ] = arr1[ i + 1 ];
}
arr1[ 0 ].qaz += arr2.Length; // the only one line added to merge sort
return Concat( arr1[ 0 ], Merge( tail, arr2 ) );
}

tail = null;
if ( arr2.Length > 1 ) { tail = new Number[ arr2.Length - 1 ]; }
for ( int i = 0; i + 1 < arr2.Length; i++ ) {
tail[i] = arr2[ i + 1 ];
}

return Concat( arr2[ 0 ], Merge( arr1, tail ) );
}

private static Number[] Concat( Number firstElm, Number[] arr ) {

var res = new Number[ arr.Length + 1 ];
res[ 0 ] = firstElm;

for ( int i = 0; i < arr.Length; i++ ) {
res[ i + 1 ] = arr[ i ];
}
return res;
}
public struct Number {
public int Value;
public int qaz;
}``````

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

You can do this without mergesort.

1. For each number, make a new object storing that number and its index, and put them into another array
2. Sort this array according to the value of the objects.
3. Starting from the end, maintain a binary index tree storing the (original) indices. (By calling update(i, 1))
4. As we go along, find the number of (original) indices that we have seen that are greater than our current (original) index (log n using binary index tree, just compute sum(idx+1,n))
5. Keep a max value, updating it as we go.

O(nlogn) time, O(N) space. If we use out original array for the binary index tree, we only need one extra size n array.

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

using System;
class HelloWorld {
static void Main()
{
Console.WriteLine("enter the numbers:");
int[] arr = new int[num];
for(int i = 0; i<num; i++)
{
arr[i] = data;
}
int count=0;
for(int j = 0; j<num; j++)
{
for(int k=0; k<num; k++)
{
if(arr[j]< arr[k] && (j<k))
count++;
}
Console.WriteLine("qaz of"+"("+arr[j]+")"+"="+count);
count = 0;
}
}
}

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

using System;
class HelloWorld {
static void Main()
{
Console.WriteLine("enter the numbers:");
int[] arr = new int[num];
for(int i = 0; i<num; i++)
{
arr[i] = data;
}
int count=0;
for(int j = 0; j<num; j++)
{
for(int k=0; k<num; k++)
{
if(arr[j]< arr[k] && (j<k))
count++;
}
Console.WriteLine("qaz of"+"("+arr[j]+")"+"="+count);
count = 0;
}
}
}

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

Sort the given elements.
To find qaz(x), Find the number of elements to the right of the number in the sorted array( say p) and the number of elements to the right of the number in the original array(say q).
Then qaz(x) = min(p,q)

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

Wrong
a = [10, 5, 7, 2, 1]
sorted(a) = [1, 2, 5, 7, 10]
For 5 we have p = 2 and q = 2. So prabhjot_singh_qaz = min(p, q) = min(2, 2) = 2. But real qaz(5) = 1

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

*q=3

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

I was thinking about implementing this as a binary tree. Something along this lines in Pythonish pseudocode:

``````MAX_QAZ = 0

class Node:
global MAX_QAZ

def __init__(self, value):
self.qaz = 0
self.value = value
self.right_child, self.left_child = None, None

def insert(self, number):
if number > self.value:
if self.right_child is not None:
self.right_child.insert(number)
else:
self.right_child = Node(number)
self.qaz += 1
if self.qaz > MAX_QAZ:
MAX_QAZ = self.qaz
self.left_child.increment_childrens_qaz()
else:
if self.left_child is not None:
self.left_child.insert(number)
else:
self.left_child = Node(number)

def increment_childrens_qaz(self):
self.qaz += 1
if self.qaz > MAX_QAZ:
MAX_QAZ = self.qaz
self.left_child.increment_childrens_qaz()
self.right_child.increment_childrens_qaz()

class BinaryTree:

def insert(self, number):
if self.root_node is None:
self.root_node = Node(number)
return
self.root_node.insert(number)

tree = BinaryTree()
for number in list:
tree.insert(number)
print MAX_QUAZ``````

Basically each time a node is inserted it's qaz is initialized to 0. If it's inserted to the left of existing node - existing node's qaz doesn't change. If it is inserted on the right of the existing node - existing node's qaz increments, and so does qaz of everything to the left of the existing node.

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

it's a beautiful answer and it works, but it doesn't achieve the nlog(n), for example if the array is already sorted it'd be o(n^2)

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

Hm... How is it O(n^2)? For each element (n) we insert a node (log n), therefore O(n log n), right? Can you explain how is in O(n^2)?

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

He's saying that in the worst case, when you have a sorted array, it will be O(n^2). This is because you are building a degenerate tree, where every node only has a right child or not children, or a tree with only left or no children. It's like building a linked list where you always start traversing from the head.

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

logic
build a binary tree rooted at first element. keep count of nodes to right of every node while building tree. visit every node
qaz (for number at node) = number of nodes to it's right + number of nodes to its' parents right (if parent is present) + 1 (if parent is present parent)

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

it's a beautiful answer and it works, but it doesn't achieve the nlog(n), for example if the array is already sorted it'd be o(n^2)

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

build AVL to solve "already sorted" problem.

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

could you please elaborate? once you re-organize the tree, the indices will be all mixed up,

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

None of the tree solution can guarantee an O(nlogn) in worst case.

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

Find qaz from end of the array towards start as in the below psuedocode. qaz of last element is always 0.

if(arr[i-1]<=arr[i])
{qaz(i-1) = qaz(i)+1;}
else
{ int j=i;
//Increment j until until arr[i-1]<=arr[j]
qaz(i-1) = qaz(j)+1;
}

we could keep track of the max qaz in the process.

In the worst case, this could go to o(n2) though.

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

sounds correct, but as you said it's O(n^2)

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

This is an O(n) solution.

``````public class MaxQaz {

public static int findMaxQaz(int[] A) {

int maxQaz = 0;
int qaz = 0;

if (A.length == 0 || A.length == 1) {
return maxQaz;
}
int num = A;

for (int i = 1; i < A.length; i++) {
if (num < A[i]) { // As long as the previous number is less than
// current keep counting
qaz++;
}

if (num > A[i] || A.length - i == 1) { // if greater or reached end
maxQaz = Math.max(qaz, maxQaz); // store the current count if it
// is more than the max recorded
qaz = 0; // Reset the count
if ((A.length - i) < maxQaz) { // No need to continue if the
// rest of the length is less
// than maxqaz,
break;
}
num = A[i]; // Use the current number to compare next
}
}
return maxQaz;
}

public static void main(String[] args) {
int[] array = { 50, 23, 42, 1, 2, 3, 4, 9, 83, 98, 33, 55, 21, 44 };
//int[] array = { 33, 25, 26, 58, 41, 59 };

System.out.println(MaxQaz.findMaxQaz(array));
}
}``````

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

Does this work for {2, 3, 1, 4, 5} ? The correct answer should be 3, i believe your algorithm produces 2.

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

Try {6,7,1,8}, I believe your algorithm produces 1, the correct answer is 2, I don't think O(n) is possible

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

Build BST at the same time find maxQaz.

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

It's not necessarily O(nlong), if the list is already sorted then it's be O(n^2)

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

Maybe I didn't understand something, but I think about O(n) algorithm.

Step 1: Finding the x index of the max qaz

The number which has the max qaz should be the first number in the list that no number before is smaller than it. If there is a number before that is smaller than it so its qaz is greater. Therefore we should first move on the list and stop when we find a number that is bigger than the current minimum. The wanted index is the previous index(from our stop point in the list).

Step 2: Computing the qaz

After we find the index of the number with the max qaz, we just need to move on the rest of the list and count the number which are greater this number.

These two steps can be done with one run on the array, so it runs on O(n).
Feel free to correct me...

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

33 , 25 , 26 , 1 , 5 ,6 ,7 ,9 , 14 ,20,21,23,29
try this case and tell me what is the result.
using your algorithm it will returns that the max is 25 with qaz = 2
but the right answer is 1 with qaz = 9
sorry, but I think its wrong

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

@Pointer
You are right. It's wrong

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

Could you please provide some code to support this argument?

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.

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