01/27 princeton on-site

boyshone 发表于 2016-2-16 22:51
recursive 不是还是用了extra space在stack上阿？

这个就不能这么较真了，代码还占空间呢，他的意思应该就是指在你的代码里不在申请额外的变量，而且递归本质就是栈。我觉得面试就跟考试一样，要想面试官想要什么样的答案

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

daniel123 发表于 2016-2-18 03:49
lz请教一个问题， Your interviews will be technical. Be prepared to write code using paper and pencil ...

我的也是这儿写的，这个不用担心

_binary_ 发表于 2016-2-17 14:45
这个就不能这么较真了，代码还占空间呢，他的意思应该就是指在你的代码里不在申请额外的变量，而且递归本 ...

我觉得这不是较真啊。如果被问到recursive的空间复杂度，能说O(1)吗？明显不是啊。

_binary_ 发表于 2016-2-17 14:45
这个就不能这么较真了，代码还占空间呢，他的意思应该就是指在你的代码里不在申请额外的变量，而且递归本 ...

而且，从后往前打印，reverse两次就可以了，也达到了时间O(n)，空间O(1)

_binary_ 发表于 2016-2-19 00:03
我的也是这儿写的，这个不用担心

谢楼主了

最后还是想不出来，给了我一个hint说recursive，恍然大悟，就把答案写出来了，面试官表示满意。   难道recursive系统给函数分配的空间不算空间嘛？不还是O(N)的空间嘛？面试官是搞笑呢是不是。。。。

tldxk 发表于 2016-2-19 05:06
而且，从后往前打印，reverse两次就可以了，也达到了时间O(n)，空间O(1)

好像忘在帖子里写，follow up的时候就说了前提不能reverse