Amazon Interview Question
Country: United States
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?
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]".
yes, even for dups, this solution works well. All you need to do is, insert duplicates on right side
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.
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]);
}
}
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);
}
}
}
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;
}
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.
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.
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;
updateSons(root.p_right);
}
else{
int aux = root.count;
root.count++;
root.p_left = processValue(root.p_left, value, aux - 2);
updateSons(root.p_right);
}
return root;
}
private void updateSons(Node root){
if(root == null)
return;
root.count++;
updateSons(root.p_left);
updateSons(root.p_right);
}
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
}
}
}
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)
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[0];
int[] countArr = new int[ minAndMax[1]- minAndMax[0] + 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;
}
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[2][sorted1[0].length + sorted2[0].length];
int index1 = 0, index2 = 0, offset = 0;
for (int x = 0; x < sorted1[0].length + sorted2[0].length; x++) {
if (index1 < sorted1[0].length && index2 < sorted2[0].length) {
if (sorted1[0][index1] < sorted2[0][index2]) {
consolidatedArray[0][x] = sorted1[0][index1];
consolidatedArray[1][x] = sorted1[1][index1];
auxiliaryArray[sorted1[1][index1++]] += offset;
} else {
consolidatedArray[0][x] = sorted2[0][index2];
consolidatedArray[1][x] = sorted2[1][index2++];
offset++;
}
} else if (index1 < sorted1[0].length) {
consolidatedArray[0][x] = sorted1[0][index1];
consolidatedArray[1][x] = sorted1[1][index1];
auxiliaryArray[sorted1[1][index1++]] += offset;
} else if (index2 < sorted2[0].length) {
consolidatedArray[0][x] = sorted2[0][index2];
consolidatedArray[1][x] = sorted2[1][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] + " ");
}
}
}
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();
}
max_heap.add(arr[i]);
}
return arr_low;
}
Comparator :
public class CompForMax implements Comparator<Integer> {
public int compare( Integer x, Integer y ){
return y - x;
}
};
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 ;
}
}
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);
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
}
// printArray(result);
}
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 = [0]*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])
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]. "
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 };
array.addAll(Arrays.asList(arr));
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++;
}
}
count.add(counter);
pos++;
}
System.out.println("Output: " + count);
}
}
This has required O(nlogn) complexety
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
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}
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
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.
- Anonymous June 22, 2014We can just increment the count for duplicates and not add them to the BST.