• <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 閱讀(780) 評論(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;
            }  回復  更多評論
              

            久久久精品国产Sm最大网站| 国产亚洲美女精品久久久久狼| 久久国产精品免费一区| 草草久久久无码国产专区| 亚洲Av无码国产情品久久| 色天使久久综合网天天| 99久久精品国产麻豆| 色诱久久av| 久久综合狠狠综合久久激情 | 怡红院日本一道日本久久 | 久久久国产视频| 久久香蕉国产线看观看精品yw | 精品久久久无码人妻中文字幕| 久久久久亚洲Av无码专| 久久精品免费大片国产大片| 麻豆成人久久精品二区三区免费| 国产午夜精品理论片久久| 久久久免费精品re6| 伊人久久大香线蕉精品不卡| 久久91精品国产91久久小草| 欧美国产成人久久精品| 国产成人精品久久综合| 99麻豆久久久国产精品免费| 欧美日韩精品久久久久| 中文字幕久久亚洲一区| 久久国产精品一区| 国产农村妇女毛片精品久久| 99精品国产在热久久无毒不卡 | 人人狠狠综合久久88成人| 亚洲精品乱码久久久久久蜜桃| 精品无码久久久久久久动漫| 91精品国产91久久久久福利| 久久久精品国产sm调教网站| 色综合久久无码中文字幕| 精品国产99久久久久久麻豆| 日本精品久久久久久久久免费| 99久久99久久精品国产| 97超级碰碰碰碰久久久久| 久久精品国产72国产精福利| 精品国产一区二区三区久久蜜臀| 亚洲精品国产成人99久久|