一亩三分地论坛

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

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

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。 面试官是一个老印。 题目如下: . 1point3acres.com/bbs
public class ExpiringMap<K, V> {
      
        public void put(K key, V value, long duration) {
      
        }. more info on 1point3acres.com

        public V get(K key) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
      
        }
}

[size=14.6667px]

面试的环境是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毫秒:
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中并没有写出。 望其他大神补充。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


我当时比较紧张,写出的答案大致方向上应该基本靠谱:
public class Data<V> {.鐣欏璁哄潧-涓浜-涓夊垎鍦
        // fields
V value;
long duration;
long startTime;      

        // methods
        public Data (V value, long duration, long startTime) {-google 1point3acres
                this.value = value;
                this.duration = duration;. 鍥磋鎴戜滑@1point 3 acres
                this.startTime = startTime;
        }
}

public class ExpiringMap<K, V> {
        // fields.鏈枃鍘熷垱鑷1point3acres璁哄潧
        Hashmap map = new HashMap<K, Data>();. more info on 1point3acres.com

        // methods
        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;
                }
        }
}


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

评分

4

查看全部评分

myqdkl 发表于 2016-9-28 01:34:57 | 显示全部楼层
加油 祝好运!
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-9-28 02:25:09 | 显示全部楼层
indeed的new grad职位已经开了?
回复 支持 反对

使用道具 举报

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

import java.util.HashMap;
import java.util.Map;

public class ExpiredMap<K,V> {
          Map<K,V> map;
          Map<K,LifeCycle> lifeMap ;
          public ExpiredMap() {
                this.map =  new HashMap<K,V>(); ;
                this.lifeMap = new HashMap<K,LifeCycle>();
                  
        }

        public void put(K key, V value, long duration) {
            LifeCycle lifeCycle = new LifeCycle(duration);  
            map.put(key, value); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            lifeMap.put(key, lifeCycle);.鏈枃鍘熷垱鑷1point3acres璁哄潧
    }

      public V get(K key) {
              LifeCycle lifeCycle =  lifeMap.get(key) ; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
              if(lifeCycle == null  || lifeCycle.isExpired()){
                      return null;
              }. From 1point 3acres bbs
              return map.get(key);
      }.鏈枃鍘熷垱鑷1point3acres璁哄潧
      class LifeCycle{
              long start;. more info on 1point3acres.com
              long duration;
              public LifeCycle(long duration){
                      start = System.currentTimeMillis();
                      this.duration = duration;
              }.鏈枃鍘熷垱鑷1point3acres璁哄潧
              public boolean isExpired(){
                      return System.currentTimeMillis() - start > duration;
              }
. 1point 3acres 璁哄潧      }
}
回复 支持 反对

使用道具 举报

格格笑 发表于 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 发表于 前天 06:28 | 显示全部楼层
LZ,我发现你的code可能有点小问题,这里,
                if (data.startTime + data.duration <= System.currentTimeMills()) {
                        return data.value;
是不是应该大于等于?
或者是我二了?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

忆梦前尘 发表于 前天 06:41 | 显示全部楼层
lyyy7537721825 发表于 2016-12-8 14:28
LZ,我发现你的code可能有点小问题,这里,
                if (data.startTime + data.duration
-google 1point3acres
确实有问题。。我认为改成小于等于是对的。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
说明这个持续时间不够持久,当前的时间一检查,发现过期了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 01:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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