近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 6486|回复: 43
收起左侧

刚面玩linkedIn求人品

[复制链接] |试试Instant~ |关注本帖
billupus 发表于 2014-10-15 03:28:13 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Linkedin - 网上海投 - 技术电面 |Other

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

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

x
这两个星期为了个LinkedIn几乎找了所有能找的资料,结果还是碰上意料之外的情况。。。算了先等结果。
先讲Project。我在cmu做的是web方面的project,这个面试官似乎很感兴趣问了很多,包括怎么test遇到什么问题performance什么的,讲的还不错。然后是两个coding:

1. Deepest comman ancestor (with parent nodes). LinkedIn这题都快问烂了...我说了用hashmap的方法,他说你能不能不用额外空间,我想了一下又说了那个把两个节点调到一个高度的做法。
. Waral 鍗氬鏈夋洿澶氭枃绔,2. 实现一个Max Stack, 支持peekMax() 和popMax(). 很自然地用两个栈去做,但是这样popMax的时候很费时间。然后我又加了一个stack存的是max value的index, 把stack全变成ArrayList, 然后就开始纠结pop了。。。结果corner case太多没写完。。。不过他也说这题要简单clean是比较难

不知道能不能行吖。求过...要么两个星期白搞了

评分

1

查看全部评分

本帖被以下淘专辑推荐:

traceroute_su 发表于 2014-10-15 04:51:05 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
谢谢面经 想问 第一题 with parent nodes 是说有child->parent? 如果是这样 两个点往上回指,指针重合即输出? 不会是这样吧。。。 如果没有那个link,递归不是就可以做了么 我可能没理解lz的意思要用hash,还有“节点调到同一高度” 抱歉打扰 我下周也linkedin面试 先练习下 谢谢
回复 支持 反对

使用道具 举报

 楼主| billupus 发表于 2014-10-15 05:01:44 | 显示全部楼层
关注一亩三分地微博:
Warald
traceroute_su 发表于 2014-10-15 04:51.鐣欏璁哄潧-涓浜-涓夊垎鍦
谢谢面经 想问 第一题 with parent nodes 是说有child->parent? 如果是这样 两个点往上回指,指针重合即输 ...

对就是每个node除了left和right还有个parent
-google 1point3acres
Class Node {
       Node left;
       Node right;
       Node parent;
}
root节点parent是null. 没有parent的做法的确是递归,但是有parent指针的话递归就划不来了。举个例子:

        ____3___
       /              \
      5               1
   /      \        /      \
  6       2     0        8
         /  \
        7   4

要找4 和 8的lca,把4先设成到2,因为2 和 8 深度一样。然后2 和 8 一起沿着parent往上,碰到的第一个一样的节点就是第一个祖先了。
回复 支持 反对

使用道具 举报

traceroute_su 发表于 2014-10-15 05:04:53 | 显示全部楼层
billupus 发表于 2014-10-15 05:01. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对就是每个node除了left和right还有个parent

Class Node {

哦!一下子明白楼主的意思了 原来是这样!神回复 嘿嘿 谢谢
回复 支持 反对

使用道具 举报

 楼主| billupus 发表于 2014-10-15 05:09:56 | 显示全部楼层
traceroute_su 发表于 2014-10-15 05:04.鐣欏璁哄潧-涓浜-涓夊垎鍦
哦!一下子明白楼主的意思了 原来是这样!神回复 嘿嘿 谢谢

:) 树好难画。。。
回复 支持 反对

使用道具 举报

traceroute_su 发表于 2014-10-15 05:20:25 | 显示全部楼层
billupus 发表于 2014-10-15 05:09
:) 树好难画。。。

感激不尽啊!希望LZ rp爆棚 顺利onsite 据说linkedin的onsite要7轮 非常疲劳 养精蓄锐吧!加油
回复 支持 反对

使用道具 举报

davidwh 发表于 2014-10-15 07:17:07 | 显示全部楼层
用linkedlist行不行? 这个pop的时候只要知道index,O(1)时间就搞定了? 不知道这样想对不对
回复 支持 反对

使用道具 举报

 楼主| billupus 发表于 2014-10-15 08:35:01 | 显示全部楼层
davidwh 发表于 2014-10-15 07:17.鐣欏璁哄潧-涓浜-涓夊垎鍦
用linkedlist行不行? 这个pop的时候只要知道index,O(1)时间就搞定了? 不知道这样想对不对

问题是popMax的时候所有在那个index之后的max值都要改。改成多少是要分情况讨论的 :)
回复 支持 反对

使用道具 举报

yzl232 发表于 2014-10-15 08:59:42 | 显示全部楼层
楼主挺厉害的!!!加油!
回复 支持 反对

使用道具 举报

byrlhb 发表于 2014-10-15 10:34:04 | 显示全部楼层
第二题比较弱智的方法,不知道行不行,楼主参考。。。一个支持max()的max栈,然后再来一个普通栈,删除的时候普通栈push max栈pop出来的元素,知道碰到最大值为止,然后把最大值pop掉,再把普通栈的元素push回去
回复 支持 反对

使用道具 举报

 楼主| billupus 发表于 2014-10-15 11:07:39 | 显示全部楼层
byrlhb 发表于 2014-10-15 10:34
第二题比较弱智的方法,不知道行不行,楼主参考。。。一个支持max()的max栈,然后再来一个普通栈,删除的时 ...

可以的吖~就是复杂了点最差是O(n)。我最开始就是这么说的不过后面想改简单点
回复 支持 反对

使用道具 举报

wjl2525 发表于 2014-10-15 11:16:36 | 显示全部楼层
lz,请问max stack这题,是只需要支持peekMax和popMax,不需要支持正常的peek和pop吗?
回复 支持 反对

使用道具 举报

pandakuo 发表于 2014-10-15 11:26:16 | 显示全部楼层
今天二面 問的題目都有點不像是平常會看到的-google 1point3acres

第三題他問我說 Design a singleton class

然後就問說要怎樣做到thread-safe blah blah
回复 支持 反对

使用道具 举报

 楼主| billupus 发表于 2014-10-15 11:48:44 | 显示全部楼层
wjl2525 发表于 2014-10-15 11:16
lz,请问max stack这题,是只需要支持peekMax和popMax,不需要支持正常的peek和pop吗?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
当然也支持。但是他主要是考popMax和peekMax,我顺便把正常的peek和pop也说了一下
回复 支持 反对

使用道具 举报

wjl2525 发表于 2014-10-15 12:05:14 | 显示全部楼层
billupus 发表于 2014-10-15 11:48
当然也支持。但是他主要是考popMax和peekMax,我顺便把正常的peek和pop也说了一下
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果你需要支持正常的pop的话,那popMax的定义是什么呢?如果max元素不恰好是原来stack的peek,是不是需要把原来stack里直到max的所有元素都pop出来?这个是没办法在O(1)时间做到的啊?为什么你会觉得popMax很费时间呢?
回复 支持 反对

使用道具 举报

 楼主| billupus 发表于 2014-10-15 12:08:05 | 显示全部楼层
pandakuo 发表于 2014-10-15 11:26
今天二面 問的題目都有點不像是平常會看到的

第三題他問我說 Design a singleton class

其实singleton class很经常考。。。虽然不是算法。我上次BloomBerg就被这个坑过还记忆犹新!

在java里我觉得只要套上synchronized就是thread-safe了。。。

Class Singleton {-google 1point3acres
      private static Singleton sc = null;
      
      private Singleton() {
           /* do something */
      }

     public static synchronized Singleton getInstance() {
           /* lazy initialization */
           if(sc == null) {
                 sc = new Singleton();
           }
           return sc;
     }. 1point 3acres 璁哄潧
}
回复 支持 反对

使用道具 举报

 楼主| billupus 发表于 2014-10-15 12:10:26 | 显示全部楼层
wjl2525 发表于 2014-10-15 12:05
如果你需要支持正常的pop的话,那popMax的定义是什么呢?如果max元素不恰好是原来stack的peek,是不是需 ...

popMax是pop出最接近栈顶的max值,其他值都不变。当然可以就一直pop到这个max值再push回去,我一开始也是这么说的。但是他问有没有更好的方法...我只能往记住index那边想...结果没写完
回复 支持 反对

使用道具 举报

wjl2525 发表于 2014-10-15 12:37:41 | 显示全部楼层
billupus 发表于 2014-10-15 12:10
popMax是pop出最接近栈顶的max值,其他值都不变。当然可以就一直pop到这个max值再push回去,我一开始也是 ...

原来如此,谢啦!祝福你哈。
回复 支持 反对

使用道具 举报

lunaughty 发表于 2014-10-16 04:11:22 | 显示全部楼层
billupus 发表于 2014-10-15 12:10
popMax是pop出最接近栈顶的max值,其他值都不变。当然可以就一直pop到这个max值再push回去,我一开始也是 ...

这个感觉可以用一个链表和一个堆,链表当作栈使用,插入删除的时候同时操作那个堆就行了。
回复 支持 反对

使用道具 举报

pandakuo 发表于 2014-10-16 04:46:01 | 显示全部楼层
billupus 发表于 2014-10-15 12:08. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
其实singleton class很经常考。。。虽然不是算法。我上次BloomBerg就被这个坑过还记忆犹新!
.鐣欏璁哄潧-涓浜-涓夊垎鍦
在java里 ...

因為我是寫這樣 所以他問我的時候 我就想說應該不太做事情 可是他又一直問 我就說只好說寫如果是要write的話可能要有lock之類的 不過後來他的意思應該只是問我目前的desgin需不需要做什麼 因為他說答案是什麼都不用做. From 1point 3acres bbs

Class Singleton {
      private static Singleton sc = new Singleton();
      private Singleton() {}
     public static Singleton getInstance() {
          return sc;. 鍥磋鎴戜滑@1point 3 acres
     }
}
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

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

custom counter

GMT+8, 2017-6-23 13:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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