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;

added_qaz = 0;

i = mid;
j = high;

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

if ( j <= mid )
{
for ( x = i ; x >=low ; x-- )
{
A[ x ].qaz += added_qaz;
}
}
}
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

- koosha.nejad January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is code:

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

   added_qaz = 0;

   i = mid;
   j = high;

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

   if ( j <= mid )
   {
      for ( x = i ; x >=low ; x-- )
      {
         A[ x ].qaz += added_qaz;
      }
   }
}

- koosha.nejad January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pointer January 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Michael February 07, 2015 | Flag
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;
	}
}

- Anselmo January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- Surya January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

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

- allen.lipeng47 February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
	}
}

- pavelkushtia February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- allen.lipeng47 February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anselmo.talotta February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- allen.lipeng47 February 02, 2015 | Flag
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 = {}

- Source January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- koosha.nejad January 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!

- Source January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Boris January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- koosha.nejad January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Source January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think so

- koosha.nejad January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- james January 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- frazier June 06, 2015 | Flag
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

- cabo June 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- aodja June 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- adoba June 07, 2015 | Flag
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;
	}
}

- Anselmo January 29, 2015 | Flag Reply
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

- tsuip June 07, 2015 | Flag Reply
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!

- rizhang January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Pointer January 27, 2015 | Flag
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;
	}

- rizhang January 27, 2015 | Flag
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], [20] -> QEZ of 5 increases by 1, QEZ of 12 becomes 1

now when we merge

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

[5] -> 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)) );
    }
  }

}

- SK January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be helpful:
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.

- Pointer January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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[0]));
    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;
}

- vivekveeriah January 28, 2015 | Flag Reply
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], 0);
	Pair maxQaz(v[0], 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;
}

- study January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- vishal.j January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- vishal.j January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous February 03, 2015 | Flag
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.

- npc January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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,

- koosha.nejad January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- npc January 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- roshenw February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- koosha.nejad February 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- random October 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about this:
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.

- Anonymous January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous January 29, 2015 | Flag
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;
	}
}

- Anselmo January 29, 2015 | Flag Reply
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;
	}
}

- Anselmo January 29, 2015 | Flag Reply
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;
}

void Google6()
{
	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) );
}

- PavPS January 29, 2015 | Flag Reply
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--) {
        heap.add(arr[i]);
        max = Math.max(max, heap.tailSet(arr[i], false).size());
    }
    return max;
}

- andreytim January 29, 2015 | Flag Reply
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);
        }
}

- Hangman January 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- koosha.nejad January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Hangman January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- hnatsu July 01, 2015 | Flag
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;
}

- Jar January 31, 2015 | Flag Reply
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;
		int added = 0;
		while (pointerL >= start) {
			while (arr[pointerL] < arr[pointerR] && pointerR >= mid + 1) {
				pointerR--;
				added++;
			}
			eleTimes[pointerL] += added;
			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);
	}

}

- allen.lipeng47 February 01, 2015 | Flag Reply
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) {
            set.add(i);
            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));
    }
}

- SHY February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Note that

tailSet(...).size()

is of

O(log(n))

- SHY February 01, 2015 | Flag
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.

- Pierce February 01, 2015 | Flag Reply
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.

- Pierce February 01, 2015 | Flag Reply
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.

- Pierce February 01, 2015 | Flag Reply
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.

- Pierce February 01, 2015 | Flag Reply
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.

- Pierce February 01, 2015 | Flag Reply
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.

- Pierce February 01, 2015 | Flag Reply
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.

- Pierce February 01, 2015 | Flag Reply
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.

- Pierce February 01, 2015 | Flag Reply
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.

- pierce February 01, 2015 | Flag Reply
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.

- forAQuestion February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- forAQuestion February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sounds interesting, have you written the code?

- koosha.nejad February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- forAQuestion February 04, 2015 | Flag
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.

- qpz February 04, 2015 | Flag Reply
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.

- VJ February 08, 2015 | Flag Reply
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.

- VJ February 08, 2015 | Flag Reply
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.

- VJ February 08, 2015 | Flag Reply
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).

- papishvili February 09, 2015 | Flag Reply
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 }

- koosha.nejad February 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Eason March 05, 2015 | Flag
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[0]









##### 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[0], 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[0]))

    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[0]:

                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[0]:

                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[0].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[0].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"

- ferma February 10, 2015 | Flag Reply
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[0]









##### 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[0], 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[0]))

    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[0]:

                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[0]:

                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[0].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[0].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"

- Anonymous February 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Easy peasy.

- Peasy Easy February 15, 2015 | Flag Reply
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;
}

- YD February 23, 2015 | Flag Reply
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

- blop June 07, 2015 | Flag Reply
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

- Anonymous June 11, 2015 | Flag Reply
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++];
	}
}

- dshao3@asu.edu June 22, 2015 | Flag Reply
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++)
			qaz.add(Math.min(size-i, map.get(sortedKeys.get(i))));
		Collections.sort(qaz);
		return qaz.get(qaz.size()-1);
	}

- Reyhan JB July 21, 2015 | Flag Reply
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[6] = {33 , 25 , 26 , 58 , 41 , 59};
  
  printf("max qaz %d\n", qaz(a, 6));
  return 0;
}

- r_coder September 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done using two stacks

- bharat December 08, 2015 | Flag Reply
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};
	}

- EPavlova January 14, 2016 | Flag Reply
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;
}

- zr.roman January 14, 2016 | Flag Reply
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.

- aascrivener July 24, 2016 | Flag Reply
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)

- Prabhjot Singh January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- Dz January 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

*q=3

- Dz January 27, 2015 | Flag
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.

- valoris January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- koosha.nejad January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- valoris January 28, 2015 | Flag
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.

- rizhang January 28, 2015 | Flag
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)

- sb January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- koosha.nejad January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

build AVL to solve "already sorted" problem.

- sb January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- koosha.nejad January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- pavelkushtia February 01, 2015 | Flag
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.

- Dinesh January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- koosha.nejad January 28, 2015 | Flag
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[0];

		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));
	}
}

- Jai January 28, 2015 | Flag Reply
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.

- surya January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- koosha.nejad January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Build BST at the same time find maxQaz.

- Dehong February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- koosha.nejad February 02, 2015 | Flag
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...

- Head January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- Pointer January 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Pointer
You are right. It's wrong

- Head January 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please provide some code to support this argument?

- bim January 27, 2015 | Flag


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