一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2218|回复: 13
收起左侧

Linkedin 第一轮店面,面得太渣,发帖为下一次攒RP

[复制链接] |试试Instant~ |关注本帖
ki87uj 发表于 2014-12-3 05:49:26 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Linkedin - 内推 - 技术电面 |Other

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

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

x
刚刚面完,一道很简单的题目,之前网友提到过,但是可能因为太简单,就没有仔细讨论。.鏈枃鍘熷垱鑷1point3acres璁哄潧
可以说比很多leetcode上的题目都简单。但是我表现太渣了,对generic太不熟悉,经过面试官反复提醒才改对了所有的bugs。一小时只做了一道题,肯定挂了。。。
我把所有我面试的代码都贴出来,希望帮助到后面的同学

两位面试官名字是Brian和Jerry,电话质量不好,听不清楚,我不知道原因,我自己手机信号是满格的。断了两次。面试官自始至终非常的nice,赞一下linkedin!. from: 1point3acres.com/bbs

/**
* Given a nested list of integers, returns the sum of all integers in the list weighted by their depth
* For example, given the list {{1,1},2,{1,1}} the function should return 10 (four 1's at depth 2, one 2 at depth 1)
* Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3)-google 1point3acres
*/

{1,2,{1,2}}
input.getInteger() =1.鐣欏璁哄潧-涓浜-涓夊垎鍦
input.getInteger()  =2
input.getInteger()  = null?

ArrayList<NestedInteger> input. from: 1point3acres.com/bbs
. 1point3acres.com/bbs
上面是题目
下面是我写的代码部分

public int depthSum (List<NestedInteger> input). From 1point 3acres bbs
{
    //Implementation here

. visit 1point3acres.com for more.
    return getSum(input,1);
}


public int getSum(List<NestedInteger> input,int level){
//base case should arrive the deepest level
    int addup = 0;
    if(input.size() == 0)
        return 0;

    for(int i=0;i<input.size();i++){
        if(input.get(i).isInteger()){//input.get(i) is an integer
            addup += input.get(i).getInteger()*level;
        }
        else{. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
            addup += getSum(input.get(i).getList(),level+1);. 鍥磋鎴戜滑@1point 3 acres
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    }. 1point3acres.com/bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
    return addup;
}
下面是给出的一个interface,其实就是一个class,我在这个class的理解上傻逼了很久。。。。。其实人家写的很清楚了
基本功不行啊。。。。面壁去了。。。

public interface NestedInteger
{
    /** @return true if this NestedInteger holds a single integer, rather than a nested list */
    boolean isInteger();

    /** @return the single integer that this NestedInteger holds, if it holds a single integer. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
     * Return null if this NestedInteger holds a nested list */
    Integer getInteger();. From 1point 3acres bbs

    /** @return the nested list that this NestedInteger holds, if it holds a nested list
     * Return null if this NestedInteger holds a single integer */
    List<NestedInteger> getList();
}




下面是我们的讨论
. 1point 3acres 璁哄潧
//List<NestedInteger>
. 1point 3acres 璁哄潧
// {} => 0
//{} isInteger() =  false// 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
//How to judge when I arrive at deepest level
//If you're at the deepest level, will there be any more Nestedintegers nested within .鏈枃鍘熷垱鑷1point3acres璁哄潧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
/**
* This is the interface that represents nested lists.
* You should not implement it, or speculate about its implementation.. 鍥磋鎴戜滑@1point 3 acres
*/. 鍥磋鎴戜滑@1point 3 acres
-google 1point3acres

. visit 1point3acres.com for more.

评分

6

查看全部评分

xnature 发表于 2015-10-18 02:24:20 | 显示全部楼层
DFS。看到{,深度+1, 看到}, 深度-1。
  1. #include <string>
  2. #include <iostream>
  3. using namespace std;

  4. int fun(string s) {
  5.     int d = 0;
  6.     int ret = 0;
  7.     int num = 0;
  8.     for (auto c : s) {
  9.         if (c == '{') {
  10.             ret += num * d;
  11.             num = 0;
  12.             d ++;. 鍥磋鎴戜滑@1point 3 acres
  13.         }
  14.         else if (c == '}') {
  15.             ret += num * d;
  16.             num = 0;
  17.             d--;
  18.         }
  19.         else if (c == ',') {
  20.             ret += num * d;
  21.             num = 0;
  22.         }
  23.         else if (c >= '0' && c <= '9') {. From 1point 3acres bbs
  24.             num = num * 10 + c - '0';
  25.         }
  26.     }
  27.     return ret;
  28. }

  29. int main(int argc, char const *argv[]). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  30. {
  31.     cout<<fun("{1,{40,{6}}}");
  32.     return 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33. }
复制代码
回复 支持 1 反对 0

使用道具 举报

gosteve 发表于 2014-12-30 11:08:55 | 显示全部楼层
学习了 多谢分享~
回复 支持 反对

使用道具 举报

yuqinlear 发表于 2015-1-5 02:27:58 | 显示全部楼层
看了下这个public interface NestedInteger三个API,.鐣欏璁哄潧-涓浜-涓夊垎鍦
既然不是Integer就是List,有其中一个API就够了吧。
回复 支持 反对

使用道具 举报

lqs4188980 发表于 2015-1-11 09:32:37 | 显示全部楼层
感谢楼主分享。经典递归的设计。祝楼主好运
回复 支持 反对

使用道具 举报

lyzero00 发表于 2015-1-12 04:37:11 | 显示全部楼层
去年也面过这道题
回复 支持 反对

使用道具 举报

jiqishou 发表于 2015-2-14 05:53:44 | 显示全部楼层
之前面之前的时候没有看到楼主发的题,不然面的时候可能思路会更快速的清晰. . 1point 3acres 璁哄潧

我跟楼主面的问题差不多,也是NestedList,不过我的要多加了一层就是求得是ReverseDepthSum. 也就是层数越深,所获得的weight value越低. 举例就是 {{1,1},2,{1,1}} the function should return 8 (four 1's at weight 1, one 2 at depth 2)
* Given the list {1,{4,{6}}} the function should return 17 (one 1 at weight 3, one 4 at depth 2, and one 6 at depth 1)

其他方法和楼主用的方法一样,只是需要有个reverse weight的概念. 当时稍微想了下最后用了个list不断push_front(level)的方法实现的,最后面试官提示我是不是用queue做会更好. 我想了下确实是,first come first out. 总之第一关有惊无险的过了. 之前没有看过面经只刷了leetcode, 这次把L家的面经都好好准备下,迎接二面吧. 发出来这个变形题攒RP. 加油.
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2015-2-16 14:23:44 | 显示全部楼层
jiqishou 发表于 2015-2-14 05:53. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
之前面之前的时候没有看到楼主发的题,不然面的时候可能思路会更快速的清晰. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

我跟楼主面的问题差不多, ...

能具体讲讲是怎么用queue的吗?

我的理解,不全部遍历一遍,不知道高度是多少啊
回复 支持 反对

使用道具 举报

jiqishou 发表于 2015-2-17 03:17:10 | 显示全部楼层
sunnyroom 发表于 2015-2-16 14:23
能具体讲讲是怎么用queue的吗?

我的理解,不全部遍历一遍,不知道高度是多少啊

我后来觉得是那个人自己把面经里的nestedInteger的题给改了. 确实是要先遍历一次的,不然不知道最终的深度. 我当时也是这么做的. 不然没法全部知道level的,用list或者array做比较好我感觉,queue是他跟我说,但是我后来想想也不知道他什么意思了.
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2015-2-17 05:48:41 | 显示全部楼层
jiqishou 发表于 2015-2-17 03:17
我后来觉得是那个人自己把面经里的nestedInteger的题给改了. 确实是要先遍历一次的,不然不知道最终的深 ...

先算出高度,做法就跟楼主的一样了。.1point3acres缃

用queue的话,把每层的nestedinteger全放到arraylist里,然后这个arraylist放queue里。 . 1point3acres.com/bbs
然后通过queue的size知道高度。。。
回复 支持 反对

使用道具 举报

L纪翔L 发表于 2015-2-25 14:10:34 | 显示全部楼层
想问一下,这道题的complexity是这个么? time : O(n), n is the number of integer, Space: O(logn) recursion.
谢谢分享!
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-9-23 09:55:49 | 显示全部楼层
这个BFS更好做吧...NestedInteger就是一个树,一层层遍历. 比如{{1,1},2,{1,1}}就是
        NI
     /   |  \
   NI   2  NI
/  \       /  \
1   1     1   1

BFS的时候记录层数就行.
回复 支持 反对

使用道具 举报

shellvincent 发表于 2015-10-19 07:59:58 | 显示全部楼层
def cal(s):
    depth = 0
    res = 0
    temp = ""
    for i in s:
        if i == "{":
            depth += 1
        elif i == "}" or i == ",":
            if temp != "":
                res += int(temp) * depth
                temp = ""
            if i == "}":
                depth -= 1
        else:
            temp += i
    return res
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-11-3 12:45:39 | 显示全部楼层
dfs算出最深深度, 调sum的时候 深度-level 作为weight再dfs一遍
用queue可以做吗, 有没有办法一遍dfs完成
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 00:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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