z**********3
发帖数: 11979 | 1
就比如你这个“看到” 就是目标识别
用到KMP搜索算法
这算法是 3个老教授发明的
实现来也就 30个工程师写成库
应用起来也就找300个军方码工预制进无人机
那需要那么多人懂算法 大部分人会用就行 就像发明app算法 编写app 使用app的关系
不过你的算法人口和我一个经济领域的概念很像，叫编程人口
算法的发明和改进是稀少和缓慢的
小部分人用来做成工具
大部分人用工具来生产
这大部分人就是我说的coding population/programming population
CP/PP |
|
发帖数: 1 | 2 Where is timefall gg? Come on a... |
|
|
A********1
发帖数: 1268 | 4 扯淡把，现在刷题只是考的基础，基础就是让你写1+1=2.
你真的觉得搞算法研究的博士生不行？
人家估计觉得kmp就是很intuitive，想一想就写出来了。 |
|
c****x
发帖数: 6601 | 5 真不一定。
不妨写个KMP或paxos算法来试试，看看你一周能不能写出来。 |
|
h******k
发帖数: 810 | 6 KMP out了，用rolling hash，30分钟齐活，又快又好。 |
|
x*****n
发帖数: 3422 | 7 在广大人民为团购二房+DAC欢欣鼓舞的时候, 没品没钱的我还在用的usb外置声卡有问
题了.
型号是Creative USB Sound Blaster Audigy 2 NX SB0300
问题是随机出现的刺啦噪声, 听上去就像是老电影音轨似的,随机出现, 声音不大,但是
足够烦人的. 不播放任何声音的时候不出现
音源问题排除, mp3/ape/youtube/电影/游戏都会出现
播放器问题排除, kmp/wmp/foobar ...
耳机问题排除, 试了多个耳机/耳塞/音箱,都一样有
使用板载声卡没有出现随机刺啦噪声, 确认是audigy 2 NX的问题.
我没主意了, 大家看看有什么建议吗? |
|
s****9
发帖数: 2226 | 8 下了720p和1080i的《太平洋》，看不出差别。
以前比较过720p和1080p的同一部电影，如《色戒》，也看不出差别，哪怕在很近的距离，如1.5米。用KMP播放器软解压，甚至2部片子都暂停在有人物脸部特写的同一帧，仔细对比也看不出有差别。
有人说要60"以上的屏幕或投影才看得出差别，如果真是这样，以后只下720p的片子了，毕竟容量只有1080的1/3。
不知道大家是否有同感。
PS：发现这里是音响版，对不起。有讨论HDTV、家庭影院的版吗？ |
|
p****1
发帖数: 917 | 9 我的42寸区别很大了。我也是下载的。
try dvd player
距离，如1.5米。用KMP播放器软解压，甚至2部片子都暂停在有人物脸部特写的同一帧
，仔细对比也看不出有差别。
了，毕竟容量只有1080的1/3。 |
|
f***j
发帖数: 125 | 10 24寸显示屏上都有区别
硬解压区别大点
距离，如1.5米。用KMP播放器软解压，甚至2部片子都暂停在有人物脸部特写的同一帧
，仔细对比也看不出有差别。
了，毕竟容量只有1080的1/3。 |
|
g****n
发帖数: 3370 | 11 同意只下720P。
距离，如1.5米。用KMP播放器软解压，甚至2部片子都暂停在有人物脸部特写的同一帧
，仔细对比也看不出有差别。
了，毕竟容量只有1080的1/3。 |
|
l******o
发帖数: 1550 | 12 等离子像素边界没有lcd那么明显
距离，如1.5米。用KMP播放器软解压，甚至2部片子都暂停在有人物脸部特写的同一帧
，仔细对比也看不出有差别。
了，毕竟容量只有1080的1/3。 |
|
v****e
发帖数: 10715 | 13 主要看片源吧。区别是会有一点的，但是720P已经足够好了
距离，如1.5米。用KMP播放器软解压，甚至2部片子都暂停在有人物脸部特写的同一帧
，仔细对比也看不出有差别。
了，毕竟容量只有1080的1/3。 |
|
h********n
发帖数: 4079 | 14 都是最常见的东西, 用KMP放ape or flac, 每隔一段时间有停顿/爆音咋办?
谢谢指点 |
|
m******t
发帖数: 165 | 15 by Yahoo fiancial, KMP's dividend yield is $4.52(6.2%), but its E/P is 53
and EPS is just $1.41. how to understand its earning is much less than its
dividend? |
|
j**s
发帖数: 1028 | 16 Please recommend some funds for my portfolio. Long term for retirement.
I plan to buy some apple stock. Really want to have some good international
or world stock funds.
Any good small/mid cap/large cap stock to recommend?
Thanks indeed!
I find some - not sure how good they are: (no fee no transaction fee)
EXWAX HIINX - international
ICMAX PARSX - small cap
WTSLX DEFIX - mid cap
OAKGX - global
KMP LINE - dividend stock for long term
AAPL AMZN
I used to own MO. A good dividend stock as well.
Than... 阅读全帖 |
|
d*****1
发帖数: 1837 | 17 能展开说说什么是UBTI
holding kmp for a few years in roth ira |
|
x**l
发帖数: 64 | 18 回报本版。以下信息仅供参考。
第一轮：两个engineers，非老印老中，所以口音比较容易听懂
1、在纸上写程序 reverse a decimal number，例如输入123，输出321
trap：如果是8bit char，123的输出位321超过了127，变为负数，所以需要检查输出数
和输入数的符号位是否相同。（用bit xor检查）
2、实现char *strstr(char *sub, char *str)，就是子串匹配，返回匹配的子串地址
或者NULL。
我预先问是否要求用KMP algorithm，对方说不用，就最直接的做法。
里面没什么技巧，注意把代码写规范一些，输入参数检查,边界条件之类的。
3、general question，输入股票代码例如goog，返回股票价格，如何组织数据结构。
我先说hash，对方稍微追问了一下hash的time complexity什么时候最好，最差之类的。
然后我补充了一下还可以用binary search or binary search tree.
4，C的struct和C＋＋的struct的区别 （多4个member funct |
|
g*******y
发帖数: 1930 | 19 用? 来split不是很好吧。?在kmp预处理的时候，就当作是'?'本身，在比较str和
substr的时候，做为一个通配符。
另外，貌似题目只是问 是否存在match，不是找所有match，不需要DFS。如果找所有match，可以用DP的方法，类似于今年code jam qualification的最后一题。
token |
|
b***e
发帖数: 1419 | 20 The first case is obviously out of question, as indicated in my original
post.
The second case is nothing wrong. The kmp table would be:
a b ? d
0 -1 0 0
which result in no match in
abebcd |
|
g****s
发帖数: 16 | 21 校内的career fair。
的位置，假设subsubstr是abc,d?ef,...，用KMP在string中找到第一个abc出现的位置
，然后在c出现之后的string里继续再找d?ef的位置。。。用递归也可以做，速度慢些。
判定。
历？ 谢谢。 |
|
p*********a
发帖数: 21 | 22 Maybe KMP is enough! I wrote a program, let me know if there's any bug in it.
#include
#include
#include
#include
using namespace std;
string src, p;
vector v;
vector > next;
void KMP_init(int ix) {
next[ix].resize(v[ix].size());
next[ix][0] = -1;
int i, j;
i = 0; j = -1;
while(i
if(j==-1||v[ix][i]==v[ix][j]||v[ix][i]=='?') {
i++; j++;
if(v[ix][i]==v[ix][j]||v[ix][i]=='?')
next[ix][i] = next[ix][j];
else
next[ix][i] = j |
|
k***e
发帖数: 556 | 23 都是paper的内容 发在顶级会议和杂志上的内容
怎么能要求当场写 我看能直接写个kmp就不错了 |
|
H*M
发帖数: 1268 | 24 不是啊.我说的那个最简单的手工构建方法.
kmp其实也蛮难一次写对的... |
|
H*M
发帖数: 1268 | 25 s1: abcdefg
s2: dcbe
要你找到一个s1中的一个substring,matches s2,但是，这个substring的顺序不重要，
比如bcde also matches dcbe
KMP,和surfix tree都不可以了。
有没有什么efficient的方法？
大家讨论讨论。好象在哪看过这题。 |
|
g*******y
发帖数: 1930 | 26 很多都是老题，不过我专门整理了一下：
1. string match:
string Text, Pattern;
find a substring of Text matches with Pattern.
解法纲要：Rabin-Karp, KMP, suffix tree
变种1b: multiple match:
string Text, PatternSet[n];
find a substring of Text matches with any one pattern in the set;
解法纲要: Rabin-Karp
2.LCSubstring:
string A,B;
find the longest common consecutive substring;
解法纲要：DP(A.len*B.len复杂度)，suffix tree(A.len+B.len复杂度)
3.Longest Palindrome
string A;
find the longest substring of A which is a palindrome;
解法纲要：类似2
4.Wild |
|
m*****f
发帖数: 1243 | 27 为什么只提到KMP algorithm没有BM algorithm呢? 或者是已经包含了? |
|
m******9
发帖数: 968 | 28 这种题目好难呀，估计只有google facebook这样的可能考到 |
|
B*****t
发帖数: 335 | 29 find the longest palindrome in a string 不是么？ |
|
w******k
发帖数: 917 | 30 这个是说个suffix tree的idea
没法写code的吧 |
|
B*****t
发帖数: 335 | 31 我想面试中60%以上是考你的idea吧，尤其是电面。 |
|
|
|
c***g
发帖数: 472 | 34 我前段时间programming test 我程序就用到了prefix tree/trie |
|
h*******x
发帖数: 12808 | 35 K比如给你一个a,b两个string，判断a是否在b里面出现过。
面试遇到这样的问题，需要写KMP算法吗? |
|
B*****t
发帖数: 335 | 36 先问他题目的规模。
小规模的crossword，直接DFS就可以了。
对于比较复杂的crossword，两种方法：
1. 要先根据已知的word建一个trie，在map上每一个起始点和交点进行search，跟dfs
也差不多。
2. AC-Automation,其实就是trie上的KMP，search起来在某些情况下比trie要快一些。
还可以在它上面进行DP，不过估计面试不会被问到。
good luck！ |
|
B*****t
发帖数: 335 | 37 Robin-Carp
KMP
Sunday
BM
... |
|
S******a
发帖数: 862 | 38 ......
给包子的话我写给你
多练练25很轻松
类似的，我面试的时候20min写过KMP字符串匹配
这些经典算法我都每次面试前都会过一遍
如果是电面，我就直接翻出写过的code来贴过去 |
|
j**l
发帖数: 2911 | 39 什么KMP, Rabin-Karp, BM, Suffix Tree, Suffix Array, 能用上的请尽量用
1. Write a function f(a, b) which takes two character string arguments and
returns a string containing only the characters found in both strings in the
order of a. Write a version which is O(n^2) and one which is O(n).
2. Given that one of the strings is very very long , and the other one could
be of various sizes. Windowing will result in O(N+M) solution but could it
be better? May be NlogM or even better?
3. Given that you have one str |
|
|
I**********s
发帖数: 441 | 41 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
j***n
发帖数: 301 | 42 检查一个string是不是另外一个substring是怎么做的呢？用brute force还是KMP、BM？ |
|
|
j**l
发帖数: 2911 | 44 来自主题: JobHunting版 - AMZ面经 找出word的重复频率
是给定特定的一个单词还是所有的单词？
是考察KMP, Rabin-Karp之类的模式匹配算法还是考察Hash table? |
|
s*********t
发帖数: 1663 | 45 这是strstr()吧？
算法改成KMP算法，具体细节的去搜索一下吧，忘记了。 |
|
c******t
发帖数: 1500 | 46 strstr函数如果使用KMP的话会不会效率更高呢？
为什么楼主说不需要？ |
|
A********l
发帖数: 184 | 47 是interviewer说不需要些kmp算法，简单点就可以了
P.S.: 我比较懒，很多东西没有表述清楚。 |
|
b*****n
发帖数: 221 | 48 弯曲中型Internet related公司..连午餐共见了六个人.三个三哥.Followup很多.感觉不好.move on了.
1. permutation chars in a vector. how to deal with duplicates.
2. merge two sorted array. How to remove duplicates?
3. binary tree 的 In-order travsal. Non-recursion.
4. find number of bits in an integer. How to improve?
5. substring()的实现. KMP之外的算法.
6. 六面体喷六种不同颜色, 共有多少种组合? 可以通过旋转得到的算一种.
7. 海盗分金.
8. factory method pattern. 举例说明Facade和decorator pattern的区别.
9. 工作中遇到的architecture design问题.如何简化一个architecture?
10. 何如比较两个网页的相像程度?
11. K-mea |
|
w***g
发帖数: 5958 | 49 你还记得KMP，好牛！
候。
substring
match |
|
s*******t
发帖数: 248 | 50 一个test manager面的。
1. SDE, SDET, PM, 你选择哪个，为什么？
我说想从SDE或SDET开始，因为PM需要一些实际经验，他说make sense。
2，他问，你比较想evaluate data 还是 find pattern from data ?
我说后者
感觉前两个问题，就是看看你向往那个职位。
3，talk about the most challenging project or problem you faced before?
我简单讲了下现在做的项目，前一天晚上简单准备了一下，有个师弟昨天面的，刚好也
是这个题。
4， coding, replace the pattern from a string with 'X'.
for example replace 'abcdeffdfegabcabc',with 'XdeffdfegX', when you face
multiple abc, just replace all of them with one 'X'. like 'abcabc' with X.
因为前面的人占用了太多时间，给... 阅读全帖 |
|
