B*******1
发帖数: 2454 | 1 Give an unsorted array find count of pairs of numbers[a,b] where a > b and b
comes after a in the array.
Eg. {8,3,6,10,5}
the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
觉得这题跟amazon的这个很像，大家有没有这个感觉啊？
You have an array like ar[]= {1,3,2,4,5,4,2}. 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].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(n)
use of extra space allowed. | m****t
发帖数: 555 | 2 就是这道题。只能 达到 O(nlgn)
http://stackoverflow.com/questions/3836767/interview-question-r
b
equal
【在 B*******1 的大作中提到】
: Give an unsorted array find count of pairs of numbers[a,b] where a > b and b
: comes after a in the array.
: Eg. {8,3,6,10,5}
: the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
: 觉得这题跟amazon的这个很像，大家有没有这个感觉啊？
: You have an array like ar[]= {1,3,2,4,5,4,2}. 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].
: So the output of above should be {0,2,1,2,2,1,0}
: Time complexity : O(n)
| g**********y
发帖数: 14569 | 3 这个是求总和，比Amazon的简单。要是Amazon那个O(n)可解，这个也可以。但是这个有
O(n)解，不表明Amazon那个也有。
b
equal
【在 B*******1 的大作中提到】
: Give an unsorted array find count of pairs of numbers[a,b] where a > b and b
: comes after a in the array.
: Eg. {8,3,6,10,5}
: the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
: 觉得这题跟amazon的这个很像，大家有没有这个感觉啊？
: You have an array like ar[]= {1,3,2,4,5,4,2}. 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].
: So the output of above should be {0,2,1,2,2,1,0}
: Time complexity : O(n)
| d*******d
发帖数: 2050 | 4 use a bst, each node contain an extra field which hold the number of nodes
in the tree. | h**6
发帖数: 4160 | | d*******d
发帖数: 2050 | | g**********y
发帖数: 14569 | 7 O(nlogn)不难，但是肯定没有O(n)的解吗？
【在 h**6 的大作中提到】
: 用二叉索引树很容易的吧。
| r*******g
发帖数: 1335 | 8 hi
你们的思路是，对unsorted array做bst？然后呢？
【在 g**********y 的大作中提到】
: O(nlogn)不难，但是肯定没有O(n)的解吗？
| g**********y
发帖数: 14569 | 9 CLRS习题2.4-d
public class InversionCount {
public int count(int[] a) {
return mergeSort(a, 0, a.length - 1);
}
private int mergeSort(int[] a, int p, int r) {
if (p >= r) return 0;
int q = (p + r) / 2;
int c1 = mergeSort(a, p, q);
int c2 = mergeSort(a, q+1, r);
return c1 + c2 + merge(a, p, q, r);
}
private int merge(int[] a, int p, int q, int r) {
int[] t = new int[r - p + 1];
int count = 0;
int i = p;
int j = q+1;
int k = 0;
while (i<=q && j<=r) {
if (a[i] <= a[j]) {
t[k++] = a[i++];
}
else {
t[k++] = a[j++];
count += q-i+1;
}
}
while (i<=q) t[k++] = a[i++];
while (j<=r) t[k++] = a[j++];
for (i=p; i<=r; i++) a[i] = t[i-p];
return count;
}
}
【在 r*******g 的大作中提到】
: hi
: 你们的思路是，对unsorted array做bst？然后呢？
| s***f
发帖数: 226 | 10 一个unsorted array建立BST的worst time complexity是O(n^2)吧？ | | | g**********y
发帖数: 14569 | 11 hans说的应该是B-tree, 不是bst.
【在 s***f 的大作中提到】
: 一个unsorted array建立BST的worst time complexity是O(n^2)吧？
| r*******g
发帖数: 1335 | 12 man，我是想问思路啊，你给我的是mergesort的实现。
mergesort和这个题什么关系？
【在 g**********y 的大作中提到】
: CLRS习题2.4-d
: public class InversionCount {
: public int count(int[] a) {
: return mergeSort(a, 0, a.length - 1);
: }
:
: private int mergeSort(int[] a, int p, int r) {
: if (p >= r) return 0;
: int q = (p + r) / 2;
: int c1 = mergeSort(a, p, q);
| g**********y
发帖数: 14569 | 13 无语，你不能读读程序吗？如果不愿意读，你运行一下程序也行啊。
【在 r*******g 的大作中提到】
: man，我是想问思路啊，你给我的是mergesort的实现。
: mergesort和这个题什么关系？
| r*******g
发帖数: 1335 | 14 哈哈，不好意思，刚才看的太不仔细了，你是对的，原来就是mergesort的时候不断求
和就行了，这个想法很好。thanks
【在 g**********y 的大作中提到】
: 无语，你不能读读程序吗？如果不愿意读，你运行一下程序也行啊。
| d********y
发帖数: 2114 | 15 看了你的程序想起来以前做过这题。
可能是放在merge sort后面的练习里面的。
忘了可以这么做这个题了。
【在 g**********y 的大作中提到】
: 无语，你不能读读程序吗？如果不愿意读，你运行一下程序也行啊。
| g*****i
发帖数: 2162 | 16 bst怎么做? unbalance bst的话10和5在两个不同的tree里,怎么找到这对pair?
【在 d*******d 的大作中提到】
: use a bst, each node contain an extra field which hold the number of nodes
: in the tree.
| d*******d
发帖数: 2050 | 17 struct Node{
int v;
int count;
Node * left;
Node * right;
Node(int _v):v(_v), count(1), left(0), right(0){}
};
void insert(Node * & root, int v, int & c){
if( root == 0){
root = new Node(v);
return;
}
root->count++;
if( root->v == v){
if(root->right)
c = c + root->right->count;
}else if( v < root->v){
insert(root->left, v, c);
c = c + root->count - root->left->count;
}else{
insert(root->right, v, c);
}
return;
}
int find(int * a, int n){
Node * root = 0;
int c = 0;
for(int i = 0; i< n; i++){
insert( root, a[i], c);
}
return c;
}
【在 g*****i 的大作中提到】
: bst怎么做? unbalance bst的话10和5在两个不同的tree里,怎么找到这对pair?
| B*******1
发帖数: 2454 | | l****s
发帖数: 165 | 19 google jobs:
http://jobguiding.com/it-jobs/it-companies/google.html
b
equal
【在 B*******1 的大作中提到】
: Give an unsorted array find count of pairs of numbers[a,b] where a > b and b
: comes after a in the array.
: Eg. {8,3,6,10,5}
: the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
: 觉得这题跟amazon的这个很像，大家有没有这个感觉啊？
: You have an array like ar[]= {1,3,2,4,5,4,2}. 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].
: So the output of above should be {0,2,1,2,2,1,0}
: Time complexity : O(n)
|
|
