分享下银行招开发人员的第一轮题目

wangbo1118

邮件里发过来让你做的，主要写解决问题的思路
给应聘Java developer的人参考

Tech interview questions - “homework”
The following items should be completed in Java 1.7 without relying on other frameworks. The code should be production ready. Make reasonable assumptions if any information is missing.
If needed, make notes explaining the assumptions. Please don’t send binaries.Ideally your code can be compiled with Maven.
1.,
Implement an in-memory cache. What we know about the use case:
- The TTL of the items is fairly short (~10 seconds)
- The system has plenty of memory
- The keys are widely distributed across the keyspace
- Each item may or may not be accessed during the TTL
- Each item might be accessed multiple times during the TTL
2.,
Create a simple framework where work items can be submitted. Each work item is an instance of a class and the definition of “parallelism”, which controls how many threads are created to execute the work item.
The framework makes sure that the number of threads executing the work item should remain the same until the threads finished executing the work item, eg.: if the work item dies, the framework should restart it.
There is no need to cater for timeouts.
Sample interfaces for the framework:
public interface WorkItemExecutor
{
void executeWorkItem(WorkItem w, intparallelism);
}
public interface WorkItemCompletionCallback
{
void complete();
}
public interface WorkItem
{
void execute(WorkItemCompletionCallback callback);
}

karaoke_oz

看不懂....

wangbo1118

karaoke_oz 发表于 2014-8-5 16:22
看不懂....

那句看不懂啊？

Bessy

2个单词之间总要用空格分开吧.

1. 也许用 LRUcahce.
2. 可能用 CyclicBarrier

wangbo1118

Bessy 发表于 2014-8-5 20:48
2个单词之间总要用空格分开吧.

1. 也许用 LRUcahce.

sorry，我也不知道为什么贴进来很多空格就没了

题目不是说不能用框架吗？ LRUcache是安卓的库吗？

你能说下你的思路吗？

Bessy

wangbo1118 发表于 2014-8-5 23:04
sorry，我也不知道为什么贴进来很多空格就没了

题目不是说不能用框架吗？ LRUcache是安卓的库吗？

LRUCache -Least Recently Used cache 是个基本的cache 算法，就是把不常访问的数据删除。
如果是software engineer 职位,需要自己做一个LRUCache，可以用双向链表+hashtable. 如果是developer 职位就可以直接用LinkedhashMap + concurrenty，当然自己写一个LRUCache 显示基本功扎实。

题目的问题是：
- The TTL of the items is fairly short (~10 seconds)

Map的， Key保存访问的值，value保留最后访问时间

- The system has plenty of memory

有大量的，但不是无限的。所以要用LRUCache把不常用的删掉.

如果题目是没有大量的内存。 就需要用CopyOnWriteArrayList，加入listener去监听动态的时间。

但感觉他们的意思是不考虑内存的问题，如果那样就用ConcurrentHashMap保存<key, value>。这个简单许多。

- The keys are widely distributed across the keyspace

Hash算法会自动实现这个功能,

- Each item may or may not be accessed during the TTL

打酱油的

- Each item might be accessed multiple times during the TTL

用 ReentrantReadWriteLock 去更新访问时间<value>

wangbo1118

Bessy 发表于 2014-8-6 11:56
LRUCache -Least Recently Used cache 是个基本的cache 算法，就是把不常访问的数据删除。
如果是softwa ...

呵呵，看来是同道中人了

我的理解有一点点不一样


我的理解Least Recently Used cache，一般是用在缓存大小明显受到限制的情况下，当缓存装满了，这个时候最先踢出的是缓存中最不常用的记录。实现的方法就是每次命中缓存，就把命中的时间戳更新，以让其排到最后被踢出的位置


我觉得既然题目中提到了TTL（Time To Live），是不是就和Least Recently Used cache 没有太大的关系呢？


现实中我碰到有TTL的缓存情况很少，比如DNS服务器，当一个域名和ip被DNS请求从服务器拿回来的时候，同时还有一个TTL值一起拿回来，然后一起存在本地的缓存（一般TTL是一天），然后这样短期里访问就不用再问服务器了，因为网站的ip变化没那么频繁，这样可以大幅减少DNS请求，可能造成的不良后果也只是在缓存里不正确ip还没过期的时候，会有访问不到的情况，这个时候让他主动清缓存再尝试去多访问一次DNS就好了，就是说代价很小，收益很大


我在想，这里提的TTL应该是类似的吧，既然有TTL 了，过期时间就已经被TTL指定了，我们应该就不用LRU这样的淘汰机制了吧？（这里是对题目描述情况的关键理解差异点）

如果按照这样的理解，那简单一点实现就是ConcurrentHashMap保存<key, value>，value保存的是TTL，然后在get方法里面判断是不是过期了，如果过期了，就返回空，然后清空对应的缓存

这样的简单实现就是不考虑缓存满的情况了，因为题目里面说内存超大的

如果要在这个基础上进一步改进，可以写一个线程专门定期去清理过期的缓存，释放一点内存

不知道我的理解是否正确，有没有什么漏洞，欢迎讨论：）

Bessy

呵呵，我也感觉我们都不是做多线程的。 我是做数据的。应该在标题上加个多线程，吸引大牛进来。

LRUCahce 是对应 需求“The system has plenty of memory”。因为Key值是developer定的，机器上的内存developer可以设定。所以可以计算出可以保存 多少条记录， 也就是LRUcahce 的容量。

但是你的方法 “可以写一个线程专门定期去清理过期的缓存，释放一点内存”， 就不好控制这个“定期”了。因为一个系统的through put是由用户产生的。而且ConcurrentHashMap没有排序，每次检查 Big O(n)，假如每分钟有1百万条记录，你需要考虑“清理过期”的消耗,和内存的增长。再加上下面提到的读写冲突问题。系统很快就会崩溃。

“get方法判断是不是过期” 只解决了多线程的读。你没考虑多线程的读写冲突问题。 你可以考虑把Value值定为immutable， 但对于频繁读写的系统，消耗也是不可接受的。

如果一定要用ConcurrentHashMap 就要考虑我的第二种方案”用CopyOnWriteArrayList，加入listener去监听动态的时间“。具体时间可以参考 Apache Mina 的 expiredMap (http://svn.apache.org/repos/asf/ ... il/ExpiringMap.java). 但LinedIn做这个是因为他的内存实在是hold不住了。  

piddock

wangbo1118 发表于 2014-8-7 11:41
呵呵，看来是同道中人了

我的理解有一点点不一样

"我觉得既然题目中提到了TTL（Time To Live），是不是就和Least Recently Used cache 没有太大的关系呢？"

还是有关系的，下次当你执行get这个数据，首先要查看有没有过期，如果过期了，直接要从cache里面删掉，不管这个数据是在cache中排在了哪里。

Oken

题目不错，既不是太难又不是很白，而且可以展开讨论。这地方因该值得去

Bessy

piddock 发表于 2014-8-7 13:18
"我觉得既然题目中提到了TTL（Time To Live），是不是就和Least Recently Used cache 没有太大的关系呢 ...

你和LZ理解是相似的 "下次当你执行get这个数据，首先要查看有没有过期，如果过期了，直接要从cache里面删掉"。 但我不是这样理解的。

我感觉这是一个考点， 如果client.get（）数据，过期不是要从cache里面删掉，而是要更新数据的访问时间，LRUCache就不会把数据删掉。 如果用检查线程，检查线程.get()的过期数据可以删掉。 但2个都必须考虑读写锁。

piddock

Bessy 发表于 2014-8-7 14:04
你和LZ理解是相似的 "下次当你执行get这个数据，首先要查看有没有过期，如果过期了，直接要从cache里面删 ...

难道理论上不是过期了就该删掉，重新从其他地方（如外存等）load进入memory吗？更新访问时间没有意义，旧的数据需要被新的数据替代。

虞宅与美丽

不明觉厉

fantom

年薪20万的楼

ATO

大牛来了，你们在说啥，我没看懂

很明显

第一题，不用想太多了

- The TTL of the items is fairly short (~10 seconds)
生成时间记下来，后面看过期没过期
- The system has plenty of memory
不用随时清理
- The keys are widely distributed across the keyspace
不用考虑key hash到一个slot的情况
- Each item may or may not be accessed during the TTL
废话
- Each item might be accessed multiple times during the TTL
access到就加10秒，过期的return null，把新产生的cache起来

就完了呗，还想什么least visit

这题我见过啊，不知道谁抄谁

很明显

真有题目的时候，平时那些高瞻远瞩，指点江山的“大牛”就不来了

Bessy

piddock 发表于 2014-8-7 15:56
难道理论上不是过期了就该删掉，重新从其他地方（如外存等）load进入memory吗？更新访问时间没有意义，旧 ...

1. 删除一个Object 需要GC回收。建立新的对象需要申请内存,这样的消耗，并发程序很难承受。 所以尽力避免建立新的object。 所以人们开始考虑重用对象。如：thread pool, database connection pool.

Reuse Objects Instead of Creating New Ones If Possible：
http://docs.oracle.com/cd/A97688 ... bp/java.htm#1007412

2. 在并发系统中,如果修改已经存在的Object. 其他‘读’操作等这个‘写锁’执行后，可以正常进行读。如果删除对象，其他的‘读’操做就要被丢掉，然后再重新建立Object.

Bessy

ATO 发表于 2014-8-7 17:47
大牛来了，你们在说啥，我没看懂

大牛是在办公室，揣着明白装糊度。 我们这些找工的，是想装明白，却被雇主看破了。

Bessy

很明显 发表于 2014-8-7 19:09
第一题，不用想太多了

- The TTL of the items is fairly short (~10 seconds)

“access到就加10秒，“， 一共32个级别的锁（默认是16），你怎么用锁更优.。先那两个放上试试，不行再换？

”过期的return null” 怎么判断是否过期，你的判断策略？

很明显

Bessy 发表于 2014-8-7 19:55
“access到就加10秒，“， 一共32个级别的锁（默认是16），你怎么用锁更优.。先那两个放上试试，不行再换 ...

想太多了

考点想出来了，你还在想什么，狠不得把自己知道不知道都加进去吧

piddock

Bessy 发表于 2014-8-7 19:41
1. 删除一个Object 需要GC回收。建立新的对象需要申请内存,这样的消耗，并发程序很难承受。 所以尽力避免 ...

重用对象从概念上来说是很好的，但是用在这里是否有点偏题？

我的理解，第一题也就是LRU算法的应用，网上有不少现成的Java例子。

千叶

Mark一记

wangbo1118

piddock 发表于 2014-8-7 23:53
重用对象从概念上来说是很好的，但是用在这里是否有点偏题？

我的理解，第一题也就是LRU算法的应用，网 ...

我就偏题一下。。。

对于重用对象，要看场合


之前我做的产品是个电信的应用服务器，然后我们做的时候的策略是，尽量减少生命周期很长的对象，有些对象就让它不断的创建，消亡，再创建。

这样做的理由是，基于GC的策略，GC会经常来一次小的清扫，然后等到快不行了来一次大的清扫，这样的系统，很多小对象就在小清扫中被收集了，系统很难进入到大清扫阶段，而大清扫会hold住内存，让系统有明显的停滞感，服务器要避免的就是这种停滞，而收集的cpu开销，还有内存开销，都是系统可以负担的，唯独这个大清扫时hold住内存的停滞，是没法避免的

还有就是缓存的设计，是一开始就让缓存分配到尽可能的大，而且一开始就让它分配好，而不是像一般的程序是动态分配的，有多少内容会动态增长的。这样的话分配缓存就影响的是服务器启动的时间，系统起来以后就快了，因为不用再分配了。
对这样的大型服务器来说，硬件配个几十几百个G的内存都是可行的，CPU弄个几排也没问题，关键要运行的时候一直“爽”，别不稳定，别卡



这两点题外话不知道有没有表达清楚

Bessy

piddock 发表于 2014-8-7 23:53
重用对象从概念上来说是很好的，但是用在这里是否有点偏题？

我的理解，第一题也就是LRU算法的应用，网 ...

减少建立不必要的Objext，应该是OO的基本原则。除非对方不要求会OO.  这就如同一个找工的说有5年开发经验，但定义变量还是 int a, boolean b,一样。

更何况，删除的Object, 立刻又被重新建立，这个逻辑上都说不通。

这2个题都是考多线程开发。 简化点，这道题主要考，用 ReentrantReadWriteLock 去更新访问时间<value>。

Bessy

wangbo1118 发表于 2014-8-8 00:44
我就偏题一下。。。

对于重用对象，要看场合

你做的应该不是电信对普通用户的实时并发系统，应该也不是有些delay的系统如，（SMS, MMS系统），否则，你就会看到在高峰期，内存在不断增长，直到系统崩溃。 因为，GC无法获得资源去回收内存。
也许我猜错了。

righttang

in memory cache 还要自己写么，汗。。。。
真的要production ready 那集群，同步，fail over 怎么办？  我一般用现成的cache 产品，比如说coherence..

直接建立一个，policy, 你想怎么配置就怎么配置

很明显

澳洲IT，人才济济

piddock

wangbo1118 发表于 2014-8-8 00:44
我就偏题一下。。。

对于重用对象，要看场合

你说的实际上是增量垃圾收集方法，有的系统确实偏向于这种经常性的小暂缓，而尽量避免完全的停顿。

但是凡事都有tradeoff，不断的创建新的对象，再不停的收集，从总体性能上讲应该是下降的。

重用对象可以考虑用简单的pool之类的方法，更繁琐的是分析相同类型的对象的生命周期是否overlap，如果不是的话就可以重用，这当然已经归入research的范畴了。

piddock

Bessy 发表于 2014-8-8 07:36
减少建立不必要的Objext，应该是OO的基本原则。除非对方不要求会OO.  这就如同一个找工的说有5年开发经验 ...

OO并没有说要尽量减少建立不必要的Object，我的理解OO就是三个原则：继承、封装和多态。

相反，从软工的角度讲，很多情况下都是推荐建立很多同类型的短生命周期的Object，使得程序简单易懂。