中午不知道吃啥的，又可以省了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

中午不知道吃啥的，又可以省了

中午不知道吃啥的，又可以省了# Joke - 肚皮舞运动

j*22012-07-12 07:07

1 楼

1. 如何设计一个 short link 生成器?
What are the keys and values in the hashtable?
2. Given an input string and an order string, e.g., "house" and "soup",
print out characters in input string according to character order in the
order string. For characters in input string but not in the order string,
output them in the end, their relative order doesn't matter. For example,
for input string "house", "souhe" and "soueh" are valid outputs.
我完全看懵了....... 这题想考什么呀? 因为我有一个很stupid的法子
Associate each char of the order string a count. Go over the input string,
populate the count field. Go over the order string, output the char count
times. Also while we go over the input string, mark a char[256] table. Then
output those that are not in the order string.
可是这出题的本意是什么呀?

G*r2012-07-12 07:07

2 楼

h*92012-07-12 07:07

3 楼

Don't understand question #1.
Question #2 seems too simple. Any trap???
String input = "house";
String order = "soup";
LinkedHashMap map = new LinkedHashMap>();
for(int i = 0; i < order.length(); i++)
{
map.put(order.charAt(i), 0);
}
for(int i = 0; i < input.length(); i++)
{
char c = input.charAt(i);
if(map.contains(c))
map.put(c, map.get(c)++);
else
map.put(c, 1);
}
for(Map.Entry entry : map)
{
for(int i = 0; i < entry.getValue(); i++)
{
System.out.print(entry.getKey());
}
}

r*e2012-07-12 07:07

4 楼

真得很灵验...应该送给减肥版的朋友们

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

: `

g*e2012-07-12 07:07

5 楼

1. why hashtable? you only need to map a unique integer to a string.

【在 j********2 的大作中提到】

: 1. 如何设计一个 short link 生成器?
: What are the keys and values in the hashtable?
: 2. Given an input string and an order string, e.g., "house" and "soup",
: print out characters in input string according to character order in the
: order string. For characters in input string but not in the order string,
: output them in the end, their relative order doesn't matter. For example,
: for input string "house", "souhe" and "soueh" are valid outputs.
: 我完全看懵了....... 这题想考什么呀? 因为我有一个很stupid的法子
: Associate each char of the order string a count. Go over the input string,
: populate the count field. Go over the order string, output the char count

B*u2012-07-12 07:07

6 楼

考，吐了一地。把标题搞得再省目点。

b*u2012-07-12 07:07

7 楼

1. long url -> hash number (key) -> short url (value)
2. put the order string into a hashtable.
traverse the input string, whenever we see a char not in the hashtable,
erase it and push it to the back of the string.

e*e2012-07-12 07:07

8 楼

Where short url (value) come from? How do you get it? I can see after
hashing long url, you can get the key. But no idea about how to calculate to
get short url (value). Thanks.

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

: 1. long url -> hash number (key) -> short url (value)
: 2. put the order string into a hashtable.
: traverse the input string, whenever we see a char not in the hashtable,
: erase it and push it to the back of the string.

b*u2012-07-12 07:07

9 楼

按照62进制把数字转成字符

to

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

: Where short url (value) come from? How do you get it? I can see after
: hashing long url, you can get the key. But no idea about how to calculate to
: get short url (value). Thanks.

e*e2012-07-12 07:07

10 楼

Thanks for the answer. It seems the key and value can be converted to each
other. So if I get either the key or the value, I can always calculate to
get the other. What's the point of putting this pair into a hashtable?
Thanks.

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

: 按照62进制把数字转成字符
:
: to

e*e2012-07-12 07:07

11 楼

for 1, I don't think hashtable is needed. The goal is to get a shortened url
. So "long url -> hash number -> (62进制把数字转成字符)short url" is good
enough.

【在 j********2 的大作中提到】

g*y2012-07-12 07:07

12 楼

第二题，只需要把第一个string中的数字map到第二个string的order就好了。
def reorder(str, order_str):
d = {c:i for i, c in enumerate(order_str)}
str = [c for c in str]
def get_key(c):
if c in d:
return d[c]
else:
return len(d)
str.sort(key=get_key)
return "".join(str)

b*u2012-07-12 07:07

13 楼

还是有区别吧，
hash值如果不能保证unique，就会出现几个长地址对同一个短地址，这时候需要
hashtable解决collision
不过这样一想 hash表的值就应该是长地址而非短地址，这样重复的长地址进行查询就
不会当作collision来弄

url

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

: for 1, I don't think hashtable is needed. The goal is to get a shortened url
: . So "long url -> hash number -> (62进制把数字转成字符)short url" is good
: enough.

c*t2012-07-12 07:07

14 楼

弱问为什么是62进制,是因为url可用的字符一共有62个吗？26字母大小写+10数字？那
符号为何不能用在short link？

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

: 按照62进制把数字转成字符
:
: to

g*e2012-07-12 07:07

15 楼

hash个啥。直接auto increment id就行了。当然了，getUniqueId本身就是一道高深的
设计题。我们可以从mysql(或其他RDBMS)的auto increment id开始。

g*y2012-07-12 07:07

16 楼

那取地址的时候就麻烦了，需要scan。

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

: hash个啥。直接auto increment id就行了。当然了，getUniqueId本身就是一道高深的
: 设计题。我们可以从mysql(或其他RDBMS)的auto increment id开始。

g*y2012-07-12 07:07

17 楼

A-Za-z0-9

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

: 弱问为什么是62进制,是因为url可用的字符一共有62个吗？26字母大小写+10数字？那
: 符号为何不能用在short link？

g*e2012-07-12 07:07

18 楼

为什么要scan？ short url直接转换成ID， select url from Table where id = "$id"

【在 g****y 的大作中提到】

: 那取地址的时候就麻烦了，需要scan。

l*a2012-07-12 07:07

19 楼

The short url has to be unique, so the short url can be used as key. The
long url will be used as value.
The reason to use short url as key but not auto increment id is to prevent
ppl from getting the long url by brute force.
How to generate unique short url can be the follow up question.

c*t2012-07-12 07:07

20 楼

hashcode 和short link都不是唯一啊，怎么做key?

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

: 还是有区别吧，
: hash值如果不能保证unique，就会出现几个长地址对同一个短地址，这时候需要
: hashtable解决collision
: 不过这样一想 hash表的值就应该是长地址而非短地址，这样重复的长地址进行查询就
: 不会当作collision来弄
:
: url

g*y2012-07-12 07:07

21 楼

转晕了。对的，直接取就好了。不需要scan。

id"

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

: 为什么要scan？ short url直接转换成ID， select url from Table where id = "$id"

c*t2012-07-12 07:07

22 楼

同意。

【在 l*****a 的大作中提到】

: The short url has to be unique, so the short url can be used as key. The
: long url will be used as value.
: The reason to use short url as key but not auto increment id is to prevent
: ppl from getting the long url by brute force.
: How to generate unique short url can be the follow up question.

m*f2012-07-12 07:07

23 楼

进来学习

【在 j********2 的大作中提到】

s*62012-07-12 07:07

24 楼

如何设计一个 short link 生成器?
--直接放数据库存着,然后靠id取出来,这样难道不行吗?

g*e2012-07-12 07:07

25 楼

这个题目不问hash func怎么设计？62进制很容易overflow的，原url长一点就挂了

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

: 同意。

g*e2012-07-12 07:07

26 楼

跟url本身没关系

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

: 这个题目不问hash func怎么设计？62进制很容易overflow的，原url长一点就挂了

p*22012-07-12 07:07

27 楼

同意。

【在 l*****a 的大作中提到】

p*22012-07-12 07:07

28 楼

第一题
encrypt(hash(long url))
第二题，类似count sort

g*e2012-07-12 07:07

29 楼

前面不是在讨论用62进制做hash func么？可能我理解错了。方便展开讲讲么？多谢

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

: 跟url本身没关系

g*e2012-07-12 07:07

30 楼

可以用URL的一部分，比如最后一段加一个unique number一起做hash。返回url: http://tiny.url/part_of_url/base_62_hash
俺们公司内部的tiny url应该就是这么搞的，我猜的，不负责

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

: 前面不是在讨论用62进制做hash func么？可能我理解错了。方便展开讲讲么？多谢

c*t2012-07-12 07:07

31 楼

好像靠谱，
问一下这样的话，原问题“hashtable里的key和value"存什么，是什么答案？

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

: 可以用URL的一部分，比如最后一段加一个unique number一起做hash。返回url: http://tiny.url/part_of_url/base_62_hash
: 俺们公司内部的tiny url应该就是这么搞的，我猜的，不负责