一亩三分地论坛

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

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

Indeed 9月电面

[复制链接] |试试Instant~ |关注本帖
liu452 发表于 2016-9-26 11:41:57 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Indeed - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

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

x

大家好,新人第一次发帖有点紧张:

目前EE转码农中,然后再LinkedIn上撩道一个Indeed的HR。 相谈甚欢之后安排了面试。 面试的职位是App Developer,在Austin。 面试官是一个老印。 题目如下:
public class ExpiringMap<K, V> {
      
        public void put(K key, V value, long duration) {
       . 1point3acres.com/bbs
        }

        public V get(K key) {
      
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
}
. Waral 鍗氬鏈夋洿澶氭枃绔,
[size=14.6667px]
.1point3acres缃
面试的环境是hackerrank,面试官的意思是要求写一个类似于hashmap的结构,其中除了传统的key和value之外另加了一个duration。 要求实现的功能是说讲一个数据存入此Map后,在duration的时间范围内call get function可以得出相应的value。 但是一但超出duration的这个时间,再call get function就只能返回 null。 举个例子 :
put(10, 35, 3000);
//在3000 毫秒以内:
get(10) --> return 35;
//超出3000毫秒:. Waral 鍗氬鏈夋洿澶氭枃绔,
get(10) --> return null;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
简单而言就是所谓的“限时阅读“。 题目UP主记得很清楚,不会有问题。

那么我的分析如下:
1.首先传统的hashmap只有key和value两个,那么要引入duration的这个参数,必须自己新建一个class data,里面存入泛型V还有一个关于时间的参数 duration, 并且还得记录这个数据写入的时间。
2.Java中有一个API叫做System.currentTimeMills(); 这个function可以get到系统当前的时间,并且是一millsecond的形式记录的。 那么在此基础上,加深我们有startTime,让startTime =  System.currentTimeMills()。 然后再call get function时再call一个System.currentTimeMills()。 如果 startTime + duration 小于 System.currentTimeMills(), 那么就可以返回null;
3.第三点其实是个细节,有点考察OOD design的功底,当时Up主没有想出来,后来经过和别人讨论,得出来的结论:
就是在data 超出duration之后,其实得引入一个remove function。 要不然在实际情况下,大量无用的data存在系统中会占用大量的空间。 所以我们在get 的时候应该remove掉expire的data。
4.继续引申第三点,不只是在get function中应该remove。 最理想的方式应该是每个一段时间就应该check一下内存,然后remove expired data。 但是UP功力还不够,下面的code中并没有写出。 望其他大神补充。

. From 1point 3acres bbs
我当时比较紧张,写出的答案大致方向上应该基本靠谱:
public class Data<V> {
        // fields
V value;
long duration;
long startTime;      

        // methods
        public Data (V value, long duration, long startTime) {
                this.value = value;
                this.duration = duration;
                this.startTime = startTime;
        }. 1point 3acres 璁哄潧
}
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
public class ExpiringMap<K, V> {
        // fields
        Hashmap map = new HashMap<K, Data>();

        // methods. visit 1point3acres.com for more.
        public void put(K key, V value, long durationMillis) {
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴                long startTime = System.currentTimeMills();
                Data data = new Data(value, durationMillis, startTime);
                map.put(key, data);
        }
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        public V get(K key) {
                Data data = map.get(key);.鐣欏璁哄潧-涓浜-涓夊垎鍦
                if (data == null) return null;
                if (data.startTime + data.duration <= System.currentTimeMills()) {
                        return data.value;
                } else {
                        map.remove(key);
return null;
                }
        }
}


本人第一次发帖,希望大家点赞。 也希望正在找工作的小伙伴们一切顺利啦。。。。。。。

评分

5

查看全部评分

myqdkl 发表于 2016-9-28 01:34:57 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
加油 祝好运!
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-9-28 02:25:09 | 显示全部楼层
关注一亩三分地微博:
Warald
indeed的new grad职位已经开了?
回复 支持 反对

使用道具 举报

laonong15 发表于 2016-9-30 00:08:08 | 显示全部楼层
MY two cents :.鏈枃鍘熷垱鑷1point3acres璁哄潧
The ides is use two maps  to  store the    key value pair and  key  lifecycle.   

import java.util.HashMap; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
import java.util.Map;. visit 1point3acres.com for more.

public class ExpiredMap<K,V> {
          Map<K,V> map;
          Map<K,LifeCycle> lifeMap ;
          public ExpiredMap() {
                this.map =  new HashMap<K,V>(); ;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                this.lifeMap = new HashMap<K,LifeCycle>();
                  . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }.1point3acres缃

        public void put(K key, V value, long duration) {
            LifeCycle lifeCycle = new LifeCycle(duration);  
            map.put(key, value);
            lifeMap.put(key, lifeCycle);
    }

      public V get(K key) {. 1point3acres.com/bbs
              LifeCycle lifeCycle =  lifeMap.get(key) ;
              if(lifeCycle == null  || lifeCycle.isExpired()){
                      return null;
              }
              return map.get(key);
      }
      class LifeCycle{
              long start;
              long duration;
              public LifeCycle(long duration){. visit 1point3acres.com for more.
                      start = System.currentTimeMillis();
                      this.duration = duration;
              }
              public boolean isExpired(){
                      return System.currentTimeMillis() - start > duration;
              }
      }
}
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-11-19 07:38:15 | 显示全部楼层
laonong15 发表于 2016-9-30 00:08
MY two cents :
The ides is use two maps  to  store the    key value pair and  key  lifecycle.   
...

感谢这位兄台分享代码,亮点是吧isExpire 写到了class里面,很OOD,但是我感觉你的代码也没有处理up主说的定时删掉无效data的操作,甚至,你在get到无效key的时候 都没有把相应的 你new出来放在两个map 里的key - value pair 和key- lifecycle pair给删掉呀。。。是吗?
回复 支持 反对

使用道具 举报

格格笑 发表于 2016-11-19 07:41:15 | 显示全部楼层
感谢up主分享,我有一个想法,你可以用多线程  再写一个线程,每常数时间来遍历删除一下无效data  ,但是我觉得这个应该超出了tech interview  coding的范围吧,图论已经很少考了,这多线程是神马鬼,所以我觉得up主的代码应该够了,或者非得删除无效代码你可以在每次get 或者put的时候就遍历map 删掉无效data 但是会严重降低put 和 get的效率
回复 支持 反对

使用道具 举报

lyyy7537721825 发表于 2016-12-9 06:28:18 | 显示全部楼层
LZ,我发现你的code可能有点小问题,这里,
                if (data.startTime + data.duration <= System.currentTimeMills()) {. 1point 3acres 璁哄潧
                        return data.value;
是不是应该大于等于?
或者是我二了?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-12-9 06:41:39 | 显示全部楼层
lyyy7537721825 发表于 2016-12-8 14:28
LZ,我发现你的code可能有点小问题,这里,
                if (data.startTime + data.duration

确实有问题。。我认为改成小于等于是对的。

说明这个持续时间不够持久,当前的时间一检查,发现过期了。
回复 支持 反对

使用道具 举报

shiroh880527 发表于 2016-12-25 02:12:35 | 显示全部楼层
@laonong15 思路是正确的,只需要继续想下去。 思路的大体方向应该是和LRU Cache差不多,如果读过Java Guava里的local cache的实现,那就更有思路了
要达成constant time的put和get显然是需要一个hashmap.来存放具体的key value pair.
然后entry class里面放一个timestamp用来存放写入时间和TTL

另外搞一个hashmap
. 鍥磋鎴戜滑@1point 3 acreskey是TTL
value是Doubly linked list.
每一次写入的时候你都要根据TTL找到对应的List, 把entry append 到最后。
这个list就是按照写入时间排序的,越前面的肯定越早写入,也应该越早被expire掉。
每次set的时候都扫一遍对应的list并且do expiration直到发现没有expired的值。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
每次get的的时候如果发现entry已经expired,remove掉这个entry并且同时Remove掉同一list中之前的也就是比这个entry更早写入的那些entry.

这样就不需要另启一个thread去做clean up了,扫全表的clean up开销太大了。.鐣欏璁哄潧-涓浜-涓夊垎鍦
同时在大多数情况写读写都是O(1)的,只有在某一个duration很久没有被Set或者get了才会是O(n)其中n也只是那个list的长度。而且这种时候的lock也只需要加在其中一个list上,对全局的性能并不影响。

代码我就不写了。祝楼主好运。
回复 支持 反对

使用道具 举报

sophie729 发表于 2017-1-12 12:27:46 | 显示全部楼层
楼主拿到 onsite了喵?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-29 19:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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