# Sort by Frequency and Value - Amazon Top Interview Questions

### Problem Statement :

```Given a list of integers nums, order nums by frequency, with most frequent values coming first. If there's a tie in frequency, higher valued numbers should come first.

Constraints

0 ≤ n ≤ 100,000 where n is the length of nums

Example 1

Input

nums = [1, 1, 5, 5, 5, 2, 2, 2, 1, 1]

Output

[1, 1, 1, 1, 5, 5, 5, 2, 2, 2]

Explanation

Since 1 occurs most frequently (4 times) they come first. 5 and 2 are then tied in terms of frequency
(both 3 times) but 5 has higher value so it comes second.```

### Solution :

```                        ```Solution in C++ :

bool sortcol(const pair<int, int>& v1, const pair<int, int>& v2) {
if (v1.second == v2.second) return v1.first > v2.first;
return v1.second > v2.second;
}
vector<int> solve(vector<int>& nums) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); i++) m[nums[i]]++;
vector<pair<int, int>> v(m.begin(), m.end());
sort(v.begin(), v.end(), sortcol);
vector<int> construct;

for (int i = 0; i < v.size(); i++) construct.insert(construct.end(), v[i].second, v[i].first);
return construct;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int[] solve(int[] nums) {
Map<Integer, int[]> map = new HashMap<>();

for (int num : nums) {
int[] arr = map.getOrDefault(num, new int[] {num, 0});
arr++;
map.putIfAbsent(num, arr);
}

int index = 0;
int[][] arrays = new int[map.size()][];
for (int[] arr : map.values()) arrays[index++] = arr;

Arrays.sort(arrays, (a, b) -> a == b ? b - a : b - a);

index = 0;
for (int i = 0; i < arrays.length; i++)
for (int j = arrays[i]; j > 0; j--) nums[index++] = arrays[i];

return nums;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, nums):
count = collections.Counter(nums)
return sorted(nums, key=lambda x: (count[x], x), reverse=True)```
```

## Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty