亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Google Interview - Compute the h-index of a

系統 2440 0

Google:

Compute the h-index of a list of papers, given their citation count. Can you do it in linear time? How about a distributed algorithm for the task?

?

Facebook:

Given: for every paper authored, there is a citation count vector. The h-index is a measure of researcher importance. h-index: The largest number i such that there are i papers each with at least i citations.?

1. Suppose that the citation-vector is sorted, how to efficiently compute the h-index??

2. Suppose that the citation-vector is not sorted, how to efficiently compute the h-index? time complexity? an algorithm with time complexity n?

?

Princeton algorithm:

Given an array of N positive integers, its h-index is the largest integer h such that there are at least h entries in the array greater than or equal to h. Design an algorithm to compute the h-index of an array.?

Hint: median or quicksort-like partitioning and divide-and-conquer.

?

Solution:

- Create an int[] Histogram as big as the maximum number of publications of any particular scientist).?

- If all publication reference counts are stored in another int[] references, then go over this array and, on each publication, if it's reference count is R, then do Histogram[R]++. While doing this, keep the maximum reference count in Max.?

- After building the histogram, do a decreasing loop on int[] Histogram from i=Max, adding Histogram[i] values to int hIndex. When hIndex >= i, return i as the hIndex.?

... As to the distributed part, let several machines build the Histogram of disjoint sets of somebody's publications, and then have one machine add up those histograms and return hIndex as described above.

?

1. binary-search (O(log(n)). If citations[i] >= i then h >= i (if array's in descending order).

2. Here's a O(n) time & space solution in ruby. The trick is you can ignore citation-counts larger than n.

?

If there are 'n' papers in total, this problem can be solved in O(n) with space complexity of O(n). Note that, h-index can be between 0 to n. Say if the h-index is 10, this means, there has to be 10 papers with citation count >= 10. So if we can find out the number of papers with citations >=X for every X (and store it in an array C) where X ranges between 0 to n, then by scanning the count array C from the right to left, we can find the h-index at index i where i == C[i].?

Pseudocode:?
input array A of length n.?

- init array C[0] to C[n] with 0?
- foreach p in A, if p >= n, c[n]++; else c[p] +=1?
- for i=n-1 to 0, c[i]=c[i]+c[i+1]?
- for i=n to 0, if c[i] == i return i

?

      // assume sorted in descending order, O(lgN)
public static int getHIndexFromSorted(int[] citation) {
    int low = 0; int high = citation.length - 1;
    while(low <= high) {
        int idx = (low+high)/2;
        if(citation[idx] >= idx + 1) {
            low = idx + 1;
        } else {
            high = idx - 1;
        }
    }
    return low;
}

// sort the array, O(NlgN)
public static int computeHIndexBySorting(int[] A) {
    Arrays.sort(A);
    int h = 0;
    for (int i = A.length-1; i >= 0; i--) {
        if(A[i] > h) {
            h++;
        } else {
            return h;
        }
    }
    return -1;
}

// no need to sort array, O(N)
public static int computeHIndex(int[] A) {
    int n = A.length;
    int[] s = new int[n+1];
    for(int num : A) {
        num = Math.min(n ,num);
        s[num]++;
    }
    int sum = 0;
    for (int i = s.length-1; i >= 0; i--) {
        sum += s[i];
        if(sum >= i) {
            return i;
        }
    }
    return -1;
}
    

?

?

Reference:

http://en.wikipedia.org/wiki/H-index

http://www.careercup.com/question?id=14585874

http://algs4.cs.princeton.edu/25applications/

http://www.glassdoor.com/Interview/Compute-the-h-index-of-a-list-of-papers-given-their-citation-count-Can-you-do-it-in-linear-time-How-about-a-distributed-QTN_572531.htm

?

Google Interview - Compute the h-index of a list of papers


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久久99精品九九九久久婷婷 | 日本免费网址 | 国产免费久久精品44 | 欧美 亚洲 中文字幕 | 亚洲视频在线精品 | 极品女神西比尔久久精品 | 羞羞在线视频 | 亚洲精品中文字幕久久久久久 | 欧洲毛片 | 99热这里只有精品7 99热这里只有精品8 | 久久色网 | 四虎国产精品免费久久麻豆 | 久久一区二区三区免费播放 | 美女被羞羞视频网站在线 | 亚洲日韩aⅴ在线视频 | 中文字幕日韩哦哦哦 | 日本 欧美 国产 | 日韩在线看片 | 香蕉视频在线网站 | 男人午夜影院 | 性大特级毛片视频 | 欧美日韩影视 | 香蕉精品视频在线观看入口 | 久久久国产亚洲精品 | 波多野结衣一区二区三区高清在线 | 欧洲美女a视频一级毛片 | 成人在激情在线视频 | 亚洲国产精品欧美综合 | 青青免费视频视频在线 | 中国一级毛片在线观看 | 999久久久免费精品国产牛牛 | 国产精品福利视频免费观看 | 久久久国产精品福利免费 | 性欧美一级毛片在线播放 | 亚洲欧美综合区自拍另类 | 天天干天天添 | 午夜成年人网站 | 国产激情在线视频 | 国产激情 | 91精品久久 | 婷婷亚洲五月色综合 |