感觉WASM会让JS成为新python - 未名空间MITBBS历史存档

s*t2018-08-09 07:08

1 楼

刚刚面的电面，心里没底啊。
1. Given a sorted integer array and a specific integer, find the
first position of that integer. Array contains lots of
duplicate.
我说用binary search，找到之后然后左移找到第一个于它前一个不一样的，就是
first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
多一次binary search，用一些边界条件什么的判断。这样算不算改进啊，我觉得应
该是会快点啊。
2. 有很多doc，里面有很多电话，怎么查找电话。
我说只是一次用的，hash一下找，如果以后还得用的话，就sort他们，然后按area
code做一个B tree什么的。
3. 在一个resume里面找电话。
我说如果是US的话找一个连续是10个digit的，或者中间有（）或-的，然后查头三个
digits是不是va

G*f2018-08-09 07:08

2 楼

时间追到几个月之前的一个新入职的员工身上，作为老员工我在他眼里大概有那么点神
秘的成就光环，偌大的一个工作室小了说有50号人，我坐在外企的副手位置上，让他错
误的以为我是一个什么样子的成功人士。
成功人士在他的眼里大概有以下几点：
追求完美
追求更高的要求的完美
追求极致的完美还得要低成本低人工高产出高效能的完美
然而我只是因为投资了所以挂个名在这里领取我的分红而已。然而小哥儿开始没完没了
的找我确认工作，为其名曰的学习，其实在套话
我什么时候能跟你一样啊
我要是完美到什么点才能到你这样啊
好羡慕你啊
你是移民的吗？全家都在这里吗？占便宜呀。
年轻人话多管不住嘴我理解，但积极主动的往上从我就大体上不太理解了。一开始我还
能老老实实的回答问题，后来我觉得他有点急红眼了，毕竟做的东西也差强人意，看得
出来是刚刚毕业的天马行空但脚没有落地又追求所谓的完美的类型。
我跟他好好的谈过
但那会儿他大概已经把我当做是阶级敌人，反动派了。坐在我对面把我当重洋内外的外
国狗了。至此我再也没有和他好好说过话。他就离职了。
其实，年轻的时候何必着急去追求任何完美或者别人？我觉得那都是在给自己的嫉妒心
找借口。何必非要去给自己树一个敌人，人人皆负责自己而已，何苦为难自己呢？

m*s2018-08-09 07:08

3 楼

买了被银行从户主收回的房子，听说过户很麻烦。有经验的来说说注意事项

Y*22018-08-09 07:08

4 楼

我看过一些美国所谓的两性学家写的恋爱的书比如"Why Men Marry Bitches" 和"Why
Men Love Bitches". 也听过一些专家的演讲比如"How to find your soulmate", "How
to meet the love of your life". 然后又看了一些中国，韩国的恋爱专家和女性专
家写的书比如那本韩国的“二十岁的女人必须看得书“。我觉得中西方恋爱文化的差异
很大。
西方的观点：
女性必须要认识到自己想要什么样的人，什么样的生活。 Women are in power when
it comes to dating. Women have the full control.
东方的观点：
女性一定要现实，不要幻想。
西方的观点：
Women are beautiful no matter what color, what age, what type, what weight,
what height as long as women are confident. Men are looking for women who
ar

n*72018-08-09 07:08

5 楼

有了WASM，啥语言库（C/C++/Rust/C#/Go)都可以转成WASM给JS直接用
JS也能直接写WASM了
超NB啊
本来JS就够火，这下还要抢python的地盘了

g*y2018-08-09 07:08

6 楼

1. preprocessing the array to get an array of pair
4. also preprocessing the dictionary.

l*k2018-08-09 07:08

7 楼

TITLE在银行那里
买房不就是TITLE从一个银行转到另一个银行吗？
没觉得什么麻烦的。AGENT和LOAN OFFICER都自己搞定了。
自己只要把贷款那点事弄明白，INSPECTION做仔细，CLOSING COST各项查阅清楚就行了。

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

: 买了被银行从户主收回的房子，听说过户很麻烦。有经验的来说说注意事项

f*e2018-08-09 07:08

8 楼

I think both have their own merits.
For example, everyone needs to survive in reality so it's good to set
realistic expectations, and it does not conflict with pursuing a woman's own
dreams and lifestyle.
Second paragraph have different interpretation of "beauty." Not all women
are created equal and pretty ones will be lucky in many aspects of life.
However, from personal fullfillment point of view, if a woman is not pretty,
but confident in her life, she at least has herself. If a woman is not

n*p2018-08-09 07:08

9 楼

还是frontend, 怎么抢Python地盘？

h*k2018-08-09 07:08

10 楼

duplicate的值形成一个list？

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

: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.

m*s2018-08-09 07:08

11 楼

3x a million!

了。

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

: TITLE在银行那里
: 买房不就是TITLE从一个银行转到另一个银行吗？
: 没觉得什么麻烦的。AGENT和LOAN OFFICER都自己搞定了。
: 自己只要把贷款那点事弄明白，INSPECTION做仔细，CLOSING COST各项查阅清楚就行了。

Y*22018-08-09 07:08

12 楼

mm说的很好，谢谢

own
pretty,

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

: I think both have their own merits.
: For example, everyone needs to survive in reality so it's good to set
: realistic expectations, and it does not conflict with pursuing a woman's own
: dreams and lifestyle.
: Second paragraph have different interpretation of "beauty." Not all women
: are created equal and pretty ones will be lucky in many aspects of life.
: However, from personal fullfillment point of view, if a woman is not pretty,
: but confident in her life, she at least has herself. If a woman is not

m*n2018-08-09 07:08

13 楼

有竞争是好事
让各语言使出浑身解数
码农的工作越来越轻松了

g*y2018-08-09 07:08

14 楼

hehe, I realized no need to build a bst(I was thinking about something else.
..), just preprocess to get：
vector>
where first int is the data, second int is the first occurrence index(
position)

【在 h**k 的大作中提到】

:
: duplicate的值形成一个list？

m*s2018-08-09 07:08

15 楼

Buyer's Title Insurance
Buyer's Title Insurance, also known as an Owner's Policy or Fee Policy,
protects the new owner of the property from the "history" of the property
during the duration of their ownership, whether it be 1 year or 100 years.
Since title insurance is underwritten "at the table" by the agency, it is
the least likely type of insurance to receive a claim.
The new owner is protected against previous mortgages, owners, judgments,
etc. that are of public record prior to the purchase

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

: TITLE在银行那里
: 买房不就是TITLE从一个银行转到另一个银行吗？
: 没觉得什么麻烦的。AGENT和LOAN OFFICER都自己搞定了。
: 自己只要把贷款那点事弄明白，INSPECTION做仔细，CLOSING COST各项查阅清楚就行了。

v*a2018-08-09 07:08

16 楼

觉得你总结得挺好的
韩国的那个女人写的书我也看过，不错
我想这两个能结合起来运用自如就是要追求的境界吧
不一定非得对立起来看

How

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

: 我看过一些美国所谓的两性学家写的恋爱的书比如"Why Men Marry Bitches" 和"Why
: Men Love Bitches". 也听过一些专家的演讲比如"How to find your soulmate", "How
: to meet the love of your life". 然后又看了一些中国，韩国的恋爱专家和女性专
: 家写的书比如那本韩国的“二十岁的女人必须看得书“。我觉得中西方恋爱文化的差异
: 很大。
: 西方的观点：
: 女性必须要认识到自己想要什么样的人，什么样的生活。 Women are in power when
: it comes to dating. Women have the full control.
: 东方的观点：
: 女性一定要现实，不要幻想。

b*s2018-08-09 07:08

17 楼

做在线应用简单了
比如做个科学计算的
打开浏览器即用，没有任何本地的计算bottleneck

【在 n***p 的大作中提到】

: 还是frontend, 怎么抢Python地盘？

g*y2018-08-09 07:08

18 楼

btw,楼主说的
“我说用binary search，找到之后然后左移找到第一个于它前一个不一样的”
这个是完全没必要的，完全可以调整搜索条件搜索到想找的位置，你这个一个一个的移
，可能是消耗线性的时间

else.

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

: hehe, I realized no need to build a bst(I was thinking about something else.
: ..), just preprocess to get：
: vector>
: where first int is the data, second int is the first occurrence index(
: position)

n*d2018-08-09 07:08

19 楼

Wow! It's a pretty good point you made. In fact, women educated in both
countries of China and the U.S. will find more effective ways to pursue a
happy life and make their dreams come true.

own
pretty,

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

: I think both have their own merits.
: For example, everyone needs to survive in reality so it's good to set
: realistic expectations, and it does not conflict with pursuing a woman's own
: dreams and lifestyle.
: Second paragraph have different interpretation of "beauty." Not all women
: are created equal and pretty ones will be lucky in many aspects of life.
: However, from personal fullfillment point of view, if a woman is not pretty,
: but confident in her life, she at least has herself. If a woman is not

m*n2018-08-09 07:08

20 楼

网络软件是趋势
我深深的为Python这种沉浸在小作坊不能自拔的格局而担忧啊！
三条腿
网络后端
客户前端
内容
目前python只做好了两个

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

: 做在线应用简单了
: 比如做个科学计算的
: 打开浏览器即用，没有任何本地的计算bottleneck

m*y2018-08-09 07:08

21 楼

index>
In case no preprocessing, if find the key, store current index and keep
searching to the left until reach the leaf. If finds other keys, update
current index. This is O(logn)
How to preprocess? thanks

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

: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.

t*y2018-08-09 07:08

22 楼

没什么大区别。不同的表述而已，基本上一个意思。
什么叫“女性必须要认识到自己想要什么样的人，什么样的生活。”？就是说“要现实
，不要幻想。”
为什么女人自信就解决一切了？后面你写了因为（西方）男人喜欢这样的。
为什么女人要小鸟依人？后面你写了因为（东方）男人喜欢。
总的来说，就是看男人喜欢什么了。目的都是一个，投其所好，让男人求婚。
具体操作，因人而异。西方男人也有喜欢小鸟依人的，东方也有喜欢独立的。

How

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

: 我看过一些美国所谓的两性学家写的恋爱的书比如"Why Men Marry Bitches" 和"Why
: Men Love Bitches". 也听过一些专家的演讲比如"How to find your soulmate", "How
: to meet the love of your life". 然后又看了一些中国，韩国的恋爱专家和女性专
: 家写的书比如那本韩国的“二十岁的女人必须看得书“。我觉得中西方恋爱文化的差异
: 很大。
: 西方的观点：
: 女性必须要认识到自己想要什么样的人，什么样的生活。 Women are in power when
: it comes to dating. Women have the full control.
: 东方的观点：
: 女性一定要现实，不要幻想。

T*x2018-08-09 07:08

23 楼

Python的代码缩进是不是不适合网络传输？

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

: 网络软件是趋势
: 我深深的为Python这种沉浸在小作坊不能自拔的格局而担忧啊！
: 三条腿
: 网络后端
: 客户前端
: 内容
: 目前python只做好了两个

g*y2018-08-09 07:08

24 楼

不做preprocessing就是一个普通的binary search，没啥好多讲的了，只是楼主一个一个左移的方法太差了，他面试官才问他怎么优化的。

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

:
: index>
: In case no preprocessing, if find the key, store current index and keep
: searching to the left until reach the leaf. If finds other keys, update
: current index. This is O(logn)
: How to preprocess? thanks

c*v2018-08-09 07:08

25 楼

从理论上这样讲没有错。
但是如果你要用wasm做数值计算，那开源社区10年时间可以把相关的函数接口，名字，
文档，。。。弄好吗？
很难预测各路人马互相乱搞，需要多少时间settle down

【在 n******7 的大作中提到】

: 有了WASM，啥语言库（C/C++/Rust/C#/Go)都可以转成WASM给JS直接用
: JS也能直接写WASM了
: 超NB啊
: 本来JS就够火，这下还要抢python的地盘了

m*y2018-08-09 07:08

26 楼

嗯，不过面试应该从易到难吧，第一题应该不难
第四题怎样preprocess？按数字查询的B-tree？
Thanks LZ for posting, bless

一个左移
的方法太差了，他面试官才问他怎么优化的。

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

: 不做preprocessing就是一个普通的binary search，没啥好多讲的了，只是楼主一个一个左移的方法太差了，他面试官才问他怎么优化的。

l*m2018-08-09 07:08

27 楼

这是个大问题

【在 T*******x 的大作中提到】

: Python的代码缩进是不是不适合网络传输？

r*o2018-08-09 07:08

28 楼

第3题是考算法吗，还是regular expression?

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

: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search，找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。

v*r2018-08-09 07:08

29 楼

代码缩进和网络传输有关系吗？

w*r2018-08-09 07:08

30 楼

电话是那种字母表示的怎么办?

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

: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search，找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。

N*n2018-08-09 07:08

31 楼

说反了吧？本来在前端不得不捏着鼻子写JS。有了WASM各种语言可以跳过JS直接
生成WASM，连PYTHON理论上也可以。是JS丢了地盘。

【在 n******7 的大作中提到】

: 有了WASM，啥语言库（C/C++/Rust/C#/Go)都可以转成WASM给JS直接用
: JS也能直接写WASM了
: 超NB啊
: 本来JS就够火，这下还要抢python的地盘了

r*o2018-08-09 07:08

32 楼

preprocessing这一步的的复杂度是不是O(n)？
考官是不是要O(lgn)的复杂度？

一个左移的方法太差了，他面试官才问他怎么优化的。

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

: 不做preprocessing就是一个普通的binary search，没啥好多讲的了，只是楼主一个一个左移的方法太差了，他面试官才问他怎么优化的。

c*g2018-08-09 07:08

33 楼

JavaScript这样糟糕的语言变得这么火真是历史的倒退。

g*y2018-08-09 07:08

34 楼

预处理在于一个预字上

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

: preprocessing这一步的的复杂度是不是O(n)？
: 考官是不是要O(lgn)的复杂度？
:
: 一个左移的方法太差了，他面试官才问他怎么优化的。

T*x2018-08-09 07:08

35 楼

这个不清楚。
比如在html里面用script tag嵌入一段python代码，这样能行吗？

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

: 代码缩进和网络传输有关系吗？

r*o2018-08-09 07:08

36 楼

就是说为了方便后面的处理，预处理可以复杂度很高?

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

: 预处理在于一个预字上

g*y2018-08-09 07:08

37 楼

一般预处理的目的是这个，
不过这个题的情况下，预处理也提高不了太多。

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

: 就是说为了方便后面的处理，预处理可以复杂度很高?

g*y2018-08-09 07:08

38 楼

其实第四题也是我电面遇到的题，一模一样的。

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

: 嗯，不过面试应该从易到难吧，第一题应该不难
: 第四题怎样preprocess？按数字查询的B-tree？
: Thanks LZ for posting, bless
:
: 一个左移
: 的方法太差了，他面试官才问他怎么优化的。

s*i2018-08-09 07:08

39 楼

预处理是把字典的词转换成数字，然后sort
binary search找给定的要查找的数

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

: 其实第四题也是我电面遇到的题，一模一样的。

c*s2018-08-09 07:08

40 楼

第四题就是把字典里面的单词都用2～9来表示，然后存下来，可以提高直接查找。
还有没有什么更好的方法？

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

: 其实第四题也是我电面遇到的题，一模一样的。

g*y2018-08-09 07:08

41 楼

why sort？
what's the benefit if you sort?
can you do something other than sort?

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

: 预处理是把字典的词转换成数字，然后sort
: binary search找给定的要查找的数

m*u2018-08-09 07:08

42 楼

第一题如果中数与目标数相等，当大于处理就行了吧

r*o2018-08-09 07:08

43 楼

hash?

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

: why sort？
: what's the benefit if you sort?
: can you do something other than sort?

r*o2018-08-09 07:08

44 楼

顶一下。

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

: 第3题是考算法吗，还是regular expression?

s*i2018-08-09 07:08

45 楼

为啥不sort，你可以指点一下我嘛，不要这么凶谢谢
还有一个办法是把字典做成trie map，DFS

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

: why sort？
: what's the benefit if you sort?
: can you do something other than sort?

w*k2018-08-09 07:08

46 楼

你sort怎么弄？
最后找到1256这个是一个word,你怎么返回build word?

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

: 为啥不sort，你可以指点一下我嘛，不要这么凶谢谢
: 还有一个办法是把字典做成trie map，DFS

g*y2018-08-09 07:08

47 楼

我是学面试官的口吻向你提问

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

: 为啥不sort，你可以指点一下我嘛，不要这么凶谢谢
: 还有一个办法是把字典做成trie map，DFS

w*k2018-08-09 07:08

48 楼

in an A3 way

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

: 我是学面试官的口吻向你提问

B*t2018-08-09 07:08

49 楼

1. 这题比较无聊。不过如果知道expected number of duplicate k(>4)的话，二分找
到后每次跳k/2，k/4...步找first position。
好像可以预处理，搞个hash岂不很快？
谁有不预处理更快一些的方法？
2. 觉得没有必要sort，同一个电话号码可能出现在几个不同的doc中，预处理的话，
对每个doc设计一个相同的hash函数，能节省一些search的时间。不知道还有没有更好
的办法。
3. 好像也是比较无聊的题。
4. 这种题一般来说字典里的word的数目是一定的。可以构造一个trie，检查一个数的
valid就是检查这个trie中有没有valid 的path。不知道还有什么更好的方法。

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

: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search，找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。

g*y2018-08-09 07:08

50 楼

你准备面试的时候，难道都不假定面试官都是刁难你的？我以前就说过，做题后要不停
的继续思考为什么这么做，有没有其他的方法，不要以为做出一个题目就好了。准备面
试的目的就是不停的用题目去扩展自己的思路，磨炼自己的头脑。你事先准备的充分了
，面试的时候遇到面试官换着花样问，你也就不怕不会呆在那里发愣了。
这种问了一个问题后不停的问why，what else can you think of的例子太多了，跟阿
三没关系

【在 w******k 的大作中提到】

: in an A3 way

w*k2018-08-09 07:08

51 楼

第一题我觉得你们想复杂了
考官说如果很多很多重复，明显就是针对lz说的传统binary search加向前线形，这样可
能o(n),只要稍微修改算法，如果mid is equal就search前半部分（同理如果找最后一个
occurence就找后半部分）
我觉得interviewer的意图就这么简单

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

: 1. 这题比较无聊。不过如果知道expected number of duplicate k(>4)的话，二分找
: 到后每次跳k/2，k/4...步找first position。
: 好像可以预处理，搞个hash岂不很快？
: 谁有不预处理更快一些的方法？
: 2. 觉得没有必要sort，同一个电话号码可能出现在几个不同的doc中，预处理的话，
: 对每个doc设计一个相同的hash函数，能节省一些search的时间。不知道还有没有更好
: 的办法。
: 3. 好像也是比较无聊的题。
: 4. 这种题一般来说字典里的word的数目是一定的。可以构造一个trie，检查一个数的
: valid就是检查这个trie中有没有valid 的path。不知道还有什么更好的方法。

s*i2018-08-09 07:08

52 楼

1256是个key，后面带一个数组存着所有符合条件的单词
这个主要就是预处理了，用hash也可以

【在 w******k 的大作中提到】

: 你sort怎么弄？
: 最后找到1256这个是一个word,你怎么返回build word?

w*k2018-08-09 07:08

53 楼

开玩笑的啦
这种穷追猛打的面试，一般公司都这样的呵呵
你说的很有效

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

: 你准备面试的时候，难道都不假定面试官都是刁难你的？我以前就说过，做题后要不停
: 的继续思考为什么这么做，有没有其他的方法，不要以为做出一个题目就好了。准备面
: 试的目的就是不停的用题目去扩展自己的思路，磨炼自己的头脑。你事先准备的充分了
: ，面试的时候遇到面试官换着花样问，你也就不怕不会呆在那里发愣了。
: 这种问了一个问题后不停的问why，what else can you think of的例子太多了，跟阿
: 三没关系

g*y2018-08-09 07:08

54 楼

right

样可
一个

【在 w******k 的大作中提到】

: 第一题我觉得你们想复杂了
: 考官说如果很多很多重复，明显就是针对lz说的传统binary search加向前线形，这样可
: 能o(n),只要稍微修改算法，如果mid is equal就search前半部分（同理如果找最后一个
: occurence就找后半部分）
: 我觉得interviewer的意图就这么简单

s*t2018-08-09 07:08

55 楼

preprocessing 不是也要花时间吗？你是说做linear的然后把每个的第一个存起来
啊？
但是他好像没有要求多次使用啊，只是说找一个数的第一个，所有后来改了个两次
binary
search啊。linear 一个一个的记录的话不是要用o（n）吗？

个一个左移的方法太差了，他面试官才问他怎么优化的。

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

: 不做preprocessing就是一个普通的binary search，没啥好多讲的了，只是楼主一个一个左移的方法太差了，他面试官才问他怎么优化的。

w*k2018-08-09 07:08

56 楼

u only need one round of binary search

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

: preprocessing 不是也要花时间吗？你是说做linear的然后把每个的第一个存起来
: 啊？
: 但是他好像没有要求多次使用啊，只是说找一个数的第一个，所有后来改了个两次
: binary
: search啊。linear 一个一个的记录的话不是要用o（n）吗？
:
: 个一个左移的方法太差了，他面试官才问他怎么优化的。

g*y2018-08-09 07:08

57 楼

your concern is right, whether or not to use preprocessing is determined by:
the performance boost + processing cost + how many queries in the future
by the way, as already explained in previous posts, there's no need to do
binary search twice.

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

: preprocessing 不是也要花时间吗？你是说做linear的然后把每个的第一个存起来
: 啊？
: 但是他好像没有要求多次使用啊，只是说找一个数的第一个，所有后来改了个两次
: binary
: search啊。linear 一个一个的记录的话不是要用o（n）吗？
:
: 个一个左移的方法太差了，他面试官才问他怎么优化的。

P*i2018-08-09 07:08

58 楼

第一个，找x-0.5，只剩两个数时判断一下

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

: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search，找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。

k*e2018-08-09 07:08

59 楼

终于可以鄙视下小羊了哈哈
exactly the same problem in programming pearls, binary search chapter
note that, we need to keep loop invariant [l,r) such that a[l]<= wantedstop when l = r - 1

index>

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

: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.

h*x2018-08-09 07:08

60 楼

大赞，//bless

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

: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search，找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。

g*y2018-08-09 07:08

61 楼

汗，晕，我知道这个啊

r]

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

: 终于可以鄙视下小羊了哈哈
: exactly the same problem in programming pearls, binary search chapter
: note that, we need to keep loop invariant [l,r) such that a[l]<= wanted: stop when l = r - 1
:
: index>

s*f2018-08-09 07:08

62 楼

1如果preprocess不就O(n)了.

index>

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

: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.

r*o2018-08-09 07:08

63 楼

这个第3题是不是考regular expression啊？还是考算法的？

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

: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search，找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。

h*x2018-08-09 07:08

64 楼

suffix tree?

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

: hash?

h*x2018-08-09 07:08

65 楼

第一个都是整数的话，这样做如何？
比如要a，我就去查找a-0.5。bsearch找到第一个比a-0.5大的数，对比一下就好了，这
样就是o（logn）了。

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

: 1. 这题比较无聊。不过如果知道expected number of duplicate k(>4)的话，二分找
: 到后每次跳k/2，k/4...步找first position。
: 好像可以预处理，搞个hash岂不很快？
: 谁有不预处理更快一些的方法？
: 2. 觉得没有必要sort，同一个电话号码可能出现在几个不同的doc中，预处理的话，
: 对每个doc设计一个相同的hash函数，能节省一些search的时间。不知道还有没有更好
: 的办法。
: 3. 好像也是比较无聊的题。
: 4. 这种题一般来说字典里的word的数目是一定的。可以构造一个trie，检查一个数的
: valid就是检查这个trie中有没有valid 的path。不知道还有什么更好的方法。

d*a2018-08-09 07:08

66 楼

For the second problem, maybe we should also consider the number and size of
files. when I meet the problems about finding sth in files, I might say
mergesort (external sorting)first. Because the memory may not contain the
whole hash table. If the interviewer has performance requirement, I will
think some other solution such as hash.

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

: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search，找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。

i*b2018-08-09 07:08

67 楼

I don't think sorting is needed. The numbers converted from letters are
naturally sorted.
I'm thinking if some other utilities can be provided by the dictionary, such
as get the set of words that have the
same length.
No chinese input. sorry.

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

: why sort？
: what's the benefit if you sort?
: can you do something other than sort?

a*o2018-08-09 07:08

68 楼

我怎么觉得第一题是不是想多了? 面试官是不是只是意在优化第二步:一步一步左移?
继续用二叉查找直到找到左边数字不同了就行了吧?
脑子浆糊, 见笑了-----

b*72018-08-09 07:08

69 楼

哈，第一题不用preProcessing, 因为preProcessing 已经是O(n)了。
Programming Perl上有原题，就是把loop的invariant condition 改了，这样
O(log N) 就一定能找到第一次出现的位置。
invariant:
given range A[U, L], query integer t, A[U]剩两个数的时候，A[L]就是t 第一次出现的位置，或者t不在range中。

occurence index>

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

: 1. preprocessing the array to get an array of pair
: 4. also preprocessing the dictionary.

b*72018-08-09 07:08

70 楼

哈哈，被你抢先一步了，正解！

chapter
wanted
【在 k***e 的大作中提到】

: 终于可以鄙视下小羊了哈哈
: exactly the same problem in programming pearls, binary search chapter
: note that, we need to keep loop invariant [l,r) such that a[l]<= wanted: stop when l = r - 1
:
: index>

r*o2018-08-09 07:08

71 楼

geniusxys has mentioned before that the preprocessing is a good option in
some cases even if it needs more time, because it saves the time of the
following operations.

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

: 哈哈，被你抢先一步了，正解！
:
: chapter
: wanted

v*s2018-08-09 07:08

72 楼

aglee

【在 w******k 的大作中提到】

: in an A3 way

v*s2018-08-09 07:08

73 楼

i vote for trie in problem 4 as well

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

: 1. 这题比较无聊。不过如果知道expected number of duplicate k(>4)的话，二分找
: 到后每次跳k/2，k/4...步找first position。
: 好像可以预处理，搞个hash岂不很快？
: 谁有不预处理更快一些的方法？
: 2. 觉得没有必要sort，同一个电话号码可能出现在几个不同的doc中，预处理的话，
: 对每个doc设计一个相同的hash函数，能节省一些search的时间。不知道还有没有更好
: 的办法。
: 3. 好像也是比较无聊的题。
: 4. 这种题一般来说字典里的word的数目是一定的。可以构造一个trie，检查一个数的
: valid就是检查这个trie中有没有valid 的path。不知道还有什么更好的方法。

k*s2018-08-09 07:08

74 楼

第一题很简单吧。我就用java的binary search大概写了一下，3行code
public int FindFirstInteger(double[] arr,int i) {
double x = i - 0.1;
int ret = Arrays.binarySearch(arr,x);
return -(ret+1);
}

b*72018-08-09 07:08

75 楼

Of course preprocessing is good. but if it's allowed for every
questions, and in any extend, then there is no need for algorithm
design. :>
just preprocess everything, and make a hashtable with answer>, then every query will be answered in O(1).

option in
of the

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

: geniusxys has mentioned before that the preprocessing is a good option in
: some cases even if it needs more time, because it saves the time of the
: following operations.

q*u2018-08-09 07:08

76 楼

我记得原来有一个帖子，说是成倍的或者指数型倍的向前或者向后跳跃，来搞这种大量
重复元素的数组。
1, 2, 4, 8, 16的跳或者1, 2, 4, 16, 256的跳，
具体怎么写出代码倒是忘了，是不是这样，先binarysearch, 二分的时候，从那个二分
的点开始向前（给定数小于等于的情况），或者向后（给定数大于的情况），然后跳跃？
比如我给定找第一个４，有这么个数组
1, 1, 1, 1,... 1, 2, 2, 2,...2, 3, 3, 3 .... 3, 4444444, 5, 5, 5, ...5, 6, 6
, 6, 6, 6... 6
如果是这样，光是二分，然后外加<=的时候就向前半部分找，丢弃后半部分，这么搞是
不是还是可以再用这个跳跃的办法改进？　每次对半分的时候都对那个对半的点做跳跃？

Of course preprocessing is good. but if it's allowed for every
questions, and in any extend, then there is no need for algorithm
design.

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

: Of course preprocessing is good. but if it's allowed for every
: questions, and in any extend, then there is no need for algorithm
: design. :>
: just preprocess everything, and make a hashtable with : answer>, then every query will be answered in O(1).
:
: option in
: of the

m*g2018-08-09 07:08

77 楼

1. Modify binary search. when u don't find one, find one. when u find one,
check if it is already first occurrence. if not, look for left half.
2. sounds like unix command?
3. sounds open question?
4. for a lot of digits, the possible permutations may be big
maybe preprocessing dict, convert words into numbers, then search for hit in
the orig digits?

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

: 刚刚面的电面，心里没底啊。
: 1. Given a sorted integer array and a specific integer, find the
: first position of that integer. Array contains lots of
: duplicate.
: 我说用binary search，找到之后然后左移找到第一个于它前一个不一样的，就是
: first position。然后他说如果有很多很多的duplicate的话，有没有更快的方
: 法。然后我就想先binary search找到了middle之后，再在left和middle之间进行
: 多一次binary search，用一些边界条件什么的判断。这样算不算改进啊，我觉得应
: 该是会快点啊。
: 2. 有很多doc，里面有很多电话，怎么查找电话。

f*g2018-08-09 07:08

78 楼

1. 原题：PP P93
2. 如果没有理解错的话, PP, 第一章
3. 貌似Open Question
4. 好像是PIE原题。

l*a2018-08-09 07:08

79 楼

for 4,
if only need to care the unique number which the interviewer gave,
(ordered digits) that is the issue in PIE.
if the interviewer just gave a collection of digits, ask the words
they can combined, need pre-processing

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

: 1. 原题：PP P93
: 2. 如果没有理解错的话, PP, 第一章
: 3. 貌似Open Question
: 4. 好像是PIE原题。

P*l2018-08-09 07:08

80 楼

Depends.
suppose there are 1,000 words in the dictionary.
If the telephone number is only 3 digits, you can transform the numbers into
words and lookup the dictionary
to see if it is there. Because there are only 3**3 = 27 kinds of combination
. no pre prcessing needed.
If the telephone is 10 digits, the corresponding space of words is too large
. you have to invert index the
dictionary by telephone numbers. Build a suffix tree and you can directly
lookup the numbers.

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

: 第四题就是把字典里面的单词都用2～9来表示，然后存下来，可以提高直接查找。
: 还有没有什么更好的方法？

P*l2018-08-09 07:08

81 楼

binary search find the number 1 less than the value, return the position.
Check if arr[position+1] is the value.
Or just change the invariant condition. simple.

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

: 哈，第一题不用preProcessing, 因为preProcessing 已经是O(n)了。
: Programming Perl上有原题，就是把loop的invariant condition 改了，这样
: O(log N) 就一定能找到第一次出现的位置。
: invariant:
: given range A[U, L], query integer t, A[U]: 剩两个数的时候，A[L]就是t 第一次出现的位置，或者t不在range中。
:
: occurence index>