2016年阿里巴巴校园招聘笔试试题研发工程师

void BFS(ALGraph *G, int k) { }

//以下省略局部变量的说明，visited各初始值为False InitQueue(&Q); //置空队列 EnQueue(&Q, k); //k入队 while(!QueueEmpty(&Q)){

i DeQueue(&Q); //Vi出列 visited[i] True; //设置访问标记 print(\//访问Vi for(p G->adjlist[i].firstedge;p;p p->next) //依次搜索Vi的邻近点 if(!visited[p->adjvex]) //若Vi没有访问过 EnQueue(&Q, p->adjvex); //Vi入列 } //endofwhile //BFS

第四部分：JAVA选做题（注：阿里有大量JAVA研发工程师需求；选作以

下题目有机会增加该方向面试机会）

1. 请画出工厂模式的uml图，并简要描述这些要素的作用；列举以下这个模式的优势；给

出一个jdk源码中的例子。

2. Map是非常重要的数据结构，设计出一个Map的接口，用基于hash的算法简单实现这

个Map，如果对你实现的HashMap做支持高并发场景下的线程安全的优化，怎么改进？

更进一步，可以基于此HashMap如何最简单实现支持LRU算法的cache？如果要让这个cache支持分布式缓存服务，导入了哪些要解决的问题？请列举出来并给出你的解决方法。