b*****e
发帖数: 474 | 1 // my solution using recursion + global variables
int a[] = { 2, 3, 5, 7, 10 }; // sorted coin denominations
int size = 5; // number of coin types
int partial[MAX]; // store partial solutions (coins) -
// sorted in descending order
int partialSize=0; // partial solution size (# of coins)
void print_current_solution() {
for (int i=0; i
cout << endl;
return;
}
// do ... 阅读全帖 |
|
b*****e
发帖数: 474 | 2 // my solution using recursion + global variables
int a[] = { 2, 3, 5, 7, 10 }; // sorted coin denominations
int size = 5; // number of coin types
int partial[MAX]; // store partial solutions (coins) -
// sorted in descending order
int partialSize=0; // partial solution size (# of coins)
void print_current_solution() {
for (int i=0; i
cout << endl;
return;
}
// do ... 阅读全帖 |
|
M7
发帖数: 219 | 3 First 电面:
1. 谈一下不同数据结构的优缺点。
2. 一个大文本文件里有电话号码。每行至多有一个号码。How do you process and
return the total number of phone numbers. (in command line, use grep and wc)
3. A generic tree. how to print out nodes by level (one lever a line)
说了pseudo code, 要求电面后email给他。
4. A database application is slow. How do you investigate the problem and
how to improve it.
Second 电面:
1. 写一个函数，输出一个整数里1-bit的数目。比如CountOneBits(7)应返回3。
2. 网页很慢。找出可能原因。（和一面的最后一个问题差不多）
3. 下面statements的区别是什么？接着问了关于constructor的问题(copy), shallow
vs. d... 阅读全帖 |
|
e******a
发帖数: 176 | 4 没看明白，能仔细说说么？
”最后我还是用了一个辅助的数据结构。他reply我，给了
idea. 实际上还是用两个static variable. 在recursion中计算，在foo(0)里面输出
F(X), 然后在recursion返回中在还原出F(X-1), F(X-2) …. 直到F(1), F(0).“
wc)
and |
|
z*******0
发帖数: 30 | 5 void Recursion::permute(char a[], int n){
sort(a, a+n);
permute(a, 0, n);
}
void Recursion::permute(char a[],int i,int n){
if(i==n){
//print string;
cout << a << endl;
return;
}
for(int j=i;j
if (j > i && a[j]== a[j-1]) continue;
swap(a[i],a[j]);
permute(a,i+1,n);
swap(a[j],a[i]);
}
} |
|
e*****e
发帖数: 1275 | 6 Given a BST in a language where memory must be handled manually, how do you
completely remove BST from memory? Recursion is not allowed. Was later told
that desired solution had O(N) time and O(1) space. ??????
实在是想不出不要 recursion O(1) 的办法 |
|
i****c
发帖数: 102 | 7 这题有意思！
1）easy, recursive or iterative algorithm
2) preorder+inorder, preorder+marker, level-by-level, etc.
3) I will prefer to use preorder+marker so that we can find the path to
leaves
without constructing trees in memory
A quick thought, we can do serilization by repeating parent nodes (correct
me if you find errors)
e.g., a tree, root is A, A's left is B, right is C, B's right is D, and C's
left and right are E and F respectively.
then we have AB?DACECF, ? indicates a null
4) distribute small... 阅读全帖 |
|
s*****y
发帖数: 897 | 8 来自主题: JobHunting版 - 一到电面题 For the video decoder and audio decoder, commercial one.
Many decoder use the recursive call to extrace the header which is the video
and audio's metadata information. The function will recursive for 10-20, or
maybe 50. I forget why it needs to do in this way, but there is no better w
ay.
I encounter a lot of crash in this kind of function call due to the header n
oncompliant with standard. Most of these video are recorded by chinese "shan
zhai" cellphone. |
|
g**u
发帖数: 583 | 9 求祝福，刚面完Google第一轮。
电话面试没有NDA，所以把记得的题目记下来
太紧张了，发挥的很差。。。
Interviewer迟了3分钟， 没什么口音，估计是老美。面试一开始就上Google doc，
上来就要求写2个factorial的实现。
写了factorial的定义，马上写了个recursive的实现，说了边界检查，说了overflow，
然后开始写， 结果， 居然一急之下把base case给忘写了（哭死）。。。第二个写了
个iterative的实现，解释tail recursion可以马上改写成iterative的
接着是问一个非常大的文件里面有很多string，每行一个，问如何去重？ 说了hash和
sort的2种方法，比较了time and space complexity
接着是问了 set of strings, how to sort？问了memmory的限制，问了string的长度
分布，提出可以quick sort， 要求说明原理和时间空间复杂度，被追问还有其他方法
， 脑子犯傻，说了radix sort(大忌， 不要说自己不彻底清楚的东西)，说了基本原理... 阅读全帖 |
|
b**********r
发帖数: 91 | 10 Run the ultimate example around 400 ms
here is my code
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167,
4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
145, 13, 19, 27, 39... 阅读全帖 |
|
b**********r
发帖数: 91 | 11 Run the ultimate example around 400 ms
here is my code
4, 13, 5, 4, 13, 6, 8, 12, 16, 9, 13, 13, 13, 16, 9, 2, 6, 5,
0, 4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167,
4, 17, 22, 26, 39, 45, 53, 65, 81, 90, 103, 116, 129, 145, 154, 156,
162, 167, 13, 18, 22, 35, 41, 49, 61, 77, 86, 99, 112, 125, 141, 150,
152, 158, 163, 5, 9, 22, 28, 36, 48, 64, 73, 86, 99, 112, 128, 137, 139,
145, 150, 4, 17, 23, 31, 43, 59, 68, 81, 94, 107, 123, 132, 134, 140,
145, 13, 19, 27, 39... 阅读全帖 |
|
s****n
发帖数: 48 | 12 我写了个练手的,可以处理non-full binary tree。几个要点：
1.把parent node传给recursive function
2.每次recursive call只负责连接当前root。因为parent node作为参数传进来了，我
可以access parent's next link。并且这个时候所有上层的next links都已经连接好
了。
3.左右子树分别递归处理。先处理右子树，再处理左子树。
public void AddNextLink(Tree tree)
{
if (tree.Root == null)
{
return;
}
tree.Root.Next = null;
this.AddNextLink(tree.RightTree, tree, false);
this.AddNextLink(tree.LeftTree, tree, t... 阅读全帖 |
|
i**********e
发帖数: 1145 | 13 是填满空缺的数字.
>>如果给定的数很少，就是说这个矩阵很稀疏，那么solution有可能会有很多种，答案
不是唯一的，对吧？
假设只有唯一一个答案。
另外，如果有兴趣的话，可以参考 Peter Norvig 写的有关 sudoku solver 文章（里
面还介绍了怎么生成一个 sudoku puzzle，附有完整代码）。
从他那里转载：
What is the search algorithm? Simple: first make sure we haven't already
found a solution or a contradiction, and if not, choose one unfilled square
and consider all its possible values. One at a time, try assigning the
square each value, and searching from the resulting position. In other words
, we search for a value d such ... 阅读全帖 |
|
k****n
发帖数: 369 | 14
no
This is a very interesting problem, also very chanllenging.
Worked on it for 10 mins, and finally worked it out.
For a min heap, what we can first think of is doing heap sort.
Then we have a sorted array.
How to convert it to a BST (in array)?
lets first check an example, but in extreme case:
For the sorted array 1 through 7.
The form of BST is
4
2 6
1 3 5 7
So what is it for 1 through 15?
easily to guess:
8
4 12
2 6 10 14
1 3 5 7 9 11 13 15
So it is not very hard to change an array of lengt... 阅读全帖 |
|
h**********d
发帖数: 4313 | 15 公司名就不说了，不是大公司
不过效率极高，从hr联系我到拿到offer，3周不到。。。（一个重要的原因是我一开始
就跟他说我有学校offer了，他问我prefer学校还是industry，我赶紧说当然industry
更好~）
电面1， SW director
问了interface vs abstract class， encapsulation（为啥要用，我解释了privacy,
protect data, 他似乎不是很满意。。）, exception throw的overridden为什么不能
throw更多exception， SQL语句， 问文件如果不打开如何知道有多少行（我说用linux
command.... 想了以下, cat -n|tail ? 不过他没说啥貌似听到用command很满意。。
。）
后来还做了coding assesment， OO Design, 一个小时，写了7个class，用了delegate
pattern，自我感觉比较牛叉的design （LOL）
果然director 发信来说他们都很enjoy我的homework，哈哈哈（这还用说么）
电... 阅读全帖 |
|
f******c
发帖数: 80 | 16 刚amazon一面，白人男，问的题目挺简单，都是类似于论坛里出现过的题目
1、介绍了他所在的组，blablabla。。。
2、问了些几道java概念，final 和finally区别，thread怎么用等等。。。。
下面是两道老的算法题，全程念code。。。。。
3、老题目，given an unsorted array and an integer, 找array里是否存在一个pair
之和等于integer。他要求O(n)，不能首先sort the array. 他提示用Set来做，做完还
问了怎么写test cases 验证代码正确。
4、判断两个BST是否完全相同，让用recursive 和non-recursive两种方法都做一遍，
念code。
然后就结束了，我在让写test cases的时候，不知道怎么写了。。。
现在amazon的面试题目都是经常出现的题目，唯一问题是面的时候用结结巴巴的口语念
代码真是念得头大啊。。。（想面amazon的还是好好临阵磨枪代码怎么念。。。）， |
|
p****e
发帖数: 37 | 17 贴个楼主事后写的：
bool _re_match(const char *str, const char *pattern, char prev_char) {
// 如果str匹配完，检查pattern是否匹配完，或者还剩一个"*"
if (*str == NULL)
return (*pattern == NULL || (*pattern == '*' && *(pattern+1) == NULL
)) ? true : false;
if (*pattern != '*')
{
// 如果当前pattern char不是'*', 试图匹配当前的str char, 然后
继续。
if (*pattern == '.' || *pattern == *str)
{
if (_re_match(str+1, pattern+1, *pattern))
return true;
... 阅读全帖 |
|
p****e
发帖数: 37 | 18 贴个楼主事后写的：
bool _re_match(const char *str, const char *pattern, char prev_char) {
// 如果str匹配完，检查pattern是否匹配完，或者还剩一个"*"
if (*str == NULL)
return (*pattern == NULL || (*pattern == '*' && *(pattern+1) == NULL
)) ? true : false;
if (*pattern != '*')
{
// 如果当前pattern char不是'*', 试图匹配当前的str char, 然后
继续。
if (*pattern == '.' || *pattern == *str)
{
if (_re_match(str+1, pattern+1, *pattern))
return true;
... 阅读全帖 |
|
c******r
发帖数: 225 | 19 3. read n lines of random numbers(space as delimiter) from a file, lines
with same numbers are treated as duplicated lines, regardless of the order.
check and print non-duplicate lines. performance time analysis.
sort the n line based on the # of numbers in each line o(nlgn)
only lines that have the same # of numbers will be compared
suppose we have a set of m lines of length k
for each line in line_set:
sort numbers in each line ~ o(klgk)
then build a hashmap as a helper data structure
for al... 阅读全帖 |
|
P**********c
发帖数: 3417 | 20 好久以前的事情了。后来忙着面其他的，没有发，现在发一下。
PayPal我面的这个组，面试很短，只面了4个人，题目都很简单，感觉跟我面过的其他
公司G, Apple, T, L这些都不是一个档次的难度，不管是电面还是onsite。
电面是聊天，问了一些debugging的经历。一些behavior问题，诸如:
如果project做了一半，另外一个组的architect过来告诉你这么做是错的，需要用他的
一套方法云云，应该怎么办。
如果deadline很急，是要保证schedule还是quality.
onsite第一个人问了permutate string, 没什么好说的，基本就是背答案。有趣的是，
G onsite问过同样的问题，一个亚裔女的，我给解释了半天，愣说我的recursive有问
题。Paypal这个人至少很快认同我的code是对的。我内心的好感油然而生。然后他问了
Linux的fork, 写一段code用fork实现pipe，这个有些太system oriented了，我应该有
些函数参数都是没传对的，不过他似乎不是很care，关键是general idea。他们特别喜
欢... 阅读全帖 |
|
x********i
发帖数: 10 | 21 面我的是叫做item similarity组的一个principal engineer
人很好，先介绍了半天他们组大概做什么
其实就问了两个问题
第一个是问有两个web browsing的log files，第一个条目是customer ID，问怎样找出
其中的returning customer
我先说可以把这两文件的customer ID读到两个array去，然后sort再比较，这样 time
complexity是O(nlog(n))+O(n)
然后问可不可以O(n)，我就说用hash table，然后又问如果内存限制放不下这么大的
hash table怎么办，然后我就说可以把customer ID分成几段，多几个hash table，然
后hash collision用separate chaining解决
然后就问Fibonacci，我先写了个简单的recursive算法，然后问输入大数字会怎样，他
自己说会有memory exception,问不出问题的最大数字是多少，我就说32位系统里内存
的限制和stack/heap分配的比例，时间复杂度O(n^2)
最后就写了non-... 阅读全帖 |
|
x********i
发帖数: 10 | 22 面我的是叫做item similarity组的一个principal engineer
人很好，先介绍了半天他们组大概做什么
其实就问了两个问题
第一个是问有两个web browsing的log files，第一个条目是customer ID，问怎样找出
其中的returning customer
我先说可以把这两文件的customer ID读到两个array去，然后sort再比较，这样 time
complexity是O(nlog(n))+O(n)
然后问可不可以O(n)，我就说用hash table，然后又问如果内存限制放不下这么大的
hash table怎么办，然后我就说可以把customer ID分成几段，多几个hash table，然
后hash collision用separate chaining解决
然后就问Fibonacci，我先写了个简单的recursive算法，然后问输入大数字会怎样，他
自己说会有memory exception,问不出问题的最大数字是多少，我就说32位系统里内存
的限制和stack/heap分配的比例，时间复杂度O(n^2)
最后就写了non-... 阅读全帖 |
|
S**I
发帖数: 15689 | 23 ☆─────────────────────────────────────☆
fengzhongdi (fzd) 于 (Fri May 27 14:30:18 2011, 美东) 提到:
A的onsite,我尽量客观写,大家帮我分析一下
第一个 美国人, 两个string,问第一个是否包含第二个的全部character,扩展是求第一
个string最短的substring包含第二个中所有的character.
我的解法是hashtable, 然后扩展问题是O(n)那个,先找到第一个包含全部的,然后从头
开始删除,接着从尾巴增加那个.面试官表示满意.
OOD是设计card game
交流过程很融洽.
第二个 hiring manage,印度人, 这个人带我去吃饭,然后问了我电梯设计问题,纠缠在
什么时候读楼层,还有如何判断要不要停下来接人.说了快50分钟.我个人感觉还好,反正
他也是都是笑到最后
第三个,白人,一开始问我LRU cache的设计,我直接告诉他double linked list + hash
table,他很吃惊问我是不是准备过,我说是,然后换了一题Bian... 阅读全帖 |
|
r******n
发帖数: 170 | 24 大家在讨论不是去掉tail recursion，是怎么把1337的第一个方法改成支持not full
binary tree。
你这么写，意思跟KeithDeng的一样吧，代码上却没他的简洁。
在想怎么保留1337的recursion，还能支持所有的binary tree，觉得改动很大，不是大
牛们说的稍微改改 |
|
c*******r
发帖数: 309 | 25 问了一个链表，1－>2->3->4->5, 每两个交换，2－>1->4->3->5,如果单数
情况返回最后一个。要求recursive和iterative两种方法
这个如何recursive? |
|
a********m
发帖数: 15480 | 26 dp+recursive? 这种说法有点奇怪。也许说的是recursive+memo. 都差不多。不过dp好像定义也没有那么严格。
感觉是dp问题。每个分隔点可以完全分隔或者连接两边不同数目的字符加上两遍被隔
开的两块的结果。 |
|
n*******w
发帖数: 687 | 27 recursive的意思是指dp可以写成递归形式吧。
更具体的说，是dp + recursive + backtrace。比ls的那个O(n^2)应该还要好一点。
做法是
1 先把valid的单词存成一个tries
2 从头往尾扫，找到所有valid的单词。比如applepie，假设a和apple都是valid。
3 a和apple都试一试。a的话，subproblem变成了split pplepie。apple的话，
subproblem变成了split pie。
用到了tries来剪枝，同时递归的写dp，面试的时候时间上充裕点。 |
|
S**I
发帖数: 15689 | 28 ☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 13:45:24 2012, 美东) 提到:
稍微扩展了一下。
Boggle game。从一个字符开始找邻居字符然后继续找，形成一个word。条件是，形成
了word之后要继续找，因为可能有更长的word。一旦用了一个字符以后，就不可以重复
使用了。
返回可以找到最多word情况的所有word。
更新一下：可以同时从不同的位置开始找，不一定只从一个字符开始。
☆─────────────────────────────────────☆
autumnworm (虫子，秋天的) 于 (Tue Jan 17 13:46:32 2012, 美东) 提到:
看起来好像是基本的背包问题吧。
☆─────────────────────────────────────☆
mark (花生，微爷远爷的爸爸) 于 (Tue Jan 17 14:08:07 2012, 美东) 提到:
☆───────────────────... 阅读全帖 |
|
S**I
发帖数: 15689 | 29 ☆─────────────────────────────────────☆
happymermaid (娆) 于 (Wed Apr 6 14:03:00 2011, 美东) 提到:
加recruiter一共6人
4个白男，午饭是一个组的经理 像是 土耳其／印度？ 人
除了最后一个都比较nice
另外每个人有时间都问一遍我RA做的项目，说到想吐
1. java keyword
实现浮点数的平方根，经提醒搞出来了。要考虑小于1的特殊情况； 还要想time
complexity，相对于小数点后精确位数算如何时间复杂度
2. paint fill (toggle)。关键是要考虑space complexity，主要是method stack实时
一共有多少
说了组里的相关一个问题，大概说说TRIE，有一个improvement方法不好答，他说的
用一个计算load balance function，我吐
午饭是其中一个经理，详细讲了下组里的东西，基本和我做的有点相关，感觉他们招人还是很看背景的
3. 给一个数据结构数组，（parent, child）， 重建二叉数，... 阅读全帖 |
|
w**z
发帖数: 8232 | 30 You don't have your base step for your recursive match method. Your method
runs in to NPE eventually
Need to check t1.left/right, t2.left/righ == null. All of null, return true.
If children structure mismatch, (t1 has left, t2 doesn't, etc) return false.
If children structure match, recursively calling match with non-null
children |
|
P***P
发帖数: 1387 | 31 上周4背靠背了两个， 到现在没回复， 是不是挂了？
贴贴面经：
一面（老印）
0. 聊聊家常， 问问简历
1. 对oop理解：
我答abstract data type
2. 聊聊继承吧
我说了subtype跟interface
3. 多态理解
我说我不是搞programming language的，不太懂，就那回事， 爱咋咋滴。 他问多态是不
是跟generic差不多， 我说差不多吧. (后来想想不对啊， 他丫坑我)
4. 设计车库
我都想骂人了， 最讨厌这种oo题目， 答有车库有车位， 车库有入口，告诉你车子有没有空位
子，提示下说不同车型可以return不同相应的空车位
5. circular single linked list, 怎么反序打印
我答先把list翻转了， 然后打印， 程序都写出来后。 他说你不能把input改了啊，
我真想骂他怎么不早说， 我说上个stack不久玩了。重新写个stack版的
6. 问我知道hash吧， hash怎么判断hash function好不好， 什么时候用bst, 什么时候用
hash, time complexity多少.
他让我讲讲h... 阅读全帖 |
|
m*****a
发帖数: 636 | 32 心理素质好，google使用得当。
祝马上有好消息
上周4背靠背了两个， 到现在没回复， 是不是挂了？
贴贴面经：
一面（老印）
0. 聊聊家常， 问问简历
1. 对oop理解：
我答abstract data type
2. 聊聊继承吧
我说了subtype跟interface
3. 多态理解
我说我不是搞programming language的，不太懂，就那回事， 爱咋咋滴。 他问多态是
不是跟
generic差不多， 我说差不多吧. (后来想想不对啊， 他丫坑我)
4. 设计车库
我都想骂人了， 最讨厌这种oo题目， 答有车库有车位， 车库有入口，告诉你车子有
没有空位子，
提示下说不同车型可以return不同相应的空车位
5. circular single linked list, 怎么反序打印
我答先把list翻转了， 然后打印， 程序都写出来后。 他说你不能把input改了啊，
我真想骂他
怎么不早说， 我说上个stack不久玩了。重新写个stack版的
6. 问我知道hash吧， hash怎么判断hash function好不好， 什么时候用bst, 什么时
候用
... 阅读全帖 |
|
d****o
发帖数: 1055 | 33 他是不是就想要我上面写的recursion版本？不过recursion也需要stack，需要O(n)
space啊？
你过了没有？
asked |
|
d****o
发帖数: 1055 | 34 他是不是就想要我上面写的recursion版本？不过recursion也需要stack，需要O(n)
space啊？
你过了没有？
asked |
|
g**********y
发帖数: 14569 | 35 Amazon的onsite题目难度平均来说不算大，那些很变态的题目，除非人品非常不好，应
该是碰不到的。
多准备他家最喜欢的一些问题：
- 关于树的操作，这个是一定有的
- OO-design, 这个也是一定有的
- 字符串的操作，多半会是DFS/BFS search, Boggle那个很具有代表性，如果写得不够
好，去找好的code来读懂
- Recursive一定要写熟，全排列问题，含duplicate的全排列，这两个是写recursive
的代表题。
- 基本知识点的名词解释，这个我很不喜欢，但是他们喜欢问，没办法。看你说的最擅
长什么语言，特别准备那个语言的。
Advices。 |
|
S******t
发帖数: 151 | 36 Google "selection algorithm" to find out the answer.
Basically speaking we are changing from two recursions in each call of quick
sort to only one recursion and we have an expected O(n) algorithm. |
|
w****x
发帖数: 2483 | 37
说的不错.我想补充一下:
Iteration能完全代替recursion的只有tail recursion或用栈.
题目做多了很容易感觉出哪题需要用到DP,很多地方不一定要从公式推出.
DP不明显的问题上来说, 需要仔细观察你的解法中是不是有 "重复计算", 把"重复计算
"用数据结构存储最优子结构就可以了.
有的DP可以继续化简空间复杂度, 比如LCS可以把空间复杂度O(n^2)减少到O(n),因为第
n步的DP只 和前一步(第n-1步)的最优子结果有关, 从公式上也可以看出F(n)只和F(n-1
)有关. |
|
w****x
发帖数: 2483 | 38
说的不错.我想补充一下:
Iteration能完全代替recursion的只有tail recursion或用栈.
题目做多了很容易感觉出哪题需要用到DP,很多地方不一定要从公式推出.
DP不明显的问题上来说, 需要仔细观察你的解法中是不是有 "重复计算", 把"重复计算
"用数据结构存储最优子结构就可以了.
有的DP可以继续化简空间复杂度, 比如LCS可以把空间复杂度O(n^2)减少到O(n),因为第
n步的DP只 和前一步(第n-1步)的最优子结果有关, 从公式上也可以看出F(n)只和F(n-1
)有关. |
|
s********l
发帖数: 998 | 39 啊。。。
你看的是第几版啊？
我就看的第四版 我刚翻了一下 就有一章 叫recursion 没有 recursion and DP啊。。。
看内容 和你说的很相似 |
|
U*********y
发帖数: 54 | 40 写recursive的程序时, 经常会需要建某个variable或data structure,然后多次用到它
并需要它maintain value between calls. 一般有两种方法可以选择, 一种可以在
recursive的函数里declare它static; 另一种是在函数的wrapper里declare它然后pass by
reference.
一直想知道哪种方法更好,大家有没有什么见解? |
|
l*****a
发帖数: 14598 | 41 真的吗？
stack其实就是recursion.难道recursion里会重复调用同一个结点？
我明天写写看看，你业可以拿出来证据 |
|
h****e
发帖数: 928 | 42 二爷真的是recursion修炼到一字师的地步了。:)
Recursion怎么个做法？ |
|
w****x
发帖数: 2483 | 43 top down recursion, recursion下来的函数要传递range |
|
w****x
发帖数: 2483 | 44
恩, recursion前后要还原状态, 用掉的node从vector里erase, recursion返回后再插
入, 没时间写, 以后再看 |
|
p*i
发帖数: 411 | 45 想让你用recursion？
有些面试官真心喜欢recursion |
|
c*******r
发帖数: 610 | 46 下午 onsite， 下面是面经，公司名字就不说了。 sf某 startup
首先进来一白男 ，director，直接上题目，问
n queens 的一个可行solution， 我 一开始 没有正确理解意思，给了bf 方法，他说
不是他想要的 ，搞半天 ，搞清楚是他要recursive solution，后来慢慢搞定。。。。
交流过程中对我的想法不置可否，自己看手机。。。。。
然后 engineering 经理, SQL问题，然后问了道 c 程序题，指出程序里面全部问题 ，
然后扯淡，oo design，没问什么细节 ，这个人 主要high level
第三个人，问isIdenticalTree, 然后问了道给定一棵 二叉树，找出树里面离根节点最
近的节点，使得它与给定的数值相等，这个我给了两个方法 ，一个是 level order
traversal,另一个是 recursive,问了时间和空间复杂度，然后给了几个例子，让走一
遍程序。
第四个，临时换人，我之前不知道， 出题让parse一个 string， 返回一个满足 给定
regular exp的 字符串数组 。。。。。这哥们很... 阅读全帖 |
|
d********g
发帖数: 10550 | 47 这么简单也挂，不应该啊。这题考点就两个，1是Python list内元素可以是任意对象的
概念，2是Python里赋值是传引用的概念
传引用这个，最常考的是交换a、b的值
只需要
a, b = b, a
即可。只要答上来保准面试官眼睛发亮
Python经常考的是一题多解，所谓Pythonic way（文艺解法）和传统（二逼）解法
比如一道binary tree遍历：
给一个tree和一个func，输出一个func过滤后的in-order list
二逼解法：recursion，可以在recursion过程中用func，也可以在最后用。和别的语言
没什么区别，不好看，不多说了
文艺解法：art_list = map(flatten(tree), func)，然后flatten实现一个简单的in-
order遍历。这么做可以表明你对map/filter之类的掌握程度
Python的list comprehension也是常考的，偏技术的考官都期待你用文艺解法
不过遇到非技术的考官，你说太文艺了反而听不懂，那就尽量回答得二逼一点 |
|
d********g
发帖数: 10550 | 48 这么简单也挂，不应该啊。这题考点就两个，1是Python list内元素可以是任意对象的
概念，2是Python里赋值是传引用的概念
传引用这个，最常考的是交换a、b的值
只需要
a, b = b, a
即可。只要答上来保准面试官眼睛发亮
Python经常考的是一题多解，所谓Pythonic way（文艺解法）和传统（二逼）解法
比如一道binary tree遍历：
给一个tree和一个func，输出一个func过滤后的in-order list
二逼解法：recursion，可以在recursion过程中用func，也可以在最后用。和别的语言
没什么区别，不好看，不多说了
文艺解法：art_list = map(flatten(tree), func)，然后flatten实现一个简单的in-
order遍历。这么做可以表明你对map/filter之类的掌握程度
Python的list comprehension也是常考的，偏技术的考官都期待你用文艺解法
不过遇到非技术的考官，你说太文艺了反而听不懂，那就尽量回答得二逼一点 |
|
l*****z
发帖数: 3022 | 49 这题还算正常，不过是比较难的，我在google就栽在这个题上了。后来回来好好想了想
，其实就是个递归，每层里for loop to increase the length of the current word
by one, if it is a word goto the next recursion, but prepare to further
increase if the next recursion return false. |
|
l*****z
发帖数: 3022 | 50 这题还算正常，不过是比较难的，我在google就栽在这个题上了。后来回来好好想了想
，其实就是个递归，每层里for loop to increase the length of the current word
by one, if it is a word goto the next recursion, but prepare to further
increase if the next recursion return false. |
|
