• <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;
            }  回復  更多評論
              

            中文字幕乱码人妻无码久久| 精品国产乱码久久久久软件| 国产99久久久国产精品~~牛| 97久久超碰国产精品旧版| 久久综合丝袜日本网| 内射无码专区久久亚洲| 久久久久亚洲AV无码网站| 精品无码久久久久久久动漫| 青青热久久国产久精品| 亚洲中文字幕无码久久精品1| 久久亚洲国产欧洲精品一| 亚洲国产视频久久| 潮喷大喷水系列无码久久精品 | 久久国产精品一国产精品金尊| 久久免费小视频| 久久亚洲美女精品国产精品| 久久久中文字幕日本| 欧美激情精品久久久久| 亚洲精品乱码久久久久久按摩| 热综合一本伊人久久精品| 国产精品99久久精品爆乳| 国产精品视频久久久| 日韩精品久久无码中文字幕| 久久久久久亚洲精品影院| 久久99精品久久久久久9蜜桃| 国产精品久久久天天影视| 亚洲国产精品无码成人片久久| 欧美久久一区二区三区| 国产精品美女久久久免费| 国产成人精品久久一区二区三区| 狠狠色丁香久久婷婷综合蜜芽五月 | 精品久久久久久中文字幕人妻最新| 久久综合九色综合久99| 久久久久久国产a免费观看不卡 | 久久久久久久91精品免费观看| 99久久免费国产精品| 亚洲国产精品久久| 国产国产成人久久精品| 久久精品成人免费观看97| 久久无码一区二区三区少妇| 欧美一级久久久久久久大|