《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 923|回复: 5
收起左侧

迟来的indeed电面面经

[复制链接] |试试Instant~ |关注本帖
HorikawaRaiko 发表于 2017-9-14 13:11:38 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Indeed - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
这家是一个星期之前面的了,其实就是个面经题,不过今天学校招聘会结束了想想还是发出来给下面的找工攒攒人品,求多来点面试。
题目是expiring map,老题了,地里搜一下就有,大意是设计一个map,put的时候除了key value同时还有一个timeout,get的时候如果这个value的timeout过了就得返回null。
总体思路就是用一个hashmap来存了。我先把naive的方法写了,get时发现超时就delete,这种方法只要一个expire的key value没有被访问到就会一直吃内存空间。改进的方法当时我也没想到太好的,我想的是多线程的方法,把存进hashmap的entry也同时用另外一个heap来装,然后用一个后台线程不断的peek element判断是否expire然后决定是否remove掉。这种涉及锁,不仅难写,而且性能有问题。最好的办法还是用linkedlist,大家可以参考这个帖子里亮贴的分析。之后来了onsite。. from: 1point3acres.com/bbs

求各种面试……求google OA

评分

2

查看全部评分

夜皇雪 发表于 2017-9-16 01:01:36 | 显示全部楼层
  1. public class ExpiringMap<K, V> extends TimerTask {
  2.     // fields. 1point 3acres 璁哄潧
  3.     class Node<K, V> {
  4.         // fields.1point3acres缃
  5.         private K key;
  6.         private V value;
  7.         private long duration;
  8.         private long startTime;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  9. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10.         // methods.1point3acres缃
  11.         public Node (V value, long duration, long startTime) {
  12.             this.value = value;
    . 1point3acres.com/bbs
  13.             this.duration = duration;
  14.             this.startTime = startTime;
  15.         }
  16.     }

  17.     private LinkedList<Node> list;
  18.     HashMap<K, Node> map;
  19. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.     public ExpiringMap(){
  21.         map = new HashMap<>();
  22.         list = new LinkedList<>();
  23.     }


  24. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  25.     public void put(K key, V value, long duration) {
  26.         long startTime = System.currentTimeMillis();
  27.         Node node = new Node(value, duration, startTime);
  28.         map.put(key, node);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  29.         checkTime();
  30.         addToHead(value, duration, startTime);
  31.     }

  32.     public V get(K key) {
  33.         checkTime();
    . from: 1point3acres.com/bbs
  34.         if (map.containsKey(key)) {
  35.             Node node = map.get(key);
  36.             return (V) node.value;
  37.         } else {. From 1point 3acres bbs
  38.             return null;
  39.         }
  40.     }

  41.     public void checkTime() {
  42.         long curTime = System.currentTimeMillis();. Waral 鍗氬鏈夋洿澶氭枃绔,
  43.         while (!list.isEmpty()) {
  44.             Node node = list.getLast();
  45.             if (node.duration + node.startTime > curTime) {
  46.                 list.removeLast();. Waral 鍗氬鏈夋洿澶氭枃绔,
  47.                 map.remove(node.key);. 鍥磋鎴戜滑@1point 3 acres
  48.             } else {
  49.                 break;
  50.             }
  51.         }
  52.     }
  53.     public void addToHead(V value, long duration, long startTime) {
  54.         Node node = new Node(value, duration, startTime);
  55.         list.addFirst(node);.1point3acres缃
  56.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦

  57.     @Override
  58.     public void run() {
  59.         checkTime();
  60.     }.1point3acres缃
  61. . 1point 3acres 璁哄潧
  62.     public static void main(String[] args) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  63.         Timer timer = new Timer(true);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  64.         ExpiringMap expiringMap = new ExpiringMap();
  65.         timer.schedule(expiringMap,0,1000);//1000毫秒检查一次
  66.     }
  67. }
复制代码
-google 1point3acres
自己写了一下,我也不确定是否对,所以贴一下大家找找错。. visit 1point3acres.com for more.
问一下多线程那个楼主当时写了吗,应该是只说思路吧??写感觉太复杂了。。。
回复 支持 1 反对 0

使用道具 举报

say543 发表于 2017-9-14 13:33:09 | 显示全部楼层
Shì xiàng hashMap<Key,  class>  ránhòu class lǐmiàn cún value gēn expiration time?  是向hashMap<Key, class> 然后class里面存value 跟expiration time?

补充内容 (2017-9-14 13:33):
是向hashMap<Key, class> 然后class里面存value 跟expiration time?
回复 支持 反对

使用道具 举报

candudu 发表于 2017-9-14 15:47:56 | 显示全部楼层
请问楼主哪个学校呢?招聘会这么早吗?
回复 支持 反对

使用道具 举报

 楼主| HorikawaRaiko 发表于 2017-9-14 21:53:08 | 显示全部楼层
say543 发表于 2017-9-14 13:33
Shì xiàng hashMap  ránhòu class lǐmiàn cún value gēn expiration time?  是向hashMap 然后clas ...

对的。字数字数
回复 支持 反对

使用道具 举报

 楼主| HorikawaRaiko 发表于 2017-9-14 21:53:35 | 显示全部楼层
candudu 发表于 2017-9-14 15:47
请问楼主哪个学校呢?招聘会这么早吗?

我是CMU的,招聘会开的确实早
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 17:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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