我给小刘当司机 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>bagua - 娱乐八卦

我给小刘当司机 (转载)

我给小刘当司机 (转载)# bagua - 娱乐八卦

m*i2014-01-24 08:01

1 楼

Assume you have large set of data, say more than 100,000 elements. Each data
element has a unique string associated with it.
What data structures would you use in the implementation of a single new
data structure that has all of the following properties? Explain how this
implementation works.
i) Optimal algorithmic random access time to any element knowing only the
unique string associated with it (as above)
ii) Keeps track of the order of insertion into the data structure, so you
can acquire

a*e2014-01-24 08:01

2 楼

13号scheduled，现在显示15号processed，但是信用卡还看不到，现在都16号了阿

f*r2014-01-24 08:01

3 楼

RT,父母来探亲,又想去加拿大玩.加拿大纽约领事馆网站上,说面签申请,护照只能邮寄
退回,父母担心如果护照在邮寄途中遗失,上面的美国签证也丢了.请问有没有在取签证
时顺便取回护照的?谢谢!

h*U2014-01-24 08:01

4 楼

【以下文字转载自 Dreamer 讨论区】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标题: 我给小刘当司机
发信站: BBS 未名空间站 (Fri Jan 24 17:40:03 2014, 美东)
我是千老战斗机
个子不到一米七
引体向上不会做
右手撸得已起皮
小刘妹妹身材好
常来找我当司机
虽然胸平屁股小
也不让我沾便宜
今天又要去逛mall
外边气温负十一
小雨加雪路打滑
说走就走不客气
千老哥哥别犹豫
这是妹妹看得起
握紧方向朝前看
不要偷偷竖鸡鸡
导购导游兼提包
刷卡不够我垫齐
不但要求态度好
还得不时拍马屁
“妹妹腿长腰身细
穿啥象啥真靓丽
要是什么都不穿
我给妹妹当影壁”
“妹妹皮肤好白皙
秒杀那个金发女
她们虽然波波大
出汗一股狐臭气”
“妹妹眼睛好迷离
秒杀冰冰和子怡
妹妹嘴唇自来红
兰蔻气得要倒闭”
小刘含羞把头低
“叔你真会耍嘴皮
不过不要想太多
帮我是你自愿地”
心里虽然一阵苦
脸上笑成一支菊
妹妹真会开玩笑
把叔想到哪里去
叔叔虽然想得多
肯定不敢告诉你
叔叔车上想放屁
一直憋了六站地
购物回来送到家
叔叔给你披大衣
大包小包送上楼
不经允许不进去
小刘听得好高兴
千老累得腿发硬
知道自己情商低
遇到美女没出息
正要打包往回转
碰到一个白弟弟
小刘眼睛亮出光
语调变得甜甜地
“乔吉乔吉how are you
can you teach me 学英语
这是我的手机号
this weekend you call me”
乔吉摸出小手机
this weekend 没问题
8点以后我有空
晚上你来我这里。
“外发骚货没骨气
见个白屌就湿屄
老子汽油8块半
人工也你付不起”
千老越想越生气
小刘挥手让过去
叔叔你要没有事
能否周末送我去。
千老咽下一口痰
一腔怒火便浇熄
叫我干啥我干啥
我是人民好司机。

r*u2014-01-24 08:01

5 楼

看看这样行不行，所有的elements都insert到一个array里，hash table里放element的
index。
给定一个unique string，先到hash table里找到index，再去array找到element。
另外，array是按insert顺序ordered，还可以用any index访问array里的任意元素。

data
the
the

【在 m*******i 的大作中提到】

: Assume you have large set of data, say more than 100,000 elements. Each data
: element has a unique string associated with it.
: What data structures would you use in the implementation of a single new
: data structure that has all of the following properties? Explain how this
: implementation works.
: i) Optimal algorithmic random access time to any element knowing only the
: unique string associated with it (as above)
: ii) Keeps track of the order of insertion into the data structure, so you
: can acquire

i*t2014-01-24 08:01

6 楼

你可以试试看，不过成功率不知道。
邮寄怕什么?给一个fedex的prepaid信封就好了。

【在 f**********r 的大作中提到】

: RT,父母来探亲,又想去加拿大玩.加拿大纽约领事馆网站上,说面签申请,护照只能邮寄
: 退回,父母担心如果护照在邮寄途中遗失,上面的美国签证也丢了.请问有没有在取签证
: 时顺便取回护照的?谢谢!

h*U2014-01-24 08:01

7 楼

真巧，瓜叔也在蒙面涂草

e*c2014-01-24 08:01

8 楼

LinkedHashMap

z*82014-01-24 08:01

9 楼

太后驾到？

m*i2014-01-24 08:01

10 楼

thanks! 应该是这个。不知道怎么implement的
是使用array吗？比如
MyClass* obj_ptr=new MyClass[N];
根据hash key insert to the array, 然后maintain pointer根据insert 的顺序指向
上一个insert的obj和下一个将要insert的obj?
不知道是不是这样？给解释一下吧，多谢！

【在 e********c 的大作中提到】

: LinkedHashMap

r*u2014-01-24 08:01

11 楼

hash_table 放index,
array放elements
hash_table and array are seperate.
key->(hash_table) get index, index->(array) get element.
你现在是要用俩种方式做索引，一种是用key and hash it，令一种是用array的index
，我觉得single DS只能做到用一种索引。

【在 m*******i 的大作中提到】

: thanks! 应该是这个。不知道怎么implement的
: 是使用array吗？比如
: MyClass* obj_ptr=new MyClass[N];
: 根据hash key insert to the array, 然后maintain pointer根据insert 的顺序指向
: 上一个insert的obj和下一个将要insert的obj?
: 不知道是不是这样？给解释一下吧，多谢！

e*c2014-01-24 08:01

12 楼

Map.Entry has two attributes in HashMap. With LinkedHashMap, each
node has two additional fields: before and after to form a doubly linked
list. The implementation is the same as any Hashtable but you need to update
before and after nodes accordingly upon insertion and deletion.
You can take a look at the implementation in SUN's JDK source code.

s*i2014-01-24 08:01

13 楼

赞详细解答

update

【在 e********c 的大作中提到】

: Map.Entry has two attributes in HashMap. With LinkedHashMap, each
: node has two additional fields: before and after to form a doubly linked
: list. The implementation is the same as any Hashtable but you need to update
: before and after nodes accordingly upon insertion and deletion.
: You can take a look at the implementation in SUN's JDK source code.

m*i2014-01-24 08:01

14 楼

多谢！

update

【在 e********c 的大作中提到】

b*r2014-01-24 08:01

15 楼

请问linksedHashMap对第三条怎么实现的：iii) Optimal algorithmic random access
time to any element knowing only the index of insertion.
given index, random access elem in linkedlist?

update

【在 e********c 的大作中提到】

s*i2014-01-24 08:01

16 楼

first, it's a hashmap

access

【在 b****r 的大作中提到】

: 请问linksedHashMap对第三条怎么实现的：iii) Optimal algorithmic random access
: time to any element knowing only the index of insertion.
: given index, random access elem in linkedlist?
:
: update

x*y2014-01-24 08:01

17 楼

I still don't get it....the index of the order is not the key, and then how
to use hashmap to access it in the constant time?

【在 s*****i 的大作中提到】

: first, it's a hashmap
:
: access

e*c2014-01-24 08:01

18 楼

values() will return an array of contents in the LinkedHashMap in the
insertion order. You only need to call it once and the query will be O(1)
after the first call.

x*y2014-01-24 08:01

19 楼

So, basically, LinkedHashMap realizes the 3rd property with an additional
array...
If insertion or deletion happens, we have to adjust array(call value())
again, right?

【在 e********c 的大作中提到】

: values() will return an array of contents in the LinkedHashMap in the
: insertion order. You only need to call it once and the query will be O(1)
: after the first call.

r*92014-01-24 08:01

20 楼

mark

r*92014-01-24 08:01

21 楼

mark