在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2934|回复: 5
收起左侧

[Linkedin]电面新鲜面经

[复制链接] |试试Instant~ |关注本帖
jiaozhu200601 发表于 2016-8-12 15:09:33 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类General 硕士 全职@Linkedin - 猎头 - 技术电面  | Other | 在职跳槽

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

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

x
一共60min,简单自我介绍之后就是两个coding问题:
1. 先让写了一个reverseString,没花什么时间。
. 一亩-三分-地,独家发布
2. implements 一个Two Sum interface,里面有两个method:
    a. void store (int val) :  需要选一个数据结构作为存储,然后会不停地往里面add value。我选择的是List<Integer> 作为store. From 1point 3acres bbs
    b. boolean hasPair (int target), 非常类似lc 里面的two sum,输入一个target值然后看看里面是不是有 a pair of integers 的和正好是target。 把原题中的Hashmap换成HashSet。code 如下:

public class TwoSumClass implements TwoSum{
    private final List<Integer> nums;


    public TwoSumClass {
. 一亩-三分-地,独家发布      nums = new ArrayList<Integer>();
    }

    @Override
    public void store (int val) {
       nums.add(val);
    }

    @Override
    public boolean hasPair (int val) {
       if (nums.size() < 2) {
         return false;. Waral 博客有更多文章,
       }
       Set <Integer> set = new HashSet<>();

       for (int i = 0; i < nums.size(); i ++) {. 围观我们@1point 3 acres
          if (set.containsKey (nums.get(i))) {
                 return true;. 一亩-三分-地,独家发布
          } else {
             set.add(val - nums.get(i));
          }
       }      
       return false;
    }     
}

follow up 是假设要call 30000次hasPair 方法 (nums 里面的值不变),如何在保证没有extra space complexit的情况下,减少 time complexity。关于这点, 我并没有想出很好的答案, 欢迎讨论!


评分

2

查看全部评分

say543 发表于 2016-8-13 14:40:59 | 显示全部楼层

follow up 有target 的time complexity 吗? 感觉蛮难的... 因为nums 不会改变 能够在所有store 完之后 先枚举在call hasPair 30000吗?
回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2016-8-14 03:45:00 | 显示全部楼层
say543 发表于 2016-8-13 14:40
follow up 有target 的time complexity 吗? 感觉蛮难的... 因为nums 不会改变 能够在所有store 完之后 先 ...

这样会增加space complexity吧 因为有(n^2) 种可能的组合要存储
回复 支持 反对

使用道具 举报

LearnerChao 发表于 2016-8-15 11:20:27 | 显示全部楼层
感谢楼主分享;我感觉follow-up既然有那么大的hasPair的调用,而nums不变,不如用一个hashset存所有可能的sums,在store时候更新sums,这样call hasPair的时候就可以在O(1)的时间内返回了
回复 支持 反对

使用道具 举报

say543 发表于 2016-8-15 13:45:23 | 显示全部楼层
LearnerChao 发表于 2016-8-15 11:20
感谢楼主分享;我感觉follow-up既然有那么大的hasPair的调用,而nums不变,不如用一个hashset存所有可能的s ...
. From 1point 3acres bbs

这样space complexity 会增加吗?
回复 支持 反对

使用道具 举报

LearnerChao 发表于 2016-8-16 03:13:16 | 显示全部楼层
say543 发表于 2016-8-15 13:45
这样space complexity 会增加吗?
-google 1point3acres
会增加n^2的空间
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-23 19:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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