Amazon Interview Question Software Engineer / Developers
Create another array which contains the count of numbers in the ar[]
like ar_count = {1,2,1,2,1}
Now loop ar and count the numbers which are less than ar[i] in ar_count
also reduce the count in ar_count once you completes processing of the number in ar[].
Scan from right to left.
for each i
low[i] = cf(A[i]);
increment f(A[i]) by 1
now both getting cf(A[i]) and updating f(A[i]) can be done in log(n)
(where n is the max number that is listed in the array)
with data structure BIT(Binary Indexed Tree)
TopCoder tutorial has a nice explanation of it.
Unfortunately, it can't be done in O(n).
One way to do it is to scan the array in reversed order, maintaining a balanced binary tree which can answer queries like "how many elements in the tree are smaller or equal to x".
This will do it in O(nlogn) time.
However, if the elements in the array are all integers in the range [0..m], the job can also be done in O(nlogm) time with a binary indexed tree (a tree-like-structured array).
>Unfortunately, it can't be done in O(n)
Do you have a better reason than "ftfish said so"?
"One way to do it is to scan the array in reversed order, maintaining a balanced binary tree which can answer queries like "how many elements in the tree are smaller or equal to x".
This will do it in O(nlogn) time"
@ftfish can you elaborate this method which uses a binary tree?
I think this can be done in O(n):
1.we can use a stack, traverse the arr from 0 -> n-1, for every val, if val <= top of stack, pop out the top, and the top to the child list of curr. Do this until top of stack < val or stack is empty.
2.At end, all the value in stack's target is 0, and the target of 'children of this value ' is +1.
3. Every node get visited at most twice, so is O(n).
see my python code:
def main():
ar = [1,3,2,4,5,4,2]
n = len(ar)
q = []
# val, idx, ans, children
q.append((ar[0], 0, 0, []))
for i in xrange(1, n):
curr = (ar[i], i, 0, [])
while len(q) > 0 and ar[i] <= q[len(q) - 1][0]:
tp = q.pop()
curr[3].append(tp)
q.append(curr)
ans = [0] * n
for x in q:
idx = x[1]
tar = x[2]
chi = x[3]
ans[idx] = tar
for c in chi:
q.append((c[0], c[1], c[2] + tar + 1, c[3]))
print ans
very nice gaoxiao, that seems correct. you should post in a main reply to the question to get your answer more visible
@Miguel Oliveira sorry, I find this method is wrong.
It fails the following eg:
[4,12,5,6,1,34,3,2]
o/p [3,5,3,3,0,2,1,0]
A lower bound of Omega(nlogn) can be proved by reducing the "element distinctness problem" to this one:
1. Build ar_low for ar and reversed(ar) so that we can calculate the number of elements smaller than or equal to ar[i] in the whole array for every i.
2. Compare the sum of all such numbers to binomial(n, 2)=n*(n-1)/2. If both are different, (that is, if the former is larger,) there must be equal elements in the array.
E.g.:
ar=[5,2,3]
So the number of elements in the whole array that are smaller than or equal to each element is [2,0,1], the sum is 3, which is equal to C(3,2)=3. So there's no equal element.
On the other hand, for ar=[1,5,1], the numbers are [1,2,1], summing to 4 > 3. So there is equal element.
ftfish is right. It is impossible to do it below O(nlogn) since
after we get ar_low[i], the array can be easily sorted without
any comparison. And sorting takes O(nlogn).
Does counting sort ring a bell?
I assume (my assumption might be wrong) the numbers might be in a definite range.
if the integers in the array fall in the range 0-m, and assuming m<<<n, it can be solved in O(nm) using counting sort. And since m<<<n, O(nm)~O(n), but if m is comparable to n, it cannot be done in any algorithm better than O(nlogn)
@abc I am not sure I followed your example correctly. {1,3,2,4,5,4,2}
Number of elements lesser or equal to 1=0,3=3,2=3,4=5,5=6,4=5,2=3.. am I missing something here?
you are missing one point.
The ask is to find the count of numbers less than arr[i] in subarray arr[i+1:n-1]
i=0, arr[i]=1, count(elem<=1 in arr[1:6])=0
i=1, arr[i]=3, count(elem<=3 in arr[2:6])=2
i=2, arr[i]=2, count(elem<=2 in arr[3:6])=1
i=3, arr[i]=4, count(elem<=4 in arr[4:6])=2
i=4, arr[i]=5, count(elem<=5 in arr[5:6])=2
i=5, arr[i]=4, count(elem<=4 in arr[6:6])=1
i=6, arr[i]=2, count(elem<=2 in arr[7:6])=0
But there's no mention of a definite range in the question so as to invoke counting sort() ????
The fastest and exact O(n log n) algo is using BIT (binary indexed tree)
->read elements from right and for each element a[i], update the position at T[a[i]] by +1 ---> O(lg n)
->query T[a[i]] gives sum of all the elements encountered till now from 0 to a[i] -> O(lg n)
--> memory needed is O( max(a[0],a[1]....a[n]) )
some people say AVL or Red Black tree can give similar complexity. Thats true but overhead is very large in those trees.
Scan from right to left of the array
Tree structure
Struct tree
{
int data;
int freq;
tree *left;
tree *right;
}
Now as you create the tree if the new element is to the right of the node then add the freq of that node until that element find place in the tree
The total freq = no of elements small or equal to it.
If element is already their in the tree then increase its freq.
Time complexity : T(nlogn)
Looks fine, but for the new element to be added the frequency should 1 more than the frequency of the last node (say p)u took right path from (while inserting). Because node p already has the number of elements less than this.
So, for new node req number = frequency of p + 1(for p)
I take up the example to describe how it works
Let say we have the array as {1,3,2,4,5,4,2}
Scan from right to left
1) insert 2 with freq as 1, since parent therefore count = 0 for it where count is the number of elements lower than or equal to it.
2) Insert 4, right of 2, its count will be freq of 2 and its own freq will be 1
Uptil now resulting array = {1,0}
3) Insert 5, which is right of 2 and right of 4, therefore count = freq(4) + freq(2) = 2, its freq = 1
4) Insert 4 again, right of 2 but exists, therefore
count = freq(2) + freq(4) = 2, node with value 4 freq = 2
5) Insert 2, parent count = 1 and freq = 2
6) insert 3, right of 2 and left of 4, count = freq(2) , its own freq = 1
7) Insert 1, left of 2 therefore count = 0, freq = 1
How about the array {4,1,3,2,4,5,4,2} where I add a 4 in the first position? You will not traverse through "1" and "3" in the tree. Any idea?
ibnipun10's method is absolutely WRONG! I doubt people even work on paper first, before posting to CC. Simply ridiculous!!!
Hi Anonymous,
I may have missed out this one but the method is not absolutely WRONG, as you said. Did you ever tried this algorithm to find what could be the possible error
If you slightly tweak the algorithm and increment the freq of the node if the element belongs to the left of the node then it will work fine, try it our
You do not do things in your mind and then come up random solutions
struct Tree
{
int data;
int freq;
Tree *left;
Tree *right;
};
Tree* AddNodes(Tree *node, int value, int *arr, int index, int count)
{
if(node == NULL)
{
node = new Tree();
node->data = value;
node->freq++;
node->left = NULL;
node->right = NULL;
arr[index] = count;
return node;
}
else
{
if(value == node->data)
{
arr[index] = count + node->freq;
node->freq++;
}
else if(value < node->data)
{
node->left = AddNodes(node->left, value, arr, index, count);
}
else
{
node->right = AddNodes(node->right, value, arr, index, (count + node->freq));
}
}
return node;
}
int _tmain(int argc, _TCHAR* argv[])
{
Tree *root = NULL;
int arr[] = {1,3,2,4,5,4,2};
int arrCount[7];
for(int i=6;i>=0;i--)
{
root = AddNodes(root, arr[i], arrCount, i, 0);
}
return 0;
}
<pre lang="java" line="1" title="CodeMonkey51041" class="run-this">// Code is huge but surely work this O(nlogn) according to coreman books hint
import java.util.Random;
class Inversions {
public static void main(String args[]) // entry point from OS
{
int[] a = new int[5];
int[] b = new int[5];
int[] c = new int[5];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(37);
b[i] = i;
System.out.printf("%3d", a[i]);
}
System.out.println();
System.out.println("Total Inversion:-"
+ mergeSort(a, b, c, 0, a.length - 1));
System.out.print("Pairs:-");
for (int i = 0; i < a.length; i++) {
System.out.printf("(%3d,%3d)", i, c[i]);
}
}
private static int mergeSort(int[] a, int[] b, int[] c, int p, int r) {
// TODO Auto-generated method stub
int count = 0;
if (p < r) {
int q = (p + r) / 2;
count = mergeSort(a, b, c, p, q);
count += mergeSort(a, b, c, q + 1, r);
count += merge(a, b, c, p, q, r);
}
return count;
}
private static int merge(int[] a, int[] b, int[] c, int p, int q, int r) {
// TODO Auto-generated method stub
int[] left = new int[q - p + 1];
int[] right = new int[r - q];
int[] left1 = new int[q - p + 1];
int[] right1 = new int[r - q];
for (int i = 0; i < left.length; i++) {
left[i] = a[p + i];
left1[i] = b[p + i];
}
for (int i = 0; i < right.length; i++) {
right[i] = a[i + q + 1];
right1[i] = b[i + q + 1];
}
int count = 0;
int x = 0;
int i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
a[p] = left[i];
b[p] = left1[i];
c[b[p]] += x;
count = count + x * 1;
p++;
i++;
} else {
x++;
a[p] = right[j];
b[p] = right1[j];
p++;
j++;
}
}
while (i < left.length) {
a[p] = left[i];
b[p] = left1[i];
count = count + x * 1;
c[b[p]] += x;
i++;
p++;
}
while (i < right.length) {
a[p] = right[i];
b[p] = right1[i];
i++;
p++;
}
return count;
}
}
</pre><pre title="CodeMonkey51041" input="yes">
</pre>
This can be done is O(n) time. Let a array ar_low initialized to 0.
for(i=0;i<length.arr;i++)//contains no. of numbers equal
ar_low[ar[i]]++;
for(i=1;i<length;i++)//contains no. of numbers less than
ar_low[i]+=ar_low[i-1];
it gives all the values which are less than a particular value. for eg: {1,3,2,4,5,4,2} for 5 it should give 2 which are vals <= ahead of 5 but here u consider values behind and after of that value
for clarity
As values could be sparse in the array
second for loop should be ar_low[ar[i]]+=ar_low[ar[i-1]]
Let the range of elements is m.
Starting from right most, create a bit vector for each position representing the values bit set for the values right to it.
Continue doing till the leftmost. (OR with the previous one gives the current one)
Then from starting left, for each value create a bit vector with all ones till the value and zeros less than the value and AND it with the bit vector for the position created in the previous walk. The number of set bits gives the values less than the current value and right to the current position.
#include <iostream>
- abc July 13, 2010#include <stack>
#define N 9
using namespace std;
int main ()
{
int a[N] = {1, 5, 10, 3, 4, 16, 29, 2, 7}; /* Input Array /
int b[N] = {0}; / Output Array */
int i;
stack <int> st;
for (i=0; i<N ; i++)
{
while (!st.empty() && a[i] < a[st.top()]) {
b[st.top()] = a[i];
st.pop();
}
st.push(i);
}
while (!st.empty())
{
b[st.top()] = 0;
st.pop();
}
cout<<"\n\n";
for (i=0;i < N;i++)
cout<<b[i]<<" ";
cout<<"\n";
}