• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            life02

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              197 隨筆 :: 3 文章 :: 37 評論 :: 0 Trackbacks

            2009.9.12日下午 迅雷2筆試題

            有一副牌編號0~51,請把這副牌盡可能隨機的發到4個人手里
            注1:已經有rand()函數可以調用,但是rand()函數開銷較大,請盡量少調用

            a,b,c,d分別是13個元素的1維數組
            函數原型 void deal( int[] a, int[] b, int[] c, int[] d );


            實現字符串反轉的c庫函數 char* strrev(char* string)
            注1:不可利用其他庫函數,算法盡量高效、占用空間少。


            有10億個數,這些數的值都在0~1000萬之內。實現接口 get_bigger_count( unsigned value )
            輸入一個值value,返回這10億個數中比value值大的數的數目。
            class order_calculate
            {
            public:
            order_calculate();
            ~order_calculate();
            unsinged get_bigger_count( unsigned value )
            }
            注1:get_bigger_count接口會被頻繁的調用,實現要高效
            注2:可以自己往內部任意添加變量和接口
            注3:有個現成的接口 unsigned get_value_by_index( int idx ) 可以調用,該接口返回指定索引的value值
                 比如 get_value_by_index( 100 ), 返回10億個數中第100個數的值。該接口開銷較大,盡量少調用。



            http://topic.csdn.net/u/20090912/20/8c60e06e-321c-49a6-b2cc-59248ba9cf36.html?28642 

            posted on 2009-09-13 16:29 life02 閱讀(783) 評論(2)  編輯 收藏 引用 所屬分類: 筆試

            評論

            # re: 筆試題 2009-09-14 18:16 life02
            第三題正解如下:
            這題很明顯已經告訴各位了,算法復雜度是o(1),任何其他排序算法都是錯的,只有桶排序可行,原因也很明顯,符合桶排序的特征,0到1000萬的取值范圍已經固定了,相對10億來說1000萬是很小了。

            所以只要設立0到1000萬的桶,中間附加計數即可,什么意思呢,10億個數據,如果縮小一點:范圍是0到10的話
            0,1,2,3,4,5,6,7,8,9,10

            在每一個桶下面掛一個count,掃描完后,10億個數據肯定都在這10個桶里(1000萬類似)

            這樣在接下來查詢的時候,其實比較空間只有0到1000萬,和10億一點關系都沒有,而且每個桶還幫你記著大于該數的個數,所以假定要比較的數值是5,則結果就是5,6,7,8,9,10的count之和。

            計算空間最大浪費就是在0到1000萬里面,找到你的那個數值,但是總比N要小很多,這個結論拿出去,面試來說,應該可以得滿分,至于效率,空間什么的,就自己優化1000萬數據的比較算法啦。  回復  更多評論
              

            # re: 筆試題 2009-09-18 10:09 life02
            #include <iostream>
            #include <stdio.h>
            #include <assert.h>
            using namespace std;


            static unsigned int *pindex;

            #define L 10000001
            unsigned get_bigger_count(unsigned value)
            {
            assert(value<L-1);
            static binit(false);
            unsigned int rval(0);
            if(!binit)
            {
            FILE *fp = fopen("datafile", "r+b");
            unsigned int i = 0;
            unsigned int shu;
            pindex = new unsigned int[L];
            memset(pindex, 0, sizeof(unsigned int)*L);

            while(fscanf(fp,"%ld",&shu)!=-1){
            /* cout<<shu<<endl;*/
            pindex[shu]++;
            }
            fclose(fp);
            for(i=L-1; i>0; --i)
            pindex[i-1] += pindex[i];
            }
            binit = true;
            rval = pindex[value+1];
            return rval;
            }




            int main(){
            unsigned un;
            un=get_bigger_count(8738787);
            cout<<un<<endl;
            return 0;
            }  回復  更多評論
              

            精产国品久久一二三产区区别| 日本WV一本一道久久香蕉| 国产精品无码久久综合| 狠狠色丁香婷综合久久| 精品综合久久久久久88小说| 亚洲国产视频久久| 久久精品国产精品青草| 亚洲欧美成人久久综合中文网| 亚洲精品乱码久久久久66| 国产午夜精品久久久久九九电影| yy6080久久| 久久精品亚洲福利| 久久久久无码精品国产不卡| 亚洲国产日韩欧美久久| 日韩亚洲欧美久久久www综合网| 久久久久久精品久久久久| 久久精品一区二区三区不卡| 青青草原综合久久大伊人| 99久久精品免费国产大片| 久久婷婷五月综合97色| 精品久久久久久国产三级| 久久久久99精品成人片直播| 久久青青色综合| 久久99久久无码毛片一区二区 | 人妻中文久久久久| a级成人毛片久久| 2021精品国产综合久久| 精品久久久无码人妻中文字幕| 日韩久久无码免费毛片软件| 精品久久综合1区2区3区激情| 久久99精品国产99久久| 久久w5ww成w人免费| 久久精品亚洲中文字幕无码麻豆 | 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 精品久久久久中文字幕日本| 国内精品久久久久久久久电影网 | 亚洲精品99久久久久中文字幕 | 热re99久久精品国99热| 日本欧美久久久久免费播放网| 精品人妻伦九区久久AAA片69| 久久天天躁狠狠躁夜夜躁2014|