logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
onsite后收到A家的拒信，面经。
avatar
onsite后收到A家的拒信，面经。# JobHunting - 待字闺中
i*7
1 楼
第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
母，但是变出来的都是valid word。
例子：head->heal->teal->tell->tall->tail
给你一个input和target，判断input能不能到达target。
说算法复杂度。
第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
第三个面试官：求平方根。不能用牛顿迭代法。
第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
栈）
第五个面试官：估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？
忘了说了，这题还有一个follow up：
如果让你设计编译器的栈，你怎么设计？
第二，先写一个mergesort。
然后问你算法复杂度，但是有条件：假如你每访问一个整型数的算法复杂度为o(a)，总
的算法复杂度是多少。
（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）
avatar
y*g
2 楼
o(a), a是什么东西？访问每个整形数 包括 index++这种吗？
avatar
H*e
3 楼
interesting; "不能用牛顿迭代法"
why?

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
i*7
4 楼
其实具体来说是这样的。
有一个类
class A
{
int a;
string b;}
你只能通过geta()来访问a，但是每次geta()都会对string b进行操作，
所以geta()的时间复杂度取决于b的长度
假设geta()的时间复杂度是o(length)，length是b的平均长度。
就求总的时间复杂度。

【在 y*******g 的大作中提到】
: o(a), a是什么东西？访问每个整形数 包括 index++这种吗？
avatar
i*7
5 楼
我当时一听这道题目，心头一喜，眉头深锁，然后过了一会儿，我说：我猜，能用牛顿
迭代法吧？
她说：不让你用牛顿迭代法呢。任何数学上tricky的方法都不让你用呢。

【在 H***e 的大作中提到】
: interesting; "不能用牛顿迭代法"
: why?
avatar
t*e
6 楼
二叉树preorder非递归遍历这题树的节点有没有parent指针？没有的话还真不知道怎么
做。
avatar
i*7
7 楼
他说可以有。就是做O(1)不用堆栈的版本可以有，其他都不可以有。。

【在 t******e 的大作中提到】
: 二叉树preorder非递归遍历这题树的节点有没有parent指针？没有的话还真不知道怎么
: 做。
avatar
w*o
8 楼
求平方根的题，是用binary search?
还有这个函数的原型是什么？输入是float,还是int,输出呢？
就是问 原型是 float sqrt(float x)? 还是 int sqrt(int x)?
xiexie !

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
i*7
9 楼
double.
对，我最后给的答案就是binary search。然后她还问了一下算法复杂度。

【在 w****o 的大作中提到】
: 求平方根的题，是用binary search?
: 还有这个函数的原型是什么？输入是float,还是int,输出呢？
: 就是问 原型是 float sqrt(float x)? 还是 int sqrt(int x)?
: xiexie !
avatar
H*e
10 楼
我猜她不会

【在 i*********7 的大作中提到】
: 我当时一听这道题目，心头一喜，眉头深锁，然后过了一会儿，我说：我猜，能用牛顿
: 迭代法吧？
: 她说：不让你用牛顿迭代法呢。任何数学上tricky的方法都不让你用呢。
avatar
w*o
11 楼
这个scroller是什么东东？怎么跟股票有关系？能否讲讲？难道这个是经典的题？
“
第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
”

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
l*8
12 楼
mergesort
O(a*n + n*logn)

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
t*7
13 楼
第一题就是深度遍历???还是有很牛的搞法?
avatar
p*2
14 楼

＋DP吧

【在 t*********7 的大作中提到】
: 第一题就是深度遍历???还是有很牛的搞法?
avatar
w*x
15 楼
"写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
右子树的leftmost, 是右节点的话就再往上爬
avatar
w*x
16 楼
"估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？"
程序跑和compiler有什么关系??
avatar
p*2
17 楼

stack是compiler搞的吧？

【在 w****x 的大作中提到】
: "估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
: 栈的具体运作是怎样的？"
: 程序跑和compiler有什么关系??
avatar
w*x
18 楼
"（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）"
为什么nalogn不对??
每次便利na, 遍历logn次啊
avatar
w*x
19 楼

好吧, 那程序跑得时候一个线程对应一个stack, call 一个function就套一个stack,
return一个function就收起一个stack. stack表达方式就是esp寄存器是栈顶, ebi是栈
基址, ebi+xxx对参数寻址, ebi-xxx对局部变量寻址. 当函数返回的时候esp = ebi +
xxx(参数空间), 当call一个函数的时候先push参数, 然后ebi = esp, 然后esp + 所有
该函数对应的局部变量空间. 这么答差不多了吧....

【在 p*****2 的大作中提到】
:
: stack是compiler搞的吧？
avatar
p*2
20 楼

preorder吗？

【在 w****x 的大作中提到】
: "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
: 有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
: 右子树的leftmost, 是右节点的话就再往上爬
avatar
p*2
21 楼

+
挺详细，我都记不清楚了。

【在 w****x 的大作中提到】
:
: 好吧, 那程序跑得时候一个线程对应一个stack, call 一个function就套一个stack,
: return一个function就收起一个stack. stack表达方式就是esp寄存器是栈顶, ebi是栈
: 基址, ebi+xxx对参数寻址, ebi-xxx对局部变量寻址. 当函数返回的时候esp = ebi +
: xxx(参数空间), 当call一个函数的时候先push参数, 然后ebi = esp, 然后esp + 所有
: 该函数对应的局部变量空间. 这么答差不多了吧....
avatar
p*2
22 楼
感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
avatar
w*x
23 楼

Oh, 看成in-order了

【在 p*****2 的大作中提到】
: 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
avatar
w*x
24 楼
pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
上爬
avatar
p*2
25 楼

嗯。应该还好。不算很难的题。

【在 w****x 的大作中提到】
: pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
: 上爬
avatar
w*o
26 楼
esp 和 ebi有什么区别？
感觉他们可以用一个寄存器就够了。
写了个dummy的代码，能不能给分析一下函数调用的时候stack的变化，和相关寄存器的
值得变化？
比如
int add(int a, int b)
{
int c;
c = a + b;
return c;
}
int main()
{
int x = 1;
int y = 2;
int z;
>>>>>>>>能否说说调用add前后stack和寄存器的情况
z = add(x, y);
>>>>>>>
printf("%d\n", z);
return 0;
}

+

【在 w****x 的大作中提到】
: pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
: 上爬
avatar
w*x
27 楼

不记得了， 看看反汇编就知道了

【在 w****o 的大作中提到】
: esp 和 ebi有什么区别？
: 感觉他们可以用一个寄存器就够了。
: 写了个dummy的代码，能不能给分析一下函数调用的时候stack的变化，和相关寄存器的
: 值得变化？
: 比如
: int add(int a, int b)
: {
: int c;
: c = a + b;
: return c;
avatar
S*t
28 楼
第一题和DP没有一毛钱的关系吧……

【在 p*****2 的大作中提到】
:
: 嗯。应该还好。不算很难的题。
avatar
p*2
29 楼

我怎么感觉有呢？难道我感觉错误了？

【在 S******t 的大作中提到】
: 第一题和DP没有一毛钱的关系吧……
avatar
a*o
30 楼
第一题，第二题，第五题，有没有哪位大牛能够讲讲是怎么做的？尤其是第二题和第五
题，谢啦
avatar
a*o
31 楼
能讲解一下这个是怎么算出来的么？谢谢啦

【在 l*********8 的大作中提到】
: mergesort
: O(a*n + n*logn)
avatar
s*r
32 楼
这的确是一道好题，可以考很多设计。
-----------------------------------------------------
设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
avatar
l*8
33 楼
有一个类
class A
{
int a;
string b;}
你只能通过geta()来访问a，但是每次geta()都会对string b进行操作，
所以geta()的时间复杂度取决于b的长度
假设geta()的时间复杂度是o(length)，length是b的平均长度。
就求总的时间复杂度。
for an object of A, we only need to call geta() once and assign its return value to an integer.
so O(a*n + nlogn)

【在 a*******o 的大作中提到】
: 能讲解一下这个是怎么算出来的么？谢谢啦
avatar
p*2
34 楼

第一题写了一下，还不算容易。刚开始题目理解错了。
HashSet hs = new HashSet();
HashMap hm = new HashMap();
HashSet visited = new HashSet();
boolean Change(String a, String b)
{
visited.add(a);
if (a.equals(b))
return true;
if (hm.containsKey(a))
return hm.get(a);
char[] arr = a.toCharArray();
for (int i = 0; i < arr.length; i++)
{
if (arr[i] != b.charAt(i))
{
for (char c = 'a'; c <= 'z'; c++)
{
char tmp = arr[i];
arr[i] = c;
String str = new String(arr);
if (!visited.contains(str) && hs.contains(str)
&& Change(str, b))
{
hm.put(a, true);
return true;
}
arr[i] = tmp;
}
}
}
hm.put(a, false);
return false;
}

【在 a*******o 的大作中提到】
: 第一题，第二题，第五题，有没有哪位大牛能够讲讲是怎么做的？尤其是第二题和第五
: 题，谢啦
avatar
S*t
35 楼
……有什么关系，不就是建图再BFS/DFS么……

【在 p*****2 的大作中提到】
:
: 第一题写了一下，还不算容易。刚开始题目理解错了。
: HashSet hs = new HashSet();
: HashMap hm = new HashMap();
: HashSet visited = new HashSet();
: boolean Change(String a, String b)
: {
: visited.add(a);
: if (a.equals(b))
: return true;
avatar
p*2
36 楼

需要建图吗？

【在 S******t 的大作中提到】
: ……有什么关系，不就是建图再BFS/DFS么……
avatar
S*t
37 楼
我大概写一个吧，没编译，不知道靠谱不
#include
#include
#include
using namespace std;
string dict[MAXNUM];
vector graph[MAXNUM];
bool visited[MAXNUM];
bool diff_one(string a,string b) {
int len_a = (int)a.size();
int len_b = (int)b.size();
if (len_a != len_b) return false;
int cnt = 0;
for(int i=0;iif(a[i]!=b[i]) cnt++;
return cnt == 1;
}
void preprocess() {
int dict_sz = (int)dict.size();
for(int i=0;ifor(int j=i+1;jif(diff_one(dict[i],dict[j])) {
graph[i].push_back(j);
graph[j].push_back(i);
}
}
}
bool flag;
void dfs(int now, int dest) {
if(now==dest) flag = true;
if(flag) return;
visited[now] = true;
int num_adj = (int)graph[now].size();
for(int i=0;iif(!visited[graph[now][i]])
dfs(graph[now][i], dest);
}
void check(string a,string b) {
flag = false;
memset(visited,0,sizeof(visited));
preprocess();
int dict_sz = (int)dict.size();
for(int i=0;iif(dict[i] == a) startidx = i;
for(int i=0;iif(dict[i] == b) endidx = b;
dfs(startidx,endidx);
printf("%s\n",flag?"YES":"NO");
}

【在 p*****2 的大作中提到】
:
: 需要建图吗？
avatar
S*t
38 楼
这个就是看个人的编程风格和习惯了。
反正即使你不建图，本质上也是要去construct a graph on-the-fly的
而且先把图建好的好处是可以较为方便的处理multiple queries

【在 p*****2 的大作中提到】
:
: 需要建图吗？
avatar
i*7
39 楼
我刚毕业，申的当然是SDE I......最后一个人问的问题，我就没答的让他满意过。。。

【在 p*****2 的大作中提到】
: 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
avatar
i*7
40 楼
我也不知道，面试官最后不肯说答案。
他只给了我提示：用数学归纳法自己去思考一下。（就是说，如果只有一个节点，算几
次，两个呢？三个呢？四个呢？让我自己往下推试试。）
当然。。这已经是面试结束后的事儿了

【在 w****x 的大作中提到】
: "（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）"
: 为什么nalogn不对??
: 每次便利na, 遍历logn次啊
avatar
p*2
41 楼

。。
你stack那个答的怎么样？这个复杂度的我还没时间想呢。不容易。

【在 i*********7 的大作中提到】
: 我刚毕业，申的当然是SDE I......最后一个人问的问题，我就没答的让他满意过。。。
avatar
i*7
42 楼
答成屎一样。他让我随便写一个程序，然后问我，跑完了程序后，堆栈应该长啥样。
堆栈我倒没有画错。但是解释的跟屎一样。

【在 p*****2 的大作中提到】
:
: 。。
: 你stack那个答的怎么样？这个复杂度的我还没时间想呢。不容易。
avatar
i*7
43 楼
我觉得不是，她肯定会。
她说这题可以有很多种解法。
感觉现在A家反面经的倾向很明显，这一题面经里面的标准解就是牛顿迭代。

【在 H***e 的大作中提到】
: 我猜她不会
avatar
S*t
44 楼
……哪有什么”面经标准解“这个说法
面经还不是面试的人写的……

【在 i*********7 的大作中提到】
: 我觉得不是，她肯定会。
: 她说这题可以有很多种解法。
: 感觉现在A家反面经的倾向很明显，这一题面经里面的标准解就是牛顿迭代。
avatar
i*7
45 楼
我的意思是面经里面大多人提到这个问题的时候都会提到牛顿迭代法。。

【在 S******t 的大作中提到】
: ……哪有什么”面经标准解“这个说法
: 面经还不是面试的人写的……
avatar
i*7
46 楼
而且最后面试我的人都直接说了：我知道你们都会上网查，亚马逊也给我们面试官自己
设计题目的权利，我们只好自己重新设计一些别的难题了。当然，这也是面试结束后，
我和他闲聊的时候他说的

【在 S******t 的大作中提到】
: ……哪有什么”面经标准解“这个说法
: 面经还不是面试的人写的……
avatar
p*2
47 楼

我就不会牛顿迭代

【在 i*********7 的大作中提到】
: 我的意思是面经里面大多人提到这个问题的时候都会提到牛顿迭代法。。
avatar
i*7
48 楼
咳咳。好吧。只是我的印象。
反正给我的感觉是，要是你回答的比较快的。他们会认为你做过，然后立马就让你换个
角度去想。

【在 p*****2 的大作中提到】
:
: 我就不会牛顿迭代
avatar
y*n
49 楼
本来想找个比二分法更好的逼近方法，结果写成这下面这样。
用公式推了一下，居然是牛顿迭代的等效变形。居然没跳出牛顿的手掌心。
double Sqrt(double value, double acceptDifference)
{
double root = 1;
double difference = value - root * root;
while (Math.Abs(difference) > acceptDifference)
{
root += difference / 2 / root;
difference = value - root * root;
}
return root;
}
没做输入检查
avatar
G*s
50 楼
谢谢分享。

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
w*x
51 楼

数学归纳法....
我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
是不是面试官自己没弄清楚.

【在 i*********7 的大作中提到】
: 我也不知道，面试官最后不肯说答案。
: 他只给了我提示：用数学归纳法自己去思考一下。（就是说，如果只有一个节点，算几
: 次，两个呢？三个呢？四个呢？让我自己往下推试试。）
: 当然。。这已经是面试结束后的事儿了
avatar
i*7
52 楼
我不确定。
我第一个反应给的就是nalogn的答案，他斩钉截铁的说不对。
而且他说这题不是nalogn，很大程度上是因为这题目用的sort方法是mergesort。所以
不是这个。但他也说，这题目答案里面会有log存在。

【在 w****x 的大作中提到】
:
: 数学归纳法....
: 我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
: 是不是面试官自己没弄清楚.
avatar
i*7
53 楼
而且他给的例子的确好像有些道理。
他有一步步引导我去看：
他让我算了只有一个节点，两个节点，三个节点的时候，该有几次的运算。
分别是o(a),o(2a),o(4a).
而且后来我还推了一下，有四个节点的时候，应该存在了o(6a)次的计算。
这好像就不太符合nalogn的答案了。

【在 w****x 的大作中提到】
:
: 数学归纳法....
: 我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
: 是不是面试官自己没弄清楚.
avatar
q*y
54 楼
O(1)空间非递归preorder，没有parent指针不行吧。难道有更牛逼的解法？
求mergsort那题复杂度正解。

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
w*x
55 楼

你看看对于普通的merge sort, nalogn的来源是每次都作2分, 就像一颗二叉树一样,
根节点是原始数组, 第一次分成两个相等的小数组, 看成两个子节点, 每个子节点n/2
个元素, 加起来还是n个.再往下分, 第3层有2^2 = 4个子节点, 每个节点n/4个元素,
一共还是n个.
所以说每层有n个节点, 一共有logn层. 对于每层你做merge的时间复杂度是na, 所以总
时间复杂度是nalogn, 不知道他想怎么算

【在 i*********7 的大作中提到】
: 我不确定。
: 我第一个反应给的就是nalogn的答案，他斩钉截铁的说不对。
: 而且他说这题不是nalogn，很大程度上是因为这题目用的sort方法是mergesort。所以
: 不是这个。但他也说，这题目答案里面会有log存在。
avatar
g*e
56 楼
lz这个是sdeI的面经啊？怎么这么难。最后mergesort a难道不是常数吗？我觉得就是
nlogn
avatar
i*7
57 楼
嗯，现在的SDE I就可以逆天了。。。
感觉自己都超水平发挥了。前面四个都还好。。
最后一个倒了。可能系统设计的时候也给了我negative。他说我没有考虑到server会
down的情况，说要设计一个数据库进行备份。。。

【在 g*********e 的大作中提到】
: lz这个是sdeI的面经啊？怎么这么难。最后mergesort a难道不是常数吗？我觉得就是
: nlogn
avatar
l*8
58 楼
还真是n*a*logn啊。 我之前想错了。

2

【在 w****x 的大作中提到】
:
: 你看看对于普通的merge sort, nalogn的来源是每次都作2分, 就像一颗二叉树一样,
: 根节点是原始数组, 第一次分成两个相等的小数组, 看成两个子节点, 每个子节点n/2
: 个元素, 加起来还是n个.再往下分, 第3层有2^2 = 4个子节点, 每个节点n/4个元素,
: 一共还是n个.
: 所以说每层有n个节点, 一共有logn层. 对于每层你做merge的时间复杂度是na, 所以总
: 时间复杂度是nalogn, 不知道他想怎么算
avatar
q*y
59 楼
楼主说nalogn不对啊。

【在 l*********8 的大作中提到】
: 还真是n*a*logn啊。 我之前想错了。
:
: 2
avatar
l*8
60 楼
可能是要改进算法吧。 直接用merge sort就是nalogn

【在 q***y 的大作中提到】
: 楼主说nalogn不对啊。
avatar
z*8
61 楼
pre-order iterative 不用stack， 用parent pointer怎么做？需要mark node吗？

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
i*7
62 楼
要一个previous指针指向你前面遍历过的节点。
然后分三个case做。
1.上一个指针是parent。
2.上一个指针是自己的左子树。
3.上一个指针是自己的右子树。
好好想想吧

【在 z*********8 的大作中提到】
: pre-order iterative 不用stack， 用parent pointer怎么做？需要mark node吗？
avatar
i*7
63 楼
第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
母，但是变出来的都是valid word。
例子：head->heal->teal->tell->tall->tail
给你一个input和target，判断input能不能到达target。
说算法复杂度。
第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
第三个面试官：求平方根。不能用牛顿迭代法。
第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
栈）
第五个面试官：估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？
忘了说了，这题还有一个follow up：
如果让你设计编译器的栈，你怎么设计？
第二，先写一个mergesort。
然后问你算法复杂度，但是有条件：假如你每访问一个整型数的算法复杂度为o(a)，总
的算法复杂度是多少。
（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）
avatar
y*g
64 楼
o(a), a是什么东西？访问每个整形数 包括 index++这种吗？
avatar
H*e
65 楼
interesting; "不能用牛顿迭代法"
why?

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
i*7
66 楼
其实具体来说是这样的。
有一个类
class A
{
int a;
string b;}
你只能通过geta()来访问a，但是每次geta()都会对string b进行操作，
所以geta()的时间复杂度取决于b的长度
假设geta()的时间复杂度是o(length)，length是b的平均长度。
就求总的时间复杂度。

【在 y*******g 的大作中提到】
: o(a), a是什么东西？访问每个整形数 包括 index++这种吗？
avatar
i*7
67 楼
我当时一听这道题目，心头一喜，眉头深锁，然后过了一会儿，我说：我猜，能用牛顿
迭代法吧？
她说：不让你用牛顿迭代法呢。任何数学上tricky的方法都不让你用呢。

【在 H***e 的大作中提到】
: interesting; "不能用牛顿迭代法"
: why?
avatar
t*e
68 楼
二叉树preorder非递归遍历这题树的节点有没有parent指针？没有的话还真不知道怎么
做。
avatar
i*7
69 楼
他说可以有。就是做O(1)不用堆栈的版本可以有，其他都不可以有。。

【在 t******e 的大作中提到】
: 二叉树preorder非递归遍历这题树的节点有没有parent指针？没有的话还真不知道怎么
: 做。
avatar
w*o
70 楼
求平方根的题，是用binary search?
还有这个函数的原型是什么？输入是float,还是int,输出呢？
就是问 原型是 float sqrt(float x)? 还是 int sqrt(int x)?
xiexie !

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
i*7
71 楼
double.
对，我最后给的答案就是binary search。然后她还问了一下算法复杂度。

【在 w****o 的大作中提到】
: 求平方根的题，是用binary search?
: 还有这个函数的原型是什么？输入是float,还是int,输出呢？
: 就是问 原型是 float sqrt(float x)? 还是 int sqrt(int x)?
: xiexie !
avatar
H*e
72 楼
我猜她不会

【在 i*********7 的大作中提到】
: 我当时一听这道题目，心头一喜，眉头深锁，然后过了一会儿，我说：我猜，能用牛顿
: 迭代法吧？
: 她说：不让你用牛顿迭代法呢。任何数学上tricky的方法都不让你用呢。
avatar
w*o
73 楼
这个scroller是什么东东？怎么跟股票有关系？能否讲讲？难道这个是经典的题？
“
第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
”

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
l*8
74 楼
mergesort
O(a*n + n*logn)

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
t*7
75 楼
第一题就是深度遍历???还是有很牛的搞法?
avatar
p*2
76 楼

＋DP吧

【在 t*********7 的大作中提到】
: 第一题就是深度遍历???还是有很牛的搞法?
avatar
w*x
77 楼
"写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
右子树的leftmost, 是右节点的话就再往上爬
avatar
w*x
78 楼
"估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？"
程序跑和compiler有什么关系??
avatar
p*2
79 楼

stack是compiler搞的吧？

【在 w****x 的大作中提到】
: "估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
: 栈的具体运作是怎样的？"
: 程序跑和compiler有什么关系??
avatar
w*x
80 楼
"（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）"
为什么nalogn不对??
每次便利na, 遍历logn次啊
avatar
w*x
81 楼

好吧, 那程序跑得时候一个线程对应一个stack, call 一个function就套一个stack,
return一个function就收起一个stack. stack表达方式就是esp寄存器是栈顶, ebi是栈
基址, ebi+xxx对参数寻址, ebi-xxx对局部变量寻址. 当函数返回的时候esp = ebi +
xxx(参数空间), 当call一个函数的时候先push参数, 然后ebi = esp, 然后esp + 所有
该函数对应的局部变量空间. 这么答差不多了吧....

【在 p*****2 的大作中提到】
:
: stack是compiler搞的吧？
avatar
p*2
82 楼

preorder吗？

【在 w****x 的大作中提到】
: "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
: 有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
: 右子树的leftmost, 是右节点的话就再往上爬
avatar
p*2
83 楼

+
挺详细，我都记不清楚了。

【在 w****x 的大作中提到】
:
: 好吧, 那程序跑得时候一个线程对应一个stack, call 一个function就套一个stack,
: return一个function就收起一个stack. stack表达方式就是esp寄存器是栈顶, ebi是栈
: 基址, ebi+xxx对参数寻址, ebi-xxx对局部变量寻址. 当函数返回的时候esp = ebi +
: xxx(参数空间), 当call一个函数的时候先push参数, 然后ebi = esp, 然后esp + 所有
: 该函数对应的局部变量空间. 这么答差不多了吧....
avatar
p*2
84 楼
感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
avatar
w*x
85 楼

Oh, 看成in-order了

【在 p*****2 的大作中提到】
: 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
avatar
w*x
86 楼
pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
上爬
avatar
p*2
87 楼

嗯。应该还好。不算很难的题。

【在 w****x 的大作中提到】
: pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
: 上爬
avatar
w*o
88 楼
esp 和 ebi有什么区别？
感觉他们可以用一个寄存器就够了。
写了个dummy的代码，能不能给分析一下函数调用的时候stack的变化，和相关寄存器的
值得变化？
比如
int add(int a, int b)
{
int c;
c = a + b;
return c;
}
int main()
{
int x = 1;
int y = 2;
int z;
>>>>>>>>能否说说调用add前后stack和寄存器的情况
z = add(x, y);
>>>>>>>
printf("%d\n", z);
return 0;
}

+

【在 w****x 的大作中提到】
: pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
: 上爬
avatar
w*x
89 楼

不记得了， 看看反汇编就知道了

【在 w****o 的大作中提到】
: esp 和 ebi有什么区别？
: 感觉他们可以用一个寄存器就够了。
: 写了个dummy的代码，能不能给分析一下函数调用的时候stack的变化，和相关寄存器的
: 值得变化？
: 比如
: int add(int a, int b)
: {
: int c;
: c = a + b;
: return c;
avatar
S*t
90 楼
第一题和DP没有一毛钱的关系吧……

【在 p*****2 的大作中提到】
:
: 嗯。应该还好。不算很难的题。
avatar
p*2
91 楼

我怎么感觉有呢？难道我感觉错误了？

【在 S******t 的大作中提到】
: 第一题和DP没有一毛钱的关系吧……
avatar
a*o
92 楼
第一题，第二题，第五题，有没有哪位大牛能够讲讲是怎么做的？尤其是第二题和第五
题，谢啦
avatar
a*o
93 楼
能讲解一下这个是怎么算出来的么？谢谢啦

【在 l*********8 的大作中提到】
: mergesort
: O(a*n + n*logn)
avatar
s*r
94 楼
这的确是一道好题，可以考很多设计。
-----------------------------------------------------
设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
avatar
l*8
95 楼
有一个类
class A
{
int a;
string b;}
你只能通过geta()来访问a，但是每次geta()都会对string b进行操作，
所以geta()的时间复杂度取决于b的长度
假设geta()的时间复杂度是o(length)，length是b的平均长度。
就求总的时间复杂度。
for an object of A, we only need to call geta() once and assign its return value to an integer.
so O(a*n + nlogn)

【在 a*******o 的大作中提到】
: 能讲解一下这个是怎么算出来的么？谢谢啦
avatar
p*2
96 楼

第一题写了一下，还不算容易。刚开始题目理解错了。
HashSet hs = new HashSet();
HashMap hm = new HashMap();
HashSet visited = new HashSet();
boolean Change(String a, String b)
{
visited.add(a);
if (a.equals(b))
return true;
if (hm.containsKey(a))
return hm.get(a);
char[] arr = a.toCharArray();
for (int i = 0; i < arr.length; i++)
{
if (arr[i] != b.charAt(i))
{
for (char c = 'a'; c <= 'z'; c++)
{
char tmp = arr[i];
arr[i] = c;
String str = new String(arr);
if (!visited.contains(str) && hs.contains(str)
&& Change(str, b))
{
hm.put(a, true);
return true;
}
arr[i] = tmp;
}
}
}
hm.put(a, false);
return false;
}

【在 a*******o 的大作中提到】
: 第一题，第二题，第五题，有没有哪位大牛能够讲讲是怎么做的？尤其是第二题和第五
: 题，谢啦
avatar
S*t
97 楼
……有什么关系，不就是建图再BFS/DFS么……

【在 p*****2 的大作中提到】
:
: 第一题写了一下，还不算容易。刚开始题目理解错了。
: HashSet hs = new HashSet();
: HashMap hm = new HashMap();
: HashSet visited = new HashSet();
: boolean Change(String a, String b)
: {
: visited.add(a);
: if (a.equals(b))
: return true;
avatar
p*2
98 楼

需要建图吗？

【在 S******t 的大作中提到】
: ……有什么关系，不就是建图再BFS/DFS么……
avatar
S*t
99 楼
我大概写一个吧，没编译，不知道靠谱不
#include
#include
#include
using namespace std;
string dict[MAXNUM];
vector graph[MAXNUM];
bool visited[MAXNUM];
bool diff_one(string a,string b) {
int len_a = (int)a.size();
int len_b = (int)b.size();
if (len_a != len_b) return false;
int cnt = 0;
for(int i=0;iif(a[i]!=b[i]) cnt++;
return cnt == 1;
}
void preprocess() {
int dict_sz = (int)dict.size();
for(int i=0;ifor(int j=i+1;jif(diff_one(dict[i],dict[j])) {
graph[i].push_back(j);
graph[j].push_back(i);
}
}
}
bool flag;
void dfs(int now, int dest) {
if(now==dest) flag = true;
if(flag) return;
visited[now] = true;
int num_adj = (int)graph[now].size();
for(int i=0;iif(!visited[graph[now][i]])
dfs(graph[now][i], dest);
}
void check(string a,string b) {
flag = false;
memset(visited,0,sizeof(visited));
preprocess();
int dict_sz = (int)dict.size();
for(int i=0;iif(dict[i] == a) startidx = i;
for(int i=0;iif(dict[i] == b) endidx = b;
dfs(startidx,endidx);
printf("%s\n",flag?"YES":"NO");
}

【在 p*****2 的大作中提到】
:
: 需要建图吗？
avatar
S*t
100 楼
这个就是看个人的编程风格和习惯了。
反正即使你不建图，本质上也是要去construct a graph on-the-fly的
而且先把图建好的好处是可以较为方便的处理multiple queries

【在 p*****2 的大作中提到】
:
: 需要建图吗？
avatar
i*7
101 楼
我刚毕业，申的当然是SDE I......最后一个人问的问题，我就没答的让他满意过。。。

【在 p*****2 的大作中提到】
: 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
avatar
i*7
102 楼
我也不知道，面试官最后不肯说答案。
他只给了我提示：用数学归纳法自己去思考一下。（就是说，如果只有一个节点，算几
次，两个呢？三个呢？四个呢？让我自己往下推试试。）
当然。。这已经是面试结束后的事儿了

【在 w****x 的大作中提到】
: "（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）"
: 为什么nalogn不对??
: 每次便利na, 遍历logn次啊
avatar
p*2
103 楼

。。
你stack那个答的怎么样？这个复杂度的我还没时间想呢。不容易。

【在 i*********7 的大作中提到】
: 我刚毕业，申的当然是SDE I......最后一个人问的问题，我就没答的让他满意过。。。
avatar
i*7
104 楼
答成屎一样。他让我随便写一个程序，然后问我，跑完了程序后，堆栈应该长啥样。
堆栈我倒没有画错。但是解释的跟屎一样。

【在 p*****2 的大作中提到】
:
: 。。
: 你stack那个答的怎么样？这个复杂度的我还没时间想呢。不容易。
avatar
i*7
105 楼
我觉得不是，她肯定会。
她说这题可以有很多种解法。
感觉现在A家反面经的倾向很明显，这一题面经里面的标准解就是牛顿迭代。

【在 H***e 的大作中提到】
: 我猜她不会
avatar
S*t
106 楼
……哪有什么”面经标准解“这个说法
面经还不是面试的人写的……

【在 i*********7 的大作中提到】
: 我觉得不是，她肯定会。
: 她说这题可以有很多种解法。
: 感觉现在A家反面经的倾向很明显，这一题面经里面的标准解就是牛顿迭代。
avatar
i*7
107 楼
我的意思是面经里面大多人提到这个问题的时候都会提到牛顿迭代法。。

【在 S******t 的大作中提到】
: ……哪有什么”面经标准解“这个说法
: 面经还不是面试的人写的……
avatar
i*7
108 楼
而且最后面试我的人都直接说了：我知道你们都会上网查，亚马逊也给我们面试官自己
设计题目的权利，我们只好自己重新设计一些别的难题了。当然，这也是面试结束后，
我和他闲聊的时候他说的

【在 S******t 的大作中提到】
: ……哪有什么”面经标准解“这个说法
: 面经还不是面试的人写的……
avatar
p*2
109 楼

我就不会牛顿迭代

【在 i*********7 的大作中提到】
: 我的意思是面经里面大多人提到这个问题的时候都会提到牛顿迭代法。。
avatar
i*7
110 楼
咳咳。好吧。只是我的印象。
反正给我的感觉是，要是你回答的比较快的。他们会认为你做过，然后立马就让你换个
角度去想。

【在 p*****2 的大作中提到】
:
: 我就不会牛顿迭代
avatar
y*n
111 楼
本来想找个比二分法更好的逼近方法，结果写成这下面这样。
用公式推了一下，居然是牛顿迭代的等效变形。居然没跳出牛顿的手掌心。
double Sqrt(double value, double acceptDifference)
{
double root = 1;
double difference = value - root * root;
while (Math.Abs(difference) > acceptDifference)
{
root += difference / 2 / root;
difference = value - root * root;
}
return root;
}
没做输入检查
avatar
G*s
112 楼
谢谢分享。

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
w*x
113 楼

数学归纳法....
我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
是不是面试官自己没弄清楚.

【在 i*********7 的大作中提到】
: 我也不知道，面试官最后不肯说答案。
: 他只给了我提示：用数学归纳法自己去思考一下。（就是说，如果只有一个节点，算几
: 次，两个呢？三个呢？四个呢？让我自己往下推试试。）
: 当然。。这已经是面试结束后的事儿了
avatar
i*7
114 楼
我不确定。
我第一个反应给的就是nalogn的答案，他斩钉截铁的说不对。
而且他说这题不是nalogn，很大程度上是因为这题目用的sort方法是mergesort。所以
不是这个。但他也说，这题目答案里面会有log存在。

【在 w****x 的大作中提到】
:
: 数学归纳法....
: 我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
: 是不是面试官自己没弄清楚.
avatar
i*7
115 楼
而且他给的例子的确好像有些道理。
他有一步步引导我去看：
他让我算了只有一个节点，两个节点，三个节点的时候，该有几次的运算。
分别是o(a),o(2a),o(4a).
而且后来我还推了一下，有四个节点的时候，应该存在了o(6a)次的计算。
这好像就不太符合nalogn的答案了。

【在 w****x 的大作中提到】
:
: 数学归纳法....
: 我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
: 是不是面试官自己没弄清楚.
avatar
q*y
116 楼
O(1)空间非递归preorder，没有parent指针不行吧。难道有更牛逼的解法？
求mergsort那题复杂度正解。

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
w*x
117 楼

你看看对于普通的merge sort, nalogn的来源是每次都作2分, 就像一颗二叉树一样,
根节点是原始数组, 第一次分成两个相等的小数组, 看成两个子节点, 每个子节点n/2
个元素, 加起来还是n个.再往下分, 第3层有2^2 = 4个子节点, 每个节点n/4个元素,
一共还是n个.
所以说每层有n个节点, 一共有logn层. 对于每层你做merge的时间复杂度是na, 所以总
时间复杂度是nalogn, 不知道他想怎么算

【在 i*********7 的大作中提到】
: 我不确定。
: 我第一个反应给的就是nalogn的答案，他斩钉截铁的说不对。
: 而且他说这题不是nalogn，很大程度上是因为这题目用的sort方法是mergesort。所以
: 不是这个。但他也说，这题目答案里面会有log存在。
avatar
g*e
118 楼
lz这个是sdeI的面经啊？怎么这么难。最后mergesort a难道不是常数吗？我觉得就是
nlogn
avatar
i*7
119 楼
嗯，现在的SDE I就可以逆天了。。。
感觉自己都超水平发挥了。前面四个都还好。。
最后一个倒了。可能系统设计的时候也给了我negative。他说我没有考虑到server会
down的情况，说要设计一个数据库进行备份。。。

【在 g*********e 的大作中提到】
: lz这个是sdeI的面经啊？怎么这么难。最后mergesort a难道不是常数吗？我觉得就是
: nlogn
avatar
l*8
120 楼
还真是n*a*logn啊。 我之前想错了。

2

【在 w****x 的大作中提到】
:
: 你看看对于普通的merge sort, nalogn的来源是每次都作2分, 就像一颗二叉树一样,
: 根节点是原始数组, 第一次分成两个相等的小数组, 看成两个子节点, 每个子节点n/2
: 个元素, 加起来还是n个.再往下分, 第3层有2^2 = 4个子节点, 每个节点n/4个元素,
: 一共还是n个.
: 所以说每层有n个节点, 一共有logn层. 对于每层你做merge的时间复杂度是na, 所以总
: 时间复杂度是nalogn, 不知道他想怎么算
avatar
q*y
121 楼
楼主说nalogn不对啊。

【在 l*********8 的大作中提到】
: 还真是n*a*logn啊。 我之前想错了。
:
: 2
avatar
l*8
122 楼
可能是要改进算法吧。 直接用merge sort就是nalogn

【在 q***y 的大作中提到】
: 楼主说nalogn不对啊。
avatar
z*8
123 楼
pre-order iterative 不用stack， 用parent pointer怎么做？需要mark node吗？

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
i*7
124 楼
要一个previous指针指向你前面遍历过的节点。
然后分三个case做。
1.上一个指针是parent。
2.上一个指针是自己的左子树。
3.上一个指针是自己的右子树。
好好想想吧

【在 z*********8 的大作中提到】
: pre-order iterative 不用stack， 用parent pointer怎么做？需要mark node吗？
avatar
l*5
125 楼
第一题构图+bfs的复杂度是多少?
avatar
c*t
126 楼
还真的不是nalogn
举例：3 1 4 2
第一次，3 1比较，4 2比较，读了4次 结果 1 3 2 4
第二次 1 3 与 2 4 merge, 1 2比较 3 2比较 3 4比较, 读了 6次 结果1 2 3 4
所以对于4个数，一共10a次 ！= a*4log4 (8a)。difference是因为merge步骤有的数要
反复读。
我计算出了前面6次的结果
0 2 6 10 16 22 28 34
归纳法,因为merge sort对n先split,分别处理完两段，再merge，所以公式如下：
f(1)=0
if even: f(2n)=2*f(n)+ (2n-1)*2 （2*f(n)是两段的cost, (2n-1)*2是merge的cost)
if odd: f(2n+1)=f(n)+f(n+1)+(2n)*2（f(n)+f(n+1)是两段的cost, (2n)*2是merge的
cost)
数学不行，哪位大侠能简化写成 f(n)=lg(n)...

【在 l*********8 的大作中提到】
: 可能是要改进算法吧。 直接用merge sort就是nalogn
avatar
j*y
127 楼
感觉递归式子就是
T(n) = 2T(n / 2) + O(an), 用 master定理算出来就是
an log n 阿

还真的不是nalogn
举例：3 1 4 2
第一次，3 1比较，4 2比较，读了4次 结果 1 3 2 4
第二次 1 3 与 2 4 merge, 1 2比较 3 2比较 3 4比较, 读了 6次 结果1 2 3 4
所以对于4个数，一共10a次 ！= a*4log4 (8a)。difference是因为merge步骤有的数要
反复读。
我计算出了前面6次的结果
0 2 6 10 16 22 28 34
归纳法,因为merge sort对n先split,分别处理完两段，再merge，所以公式如下：
f(1)=0
if even: f(2n)=2*f(n)+ (2n-1)*2 （2*f(n)是两段的cost, (2n-1)*2是merge的cost)
if odd: f(2n+1)=f(n)+f(n+1)+(2n)*2（f(n)+f(n+1)是两段的cost, (2n)*2是merge的
cost)
数学不行，哪位大侠能简化写成 f(n)=lg(n)...

【在 c********t 的大作中提到】
: 还真的不是nalogn
: 举例：3 1 4 2
: 第一次，3 1比较，4 2比较，读了4次 结果 1 3 2 4
: 第二次 1 3 与 2 4 merge, 1 2比较 3 2比较 3 4比较, 读了 6次 结果1 2 3 4
: 所以对于4个数，一共10a次 ！= a*4log4 (8a)。difference是因为merge步骤有的数要
: 反复读。
: 我计算出了前面6次的结果
: 0 2 6 10 16 22 28 34
: 归纳法,因为merge sort对n先split,分别处理完两段，再merge，所以公式如下：
: f(1)=0
avatar
c*t
128 楼
应该是 T(n) = 2T(n / 2) + O(a（n-1）*2)，看我的例子

【在 j*****y 的大作中提到】
: 感觉递归式子就是
: T(n) = 2T(n / 2) + O(an), 用 master定理算出来就是
: an log n 阿
:
: 还真的不是nalogn
: 举例：3 1 4 2
: 第一次，3 1比较，4 2比较，读了4次 结果 1 3 2 4
: 第二次 1 3 与 2 4 merge, 1 2比较 3 2比较 3 4比较, 读了 6次 结果1 2 3 4
: 所以对于4个数，一共10a次 ！= a*4log4 (8a)。difference是因为merge步骤有的数要
: 反复读。
avatar
j*y
129 楼
那还是 anlogn阿，这个2在这里没区别

【在 c********t 的大作中提到】
: 应该是 T(n) = 2T(n / 2) + O(a（n-1）*2)，看我的例子
avatar
c*t
130 楼
还是有区别的，公式写的有点问题，应该写成
T(n) = 2*T(n / 2) + a（n-1）*2

【在 j*****y 的大作中提到】
: 那还是 anlogn阿，这个2在这里没区别
avatar
j*y
131 楼
其实感觉面试的人设了一个陷阱， 需要比较 an 和 n的阶
这个时候就要考察 a 和 n的关系了
比如 如果 a = O(n)， 那么 T(n) = O(n^2)
如果a 是常数， T(n) = n log n
如果 a = O(log n)， T(n) = n (log(n))^2, 这个时候也可以写成 anlogn

【在 c********t 的大作中提到】
: 还是有区别的，公式写的有点问题，应该写成
: T(n) = 2*T(n / 2) + a（n-1）*2
avatar
c*t
132 楼
是的。这题我觉得把a当做n的等阶比较safe. 但你说的O(n^2)不对吧，怎么也应该比O(
anlogn)大吧。

【在 j*****y 的大作中提到】
: 其实感觉面试的人设了一个陷阱， 需要比较 an 和 n的阶
: 这个时候就要考察 a 和 n的关系了
: 比如 如果 a = O(n)， 那么 T(n) = O(n^2)
: 如果a 是常数， T(n) = n log n
: 如果 a = O(log n)， T(n) = n (log(n))^2, 这个时候也可以写成 anlogn
avatar
c*t
133 楼
第一题，字母是必须变为 target相应位置的字母吗？允许如下变换吗？
aa
ba
bc
cc

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
avatar
s*0
134 楼
题hao niu bi.
avatar
s*0
135 楼
How come a = O(n)? a = O(n) means the performance of reading a element is
affected by the size of the array.

【在 j*****y 的大作中提到】
: 其实感觉面试的人设了一个陷阱， 需要比较 an 和 n的阶
: 这个时候就要考察 a 和 n的关系了
: 比如 如果 a = O(n)， 那么 T(n) = O(n^2)
: 如果a 是常数， T(n) = n log n
: 如果 a = O(log n)， T(n) = n (log(n))^2, 这个时候也可以写成 anlogn
avatar
x*o
136 楼
sde1都这这么面？还给据了？
avatar
j*y
137 楼
haha, correct, nonsense for this case

【在 s****0 的大作中提到】
: How come a = O(n)? a = O(n) means the performance of reading a element is
: affected by the size of the array.
avatar
p*e
138 楼
如果用这个方法怎样，初中就学过
http://zhidao.baidu.com/question/146072268.html
上面方法还可以延伸到开立方的

【在 y****n 的大作中提到】
: 本来想找个比二分法更好的逼近方法，结果写成这下面这样。
: 用公式推了一下，居然是牛顿迭代的等效变形。居然没跳出牛顿的手掌心。
: double Sqrt(double value, double acceptDifference)
: {
: double root = 1;
: double difference = value - root * root;
: while (Math.Abs(difference) > acceptDifference)
: {
: root += difference / 2 / root;
: difference = value - root * root;
avatar
a*n
139 楼
这个难度，不复习半年不能上啊。
avatar
P*b
140 楼
preorder O(1)怎么做？

【在 a********n 的大作中提到】
: 这个难度，不复习半年不能上啊。
avatar
G*r
141 楼
亚麻的面试官最拽（不过他家的题目还是很有水平的）。如果只是一个人面的不好被拒
应该是被BarRaiser拒了。

【在 i*********7 的大作中提到】
: 第一个面试官：经典题，单词游戏，就是给你一个head，转成tail，一次只能变一个字
: 母，但是变出来的都是valid word。
: 例子：head->heal->teal->tell->tall->tail
: 给你一个input和target，判断input能不能到达target。
: 说算法复杂度。
: 第二个面试官：HR。设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
: 。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。
: 第三个面试官：求平方根。不能用牛顿迭代法。
: 第四个面试官：写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。（就是不用堆
相关阅读
有了 lintcode 还需要刷 leetcode 么？TinyUrl的design需要NON-SQL 还是SQL16万名Uber员工将东家告上法庭 (转载)靠谱的startup，除了uber、airbnb还有哪些？EQ靠锻炼：软软的鸠头萨提亚的经验 (转载)【内部推荐】长期提供Google内推-当天回复-可以加微信-提供建议求比较2个offer老中和老印招人的标准。ICC的外包太黑了，连工资都不发如果辞职公司一般过多久withdraw H1B?请指教怎么选择uber和airbnb？也说LENDING CLUB，BANK IT， PAYPALStaff Software Engineer是做什么的？和recruiter在学校Starbucks见面着装应该正式到什么程度？连续两天挂在国人手里，snapchat＋zenefits狗家 senior是 t 几？系统设计题请教一下palindrome partitioning用memoization的问题西雅图consulting公司招contractor借人气问hsa 账户
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。