b****r
发帖数: 1272 | 1 来自主题: JobHunting版 - 一道MS题 print words from a boggle:
Given an NxN matrix, and a dictionary, print a list of all words that
appear in the matrix. You can not use the same letter twice. For example,
if the matrix were:
W A
D R
You could find the words: WAR, WARD, DRAW and RAW （一个字符只能用一次）
没想出好的方法，大牛们？ |
|
s*****r
发帖数: 773 | 2 给定任意一个n*n的字母的board, 找出board里面的单词, 我只会用递归做, 一个个search, 10*10的, 要算好久好久, 请问有没有高效的算法? 我能够想到的, 就是遇到类似绝对不会出现在一起的, 就不继续search了, 例如gj, gz的字母组合, 请问哪儿可以找到有这样的绝对不出现在一起的字母组合?
例如3*3的
y o x
r b a
v e d
合法单词如下
bred, yore, byre, abed, oread, bore, orby, robed, broad, byroad, robe
bored, derby, bade, aero, read, orbed, verb, aery, bead, bread, very, road |
|
l**s
发帖数: 50 | 3 how to define "word"?
search, 10*10的, 要算好久好久, 请问有没有高效的算法? 我能够想到的, 就是遇到
类似绝对不会出现在一起的, 就不继续search了, 例如gj, gz的字母组合, 请问哪儿可
以找到有这样的绝对不出现在
robe |
|
L****t
发帖数: 924 | 4 use a dictionary trie?
search, 10*10的, 要算好久好久, 请问有没有高效的算法? 我能够想到的, 就是遇到
类似绝对不会出现在一起的, 就不继续search了, 例如gj, gz的字母组合, 请问哪儿可
以找到有这样的绝对不出现在
robe |
|
|
m*******i
发帖数: 370 | 6 很郁闷的面挂了，不过还是贡献一下能记住的面试题目，希望对以后的xdjm有用
记不太全了，能记多少写多少吧。可能题目不是那么难对于CS的来说，我是烂校EE的通讯，
实在是EE的通讯opening太少，不好找，无奈投了很多CS的职位。
第一轮电面
1. 为啥投amazon
2. 啥是binary search tree，然后问怎么找least common ancestor
3. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
比如：9=4+5 或者9=2+3+4, 但是8就不可以 这个要写code念code
第二轮电面
1.为啥投amazon（总问）
2. 啥是polymorphism，virtual function 怎么实现的（就是回答机制，virtual
table啦，每个object都有个virtual pointer什么的）
3. design a deck of cards 传说中的设计问题
4. 还问了一个公式的，好像是postfix的啥东西，没听明白
onsite 总共6论，不算hr的话
1. boggle puzzle 找到里面所 |
|
j**l
发帖数: 2911 | 7 被面到的概率大么？
是递归还是动态规划？要用到trie或者suffix tree么？
谁有简洁清晰的思路？ |
|
j**l
发帖数: 2911 | 8 是否可以用解决骑士周游(国际象棋跳马问题)的回溯方法？ |
|
r**u
发帖数: 1567 | 9 backtracking, if needs optimization, maybe organize the dictionary to trie
for easy checking valid word. |
|
S******A
发帖数: 1002 | 10 用trie处理字典，递归的时候避免dead end |
|
B*****t
发帖数: 335 | 11 先问他题目的规模。
小规模的crossword，直接DFS就可以了。
对于比较复杂的crossword，两种方法：
1. 要先根据已知的word建一个trie，在map上每一个起始点和交点进行search，跟dfs
也差不多。
2. AC-Automation,其实就是trie上的KMP，search起来在某些情况下比trie要快一些。
还可以在它上面进行DP，不过估计面试不会被问到。
good luck！ |
|
S******A
发帖数: 1002 | 12 2 is boggle problem
load dic as trie to stop searching immediately upon a dead-end, i guess you
also need to avoid re-using any cell (char) more than once when constructing
a valid word |
|
|
j**l
发帖数: 2911 | 14 总觉得和Boggle题，跳马(骑士周游)题，迷宫题，图论，DFS, 回溯有千丝万缕的联系。不知
道和动态规划有没有关系。
题目:
嘉定每块碎片最多和另外四块碎片接合。你用到的数据结构是什么？假定你已经有了一个方法，可以告诉你两块碎片是否可以接合。你该如何解决这个puzzle, 使得你调用该方法的次数是最少的？ |
|
f*******e
发帖数: 1161 | 15 一道编程题：给一个board和字典，找到所有words
求高人提示解题思路！ |
|
|
f*******e
发帖数: 1161 | 17 就是字母的排列，比如3*3，以及每个位置的字母 |
|
h****b
发帖数: 25 | 18 来自主题: JobHunting版 - 问个算法题 一个amazon的算法题描述如下（在以前的面经里面看到的）：
boggle游戏的问题：给定一个4*4的矩阵，每个
位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
这个题目感觉下code的话很难写的啊？ 如何用DFS或者递归的话 如何避免访问重发的
元素了或者避免Loop. 还有的话用用DFS的如何构造图呢？ 感觉DFS找一个valid word
比较容易， 找出所有的words 感觉太复杂了。大家有什么简洁的算法？。谢谢了 。。 |
|
i*****d
发帖数: 4 | 19 G家电面zurich的职位。没有NDA。
面试我是一话不多的小哥。首先问了问research，让讲讲最后一篇paper的idea。
然后开始编程，只有一题，就是打印出boggle游戏所有的可能的单词。假定有一个字典
可以检测单词是否存在。
解法很简单，递归久就行。问了问复杂度，和如何优化，假定字典可以检测字串是不是
某个单词的前缀。
用google docs写程序挺痛苦的。写完后被发现几个bug逐一修正。
然后换我问问题结束。
然后给Recruiter写了封感谢信，过一会就回我有Feedback了。打电话告诉我要onsite
。真的很有效率，recruiter也
非常nice。
继续加油准备了，攒攒rp。 |
|
p*****a
发帖数: 147 | 20 boggle puzzle 找到里面所有的单词，写code。
大家讨论讨论怎么做。 |
|
|
g**e
发帖数: 6127 | 22 As promised, 某著名卖鞋A公司的纽约最新分店onsite，让我签了NDA带去，不过没人找
我要啊，哈哈。
早上似乎来了8个人，包括我这个打酱油的，有一个老中同胞，其它都是老美。有个哥
们穿着拖鞋就来了，一看就是很nb的geek。
1 on 1，见了5个人，每人一小时，每人一到两题。题目比想象的容易多了，跟版上的
根本不是一个档次。上次电面的也是。我不知道是不是因为这是exp hire，他们更看重
的是设计，分析问题和交流能力，以及一次性写对无错误的代码，包括边界检查和异常
抛出。还有在
写代码的时候穿插了很多问题，比如为什么选这个class不选别的，各自的优缺点；什
么时候返回null，什么时候throw exception之类。
1. hr
被HR轰炸了一个小时，问了我各种你们能想到的behavior问题。好些如果没工作经验，
真的很难回答，背答案是没用的。比如问你在有些情况下，你需要绕过公司的一些规定
和policy来完成一些工作，你会怎么办。比如如何控制risk，当你做了个错误的决定，
如何反应。当你screw up了一个project，你怎么办等等。都要举出工作中的... 阅读全帖 |
|
|
a*****a
发帖数: 46 | 24 boggle puzzle那道题能详细说一下么？是每行/列/斜线组成一个词 还是 整个表组一
个词？ |
|
i**********e
发帖数: 1145 | 25 我写的 boggle 游戏算法，DFS + trie.
一秒以内给出所有 5x5 的答案。
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Trie {
bool end;
Trie *children[26];
Trie() {
end = false;
memset(children, NULL, sizeof(children));
}
void insert(const char *word) {
const char *s = word;
Trie *p = this;
while (*s) {
int j = *s-'A';
assert(0 <= j && j < 26);
if (!p->childre... 阅读全帖 |
|
|
g*******e
发帖数: 61 | 27 昨天完成了A家的on-site, 一共四轮，最后一轮表现非常差，肯定挂掉了，继续海投吧
。之前在版上求了bless，现在攒RP，分享面经。
第一轮，美国小伙，说之前在MS，现在来A9个月了，Kindle组。目前参与A家的神秘项
目，不能讲太多项目内容，其实大家心里都知道是A的Tablet。
技术问题之前随意的聊了聊，然后问了一些很基本的CS问题。剩下20分钟，正式开始
tech question。很简单，给一本杂志，从里面剪字，看能不能找到指定的字符串。
我先给了brute force，O(n*m)，然后说如果用hash table, O(n)。然后说不让用额外
的buffer，怎么做？想了想，sort之后找substring，O(nlgn)。讨论完之后，说让我挑
其中一个写code。我说brute force简单，写的快，给了code后，挑了挑毛病，按时完
成。
第二轮，美国小伙。那个组不记得了。主要是面我OOD方面的问题。先问了我熟悉不熟
悉Java，答道还OK吧，刚想说很久不用Java了，问题直接就出来了。描述一下Java的GC
机制。说实话还真是记不太清楚了，现在主要写Pyth... 阅读全帖 |
|
h*********n
发帖数: 915 | 28 第一问谁看懂了？什么叫杂志里剪字？
发信人: glorywine (glorywine), 信区: JobHunting
标 题: Amazon On-site 最新面经
发信站: BBS 未名空间站 (Sat Sep 17 10:51:50 2011, 美东)
第一轮，给一本杂志，从里面剪字，看能不能找到指定的字符串。brute force O(n*m)
，hash table O(n)。不用额外buffer，sort后找substring，O(nlgn)。brute force写
code。
第二轮，OOD问题。描述Java的GC机制。reference counting蒙对了。设计餐馆订餐系
统。
我给了需要那些class，那些functions。指定其中一个方法，伪代码实现。
第三轮，binary tree找common ancestor。给字符串，每个字符出现的频率。从高到低
输出。
第四轮，hash table的实现。Boggle code实现，给game board，找所有valid word。 |
|
h*********n
发帖数: 915 | 29 第一问谁看懂了？什么叫杂志里剪字？
发信人: glorywine (glorywine), 信区: JobHunting
标 题: Amazon On-site 最新面经
发信站: BBS 未名空间站 (Sat Sep 17 10:51:50 2011, 美东)
第一轮，给一本杂志，从里面剪字，看能不能找到指定的字符串。brute force O(n*m)
，hash table O(n)。不用额外buffer，sort后找substring，O(nlgn)。brute force写
code。
第二轮，OOD问题。描述Java的GC机制。reference counting蒙对了。设计餐馆订餐系
统。
我给了需要那些class，那些functions。指定其中一个方法，伪代码实现。
第三轮，binary tree找common ancestor。给字符串，每个字符出现的频率。从高到低
输出。
第四轮，hash table的实现。Boggle code实现，给game board，找所有valid word。 |
|
t*****g
发帖数: 113 | 30 1. You have two arrays X and Y. Each are having say M and N elements already
sorted increasingly. We have to find the k-th largest one of the whole set
M + N elements.
2. Regular expression match，可以match的符号只有3种：
a-z : match a-z
a+ : match any numbers of a
.+ : repeat 1 - arbitrary times
3. boggle puzzle 找到里面所有的单词，写code
4. Given preorder of a binary tree, print out all the binary trees
5. Given a sequence of alphabetically sorted strings, try to find out the
alphabet order there. |
|
S**I
发帖数: 15689 | 31 ☆─────────────────────────────────────☆
libei (Bei) 于 (Wed Jan 11 15:43:39 2012, 美东) 提到:
面试官是Google+组的，
一上来她说看到我简历上的一篇测试自动化的文章，读了一遍，感觉"very
informative"，让后让我介绍一下相关经验。让我小高兴了一下。
第一题是coding，做的还算顺利，后来她评价说所有的cases都覆盖到了。可能算是过
关吧。
第二题我想复杂了，然后在她提示下才解决。自我感觉很不好。其实sort一下就差不多
了，不过我往复杂的树结构想去了。虽然树结构确实能解决这个问题，不过当时我解释
得很不清楚。反正很不爽。
最后瞎聊时间，她说我提到的测试自动化实践和Google内部的基本完全一样blahblah。
。。，不过我觉得这点也算不上加分吧，是个人进google一段时间后都能学会。就怕她
觉得我想问题太复杂，直接negative。
大家有啥建议想法？？
☆─────────────────────────────────────☆
peking2 (myfac... 阅读全帖 |
|
i**********e
发帖数: 1145 | 32 经典 dfs，boggle 题。
用一个二维table来记录visited cell就可以了。 |
|
|
|
s*******n
发帖数: 97 | 35 题目2：
boggle puzzle 找到里面所有的单词，写code
DFS? |
|
|
g**********y
发帖数: 14569 | 37 Amazon的onsite题目难度平均来说不算大，那些很变态的题目，除非人品非常不好，应
该是碰不到的。
多准备他家最喜欢的一些问题：
- 关于树的操作，这个是一定有的
- OO-design, 这个也是一定有的
- 字符串的操作，多半会是DFS/BFS search, Boggle那个很具有代表性，如果写得不够
好，去找好的code来读懂
- Recursive一定要写熟，全排列问题，含duplicate的全排列，这两个是写recursive
的代表题。
- 基本知识点的名词解释，这个我很不喜欢，但是他们喜欢问，没办法。看你说的最擅
长什么语言，特别准备那个语言的。
Advices。 |
|
D********g
发帖数: 650 | 38 面经回馈本版，只列出technical question.
P1:
A. Add next pointer to each node on a BTree to its next sibling on the same
level.
B. Boggle题，find all possible words from a 2D character array.
P2:
A. Given
interface Iterator {
T next();
boolean hasNext();
}
interface Predicate {
boolean accept(T t);
}
Implement a method that creates an "accept" iterator that returns items
accepted by the passedin pred variable.
Iterator conditionIterator(Iterator input, Predicate pred) {
}
B. Concurren... 阅读全帖 |
|
w***y
发帖数: 6251 | 39 Boggle题，find all possible words from a 2D character array.
这是什么样的题目? 能具体说说么? 看样子是老题, 但是我没见过//囧 |
|
z**********g
发帖数: 209 | 40 boggle 那题 dfs + tire 就好了。
请教 iterator + predicate 那题。 |
|
|
D********g
发帖数: 650 | 42 可以考虑用当前找到的最长word的length 做pruning.
if 当前string是个合法的word并且长度>= longestWordSofar.length()，则update
longestword
if 当前string是个合法prefix，继续找下去
需要字典支持isPrefix操作 |
|
g**********y
发帖数: 14569 | 43 把字典建成一棵加强版的Trie, 就是在Trie的基础上，计算每个节点可最多延长的路径
长度。然后用这个Trie来做辅助工具，剪枝遍历。 |
|
p*****2
发帖数: 21240 | 44
我面Google搞了个trie，结果没写完程序。最后人家说就是想要暴力的。 |
|
w***y
发帖数: 6251 | 45 i c
那就是：
第一个位子（0,0)开头的words,肯定要搜完所有可能
后面的就是利用了当前的maxL word 和当前prefix可能延长的maxL去剪枝
所以比找所有valid words需要的计算还是少一些的 |
|
n********k
发帖数: 40 | 46 一听字典，统计单词就是trie没跑儿。
我幼稚地认为，如果一个面试官跟你说了不要代码，就要往hash，balanced binary
search tree和trie这三个上面想了，对于trie，我惯例的回答是：“我知道prefix
tree可以On时间On空间实现，这是基因工程中最基本的算法，但是写起来很复杂，你不
会要我写吧？”然后开始狂喷
要是要代码，一切比longest increasing subsequence更复杂的算法都不要费时间去想
，一定有更简单的。 |
|
|
U*********y
发帖数: 54 | 48 //如果不爱分享, 至少懂得回报
1.一个整数数组a[], 每个元素的值代表能向前跳1到a[i]格,问最少跳几步刚好到达数
组的末端, 超出数组的index或到不了末端算失败
2.排好序的连续数组只缺一个数,二叉搜索找出来
3.Boggle游戏, 返回牌面上所有有效单词
4.按顺时针打印二叉树边缘, 解法见leetcode
5.zigzag打印二叉树, 解法见leetcode
6.电话号码的regular expression
7.二叉搜索树找相等或最相近某值的节点
8.singleton的多线程
9.股票最佳买入和卖出点
10.Kth分割 (快排序的分割步骤)
11.网络用户的网速慢,如何设计浏览器加速网页的浏览速度
12.浏览器输入URL,发生了什么
13.给电话号码, 打印所有可能字符串
14.写API, 允许用户注册一个程序到ID, 注销一个程序, 运行一个ID下所有的程序
15.找质数
16.atoi
17.讲电话本的trie设计,对比哈希表
3家的电/店的题目放在了一起,大部分都算常见题.
经验总结: 面试的不定因素太多,感觉就像抽奖. 所以不要放弃,感觉准备好了的话(以上... 阅读全帖 |
|
|
|
