【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

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

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

[Linkedin]电面新鲜面经

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

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

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

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

x
一共60min,简单自我介绍之后就是两个coding问题:
1. 先让写了一个reverseString,没花什么时间。

2. implements 一个Two Sum interface,里面有两个method:
    a. void store (int val) :  需要选一个数据结构作为存储,然后会不停地往里面add value。我选择的是List<Integer> 作为store.鏈枃鍘熷垱鑷1point3acres璁哄潧
    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) {.1point3acres缃
       nums.add(val);
    }

    @Override
    public boolean hasPair (int val) {
       if (nums.size() < 2) {
         return false;
       }
       Set <Integer> set = new HashSet<>();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

       for (int i = 0; i < nums.size(); i ++) {
          if (set.containsKey (nums.get(i))) {
                 return true;
          } else {
             set.add(val - nums.get(i));. visit 1point3acres.com for more.
          }
       }      
       return false;.鏈枃鍘熷垱鑷1point3acres璁哄潧
    }     
} . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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


评分

2

查看全部评分

say543 发表于 2016-8-13 14:40:59 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
.鏈枃鍘熷垱鑷1point3acres璁哄潧
follow up 有target 的time complexity 吗? 感觉蛮难的... 因为nums 不会改变 能够在所有store 完之后 先枚举在call hasPair 30000吗?
回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2016-8-14 03:45:00 | 显示全部楼层
关注一亩三分地微博:
Warald
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: 1point3acres.com/bbs
这样space complexity 会增加吗?
回复 支持 反对

使用道具 举报

LearnerChao 发表于 2016-8-16 03:13:16 | 显示全部楼层
say543 发表于 2016-8-15 13:45
这样space complexity 会增加吗?

会增加n^2的空间
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-21 10:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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