一亩三分地论坛

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

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

[Linkedin]电面新鲜面经

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

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

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

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

x
一共60min,简单自我介绍之后就是两个coding问题: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1. 先让写了一个reverseString,没花什么时间。. 1point 3acres 璁哄潧

2. implements 一个Two Sum interface,里面有两个method:
    a. void store (int val) :  需要选一个数据结构作为存储,然后会不停地往里面add value。我选择的是List<Integer> 作为store
    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) {. 鍥磋鎴戜滑@1point 3 acres
       nums.add(val);. 1point3acres.com/bbs
    }. 鍥磋鎴戜滑@1point 3 acres

    @Override
    public boolean hasPair (int val) {
       if (nums.size() < 2) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
         return false;. 鍥磋鎴戜滑@1point 3 acres
       }. 1point3acres.com/bbs
       Set <Integer> set = new HashSet<>();

       for (int i = 0; i < nums.size(); i ++) {
          if (set.containsKey (nums.get(i))) {. more info on 1point3acres.com
                 return true;
          } else {
             set.add(val - nums.get(i));
          }
       }      
       return false;.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }     
} . From 1point 3acres bbs

follow up 是假设要call 30000次hasPair 方法 (nums 里面的值不变),如何在保证没有extra space complexit的情况下,减少 time complexity。关于这点, 我并没有想出很好的答案, 欢迎讨论!
. From 1point 3acres bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

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 完之后 先 ...
. from: 1point3acres.com/bbs
这样会增加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 ...


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

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 13:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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