如何在一个新城市*快速*安顿物品清单

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷AI创业公司
图灵视频
招聘多个工程师职位
查看: 1032|回复: 54
收起左侧

发一个小众的tableau onsite

[复制链接] |试试Instant~ |关注本帖
我的人缘0
canoee 发表于 2018-8-11 10:59:29 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩

2018(7-9月) 码农类General 博士 全职@ - 内推 - Onsite  | Other | 其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
发一个很小众的公司Tableau面经因为离家近,正好有朋友内推,以及拿L家offer把电面给免了就去试一试

1. 设计一个纸牌游戏,从每一张牌开始,到完成一个熟悉的游戏,比如Black Jack或者 Holdem
2. 把整个树都删除,只能用O(1)空间,挂在这个上面了,只写了一个非最优解,最后大概知道怎么做了,但是没时间了
3. 设计一个电梯的系统. visit 1point3acres for more.
4. 面manager,主要看我会什么,他就跟着问什么,比如设计一个电商需要的表,最后做了一下Knn的点

总的感觉还不错,除了挂了的那一轮,还有一个影响是那一轮是remote
Move on准备下周大战

评分

参与人数 1大米 +1 收起 理由
zxc1993 + 1 给你点个赞!

查看全部评分


上一篇:推特OA
下一篇:亚麻昂赛面经
我的人缘0
magicsets 发表于 4 天前 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  97% (235)
 
 
2% (6)  踩
canoee 发表于 2018-8-17 10:41.1point3acres网
说真的,我没太看懂。。。

做了一个过程演示...

http://jsfiddle.net/whvf47k6/embedded/result
回复

使用道具 举报

我的人缘0
magicsets 发表于 4 天前 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  97% (235)
 
 
2% (6)  踩
第二题参考答案:.留学论坛-一亩-三分地

[C++] 纯文本查看 复制代码
// struct TreeNode {
//   int value;
//   TreeNode *left;
//   TreeNode *right;
// };

void EraseTree(TreeNode *node) {
  while (true) {
    for (TreeNode *last = node;
         node != nullptr && node->left == nullptr;
         last = node = last->right) {
      delete node;
    }
    if (node == nullptr) {
      break;
    }
    TreeNode *lhs = node->left;
    node->left = nullptr;
    while (lhs != nullptr) {
      // 如果lhs有至少一个child为nullptr的话,这里可以提前删除lhs节点,但总体复杂度不变。
      TreeNode *next = lhs->left;
      // 旋转:
      // --
      //                                            X
      //   X          Y                            / \
      //  / \    +     \         =>       U   +   V   Y
      // U   V          ...                            \
      //                                                ...
      lhs->left = lhs->right;
      lhs->right = node;
      node = lhs;
      lhs = next;
    }
  }
}


原理是使用树结构的变形映射“栈式遍历”时所需要记录的中间节点上下文。
. 围观我们@1point 3 acres
虽然程序表面上看是循环里面套循环,但是时间复杂度确实是O(n) —— 可以用平摊分析、数学归纳法或者构造势能函数来证明。

这里稍微提一下使用平摊分析的证明思路:

引理1:外层的while(true)循环执行次数不超过2n次
.本文原创自1point3acres论坛
因为每次执行外循环要么删除至少一个节点,要么进行一系列翻转直到一个叶子节点被翻转到树顶然后下一次循环被删除

引理2:内层的第一个循环的循环体总执行次数为n
因为每次执行删除一个节点,总共n个

引理3:内层的第二个循环的总循环次数至多为2n. 一亩-三分-地,独家发布
首先注意到总循环次数即为lhs的访问次数。

这里我们使用平摊分析,将lhs节点的每一次访问映射到lhs->left = lhs->right这一变形上 —— 也就是说,每访问一次lhs,都必然有某个节点的right child变为left child,所以我们数一数发生了多少次这样的变形就可以了。

易知在上述代码中,对于每个节点(包括叶子里的null节点),其至多有一次机会由某个父节点的right child变为left child。而包括null在内的所有节点总数不超过2n,所以循环至多发生了2n次。-google 1point3acres
. from: 1point3acres

最后综合引理123,可证时间复杂度是O(n)。
. 一亩-三分-地,独家发布
补充内容 (2018-8-17 14:44):
执行过程的一个样例:http://jsfiddle.net/whvf47k6/embedded/result
回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 6 天前 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩
vampiremm 发表于 2018-8-15 04:34
offer多选择多啊,而且也不是所有人都想做螺丝钉。没有人在找工作的时候就会认准一家的吧,只是投了一个 ...

这个我挺同意的,如果不愿意当螺丝钉的话,确实可以考虑别的机会
回复

使用道具 举报

我的人缘0
Jing666 发表于 2018-8-11 11:30:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  73% (55)
 
 
26% (20)  踩
第二题怎么做呀。。。完全没思路

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 2018-8-11 11:58:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩
Jing666 发表于 2018-8-11 11:30
第二题怎么做呀。。。完全没思路

只能用O(1)的话就只能每次找到一个leaf,然后删掉,再从顶上开始删第二个
这个主要是难在每个节点都是左右两个孩子,所以我能想到的最优解是,把整个树变成单链,然后就可以一路删过去,但是一直没有往那个方向想。
回复

使用道具 举报

我的人缘0
taoli0515 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
canoee 发表于 2018-8-11 11:58
只能用O(1)的话就只能每次找到一个leaf,然后删掉,再从顶上开始删第二个
这个主要是难在每个节点都是左 ...
.1point3acres网
LZ qingwen: why can't we recursive delete left, delete right then delete node itself? Is because they count recursive stack as not O(1) ? .本文原创自1point3acres论坛
Mei zhong wen shu ru fa, sorry :)
回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩
taoli0515 发表于 2018-8-14 01:25
LZ qingwen: why can't we recursive delete left, delete right then delete node itself? Is because t ...
. 1point 3acres 论坛
是的,不能用recursive
回复

使用道具 举报

我的人缘0
taoli0515 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
LZ居然面了两波OOD也是厉害 不知道有什么心得么?或者被追问的问题?
.本文原创自1point3acres论坛贴一下代码 请lz过目 用的java所以没有delete本身
[Bash shell] 纯文本查看 复制代码
if (root == null) return;
        while (root.left != null || root.right != null) {
            TreeNode temp = root;
            TreeNode prev = null;
            while (temp.left != null || temp.right != null) {//find the next node
                prev = temp;
                if (temp.left != null) {
                    temp = temp.left;
                } else {
                    temp = temp.right;
                }
            }
            if (prev.left == temp) prev.left = null; //use parent pointer to delete child
            else prev.right = null;
        }
回复

使用道具 举报

我的人缘0
LemonMyth 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (35)
 
 
2% (1)  踩
Set root to null and let Java garbage collection does the rest
回复

使用道具 举报

我的人缘0
ld_xixi 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (17)
 
 
5% (1)  踩
LemonMyth 发表于 2018-8-14 02:07
Set root to null and let Java garbage collection does the rest

赞!!!

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
taoli0515 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
canoee 发表于 2018-8-14 01:42
是的,不能用recursive

set root to null太逗了哈

补充内容 (2018-8-14 06:38):
顺便问下lz面的哪个组?
回复

使用道具 举报

我的人缘0
ld_xixi 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (17)
 
 
5% (1)  踩
canoee 发表于 2018-8-11 11:58
只能用O(1)的话就只能每次找到一个leaf,然后删掉,再从顶上开始删第二个
这个主要是难在每个节点都是左 ...

吧整个树变成single linkedlist 难道不是O(N)的空间复杂度?
回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩
taoli0515 发表于 2018-8-14 02:00
LZ居然面了两波OOD也是厉害 不知道有什么心得么?或者被追问的问题?
贴一下代码 请lz过目 用的java所以没 ...

我差不多就是这么做了,但这不是optimal的,就像我前面说的,面试官想要的变成单链,这样就不用循环
回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩
ld_xixi 发表于 2018-8-14 06:36
吧整个树变成single linkedlist 难道不是O(N)的空间复杂度?
. 一亩-三分-地,独家发布
不然就是nlogn吧
回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩
taoli0515 发表于 2018-8-14 06:35
set root to null太逗了哈
. visit 1point3acres for more.
补充内容 (2018-8-14 06:38):

我不知道,我朋友帮我投了两个组,我没太记得名字
回复

使用道具 举报

我的人缘0
jwang9981 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (13)
 
 
0% (0)  踩
喜欢用tableau
回复

使用道具 举报

我的人缘0
ld_xixi 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (17)
 
 
5% (1)  踩
canoee 发表于 2018-8-14 07:15
我差不多就是这么做了,但这不是optimal的,就像我前面说的,面试官想要的变成单链,这样就不用循环

来源一亩.三分地论坛. 这个面试官估计自己也是稀里糊涂的, 变成单链表不能节省空间不说, 还得循环2回
O(1)的空间复杂度只能是递归
回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩
ld_xixi 发表于 2018-8-14 09:09
这个面试官估计自己也是稀里糊涂的, 变成单链表不能节省空间不说, 还得循环2回
O(1)的空间复杂度只能 ...
.留学论坛-一亩-三分地
递归倒是不可能O(1)吧
回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩
jwang9981 发表于 2018-8-14 08:18.1point3acres网
喜欢用tableau

确实做的好,不过应该是挂了
回复

使用道具 举报

我的人缘0
ld_xixi 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (17)
 
 
5% (1)  踩
canoee 发表于 2018-8-14 09:15
递归倒是不可能O(1)吧

递归占上的空间不算, 函数退出自动回收
回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (100)
 
 
0% (0)  踩
ld_xixi 发表于 2018-8-14 09:24
递归占上的空间不算, 函数退出自动回收

这个主要是面试官说了算。。。非常尴尬
回复

使用道具 举报

我的人缘0
ld_xixi 发表于 7 天前 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (17)
 
 
5% (1)  踩
canoee 发表于 2018-8-14 11:09
这个主要是面试官说了算。。。非常尴尬

同意,所以说面试拼的是人品跟运气
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-8-21 17:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表