i*********7
发帖数: 348 | 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)，你就输了。。） |
y*******g
发帖数: 6599 | 2 o(a), a是什么东西？访问每个整形数 包括 index++这种吗？ |
H***e
发帖数: 476 | 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)的版本。（就是不用堆
|
i*********7
发帖数: 348 | 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++这种吗？
|
i*********7
发帖数: 348 | 5 我当时一听这道题目，心头一喜，眉头深锁，然后过了一会儿，我说：我猜，能用牛顿
迭代法吧？
她说：不让你用牛顿迭代法呢。任何数学上tricky的方法都不让你用呢。
【在 H***e 的大作中提到】
: interesting; "不能用牛顿迭代法"
: why?
|
t******e
发帖数: 98 | 6 二叉树preorder非递归遍历这题树的节点有没有parent指针？没有的话还真不知道怎么
做。 |
i*********7
发帖数: 348 | 7 他说可以有。就是做O(1)不用堆栈的版本可以有，其他都不可以有。。
【在 t******e 的大作中提到】
: 二叉树preorder非递归遍历这题树的节点有没有parent指针？没有的话还真不知道怎么
: 做。
|
w****o
发帖数: 2260 | 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)的版本。（就是不用堆
|
i*********7
发帖数: 348 | 9 double.
对，我最后给的答案就是binary search。然后她还问了一下算法复杂度。
【在 w****o 的大作中提到】
: 求平方根的题，是用binary search?
: 还有这个函数的原型是什么？输入是float,还是int,输出呢？
: 就是问 原型是 float sqrt(float x)? 还是 int sqrt(int x)?
: xiexie !
|
H***e
发帖数: 476 | 10 我猜她不会
【在 i*********7 的大作中提到】
: 我当时一听这道题目，心头一喜，眉头深锁，然后过了一会儿，我说：我猜，能用牛顿
: 迭代法吧？
: 她说：不让你用牛顿迭代法呢。任何数学上tricky的方法都不让你用呢。
|
|
|
w****o
发帖数: 2260 | 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)的版本。（就是不用堆
|
l*********8
发帖数: 4642 | 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)的版本。（就是不用堆
|
t*********7
发帖数: 255 | |
p*****2
发帖数: 21240 | 14
＋DP吧
【在 t*********7 的大作中提到】
: 第一题就是深度遍历???还是有很牛的搞法?
|
w****x
发帖数: 2483 | 15 "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
右子树的leftmost, 是右节点的话就再往上爬 |
w****x
发帖数: 2483 | 16 "估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？"
程序跑和compiler有什么关系?? |
p*****2
发帖数: 21240 | 17
stack是compiler搞的吧？
【在 w****x 的大作中提到】
: "估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
: 栈的具体运作是怎样的？"
: 程序跑和compiler有什么关系??
|
w****x
发帖数: 2483 | 18 "（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）"
为什么nalogn不对??
每次便利na, 遍历logn次啊 |
w****x
发帖数: 2483 | 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搞的吧？
|
p*****2
发帖数: 21240 | 20
preorder吗？
【在 w****x 的大作中提到】
: "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
: 有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
: 右子树的leftmost, 是右节点的话就再往上爬
|
|
|
p*****2
发帖数: 21240 | 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 + 所有
: 该函数对应的局部变量空间. 这么答差不多了吧....
|
p*****2
发帖数: 21240 | 22 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？ |
w****x
发帖数: 2483 | 23
Oh, 看成in-order了
【在 p*****2 的大作中提到】
: 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
|
w****x
发帖数: 2483 | 24 pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
上爬 |
p*****2
发帖数: 21240 | 25
嗯。应该还好。不算很难的题。
【在 w****x 的大作中提到】
: pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
: 上爬
|
w****o
发帖数: 2260 | 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差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
: 上爬
|
w****x
发帖数: 2483 | 27
不记得了， 看看反汇编就知道了
【在 w****o 的大作中提到】
: esp 和 ebi有什么区别？
: 感觉他们可以用一个寄存器就够了。
: 写了个dummy的代码，能不能给分析一下函数调用的时候stack的变化，和相关寄存器的
: 值得变化？
: 比如
: int add(int a, int b)
: {
: int c;
: c = a + b;
: return c;
|
S******t
发帖数: 151 | 28 第一题和DP没有一毛钱的关系吧……
【在 p*****2 的大作中提到】
:
: 嗯。应该还好。不算很难的题。
|
p*****2
发帖数: 21240 | 29
我怎么感觉有呢？难道我感觉错误了？
【在 S******t 的大作中提到】
: 第一题和DP没有一毛钱的关系吧……
|
a*******o
发帖数: 67 | 30 第一题，第二题，第五题，有没有哪位大牛能够讲讲是怎么做的？尤其是第二题和第五
题，谢啦 |
|
|
a*******o
发帖数: 67 | 31 能讲解一下这个是怎么算出来的么？谢谢啦
【在 l*********8 的大作中提到】
: mergesort
: O(a*n + n*logn)
|
s********r
发帖数: 137 | 32 这的确是一道好题，可以考很多设计。
-----------------------------------------------------
设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。 |
l*********8
发帖数: 4642 | 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 的大作中提到】
: 能讲解一下这个是怎么算出来的么？谢谢啦
|
p*****2
发帖数: 21240 | 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 的大作中提到】
: 第一题，第二题，第五题，有没有哪位大牛能够讲讲是怎么做的？尤其是第二题和第五
: 题，谢啦
|
S******t
发帖数: 151 | 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;
|
p*****2
发帖数: 21240 | 36
需要建图吗？
【在 S******t 的大作中提到】
: ……有什么关系，不就是建图再BFS/DFS么……
|
S******t
发帖数: 151 | 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;i
if(a[i]!=b[i]) cnt++;
return cnt == 1;
}
void preprocess() {
int dict_sz = (int)dict.size();
for(int i=0;i
for(int j=i+1;j
if(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;i
if(!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;i
if(dict[i] == a) startidx = i;
for(int i=0;i
if(dict[i] == b) endidx = b;
dfs(startidx,endidx);
printf("%s\n",flag?"YES":"NO");
}
【在 p*****2 的大作中提到】
:
: 需要建图吗？
|
S******t
发帖数: 151 | 38 这个就是看个人的编程风格和习惯了。
反正即使你不建图，本质上也是要去construct a graph on-the-fly的
而且先把图建好的好处是可以较为方便的处理multiple queries
【在 p*****2 的大作中提到】
:
: 需要建图吗？
|
i*********7
发帖数: 348 | 39 我刚毕业，申的当然是SDE I......最后一个人问的问题，我就没答的让他满意过。。。
【在 p*****2 的大作中提到】
: 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
|
i*********7
发帖数: 348 | 40 我也不知道，面试官最后不肯说答案。
他只给了我提示：用数学归纳法自己去思考一下。（就是说，如果只有一个节点，算几
次，两个呢？三个呢？四个呢？让我自己往下推试试。）
当然。。这已经是面试结束后的事儿了
【在 w****x 的大作中提到】
: "（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）"
: 为什么nalogn不对??
: 每次便利na, 遍历logn次啊
|
|
|
p*****2
发帖数: 21240 | 41
。。
你stack那个答的怎么样？这个复杂度的我还没时间想呢。不容易。
【在 i*********7 的大作中提到】
: 我刚毕业，申的当然是SDE I......最后一个人问的问题，我就没答的让他满意过。。。
|
i*********7
发帖数: 348 | 42 答成屎一样。他让我随便写一个程序，然后问我，跑完了程序后，堆栈应该长啥样。
堆栈我倒没有画错。但是解释的跟屎一样。
【在 p*****2 的大作中提到】
:
: 。。
: 你stack那个答的怎么样？这个复杂度的我还没时间想呢。不容易。
|
i*********7
发帖数: 348 | 43 我觉得不是，她肯定会。
她说这题可以有很多种解法。
感觉现在A家反面经的倾向很明显，这一题面经里面的标准解就是牛顿迭代。
【在 H***e 的大作中提到】
: 我猜她不会
|
S******t
发帖数: 151 | 44 ……哪有什么”面经标准解“这个说法
面经还不是面试的人写的……
【在 i*********7 的大作中提到】
: 我觉得不是，她肯定会。
: 她说这题可以有很多种解法。
: 感觉现在A家反面经的倾向很明显，这一题面经里面的标准解就是牛顿迭代。
|
i*********7
发帖数: 348 | 45 我的意思是面经里面大多人提到这个问题的时候都会提到牛顿迭代法。。
【在 S******t 的大作中提到】
: ……哪有什么”面经标准解“这个说法
: 面经还不是面试的人写的……
|
i*********7
发帖数: 348 | 46 而且最后面试我的人都直接说了：我知道你们都会上网查，亚马逊也给我们面试官自己
设计题目的权利，我们只好自己重新设计一些别的难题了。当然，这也是面试结束后，
我和他闲聊的时候他说的
【在 S******t 的大作中提到】
: ……哪有什么”面经标准解“这个说法
: 面经还不是面试的人写的……
|
p*****2
发帖数: 21240 | 47
我就不会牛顿迭代
【在 i*********7 的大作中提到】
: 我的意思是面经里面大多人提到这个问题的时候都会提到牛顿迭代法。。
|
i*********7
发帖数: 348 | 48 咳咳。好吧。只是我的印象。
反正给我的感觉是，要是你回答的比较快的。他们会认为你做过，然后立马就让你换个
角度去想。
【在 p*****2 的大作中提到】
:
: 我就不会牛顿迭代
|
y****n
发帖数: 743 | 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;
}
没做输入检查 |
G**********s
发帖数: 70 | 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)的版本。（就是不用堆
|
|
|
w****x
发帖数: 2483 | 51
数学归纳法....
我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
是不是面试官自己没弄清楚.
【在 i*********7 的大作中提到】
: 我也不知道，面试官最后不肯说答案。
: 他只给了我提示：用数学归纳法自己去思考一下。（就是说，如果只有一个节点，算几
: 次，两个呢？三个呢？四个呢？让我自己往下推试试。）
: 当然。。这已经是面试结束后的事儿了
|
i*********7
发帖数: 348 | 52 我不确定。
我第一个反应给的就是nalogn的答案，他斩钉截铁的说不对。
而且他说这题不是nalogn，很大程度上是因为这题目用的sort方法是mergesort。所以
不是这个。但他也说，这题目答案里面会有log存在。
【在 w****x 的大作中提到】
:
: 数学归纳法....
: 我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
: 是不是面试官自己没弄清楚.
|
i*********7
发帖数: 348 | 53 而且他给的例子的确好像有些道理。
他有一步步引导我去看：
他让我算了只有一个节点，两个节点，三个节点的时候，该有几次的运算。
分别是o(a),o(2a),o(4a).
而且后来我还推了一下，有四个节点的时候，应该存在了o(6a)次的计算。
这好像就不太符合nalogn的答案了。
【在 w****x 的大作中提到】
:
: 数学归纳法....
: 我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
: 是不是面试官自己没弄清楚.
|
q***y
发帖数: 236 | 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)的版本。（就是不用堆
|
w****x
发帖数: 2483 | 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存在。
|
g*********e
发帖数: 14401 | 56 lz这个是sdeI的面经啊？怎么这么难。最后mergesort a难道不是常数吗？我觉得就是
nlogn |
i*********7
发帖数: 348 | 57 嗯，现在的SDE I就可以逆天了。。。
感觉自己都超水平发挥了。前面四个都还好。。
最后一个倒了。可能系统设计的时候也给了我negative。他说我没有考虑到server会
down的情况，说要设计一个数据库进行备份。。。
【在 g*********e 的大作中提到】
: lz这个是sdeI的面经啊？怎么这么难。最后mergesort a难道不是常数吗？我觉得就是
: nlogn
|
l*********8
发帖数: 4642 | 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, 不知道他想怎么算
|
q***y
发帖数: 236 | 59 楼主说nalogn不对啊。
【在 l*********8 的大作中提到】
: 还真是n*a*logn啊。 我之前想错了。
:
: 2
|
l*********8
发帖数: 4642 | 60 可能是要改进算法吧。 直接用merge sort就是nalogn
【在 q***y 的大作中提到】
: 楼主说nalogn不对啊。
|
|
|
z*********8
发帖数: 2070 | 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)的版本。（就是不用堆
|
i*********7
发帖数: 348 | 62 要一个previous指针指向你前面遍历过的节点。
然后分三个case做。
1.上一个指针是parent。
2.上一个指针是自己的左子树。
3.上一个指针是自己的右子树。
好好想想吧
【在 z*********8 的大作中提到】
: pre-order iterative 不用stack， 用parent pointer怎么做？需要mark node吗？
|
i*********7
发帖数: 348 | 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)，你就输了。。） |
y*******g
发帖数: 6599 | 64 o(a), a是什么东西？访问每个整形数 包括 index++这种吗？ |
H***e
发帖数: 476 | 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)的版本。（就是不用堆
|
i*********7
发帖数: 348 | 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++这种吗？
|
i*********7
发帖数: 348 | 67 我当时一听这道题目，心头一喜，眉头深锁，然后过了一会儿，我说：我猜，能用牛顿
迭代法吧？
她说：不让你用牛顿迭代法呢。任何数学上tricky的方法都不让你用呢。
【在 H***e 的大作中提到】
: interesting; "不能用牛顿迭代法"
: why?
|
t******e
发帖数: 98 | 68 二叉树preorder非递归遍历这题树的节点有没有parent指针？没有的话还真不知道怎么
做。 |
i*********7
发帖数: 348 | 69 他说可以有。就是做O(1)不用堆栈的版本可以有，其他都不可以有。。
【在 t******e 的大作中提到】
: 二叉树preorder非递归遍历这题树的节点有没有parent指针？没有的话还真不知道怎么
: 做。
|
w****o
发帖数: 2260 | 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)的版本。（就是不用堆
|
|
|
i*********7
发帖数: 348 | 71 double.
对，我最后给的答案就是binary search。然后她还问了一下算法复杂度。
【在 w****o 的大作中提到】
: 求平方根的题，是用binary search?
: 还有这个函数的原型是什么？输入是float,还是int,输出呢？
: 就是问 原型是 float sqrt(float x)? 还是 int sqrt(int x)?
: xiexie !
|
H***e
发帖数: 476 | 72 我猜她不会
【在 i*********7 的大作中提到】
: 我当时一听这道题目，心头一喜，眉头深锁，然后过了一会儿，我说：我猜，能用牛顿
: 迭代法吧？
: 她说：不让你用牛顿迭代法呢。任何数学上tricky的方法都不让你用呢。
|
w****o
发帖数: 2260 | 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)的版本。（就是不用堆
|
l*********8
发帖数: 4642 | 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)的版本。（就是不用堆
|
t*********7
发帖数: 255 | |
p*****2
发帖数: 21240 | 76
＋DP吧
【在 t*********7 的大作中提到】
: 第一题就是深度遍历???还是有很牛的搞法?
|
w****x
发帖数: 2483 | 77 "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
右子树的leftmost, 是右节点的话就再往上爬 |
w****x
发帖数: 2483 | 78 "估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
栈的具体运作是怎样的？"
程序跑和compiler有什么关系?? |
p*****2
发帖数: 21240 | 79
stack是compiler搞的吧？
【在 w****x 的大作中提到】
: "估计就死在这里了。首先，让我讲述程序在跑的时候，compiler里面的
: 栈的具体运作是怎样的？"
: 程序跑和compiler有什么关系??
|
w****x
发帖数: 2483 | 80 "（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）"
为什么nalogn不对??
每次便利na, 遍历logn次啊 |
|
|
w****x
发帖数: 2483 | 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搞的吧？
|
p*****2
发帖数: 21240 | 82
preorder吗？
【在 w****x 的大作中提到】
: "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
: preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
: 有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
: 右子树的leftmost, 是右节点的话就再往上爬
|
p*****2
发帖数: 21240 | 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 + 所有
: 该函数对应的局部变量空间. 这么答差不多了吧....
|
p*****2
发帖数: 21240 | 84 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？ |
w****x
发帖数: 2483 | 85
Oh, 看成in-order了
【在 p*****2 的大作中提到】
: 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
|
w****x
发帖数: 2483 | 86 pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
上爬 |
p*****2
发帖数: 21240 | 87
嗯。应该还好。不算很难的题。
【在 w****x 的大作中提到】
: pre-order差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
: 上爬
|
w****o
发帖数: 2260 | 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差不多了， 往下爬的时候都打印， 往上爬的时候判断如果是右节点继续往
: 上爬
|
w****x
发帖数: 2483 | 89
不记得了， 看看反汇编就知道了
【在 w****o 的大作中提到】
: esp 和 ebi有什么区别？
: 感觉他们可以用一个寄存器就够了。
: 写了个dummy的代码，能不能给分析一下函数调用的时候stack的变化，和相关寄存器的
: 值得变化？
: 比如
: int add(int a, int b)
: {
: int c;
: c = a + b;
: return c;
|
S******t
发帖数: 151 | 90 第一题和DP没有一毛钱的关系吧……
【在 p*****2 的大作中提到】
:
: 嗯。应该还好。不算很难的题。
|
|
|
p*****2
发帖数: 21240 | 91
我怎么感觉有呢？难道我感觉错误了？
【在 S******t 的大作中提到】
: 第一题和DP没有一毛钱的关系吧……
|
a*******o
发帖数: 67 | 92 第一题，第二题，第五题，有没有哪位大牛能够讲讲是怎么做的？尤其是第二题和第五
题，谢啦 |
a*******o
发帖数: 67 | 93 能讲解一下这个是怎么算出来的么？谢谢啦
【在 l*********8 的大作中提到】
: mergesort
: O(a*n + n*logn)
|
s********r
发帖数: 137 | 94 这的确是一道好题，可以考很多设计。
-----------------------------------------------------
设计一个scroller，能够实时更新涨幅最高和跌幅最大的5支股票
。不仅仅是OOD，还要包括流程设计，考虑server和database的传输等。 |
l*********8
发帖数: 4642 | 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 的大作中提到】
: 能讲解一下这个是怎么算出来的么？谢谢啦
|
p*****2
发帖数: 21240 | 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 的大作中提到】
: 第一题，第二题，第五题，有没有哪位大牛能够讲讲是怎么做的？尤其是第二题和第五
: 题，谢啦
|
S******t
发帖数: 151 | 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;
|
p*****2
发帖数: 21240 | 98
需要建图吗？
【在 S******t 的大作中提到】
: ……有什么关系，不就是建图再BFS/DFS么……
|
S******t
发帖数: 151 | 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;i
if(a[i]!=b[i]) cnt++;
return cnt == 1;
}
void preprocess() {
int dict_sz = (int)dict.size();
for(int i=0;i
for(int j=i+1;j
if(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;i
if(!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;i
if(dict[i] == a) startidx = i;
for(int i=0;i
if(dict[i] == b) endidx = b;
dfs(startidx,endidx);
printf("%s\n",flag?"YES":"NO");
}
【在 p*****2 的大作中提到】
:
: 需要建图吗？
|
S******t
发帖数: 151 | 100 这个就是看个人的编程风格和习惯了。
反正即使你不建图，本质上也是要去construct a graph on-the-fly的
而且先把图建好的好处是可以较为方便的处理multiple queries
【在 p*****2 的大作中提到】
:
: 需要建图吗？
|
|
|
i*********7
发帖数: 348 | 101 我刚毕业，申的当然是SDE I......最后一个人问的问题，我就没答的让他满意过。。。
【在 p*****2 的大作中提到】
: 感觉楼主做的不差呀？怎么会悲剧？楼主申请的什么level的职位呢？
|
i*********7
发帖数: 348 | 102 我也不知道，面试官最后不肯说答案。
他只给了我提示：用数学归纳法自己去思考一下。（就是说，如果只有一个节点，算几
次，两个呢？三个呢？四个呢？让我自己往下推试试。）
当然。。这已经是面试结束后的事儿了
【在 w****x 的大作中提到】
: "（提示：如果你回答o(anlogn)或者o(anlogan)，你就输了。。）"
: 为什么nalogn不对??
: 每次便利na, 遍历logn次啊
|
p*****2
发帖数: 21240 | 103
。。
你stack那个答的怎么样？这个复杂度的我还没时间想呢。不容易。
【在 i*********7 的大作中提到】
: 我刚毕业，申的当然是SDE I......最后一个人问的问题，我就没答的让他满意过。。。
|
i*********7
发帖数: 348 | 104 答成屎一样。他让我随便写一个程序，然后问我，跑完了程序后，堆栈应该长啥样。
堆栈我倒没有画错。但是解释的跟屎一样。
【在 p*****2 的大作中提到】
:
: 。。
: 你stack那个答的怎么样？这个复杂度的我还没时间想呢。不容易。
|
i*********7
发帖数: 348 | 105 我觉得不是，她肯定会。
她说这题可以有很多种解法。
感觉现在A家反面经的倾向很明显，这一题面经里面的标准解就是牛顿迭代。
【在 H***e 的大作中提到】
: 我猜她不会
|
S******t
发帖数: 151 | 106 ……哪有什么”面经标准解“这个说法
面经还不是面试的人写的……
【在 i*********7 的大作中提到】
: 我觉得不是，她肯定会。
: 她说这题可以有很多种解法。
: 感觉现在A家反面经的倾向很明显，这一题面经里面的标准解就是牛顿迭代。
|
i*********7
发帖数: 348 | 107 我的意思是面经里面大多人提到这个问题的时候都会提到牛顿迭代法。。
【在 S******t 的大作中提到】
: ……哪有什么”面经标准解“这个说法
: 面经还不是面试的人写的……
|
i*********7
发帖数: 348 | 108 而且最后面试我的人都直接说了：我知道你们都会上网查，亚马逊也给我们面试官自己
设计题目的权利，我们只好自己重新设计一些别的难题了。当然，这也是面试结束后，
我和他闲聊的时候他说的
【在 S******t 的大作中提到】
: ……哪有什么”面经标准解“这个说法
: 面经还不是面试的人写的……
|
p*****2
发帖数: 21240 | 109
我就不会牛顿迭代
【在 i*********7 的大作中提到】
: 我的意思是面经里面大多人提到这个问题的时候都会提到牛顿迭代法。。
|
i*********7
发帖数: 348 | 110 咳咳。好吧。只是我的印象。
反正给我的感觉是，要是你回答的比较快的。他们会认为你做过，然后立马就让你换个
角度去想。
【在 p*****2 的大作中提到】
:
: 我就不会牛顿迭代
|
|
|
y****n
发帖数: 743 | 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;
}
没做输入检查 |
G**********s
发帖数: 70 | 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)的版本。（就是不用堆
|
w****x
发帖数: 2483 | 113
数学归纳法....
我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
是不是面试官自己没弄清楚.
【在 i*********7 的大作中提到】
: 我也不知道，面试官最后不肯说答案。
: 他只给了我提示：用数学归纳法自己去思考一下。（就是说，如果只有一个节点，算几
: 次，两个呢？三个呢？四个呢？让我自己往下推试试。）
: 当然。。这已经是面试结束后的事儿了
|
i*********7
发帖数: 348 | 114 我不确定。
我第一个反应给的就是nalogn的答案，他斩钉截铁的说不对。
而且他说这题不是nalogn，很大程度上是因为这题目用的sort方法是mergesort。所以
不是这个。但他也说，这题目答案里面会有log存在。
【在 w****x 的大作中提到】
:
: 数学归纳法....
: 我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
: 是不是面试官自己没弄清楚.
|
i*********7
发帖数: 348 | 115 而且他给的例子的确好像有些道理。
他有一步步引导我去看：
他让我算了只有一个节点，两个节点，三个节点的时候，该有几次的运算。
分别是o(a),o(2a),o(4a).
而且后来我还推了一下，有四个节点的时候，应该存在了o(6a)次的计算。
这好像就不太符合nalogn的答案了。
【在 w****x 的大作中提到】
:
: 数学归纳法....
: 我怎么看怎么是nalogn啊, 你确定不是这个复杂度?
: 是不是面试官自己没弄清楚.
|
q***y
发帖数: 236 | 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)的版本。（就是不用堆
|
w****x
发帖数: 2483 | 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存在。
|
g*********e
发帖数: 14401 | 118 lz这个是sdeI的面经啊？怎么这么难。最后mergesort a难道不是常数吗？我觉得就是
nlogn |
i*********7
发帖数: 348 | 119 嗯，现在的SDE I就可以逆天了。。。
感觉自己都超水平发挥了。前面四个都还好。。
最后一个倒了。可能系统设计的时候也给了我negative。他说我没有考虑到server会
down的情况，说要设计一个数据库进行备份。。。
【在 g*********e 的大作中提到】
: lz这个是sdeI的面经啊？怎么这么难。最后mergesort a难道不是常数吗？我觉得就是
: nlogn
|
l*********8
发帖数: 4642 | 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, 不知道他想怎么算
|
|
|
q***y
发帖数: 236 | 121 楼主说nalogn不对啊。
【在 l*********8 的大作中提到】
: 还真是n*a*logn啊。 我之前想错了。
:
: 2
|
l*********8
发帖数: 4642 | 122 可能是要改进算法吧。 直接用merge sort就是nalogn
【在 q***y 的大作中提到】
: 楼主说nalogn不对啊。
|
z*********8
发帖数: 2070 | 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)的版本。（就是不用堆
|
i*********7
发帖数: 348 | 124 要一个previous指针指向你前面遍历过的节点。
然后分三个case做。
1.上一个指针是parent。
2.上一个指针是自己的左子树。
3.上一个指针是自己的右子树。
好好想想吧
【在 z*********8 的大作中提到】
: pre-order iterative 不用stack， 用parent pointer怎么做？需要mark node吗？
|
l********5
发帖数: 230 | |
c********t
发帖数: 5706 | 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
|
j*****y
发帖数: 1071 | 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
|
c********t
发帖数: 5706 | 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步骤有的数要
: 反复读。
|
j*****y
发帖数: 1071 | 129 那还是 anlogn阿，这个2在这里没区别
【在 c********t 的大作中提到】
: 应该是 T(n) = 2T(n / 2) + O(a（n-1）*2)，看我的例子
|
c********t
发帖数: 5706 | 130 还是有区别的，公式写的有点问题，应该写成
T(n) = 2*T(n / 2) + a（n-1）*2
【在 j*****y 的大作中提到】
: 那还是 anlogn阿，这个2在这里没区别
|
|
|
j*****y
发帖数: 1071 | 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
|
c********t
发帖数: 5706 | 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
|
c********t
发帖数: 5706 | 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)的版本。（就是不用堆
|
s****0
发帖数: 117 | |
s****0
发帖数: 117 | 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
|
x****o
发帖数: 29677 | |
j*****y
发帖数: 1071 | 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.
|
p****e
发帖数: 3548 | 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;
|
a********n
发帖数: 1287 | |
P*******b
发帖数: 1001 | 140 preorder O(1)怎么做？
【在 a********n 的大作中提到】
: 这个难度，不复习半年不能上啊。
|
|
|
G********r
发帖数: 9 | 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)的版本。（就是不用堆
|
