cpp_projects/mitbbs at master ・ xqian/cpp_projects
1. 近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长 度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。（自 己觉得是�u在了这题。面试过程中一直没找到正确的思路，面试官开始试图给了一些引 导，但无奈没找到他所想的方向，后来他也有些不知道如何引导，因为他觉得除了答案 好像也无法给其它提示了。感觉就是两人都很无奈：他觉得都提示得那么明显了，你怎 么还不能想到呢，我自己也很着急，觉得某个点没想到，想到了就会简单，但到底是哪 个点呢。。。面试官也看他的code review去了 /* 【 在 novice (novice) 的大作中提到: 】 : 能说说第一题： : 1. 近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长 : 度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。 : 面试官是如何引导的吗？ 我的想法是滚动hash 比如短串是abcd 那么把它本身和误差为一个或两个char的短串的滚动hash值都算出来放到一个set里面 e.g. abcd bbcd cbcd ... zbcd aacd ... azcd 一共有26*10+45*26*26个备选的短串。 然后在长串里match就行了 hash function随便找个小的质数就ok 比如abcd ==>> a*7^4+b*7^3+c*7^2+d*7 */ 2. 设计 api 并用 mutex 实现一个读写锁。 3. 6. 用 C/C++ 的基本语言特性判断某个系统上栈的生长方向。 4. 给一堆点， 找一条线穿过最多的点 第四题： 任选两个点都能组成一条线y=ax+b，所以可以有个Pair (a,b) 然后我就弄个Map<Pair, Set<point>> ，找所有两点组合算它们的(a, b) pair, 把两 个点加到map.get(pair)中。 最后看map中所有的set谁的size最大， return这个对应的(a, b).Read full article from cpp_projects/mitbbs at master ・ xqian/cpp_projects
No comments:
Post a Comment