工业界资深数据科学家教你破解各大公司面试
工业界资深数据科学家教你破解各大公司面试

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
高效直聘+内推,70%面试率
AI帮你免费完善简历
直击全美十万个科技职位
把贵司招聘信息放这里
查看: 1633|回复: 56
收起左侧

发一个小众的tableau onsite

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

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

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

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

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

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

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

评分

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

查看全部评分


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

做了一个过程演示...

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

使用道具 举报

我的人缘0
magicsets 发表于 2018-8-17 05:16:05 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  97% (287)
 
 
2% (6)  踩
第二题参考答案:
.1point3acres网
[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;
    }
  }
}
.1point3acres网

原理是使用树结构的变形映射“栈式遍历”时所需要记录的中间节点上下文。. From 1point 3acres bbs

虽然程序表面上看是循环里面套循环,但是时间复杂度确实是O(n) —— 可以用平摊分析、数学归纳法或者构造势能函数来证明。

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

引理1:外层的while(true)循环执行次数不超过2n次

因为每次执行外循环要么删除至少一个节点,要么进行一系列翻转直到一个叶子节点被翻转到树顶然后下一次循环被删除
. 围观我们@1point 3 acres
引理2:内层的第一个循环的循环体总执行次数为n.1point3acres网
因为每次执行删除一个节点,总共n个

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

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

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


最后综合引理123,可证时间复杂度是O(n)。

补充内容 (2018-8-17 14:44):
执行过程的一个样例:http://jsfiddle.net/whvf47k6/embedded/result
回复

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| canoee 发表于 2018-8-11 11:58:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (179)
 
 
0% (1)  踩
Jing666 发表于 2018-8-11 11:30. 留学申请论坛-一亩三分地
第二题怎么做呀。。。完全没思路

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

使用道具 举报

我的人缘0
taoli0515 发表于 2018-8-14 01:25:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
canoee 发表于 2018-8-11 11:58
只能用O(1)的话就只能每次找到一个leaf,然后删掉,再从顶上开始删第二个
这个主要是难在每个节点都是左 ...
. 留学申请论坛-一亩三分地
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) ? . 留学申请论坛-一亩三分地
Mei zhong wen shu ru fa, sorry :)

Data Structures for Coding Interview in Python
一亩三分地独家折扣20% off

回复

使用道具 举报

我的人缘0
 楼主| canoee 发表于 2018-8-14 01:42:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  99% (179)
 
 
0% (1)  踩
taoli0515 发表于 2018-8-14 01:25
LZ qingwen: why can't we recursive delete left, delete right then delete node itself? Is because t ...

是的,不能用recursive
回复

使用道具 举报

我的人缘0
taoli0515 发表于 2018-8-14 02:00:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
LZ居然面了两波OOD也是厉害 不知道有什么心得么?或者被追问的问题?
贴一下代码 请lz过目 用的java所以没有delete本身. Waral 博客有更多文章,
[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;
        }

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.


回复

使用道具 举报

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

使用道具 举报

我的人缘0
ld_xixi 发表于 2018-8-14 06:35:11 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (20)
 
 
4% (1)  踩
LemonMyth 发表于 2018-8-14 02:07
Set root to null and let Java garbage collection does the rest

赞!!!. 留学申请论坛-一亩三分地
回复

使用道具 举报

我的人缘0
taoli0515 发表于 2018-8-14 06:35:56 | 显示全部楼层
本楼: 【顶】   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 发表于 2018-8-14 06:36:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (20)
 
 
4% (1)  踩
canoee 发表于 2018-8-11 11:58
只能用O(1)的话就只能每次找到一个leaf,然后删掉,再从顶上开始删第二个
这个主要是难在每个节点都是左 ...

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-10-16 12:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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