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

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條評論
主站蜘蛛池模板: 日韩欧美一区二区三区在线 | 国产精品一区不卡 | 亚洲精品综合久久 | 日本欧洲亚洲一区在线观看 | 午夜影院免费在线观看 | 亚洲精品区一区二区三区四 | 免费的拍拍视频在线观看 | 九九精品九九 | 羞羞网站在线看 | 国产精品资源 | 2020年国产高中毛片在线视频 | 神马影院在线观看我不卡 | 麻豆国产原创最新在线视频 | 国产亚洲综合一区二区在线 | 福利国产在线 | 四虎影院永久免费 | 成人精品国产 | 九九久久免费视频 | 国产小视频免费观看 | 成人合集大片bd高清在线观看 | 日本特级爽毛片叫声 | 成人亚洲欧美综合 | 精品无码久久久久久久动漫 | 国产精品亚洲一区二区三区正片 | 四虎网址在线 | 涩涩虎| se在线观看| 麻豆视频一区 | 一级特级aaaa毛片免费观看 | 午夜在线播放 | 一级黄色影片 | 亚洲一区二区影院 | 综合久久综合久久 | 91国内在线观看 | 国产成人精品视频一区二区不卡 | 中文字幕亚洲 综合久久 | 国产精品久久久久免费 | 亚洲欧洲日产国码二区首页 | 国产一级在线观看www色 | 午夜视频福利在线观看 | 日韩你懂的 |