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

dasheng

浏览: 148580 次
性别:
来自: 北京

最近访客更多访客>>

czldl

小轩子

skzr.org

mistlxj

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

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

Java 招聘 Spring 面试软件测试

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

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

被鄙视了，发到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();
}
}

分享到：

jnlp 与java web start | <java编程思想>学习笔记21 第21章并发 ...

2010-07-07 17:23
浏览 4923
评论(19)
论坛回复 / 浏览 (19 / 14960)
分类:非技术
查看更多

19 楼 hardPass 2010-07-09

倒，难道要规范用户的访问习惯，使他们访问一定都是按顺序访问？

18 楼 izual1128 2010-07-08

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Log {

public static void main(String[] args){
//保存用户访问日志链
Map userLogMap = new HashMap();
//保存每个用户链的计数
Map countMap = new HashMap();
//假设日志保存到 log中
List log = new LinkedList();
//浏览每一个日志
for(int i = 0 ;i<log.size(); i++){
UserLog ul = (UserLog)log.get(i);
//取得用户的访问链
List tmp = (List)userLogMap.get(ul.getUserId());

if(tmp==null){
tmp = new LinkedList();
}
//把用户的访问放到访问链中
tmp.add(ul.getPage());
//比要计数的链长了就把第一个去掉
if(tmp.size() > 3){
tmp.remove(1);
}
//正好等于要计数的链长度时计数
if(tmp.size() == 3 ){
//取得链中的路径，并计数后放到 map中
StringBuffer pagePath = new StringBuffer();
for(int j =0 ;j<tmp.size();j++){
pagePath.append(tmp.get(i)).append(",");
}
Long count = (Long)countMap.get(pagePath.toString());
if(count==null){
countMap.put(pagePath.toString(), 1);
}else{
countMap.put(pagePath.toString(), count+1);
}
}
userLogMap.put(ul.getUserId(), tmp);
}

}
}
class UserLog{
String userId;
String page;
public String getUserId() {
return userId;
}
public void setUserId(String userId) {
this.userId = userId;
}
public String getPage() {
return page;
}
public void setPage(String page) {
this.page = page;
}

}

随便写了一段，没有测试。

17 楼 dasheng 2010-07-08

<div class="quote_title">dasheng 写道</div>
<div class="quote_div">
综合了各位的意见，在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(); } }
 
大家帮看看，这样解决行不行？有没有更好的思路！！！！ 
</div>

16 楼 chinpom 2010-07-08

mercyblitz 写道

第一个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。

不知道楼主明白了吗？

看了你的回答，我现在才看懂了题目什么意思了，呵呵。

15 楼 dasheng 2010-07-08

综合了各位的意见，在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(); } }

14 楼 proud686 2010-07-08

map1： <userId, List(page_type_id)>
map2: 对map1中List.size >3 的算出可能的三节路径做为key, value就是其数字，遍历一个userId，存在就+1

13 楼 xpower 2010-07-08

<div class="quote_title">dasheng 写道</div>
<div class="quote_div">
<div class="quote_title">mercyblitz 写道</div>
<div class="quote_div">第一个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。 不知道楼主明白了吗？ </div>
<div class="quote_div">感谢mercyblitz的回复，大概看明白你的思路了，不过有一点需要讨论，你说找到一个三节路径的用户后，新增加该用户的记录把原来的替换，重新开始。我的理解是三节路径是前后包含的关系的。比如用户123 的访问路径是 home,production,detail,support,download.那么可能的三节路径是home,production,detail；production,detail,support；detail,support,download；所以我认为需要先遍历一遍日志文件，得到所有不同的用户的路径。然后按前后包含的方法来遍历所有的用户的路径。最后才加入第二HashMap。不知道对不对，希望高手继续讨论，谢谢！</div>
</div>
 三节路径已经定死了，就两个，楼主是不是想多了？

12 楼 Lincoln 2010-07-08

一般会用搜索引擎统计分析日志。

11 楼 bryande 2010-07-08

terrylrvin 写道

上海-猎头1 写道

四年以上Java软件工程师这么难找？
我是一名上海猎头，最近使用各种手段去猎人，老大要求的是4年以上J2EE相关经验，大专以上学历，在各种招聘网站和论坛上找了好几天，真的那么难找！我才做猎头没几天，郁闷死我了！
下面贴上招聘要求，如有符合要求的可以随时联系我！！！

猎头职位描述：
1，进行业务需求分析，系统设计和软件概要设计
2，进行软件详细设计和编码实现，确保安全，质量和性能
3，维护和升级现有软件产品，快速定位并修复现有软件缺陷
4，负责相关产品的文档编写
猎头职位要求：
1，本科以上学历，计算机软件或相关专业
2，四年以上J2EE项目开发经验
3，熟练掌握J2EE，包括Spring,Spring mvc,iBatis,Struts,Esb等框架，熟悉Linux,Cache,HTML,UML等相关技术
4，熟悉软件过程，热爱程序员工作，有技术追求
5，具有良好的团队合作精神，愿意分享，并积极上进
6，学习能力强，踏实肯干
7，有互联网，金融，支付等行业经验者优先
工作地点是：杭州和上海
绝对是正经的工作！！！

另外，我还有Q群
━═☆Java EE☆═━ 1894459 0/200
≮JavaEye初级程序员 7736086 190/200
大家看着加啊，都是Java程序员！都是javaeye的

你透露一点待遇方面的情况，会有人联系你的

确实
既然是猎头就应该主动联系程序员
若想被程序员主动联系确实需要非常大的诱惑才行
你要主动出击
貌似我偏题了

10 楼 terrylrvin 2010-07-08

上海-猎头1 写道

你透露一点待遇方面的情况，会有人联系你的

9 楼 berlou 2010-07-08

lyw985 写道

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

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

8 楼 phoenixfm 2010-07-08

结合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.

7 楼 lyw985 2010-07-08

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

6 楼 JimmyWen 2010-07-08

dasheng 写道

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

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

5 楼 dasheng 2010-07-08

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

4 楼 aws 2010-07-08

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

	
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的伪代码

3 楼 dasheng 2010-07-08

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

2 楼 dasheng 2010-07-07

<div class="quote_title">mercyblitz 写道</div>
<div class="quote_div">第一个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。 不知道楼主明白了吗？ </div>
<div class="quote_div">感谢mercyblitz的回复，大概看明白你的思路了，不过有一点需要讨论，你说找到一个三节路径的用户后，新增加该用户的记录把原来的替换，重新开始。我的理解是三节路径是前后包含的关系的。比如用户123 的访问路径是 home,production,detail,support,download.那么可能的三节路径是home,production,detail；production,detail,support；detail,support,download；所以我认为需要先遍历一遍日志文件，得到所有不同的用户的路径。然后按前后包含的方法来遍历所有的用户的路径。最后才加入第二HashMap。不知道对不对，希望高手继续讨论，谢谢！</div>

1 楼 mercyblitz 2010-07-07

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

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

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

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

评论

发表评论

相关推荐

最近访客更多访客>>

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