北京亚马逊 java职位笔试题 分析

上午去亚马逊北京的公司去面试了，本来以为英文面试有点问题，结果跟老外交流一点问题都没有。

还是老美的英语正宗，不像印度人。。。。。，闲话少提，不过伊还给我一道笔试题，我没有思路，

被鄙视了，发到je上希望高手能给分析分析：

1，用户访问网站时，用随机的一个字符串表示该用户，同一个用户访问别的页面也用相同的字符串表示,用户id称为userId。

2，网站的每个页面用英文字符串来表示，称为page_type_id;

3，网站的访问日志的格式是：<userId 空格 page_type_id >

4,访问路径：找出用户访问最多三节访问路径，所谓三节路径是：home--prouduct---prouduct detail;

或者 prouduct--surport --faq  等等。

要求假设已经有了一个这样的一个日志文件，用java写一个程序，找出最多的三节路径。

下面是日志文件的示例：

123 home

234 product

456 product detail

123 product

456 product

......

这样的需求其实很多的日志分析工具都提供，还是很实用。 只不过不知道他们怎么实现这个功能的。

我花了半个小时没做出来，斗胆问了那个老外，他提示用两个harshmap就可以实现。
1个harshmap 放 <userId, page_type_id >

另一个harshmap 放<(page_type_id1,page_type_id2,page_type_id3),countNum>

当时不好意思细问，假如用harshmap 来放记录的话，同一个userId的记录不是被覆盖了，还有
(page_type_id1,page_type_id2,page_type_id3)这样的路径，有很多，难道把所有的页面都作一

遍排列组合吗？希望大家指点一下！谢谢！

 

 

综合了各位的意见，在jdk1.5下，实现了该算法，大家帮看看是否符合要求：

 

public class LogRecord { //日记记录

 private String trip1 = "";

 private String trip2 = "";

 private String trip3 = "";

 public String getTrip1() {
  return trip1;
 }

 public void setTrip1(String trip1) {
  this.trip1 = trip1;
 }

 public String getTrip2() {
  return trip2;
 }

 public void setTrip2(String trip2) {
  this.trip2 = trip2;
 }

 public String getTrip3() {
  return trip3;
 }

 public void setTrip3(String trip3) {
  this.trip3 = trip3;
 }

 @Override
 public boolean equals(Object obj) { //日志是否相等
  // TODO Auto-generated method stub
  if (this == obj)
   return true;
  if (obj == null)
   return false;
  if (getClass() != obj.getClass())
   return false;

  final LogRecord other = (LogRecord) obj;

  if (trip1.equals(other.trip1) && trip2.equals(other.trip2)
    && trip3.equals(other.trip3))
   return true;
  else
   return false;
 }

 @Override
 public String toString() {
  // TODO Auto-generated method stub
  return "[" + trip1 + "--" + trip2 + "--" + trip3 + "]";
 }

 public LogRecord(String trip1, String trip2, String trip3) {
  super();
  this.trip1 = trip1;
  this.trip2 = trip2;
  this.trip3 = trip3;
 }

 @Override
 public int hashCode() {    //计算hash值
  // TODO Auto-generated method stub
  final int prime = 31;
  int result = 1;
  result = prime * result + ((trip1 == null) ? 0 : trip1.hashCode());
  result = prime * result + ((trip2 == null) ? 0 : trip2.hashCode());
  result = prime * result + ((trip3 == null) ? 0 : trip3.hashCode());
  return result;

 }

}

 

主体类：

 

import java.util.ArrayList;
import java.util.HashMap;

public class Amason {

 private static HashMap<String, ArrayList> map = new HashMap<String, ArrayList>();
 private static HashMap<LogRecord, Integer> mapCount = new HashMap<LogRecord, Integer>();

 public static void Inital() { //初始化数据
  putPages("123", "home");
  putPages("234", "product spec");
  putPages("456", "support");
  putPages("123", "download center");
  putPages("456", "home");
  putPages("456", "download center");
  putPages("234", "download center");
  putPages("123", "support");
  putPages("456", "support");
 }

 public static void putPages(String userid, String page) {//把原始数据放到hashmap中
  if (map.get(userid) == null) {
   ArrayList<String> list = new ArrayList<String>();
   list.add(page);
   map.put(userid, list);
  } else {
   ArrayList<String> list = map.get(userid);
   list.add(page);
  }

 }

 public static void putRecord(LogRecord record) { //对每个用户的路径进行分析
  if (mapCount.get(record) == null) {
   mapCount.put(record, new Integer(1));
  } else {
   Integer count = mapCount.get(record);
   count = count + 1;
   mapCount.put(record, count);
  }
 }

 public static void putUserTrack() {

  for (String usrid : map.keySet()) {
   ArrayList<String> list = map.get(usrid);

   int size = list.size();
   if (size > 2) {
    for (int i = 0; i < size && i + 2 < size; i++) {  //路径是前后包含关系
     LogRecord record = new LogRecord(list.get(i), list
       .get(i + 1), list.get(i + 2));
     putRecord(record);
    }
   }
  }
 }

 public static void getCommonTrack() {  //简单打印出结果
  System.out.print(mapCount.keySet());
  System.out.print(mapCount.values());
 }

 public static void main(String[] args) {
  Inital();
  putUserTrack();
  getCommonTrack();
 }
}

 

第一个HashMap<userID,page_type_id>,因为日志是顺序添加的，比如：
userID page_type_id
123    home                1
456    production          2
123    home                3

那么第一个HashMap保存['123','home'］，同理，第三行标示用户‘123‘在相同页面刷新，那么可以跳过（等同于HashMap保存了这个值的话），如果没有遇到相同的话，
比如：
userID page_type_id
123    home                4
123    production          5
这样路径就变成了home-production，Map=['123','home,production'］,如果在第N行，用户123的路径，没有在home-production的话，比如：
userID page_type_id
123    detail              N
那么，这个时候第一个HashMap=['123','home,production,detail'］,第二HashMap保存［‘home,production,detail‘，1］（count=1）.

接下来，又遇到了用户“123”的话，把第一个HashMap['123','home,production,detail'］的值替换掉，重复前面的做法，当路径符合三节的时候，把用户123在一个HashMap上面的值取出来，跟第二个HashMap［‘home,production,detail‘，1］的键(‘home,production,detail‘)比较，如果有的话，+1，如果没有的话，添加新的key给第二个HashMap。

不知道楼主明白了吗？

没人顶吗？发表一下意见吧

访问路径，从一个链接到另一个链接不是很像链表么

	
Map map = new HashMap();
	function putPage(userid,page){
		if(map.get(userid)==null){
			List list = new ArrayList();
			list.add(page);
			map.put(userid,list);
		}else{
			List list=map.get(userid);
			list.add(page);
		}
	}

         function getTrack(userid,startpage,limit){
              List list=map.get(userid); 
              var tracks=[];
               
              for( var i in list ) {
                  if(i==startpage){
                      var track=[];
                      for(var j=0;j<limit;j++){
                          track.push(list.get(i+j))
                      }
	             tracks.push(track);
                  }
              }
             return tracks
         }

        

混合了java和JavaScript的伪代码

aws回答的很好，用链表来存储访问路径最好了。大家发表意见！

貌似不好吧？？链表的话内存要占太多

请原谅我连题目都兴趣没看

结合mercyblitz所说，我的理解是：第一个HashMap<userid,List<page>>就是用来记录每个用户访问记录的，但List的长度应该限制在3，即当用户123查看的页面为顺序为home,product,detain,support, download时，HashMap的值依次为
<123,<home>>,
<123,<home,product>>,
<123,<home,product,detail>>, 
<123,<product,detail,support>>,
<123,<detail,support,download>>
即第一个 HashMap只存放用户最新的三条访问记录， 当用户的最近的三条访问记录发生更新时，就更新第二个HashMap.

貌似很牛逼，这么说话是阿里系的吧？