10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 339|回复: 5
收起左侧

迟来的indeed电面面经

[复制链接] |试试Instant~ |关注本帖

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

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

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

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。

求各种面试……求google OA

评分

1

查看全部评分

say543 发表于 6 天前 | 显示全部楼层
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?. 鍥磋鎴戜滑@1point 3 acres
.1point3acres缃
补充内容 (2017-9-14 13:33):
是向hashMap<Key, class> 然后class里面存value 跟expiration time?
回复 支持 反对

使用道具 举报

candudu 发表于 6 天前 | 显示全部楼层
请问楼主哪个学校呢?招聘会这么早吗?
回复 支持 反对

使用道具 举报

 楼主| HorikawaRaiko 发表于 6 天前 | 显示全部楼层
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 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
对的。字数字数
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

夜皇雪 发表于 4 天前 | 显示全部楼层
  1. public class ExpiringMap<K, V> extends TimerTask {
  2.     // fields
  3.     class Node<K, V> {
  4.         // fields
  5.         private K key;
  6.         private V value;
  7.         private long duration;. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.         private long startTime;

  9.         // methods-google 1point3acres
  10.         public Node (V value, long duration, long startTime) {
  11.             this.value = value;
  12.             this.duration = duration;
  13.             this.startTime = startTime;
  14.         }
  15.     }

  16.     private LinkedList<Node> list;
  17.     HashMap<K, Node> map;

  18.     public ExpiringMap(){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  19.         map = new HashMap<>();
  20.         list = new LinkedList<>();
  21.     }



  22.     public void put(K key, V value, long duration) {
  23.         long startTime = System.currentTimeMillis();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  24.         Node node = new Node(value, duration, startTime);
  25.         map.put(key, node);
  26.         checkTime();
  27.         addToHead(value, duration, startTime);
  28.     }
  29. . 鍥磋鎴戜滑@1point 3 acres
  30.     public V get(K key) {
  31.         checkTime();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  32.         if (map.containsKey(key)) {
  33.             Node node = map.get(key);
  34.             return (V) node.value;
  35.         } else {
  36.             return null;
  37.         }
  38.     }

  39.     public void checkTime() {
  40.         long curTime = System.currentTimeMillis();
  41.         while (!list.isEmpty()) {
  42.             Node node = list.getLast();
  43.             if (node.duration + node.startTime > curTime) {
  44.                 list.removeLast();
  45.                 map.remove(node.key);
  46.             } else {
  47.                 break;
  48.             }
  49.         }
  50.     }
  51.     public void addToHead(V value, long duration, long startTime) {
  52.         Node node = new Node(value, duration, startTime);
  53.         list.addFirst(node);
  54.     }

  55.     @Override
  56.     public void run() {
  57.         checkTime();
  58.     }. Waral 鍗氬鏈夋洿澶氭枃绔,

  59.     public static void main(String[] args) {
  60.         Timer timer = new Timer(true);
  61.         ExpiringMap expiringMap = new ExpiringMap();
  62.         timer.schedule(expiringMap,0,1000);//1000毫秒检查一次. 鍥磋鎴戜滑@1point 3 acres
  63.     }
  64. }. from: 1point3acres.com/bbs
复制代码

自己写了一下,我也不确定是否对,所以贴一下大家找找错。
问一下多线程那个楼主当时写了吗,应该是只说思路吧??写感觉太复杂了。。。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-20 03:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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