## Amazon Interview Question

• 1
of 1 vote

Country: United States

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

Start from index 'n-1' and keep adding each element in a BST. Since we're moving from the end, all the elements which are already in the BST are to be considered for the output. For an element at position 'x' every time you move to the right of a node in the BST, you know you've encountered the element of the node already and is smaller than the element at position 'x' so you increase the count of smaller values by 1. Write this count back to your array as soon as you attach the new node to it's parent.
We can just increment the count for duplicates and not add them to the BST.

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

This approach would work well for array of distinct elements. As we can't just increase the count again as we get duplicate element to insert in a BST. How will we differ from two duplicate elements at different indices in array?

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

Your solution works given the caveat that duplicate values are inserted into the left (or right, but not both) subtree, since the question states "less than or equal to ar[i]".

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

yes, even for dups, this solution works well. All you need to do is, insert duplicates on right side

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

As you insert you also keep a counter in each node that says how many such values has been encountered. Do not insert the duplicates as a separated node, instead increment the counter for that node in the tree.

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

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

I think the simplest approach to code and achieve O(n log n) is to use a Binary Indexed Tree. It's a good data structure when we want the frequencies up to some value.

We can either assume the values in the array are between 0 and some MAXVAL or preprocess the array - there are at most N distinct values and we only care about their relative order of magnitude.

``````const int MAXVAL = 10000;

int GetUpTo(int* tree, int val) {
int sum = 0;
for (; val > 0; val -= val & -val)
sum += tree[val];
return sum;
}
void Update(int* tree, int val) {
for (; val < MAXVAL; val += val & -val)
tree[val]++;
}
void Solve(int* values, int n, int* result) {
int tree[MAXVAL] = {};
for (int i = n-1; i >= 0; i--) {
result[i] = GetUpTo(tree, values[i]);
Update(tree, values[i]);
}
}``````

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

``````class Node{
Node left, right;
int index, val;
}

void findMinimums(int [] array){
int [] min_array[]=new int[array.lenght];
min_array[array.lenght-1]=0;
Node root=new Node();
root.index=array[array.lenght-1];
root.val=0;
for(int i=array.lenght-2; i>=0; i++){
insertNewNode(root, array[i], 0, min_array, i);
}
}
void insertNewNode(Node root, int index, int currentVal; int[] min_array, int arrayIndex){
if(index<=root.index){
if(index==currentVal){
currentVal++;
}
if(root.left==null){
Node node=new Node();
node.index=index;
node.val=currentVal;
min_array[arrayIndex]=val;
}
else{
insertNewNode(root.left, index, currentVal, min_array, arrayIndex);
}
}
else{
if(root.right==null){
Node node=new Node();
node.index=index;
node.val=currentVal+1;
min_array[arrayIndex]=val;
}
else{
insertNewNode(root.right, index, currentVal+1, min_array, arrayIndex);
}
}
}``````

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

We can use the insert function of Binary Search Tree with little modification as suggested by Other users.

We can also modify the node structure to keep two extra integer variable index of element and number of elements less than equal to it.

I have used extra array result to return.. since questions asked for ar_low;

``````public static Node LowestElementsTree(int[] a, int[] result, Node root, int pos, int h) {
if(root == null) {
result[pos] = h;
return new Node(a[pos]);
}

if(root.value > a[pos]) {
root.left = LowestElementsTree(a, result, root.left, pos, h);
} else {
root.right = LowestElementsTree(a, result, root.right, pos, h+1);
}
return root;
}

public static int[] getLowElements(int[] a) {
int[] result = new int[a.length];
Node root = null;
for(int i=a.length-1; i>=0; --i)
root = LowestElementsTree(a, result, root, a[i], 0);
return result;
}``````

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

Little modificaiton, In function getLowElements(int[] a). index should be passed.

``````public static int[] getLowElements(int[] a) {
int[] result = new int[a.length];
Node root = null;
for(int i=a.length-1; i>=0; --i)
root = LowestElementsTree(a, result, root, a[i], 0);
return result;
}``````

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

You can use Merge Sort with Binary search

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

How can you do this cleanly? I considered using mergesort, but you have to be careful that you keep track of the original index of the elements being sorted. Given how complicated that could be, I figured that the BST approach is more optimal. However, I would be interested if you have a clean way of using mergesort.

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

1) Make an array ar_p[] of pairs {value, index} such as ar_p[i] = {ar[i], i},
2) Fill ar_low[] with zeros,
3) Sort ar_p[] with modified "Merge Sort" algorithm by "value" field. The modification is in the "Merge" procedure:

``````Merge (left, right, ar_p, ar_low) {
...
while (...)
{
...
if (ar_p[left].value < ar_p[right].value)
{
ar_p_t[k] = ar_p[left];
++left;
}
else {
ar_p_t[k] = ar_p[right];
++ar_low[ar_p[right].index];
++right;
}
++k;
...
}
...
}``````

Instead of array of pairs we could use the array with indexes and sort the initial ar[] repeating all operations on the array of indexes.

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

Sorry, forgot to log in. If somebody wants more detailed explanation why merge sort and how it works "inversions counting algorithm" is a key for googling.

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

My proposal in Java:

``````{

class Node{
public int data;
public int count;
public Node p_left;
public Node p_right;
}

public class BSTCustom {

private Node tree;
private int val;
private Node processValue(Node root, int value, int counter){
if(root == null){
root = new Node();
root.data = value;
root.count = counter + 1;
val = root.count;
return root;
}
if(root.data < value){
root.p_right = processValue(root.p_right, value, root.count);
}
else if(root.data == value){
root.count++;
val = root.count;
}
else{
int aux = root.count;
root.count++;
root.p_left = processValue(root.p_left, value, aux - 2);
}
return root;
}
if(root == null)
return;
root.count++;
}

public BSTCustom(){
tree = null;
}
public int processValue(int value, int counter) {
tree = processValue(tree, value, counter);
return val;
}
}

---

public class Main {

public static void main(String[] args) {
BSTCustom bst = new BSTCustom();
int arr[] = {1, 3, 2, 4, 5, 4, 2};
int out[] = new int[arr.length];

for(int i = arr.length - 1; i >= 0 ; i--)
out[i] = bst.processValue(arr[i], -1);

for(int i = 0; i < arr.length; i++)
System.out.print(out[i] + " ");
System.out.println("");
//Output: 0 2 1 2 2 1 0
}
}``````

}

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

Python implementation:

``````'''
outputs an array such that when given
arr = [...]
for an index i, it gives you the number of elements in the arr[i+1:] which are smaller than arr[i]
PS: this code doesn't handle duplicates
'''
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

def insert(self, data):
if self is None:
self = Node(data)
elif data <= self.data:
# left insert
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
else:
# right insert
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)

def findNode(self, data):
if self is None:
return None
else:
if self.data == data:
return self
elif self.data > data and self.left is not None:
return self.left.findNode(data)
elif self.right is not None:
return self.right.findNode(data)

def calcLeftCount(self, data):
orderVisit = []
count = 0
node = self.findNode(data)
if node is not None and node.left is not None:
orderVisit.append(node.left)
while len(orderVisit) != 0:
node = orderVisit.pop()
count += 1
if node.right is not None:
orderVisit.append(node.right)
if node.left is not None:
orderVisit.append(node.left)
return count

if __name__ == "__main__":
root = None
_inpArr = []
_inp = " "
while True:
_inp = input('')
if _inp == "": break
_inpArr.append(int(_inp))
if root is None: root = Node(int(_inp))
else: root.insert(int(_inp))

print("Input:", _inpArr)
_output = []
for val in _inpArr:
_output.append(root.calcLeftCount(val))
print("Output:", _output)``````

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

You can achieve time O(N*K).

``````/**
* N - array length
* K - (max_value - min_value + 1)
* time: O(N*K)
* space: O(N+K)
*/
int[] lowerBounds(int[] arr){

int[] minAndMax = findMinAndMax(arr);

int offset = minAndMax;

int[] countArr = new int[ minAndMax- minAndMax + 1];

int[] res = new int[arr.length];

for( int i = arr.length-1; i >=0; i-- ){
int val = arr[i] - offset;

int lower = 0;
for( int k = val; k >=0; k-- ){
lower += countArr[k];
}
res[i] = lower;

countArr[val] += 1;
}

return res;
}``````

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

A slightly modified version of MergeSort does the trick here. Modification required to keep a track of the original index of the value.

``````public class P1 {
private int[] mainArray;
private int[] auxiliaryArray;

public P1(int[] a) {
mainArray = a;
auxiliaryArray = new int[a.length];
}

private int[][] sort(int[] a, int lo, int hi) {
if (lo >= hi) {
return new int[][]{{a[lo]}, {lo}};
}
int mid = (lo + hi) / 2;
int[][] sorted1 = sort(a, lo, mid);
int[][] sorted2 = sort(a, mid + 1, hi);
return merge(sorted1, sorted2);
}

private int[][] merge(int[][] sorted1, int[][] sorted2) {
int[][] consolidatedArray = new int[sorted1.length + sorted2.length];
int index1 = 0, index2 = 0, offset = 0;
for (int x = 0; x < sorted1.length + sorted2.length; x++) {
if (index1 < sorted1.length && index2 < sorted2.length) {
if (sorted1[index1] < sorted2[index2]) {
consolidatedArray[x] = sorted1[index1];
consolidatedArray[x] = sorted1[index1];
auxiliaryArray[sorted1[index1++]] += offset;
} else {
consolidatedArray[x] = sorted2[index2];
consolidatedArray[x] = sorted2[index2++];
offset++;
}
} else if (index1 < sorted1.length) {
consolidatedArray[x] = sorted1[index1];
consolidatedArray[x] = sorted1[index1];
auxiliaryArray[sorted1[index1++]] += offset;
} else if (index2 < sorted2.length) {
consolidatedArray[x] = sorted2[index2];
consolidatedArray[x] = sorted2[index2++];
}
}
return consolidatedArray;
}

public int[] countOfLessThanOrEqualTo() {
sort(mainArray, 0, mainArray.length - 1);
return auxiliaryArray;
}

//test client
public static void main(String[] args) {
int[] a = new int[]{44, -3, 6, 1, 8, 6, 33, 99, 6, 2, 1};
P1 p1 = new P1(a);
a = p1.countOfLessThanOrEqualTo();
for (int x = 0; x < a.length; x++) {
System.out.print(p1.auxiliaryArray[x] + " ");
}
}
}``````

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

By using a max heap and starting from the last element in the given array, compare the head of the heap with each element in the given array. If element is greater than the head, the respective arr_low[] value is the size of the heap.

``````public static int[] findRightSmallerCount(int[] arr){
int len = arr.length-1;
PriorityQueue<Integer> max_heap = new PriorityQueue<Integer>(len+1,new CompForMax());

int[] arr_low = new int[len+1];

for(int i=len;i>=0;i--){
if(i == len){
arr_low[i] = 0;
}else{
if(max_heap.peek() > arr[i]){
while(max_heap.size() > 0 && max_heap.peek() > arr[i]){
max_heap.remove();
}
}
arr_low[i] = max_heap.size();
}
}
return arr_low;
}``````

Comparator :

``````public class CompForMax implements Comparator<Integer> {
public int compare( Integer x, Integer y ){
return y - x;
}
};``````

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

create some examples. you'll see why this is incorrect

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

``````using System;

public class Program
{
public static void Main()
{
//{0,2,1,2,2,1,0}
int[] ar= {1,3,2,4,5,4,2};

int[] r = lessOrEqual(ar);
for (int i = 0; i < r.Length; i++)
Console.WriteLine(r[i]);
}

public static int[] lessOrEqual(int[] arr)
{
int[] r1 = new int[arr.Length];
for(int i = 0; i < arr.Length; i++)
{
int nf = 0;
for(int j= i+1; j < arr.Length ; j++)
{
if (arr[i] >= arr[j])
nf ++;
}
r1[i] = nf;
}

return r1			;

}
}``````

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

Slight change to Herman's code above. Using TreeMap's headMap method to get all keys less than or equal to current key and add up the count. O(nlogn) since everything is effectively BST operations

``````private static void printNewArray(int[] ar) {
TreeMap<Integer,Integer> tree = new TreeMap<Integer, Integer>();
int[] result = new int[ar.length];
for(int i=ar.length-1;i>=0;i--){
int freq = 1;
if(tree.containsKey(ar[i])){
freq = tree.get(ar[i]);
freq++;
}
tree.put(ar[i], freq);

// always returns atleast one entry since the call is inclusive
int count=0;
for(Map.Entry<Integer,Integer> entry :entrySet){
count=count+entry.getValue();
}
result[i]=count-1; // subtract the count from inclusive node entry
}
// printArray(result);
}``````

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

FirstAnswer, some tips: The moment you see nLogn, you know its tree, and insertion to BST is logn, so you are doing it for n nodes.

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

FirstAnswer, some tips: The moment you see nLogn, you know its tree, and insertion to BST is logn, so you are doing it for n nodes.

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

You could do an insertion sort starting with the last element and moving towards the first. Using a linked list to store the elements (no need for shifting) the Insert(...) method can update the list and return the amount of nodes that were skipped during insertion.

This will have a worst case of O(N^2), but the average case could suffice for the answer.

The tree structure used to achieve O(N*log(N)) is simple to figure once you maybe get a hint. This question would not be a proper phone screen question. Here is what I could come up with. I assume there should be a few bugs since I did this quickly.

``````class TreeNode:
def __init__(self, left, right, value):
self._left = left
self._right = right
self._value = value
self._onLeft = 0

def _place(node, value, smallerAbove):
if value >= node._value:
if node._right == None:
node._right = TreeNode(None, None, value)
return smallerAbove + 1
else:
return _place(node._right, value, smallerAbove + node._onLeft + 1)
else:
node._onLeft += 1
if node._left == None:
node._left = TreeNode(None, None, value)
return smallerAbove
else:
return _place(node._left, value, smallerAbove)

def solve(data):
result = *len(data)
index = len(data) - 2
root = TreeNode(None, None, data[index + 1])
while index >= 0:
result[index] = _place(root, data[index], 0)
index -= 1
return result

print solve([1,3,2,4,5,4,2])``````

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

Please give more clarifications of how each element in ar_low is calculated. what does "You need to create
another array ar_low[] such that ar_low = number of elements lower
than or equal to ar in ar[i+1:n-1]. " mean? or you meant "You need to create
another array ar_low[] such that ar_low[I] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1]. "

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

Use of array list would greatly decrease job :)
Try this one:

``````package cc.amazon.arraycounter;

import java.util.ArrayList;
import java.util.Arrays;

public class Counter {

public static void main(String[] args) {
// TODO Auto-generated method stub

ArrayList<Integer> array = new ArrayList<Integer>();
Integer arr[] = { 1,3,2,4,5,4,2 };
ArrayList<Integer> count = new ArrayList<Integer>();
int counter = 0;
int pos = 0;

for (Integer integer : array) {

counter = 0;

for (Integer num : array.subList(pos, array.size() - 1)) {

if (num <= integer) {
counter++;
}
}
pos++;
}

System.out.println("Output: " + count);
}

}``````

This has required O(nlogn) complexety

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

This has O(N^2) complexity. The sublist part is O(N), for each one of the N integers

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

Try using Longest Decreasing Subsequence.

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

``````int[] getArrayLess(int[] array) {
int[] result = new int[array.length];
TreeMap<Integer, Integer> counts = new TreeMap<Integer, Integer>();
for (int i = array.length - 1; i >= 0; i--) {
if (counts.containsKey(array[i])) {
result[i] = counts.get(array[i]) + 1;
} else {
if (counts.lowerKey(array[i]) == null) {
result[i] = 0;
} else {
result[i] = counts.lowerEntry(array[i]).getValue() + 1;
}
}
counts.put(array[i], result[i]);
}
return result;
}``````

TreeMap FTW, guaranteed O(log n) for most operations without the hazzle of rolling your own (probably faulty) BST implementation

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

This is incorrect. You're not guaranteed to get the correct frequency just by checking the lowerKey(). A simple counter-example: {3, 1, 2}. You algorithm gives {1, 0, 0} but it should be {2, 0, 0}

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

Instead of lowerKey() use .headMap(ar[i],true). Then add up the counts for returned nodes which are guaranteed to have values less than or equal to current key

``````Set<Map.Entry<Integer,Integer>> entrySet = tree.headMap(ar[i],true).entrySet();
// always returns atleast one entry since the call is inclusive
int count=0;
for(Map.Entry<Integer,Integer> entry :entrySet){
count=count+entry.getValue();
}
result[i]=count-1; // subtract the count from inclusive node entry``````

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.