# Long Distance - Amazon Top Interview Questions

### Problem Statement :

```Given a list of integers nums, return a new list where each element in the new list is the number of smaller elements to the right of that element in the original input list.

Constraints

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

Example 1

Input

lst = [3, 4, 9, 6, 1]

Output

[1, 1, 2, 1, 0]

Explanation

There is 1 smaller element to the right of 3

There is 1 smaller element to the right of 4

There are 2 smaller elements to the right of 9

There is 1 smaller element to the right of 6

There are no smaller elements to the right of 1

Example 2

Input

lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Output

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Example 3

Input

lst = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Output

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]```

### Solution :

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

vector<int> ans;
void merge(vector<int> &v, int idx[], int l, int mid, int r) {
int l_n = mid - l + 1, r_n = r - mid;
int left[l_n], right[r_n];
for (int i = 0; i < l_n; i++) left[i] = idx[l + i];
for (int i = 0; i < r_n; i++) right[i] = idx[mid + 1 + i];
for (int i = l_n - 1, j = r_n - 1, k = r; k >= l; k--) {
if (j < 0 or (i >= 0 and v[left[i]] > v[right[j]])) {
ans[left[i]] += j + 1;
idx[k] = left[i--];
} else {
idx[k] = right[j--];
}
}
}

void mergesort(vector<int> &v, int idx[], int l, int r) {
if (l < r) {
int mid = l + (r - l) / 2;
mergesort(v, idx, l, mid);
mergesort(v, idx, mid + 1, r);
merge(v, idx, l, mid, r);
}
}

vector<int> solve(vector<int> &nums) {
int n = nums.size(), idx[n];
ans = vector<int>(n, 0);
for (int i = 0; i < n; i++) idx[i] = i;
mergesort(nums, idx, 0, n - 1);
return ans;
}```
```

```                        ```Solution in Java :

import java.util.*;

// This is esentially count the number of inversions problem.

class Solution {
public int[] solve(int[] lst) {
if (lst.length == 0)
return new int;

Point[] points = new Point[lst.length];

// convert given numbers to Points
for (int i = 0; i < lst.length; i++) {
points[i] = new Point(lst[i], i);
}

int[] result = new int[points.length];

mergeSort(points, 0, points.length - 1, result);

return result;
}

private Point[] mergeSort(Point[] points, int start, int end, int[] result) {
if (start >= end)
return new Point[] {points[start]};

int mid = start + (end - start) / 2;

Point[] left = mergeSort(points, start, mid, result);
Point[] right = mergeSort(points, mid + 1, end, result);

return merge(left, right, result);
}

private Point[] merge(Point[] left, Point[] right, int[] result) {
Point[] merged = new Point[left.length + right.length];

int i = 0;
int j = 0;

while (i < left.length && j < right.length) {
if (left[i].val <= right[j].val) {
merged[i + j] = left[i];
result[left[i].index] += j;
i++;
} else {
merged[i + j] = right[j];
j++;
}
}

while (i < left.length) {
merged[i + j] = left[i];
result[left[i].index] += j;
i++;
}

while (j < right.length) {
merged[i + j] = right[j];
j++;
}

return merged;
}

// Used as a utility class to easily identify the index of an element
private class Point {
int index;
int val;

public Point(int val, int i) {
this.val = val;
this.index = i;
}
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, lst):
def mergesort(indexes):
k = len(indexes)
if k <= 1:
return indexes
left = mergesort(indexes[: k // 2])
right = mergesort(indexes[k // 2 :])
for i in range(len(indexes) - 1, -1, -1):
if not right or left and lst[left[-1]] > lst[right[-1]]:
ans[left[-1]] += len(right)
indexes[i] = left.pop()
else:
indexes[i] = right.pop()
return indexes

n = len(lst)
ans =  * n
mergesort(list(range(n)))
return ans```
```

## Insert a node at a specific position in a linked list

Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing