|
r*******t
发帖数: 99 | 2 这个题相当于一个Jump Game：一排格子，每一个可以往后面的某些格子里跳，每一跳
的cost是0。同时每一个可以往紧邻的下一个格子跳，每一跳的cost是1。把格子看成
vertex,跳看成edge的话就是一个directed graph的shortest path问题，而且这个图已
经是topologically ordered，只用从前往后scan一遍所有vertices，同时update当前
vertex前方与之相连的vertices就可以了。
每一个vertex有哪些outgoing的edges可以查用anagram索引过的dictionary来确定。索
引dictionary的时候记下最大词长可以减少look up的次数。
string minSkip(vector& dictionary, string& str) {
multimap ana2word;
size_t maxLength = 0;
for (size_t i = 0; i < dictionary.size(); ++i) {
... 阅读全帖 |
|
z********c
发帖数: 72 | 3 不知道什么要求。。我直接写的搜索然后优化成DP，他说很好
merge写了，那一场45分钟全部用来搞这个题了。。。。
补充一下电面题把:
F:
1. int strstr (const char *haystack, const char *needle)，要你实现，
bruteforce就行
2. int strstr (const char *haystack[], const char *needle)，意思就是haystack
太长了，然后一个串存不下，变成存个数组里， 把他们concatenate 以后就是
haystack，还是一样的要求，要你实现，不能有额外空间
3. 给一组字符串，按anagram分组，输出
G:
1. 找到ll里最后k个节点，把他们放到前面来
2. 那题在板上说过，一个iterator，有next和hasNext，现在要你加个wrapper，使得
支持peek操作
不少了哥。。。我问了那么多人绝对我写的码比他们都多。。 |
|
f*******t
发帖数: 7549 | 4 这是sliding window的变种吧，用两个hashtable，O(n+m)时间内可解决 |
|
w****x
发帖数: 2483 | 5
你怎么个hash法? 你每次滑动的时候hash要重新算一遍? |
|
|
A*H
发帖数: 127 | 7 you can use rolling hash |
|
c****p
发帖数: 6474 | 8 最简单的hash就可以了，比如把window内部的字节xor到一起。
滑动后把当前的hash值分别和滑出的字符和滑入的字符xor一下就是新的hash值，
代价O1。【 在 wwwyhx (wwwyhx) 的大作中提到: 】 |
|
|
p****a
发帖数: 447 | 10 不是吧,恢复map还一个while呢
with |
|
b********g
发帖数: 43 | 11 那天太神勇了。。主要都是常见题。。
1. two sum, sorted and unsorted version
2. reverse K group linked list
3. binary search tree(lowest common ancestor), extend to binary tree case
4. find unnecessary classes to compile a class in a package .
5. reverse a sentence word by word "I am joe" ---> I ma eoj
6. permutation of a string, I wrote the recursive way first and next_
permutation implementation after that.
7. intersection of two sorted array
8. rotate of a matrix, NxN case, I use transpose, NxM case, I use repl... 阅读全帖 |
|
G*********t
发帖数: 71 | 12 本人背景：无名学校CS小硕，工作一年在一家无名微型公司, 三低三无人物：资历低，
工资低，水平低、无绿壳，无淫脉，无老婆
中年白淫，语速清晰
面经：
1. 上来要coding 写一个很简单的函数 如果能被5整除输出buzz，能被3整除输出fizz
，同时能被这两个数整除输出舒服fizzbuzz，如果都不能被这两个数整除输出这个数。
2. 给你两个string 是否是anagram，我说两个hastable，然后减少到了一个，面试官
最后提出一个比较有价值的问题。如果想检验这个hastable所有value是否都为0，除了
挨个查之外用C或者C++有没有更快的办法
3. 如何实现priority queue。
三个问题，但是问了很多时间空间效率的问题，同时也问了特别特别多怎么写test
cases，木经验啊，test不咋熟，就在那冥思苦想胡说八道。
从板上的大牛牛们学了很多，所以小的尽微薄之力分享一下下。 |
|
G*********t
发帖数: 71 | 13 本人背景：无名学校CS小硕，工作一年在一家无名微型公司, 三低三无人物：资历低，
工资低，水平低、无绿壳，无淫脉，无老婆
中年白淫，语速清晰
面经：
1. 上来要coding 写一个很简单的函数 如果能被5整除输出buzz，能被3整除输出fizz
，同时能被这两个数整除输出舒服fizzbuzz，如果都不能被这两个数整除输出这个数。
2. 给你两个string 是否是anagram，我说两个hastable，然后减少到了一个，面试官
最后提出一个比较有价值的问题。如果想检验这个hastable所有value是否都为0，除了
挨个查之外用C或者C++有没有更快的办法
3. 如何实现priority queue。
三个问题，但是问了很多时间空间效率的问题，同时也问了特别特别多怎么写test
cases，木经验啊，test不咋熟，就在那冥思苦想胡说八道。
从板上的大牛牛们学了很多，所以小的尽微薄之力分享一下下。 |
|
t**i
发帖数: 314 | 14 试了anagram这道题，好像也是把处理特殊情况那行（如果str为空或者只有一个string
时返回null）去掉就没有error了 |
|
r**d
发帖数: 316 | 15 仍然按照一般的排序办法给字符串数组排序，只是判断两个字符串大小时候，不比较字
符串本身，而是比较两个字符串的字母拆开重新排序后形成的两个字符串。
这样anagram就会排在一起。
hash |
|
x*******6
发帖数: 262 | 16 请问sramble string和anagram有什么区别？不能将string里面的char排序然后看是否
一样么？ |
|
C***U
发帖数: 2406 | 17 你的recursion的方案 可能不用每个都跑一边
尝试用anagram这个函数
可以省去重复 |
|
g*****g
发帖数: 34805 | 18 牛啥呀，两个电面，atoi一堆小错，比较anagram这种题我都没做出来，人
还是让我周一去onsite了，所以着急。 |
|
a*******y
发帖数: 1040 | 19 这个最好的答案是啥？
用Trie？ 那么怎么设计让快速的能找到anagram的words那（permutated） |
|
l*****a
发帖数: 14598 | 20 啥叫digital dic ah
131的绿人
不过快速找anagram显然是hashmap |
|
d**e
发帖数: 6098 | 21 全fail了，呵呵，没什么成功经验。
1 - medtronic, LA
recruiter打电话来的，对着单子上的技术问题语言特点一个一个问，她什么也不懂，
所以有疑问也没得商量，当然我也有几个答得不好。最后不了了之。
2 - hulu, LA
电面1，跟glassdoor上面几乎没什么区别，都是问烂的题，merge sort, LRU, 还有两
个算法，给code问是做什么的，我遇到的是anagram和circle detection in
linkedlist.
电面2, 分割字符串，定义了一些rule
有三对分割符,我忘了是给什么了，但应该不太重要，就假定给的是(),{},[]，然后这
六个符如果是连续两个重复就是escaping，下面是一些例子
abc(cde)efg -> abc, cde, efg
(abc){cde}[efg] -> abc, cde, efg
(((ab))c)cd{{}}e[efg)]]] -> (ab)c, cd{}e, efg)]
没做出来，第二天一大早就被拒了。
3 - wireless generation, NYC
电面，是一个engine... 阅读全帖 |
|
z**********2
发帖数: 307 | 22 Top 10 tech interview questions
Reverse a singly lined list
Print a binary search tree level by level
Max sub sequence problem
Find the nth smallest/largest number in a unsorted array
Two sum, three sun problem
Implement math pow function
Implement merge sort for more than two arrays
Find all the anagrams from a list of words
BFS and its variants (such as determine whether a graph is bipartie)
Coin change algorithm (given a number of denominations and a target number,
find the total number of wa... 阅读全帖 |
|
g*****e
发帖数: 282 | 23 1. 看一个code sample，干嘛的，算法复杂度是多少
2. anagram。hashtable的解他们就满足了 |
|
f********a
发帖数: 4239 | 24 anagram什么的解更好？
hashtable的解是说建立两个hashtable然后比较是否相同？ |
|
s***u
发帖数: 101 | 25 MS SDET offer， 两个组 一个online service（主营bing） 一个 server and tools
（主营Azura， cloud）， 请教两个组哪个比较好? (考虑稳定，学习和上升空间）
还有一个问题，因为本人不太想做 SDET， 想问一下 如果以后 SDET 转 SDE 140要重
新file 么？ 并且 140 file 之前能转么？ 转了的话 140 是不是要重来。。？ 多谢
各位大牛！
以下是面试问题，因为oncampus 面了 3轮，onsite 只有2轮
1. n个人 挨个叫号，叫到3的人离去， 剩下的那个人是几号
2. 测试一个网页
3. 找到一个字典里的 anagram
4. 不用比较找到2个数字中 较小的一个
多谢大牛帮忙！ |
|
b***m
发帖数: 5987 | 26 第一个面试官，白人，Senior Test Lead，吃饭加瞎聊，就问了一个跟工作相关点儿的
问题：如果让你测Windows XP这样过时的产品，你怎么决定该测什么不测什么？
第二个面试官，应该是Pacific Islander，出生、长大、读书在夏威夷，Senior Test
Manager，聊了半天，做了两道题。第一题：你以往项目中你最得意或者满意的系统设
计，我讲述了我怎么设计、实现全套Windows UI的事情。第二题：给你一个任意形状，
如何判断一个点是否在该形状中？
第三个面试官，白人，Senior Test Lead，上来就做题。第一题：给定一个整数二维数
组，行和列都分别升序，再给定一个整数n，如何判断n在不在该matrix中？给出两种比
较优化的解法。第二题：他们的一套bug跟踪系统，一个大的bug数据库中不断把符合某
些设定条件的bug数据往一个handler里面push，最后log到他们自己的数据库中，如何
测试这套系统？
第四个面试官，烙印，Principal Test Manager，先瞎聊一通，然后做题。第一题：设
计一套电梯系统，包括如何调度，满足复杂需求... 阅读全帖 |
|
l*****a
发帖数: 14598 | 27 我准备的题目大多没用上:(，后两题是
2)give a dictionary and a word, print all the anagrams
3)give a sorted array ,find the biggest index if the target
is in the array |
|
s****t
发帖数: 467 | 28 刚回来，题目不难，可是遇到了很郁闷的情况。顺便问下大家遇到dev #5这种人怎么应
对比较好？
电面：
给个带有括号的字符串，判断所有的括号是否相配。扩展到几种不同的括号同时出现。
onsite：
1. manager:
给一个字符串，输出一个文件，里面每一行是一个出现的字符，后面跟着它出现的次数
。要根据出现次数降序排列。
2. senior manager:
behavior questions and past projects.
3. dev:
1）二维平面上给一堆点，再给出一个点作为目标。求离目标点最近的k个点。
2）设计A家网站上那个“买个这个东东的客人也买了下面这些东东”的feature，问了
如何scale。
4. BR:
1）给一个字典，当输入一个单词时要求返回字典里所有它的anagram。条件是可以无限
的预处理，只要输入时返回的速度最优就行。
2）elevator design: min wait time, max throughput, scale for different types
of buildings.
面到这感觉都还好，结果下面郁闷了。
5. d... 阅读全帖 |
|
p****c
发帖数: 35 | 29 先是各自简单的自我介绍。然后两道很常规的题目:
1. 判断字符串不考虑标点空格的情况下是回文.
2. 给定一组字符串, 按anagram分组后，返回list of list.
当时脑子一片空白，用了半个多小时才搞定。第一题跳过标点空格时忘了检查字符越界
. 写完后，说我先测试一下. 假设输入是一个空格, 自己走了一遍说好像可以.考官问
你的测试真的可以吗？才发现了没有检查字符越界的bug. 赶快加上.考官说可以简化一
下while的条件吗？看了一下去掉了一个多余的条件,说我看看还能再简化吗. 考官说可
以了，你的程序works, 下一个吧.
第二题一开始突然不知道该用什么数据结构。我说就定义一个less_than直接排序就可
以了. 刚想写less_than, 觉得这样太复杂，我说还是用hash或者map吧。考官说key是
什么, 我说没有key,就用hash_set或者multiset吧. 考官说你可以造一个key吗？我说
可以把字符串排序作key. 然后开始定义数据结构. hash_map, 写到
这里看了一下改成multimap阅读全帖 |
|
k*******2
发帖数: 84 | 30 来自主题: JobHunting版 - F M面经 报两个面筋，攒个人品：
F：
第一轮店面：以数数的方式压缩字符串，比如111223333变成312243;
第二轮店面:
题目1： 有个很大的integer数组，找出其中值最小的100个element;
题目2： 给出一串前序表达式，比如312*+ 就是3+1*2, 写个方法parse这个表达式；
然后被加了一轮店面：
题目1：就是那个每个数字对应几个字母，给出一串数字，求所有的对应字母组合；
题目2：一个字符串数组，按照anagram进行排序；
结果：三轮之后挂掉。。说我木有很好的交流我的思维。
M：
on campus: 闲聊；
onsite:
面的哪个组就不说了
第一轮：被放鸽子；
第二轮+lunch: 设计一个数据结构(trie)储存字典里的单词，写一个方法来判断给出一
个单词在不在字典中；写出来后让优化；
第三轮：就是那个带一个random指针可以指向任意一个节点的链表，copy给出的链表；
第四轮：循环方式中序遍历二叉树；
第三天被告知挂了。。不给告诉原因。
基本都不是很困难的题目，但是由于刷提不够，所以要达到一气呵成bug free的境界还
有很大差距。。而且没有实习经历... 阅读全帖 |
|
o********4
发帖数: 45 | 31 攢點人品,
NYC, EE小本一面, CS知識跟編程都是靠網跟書學回來的, 本科只讀了introduction to
programm跟database.
B家電面, 年輕印度人, 名字也沒介紹(我也忘了問), 一來就introduce myself, 然後2
話不說直入題 (我有講自己沒
讀過CS的課)
1: find digits that are duplicated inside an integer. Find their order as
well.
我用了%跟/10 去找digit, 第1次iteration 把digit跟index 放到MAP裡, 重複的
replace key跟value, 然後第2次iteration再用一個STACK來存不對應的index跟value,
這就可以知道那個digit在那一個位罝重複, 面試官聽起來說OK.
2: 問完第1個, 他說第2個is not necessary, but still want to know my thinking.
設計一個anagram的system, given a list of valid word... 阅读全帖 |
|
e****e
发帖数: 418 | 32 IMHO, HashSet+ArrayList+从后往前扫描 is the best solution. Time complexity
is log(n+m), n is num of words, m is num of anagrams. The space complexity
is log(m).
Set set = new HashSet();
List list = new ArrayList();
for( int i = words.size()-1; i >= 0; i-- ) {
String sortedWord = sort( words.get( i ).toLowerCase() );
if ( !set.contains( sortedWord ) ) {
set.add( sortedWord );
list.add( word );
}
}
Collections.reverse( list );
return list; |
|
o***d
发帖数: 313 | 33 ===谢绝转载==========
说个我的吧,很弱,还是人品好?顺便求下个礼拜A家onsite bless....没准备好,哭啊!G家
具说要给onsite，还没有安排。
a家:
两个电面,就一个算法问题:anagram.....其余都是behavior
g家:
一个电面,基本上算就一题: g: interviewer, m: me
g: 知道rpc么?
m: 知道,用过(心里一凉,对stub不是很懂,只知道个大概,我简历上提到了一点点rpc)
g: rpc calling怎么call?
m: 方法加参数就可以了(心理说: 要不要说ip阿?作连接用阿)
g: 还有呢?
m: ip
g: 还有呢?
m: ...........
g: ....
m: port (猜得,不知道他想问什么)
g: 对了！一个server,run several rpc software services,有什么问题？
m: 。。。。。（才不到）
g: ...
m: 哦，port 冲突（心理：自己设置一下，也不冲突阿，可是估计他问这个？）
g: 对了！
g: 怎么解决？
m: 做个底层的service来分配p... 阅读全帖 |
|
p**o
发帖数: 1012 | 34 估计同电面悲剧的握手，贡献个题目
1。找anagram,这个题据说是练手的，本来应该一口气写出来的常见题目，想了10分钟
2.合并两个BST，也写出来了
45分钟只短不长，上来二话不说直接coding，交流不多，也没问对方提示，对方应该印
度人。虽然都做出来了，但是由于写的不够顺，而且第一题他只说是warmup的，我不知
道后面是不是还有第三题，总之，觉得对方对我感觉不太好，而且题目也太简单，应该
是悲剧了 |
|
p**o
发帖数: 1012 | 35 其实那个老印和我说，你干嘛不用list,用array.他觉得list insert，比我copy出来一
个array要好些，其实我觉得半斤八两，因为我觉得array其实存储空间更省，操作更快
，因为list 要存pointer.另一方面，List就不用后面多出一个整个的空间merge了，会
省空间。还有array 需要连续空间，List可以做linkedList,所以array太大容易内存溢
出。最后就是array建立BST的时候更方便，可以直接定位index,List虽然也可以用
index定位，但是其实还是按照一个个pointer链接过去的，说是建立BST的时候，复杂
度O(n)其实我觉得是不真实，因为List.get(i)不是绝对的O(1),所以很冷淡地回复了印
度人，List虽然有好处，不过也就是那样，两个相比，未必谁好谁坏。
我觉得那个印度人大概也感觉到我的态度不好了，其实他对我态度也不好，比如说题目
的时候，根本没举例具体说，就直接说一个find anagram,merge two BST,这么短的话
，明显也是应付 |
|
j*****y
发帖数: 1071 | 36 两个word之间不会 shuffled吧？ 感觉和anagram的题目有点类似，
产生的 original sentence可能不会唯一
vector > func(string s, int start)
{
vector > result;
if(start == s.length())
{
return result;
}
for(int i = start; i < s.length(); ++i)
{
vector word = anagramWordsInDictionary(s.substr(start,
i - start + 1));
if(word.size() > 0)
{
vector > tmp = fun... 阅读全帖 |
|
|
|
|
t*********n
发帖数: 89 | 40 有没有要求每一步中间过程必须是单词？不要求的话直接统计字母种类个数就可得到需
要转换的个数，然后从头到尾分配就好了。如果要求的话dfs搜索好说，但是如何求最
小的那个呢？ |
|
|
|
|
|
|
|
l*****a
发帖数: 14598 | 47 先找出 sorted需要替换的字符
start from beginning of S
如果当前字符不在T,use the smallest character
如果当前字符在T且需要被替换(S has more than T) {
if cur char> 需要被替换的,替换当前
else { if(already has the same cur char in S as T,must update this)
替换当前
}
} |
|
b*****n
发帖数: 482 | 48 写了一下，run了几个test cases，可能还有什么corner case没想到，就先抛个砖吧。
string getAna(string s, string t) {
assert(s.length() == t.length());
int len = t.length();
map ms;
map mt;
for(int i=0;i
++mt[t[i]];
ms[t[i]] += 0;
++ms[s[i]];
}
map::iterator it=mt.begin();
for(int i=0;i
while(it!=mt.end() &&
it->second <= ms[it->first]) ++it;
char c = s[i];
if(mt.count(c) && mt[... 阅读全帖 |
|
p*****2
发帖数: 21240 | 49 我贴一下我的
val n=S.length
val s_counts=new Array[Int](26)
val t_counts=new Array[Int](26)
0 until n foreach{i=>
s_counts(S(i)-'A')+=1
t_counts(T(i)-'A')+=1
}
var count=0
for(i<-0 until n if s_counts(S(i)-'A')-t_counts(S(i)-'A')>0)
process(i)
out.println(count)
out.println(S.mkString)
out.close
def process(i:Int){
val next=find
val c=S(i)
if(t_counts(c-'A')==0 || next
S(i)=n... 阅读全帖 |
|
|
