一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1278|回复: 12
收起左侧

compressList 面经题目讨论

[复制链接] |试试Instant~ |关注本帖
106 发表于 2015-3-31 11:20:50 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@MedalliaMedallia - 内推 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
看到某位同学的onsite面经上有个题目, 没有思路, 求指点:

compressList(List<Map<K,V>> list)
有一个list,里面存了很多map,但这些map里大部分entry都是一样的,大部分对应的value也是一样的,现在怎么处理使call这个get(int listIndex, K key)的时候最快。

求大牛指教。
jiangyaokai 发表于 2015-4-3 05:51:54 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
106 发表于 2015-4-3 01:01
再请问你下你的面试官是这些吗?
10:00am-11:00am PDT: TJ Firpo
11:00am-12:00pm PDT: Aasmund Eldhu ...

TJ Aasmund Daniel are tech interviewers
Baolu is probably doing a product demo and Justin is the culture interview. .鏈枃鍘熷垱鑷1point3acres璁哄潧
David is the engineering manager, his questions are typically not very technically challenging
Everyone has their own set of questions.
回复 支持 1 反对 0

使用道具 举报

kurtwang 发表于 2015-3-31 11:29:01 | 显示全部楼层
关注一亩三分地微博:
Warald
我面过这个。。直接几个for循环一层一层遍历就行,遍历每个map,然后遍历每个map里的key
回复 支持 0 反对 1

使用道具 举报

jiangyaokai 发表于 2015-4-1 05:16:52 | 显示全部楼层
kurtwang 发表于 2015-3-31 11:29
我面过这个。。直接几个for循环一层一层遍历就行,遍历每个map,然后遍历每个map里的key

这不是问题,你当然得遍历输入。
关键是最后生成的便于查找的数据结构是什么。
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-4-1 06:11:05 | 显示全部楼层
jiangyaokai 发表于 2015-4-1 05:16. From 1point 3acres bbs
这不是问题,你当然得遍历输入。. more info on 1point3acres.com
关键是最后生成的便于查找的数据结构是什么。

还是map。。跟一个list of map,跟那个小哥讨论过。。时间复杂度是不变的,空间复杂度得看原list里面存的是什么
回复 支持 反对

使用道具 举报

 楼主| 106 发表于 2015-4-1 11:40:16 | 显示全部楼层
kurtwang 发表于 2015-4-1 06:11
还是map。。跟一个list of map,跟那个小哥讨论过。。时间复杂度是不变的,空间复杂度得看原list里面存的 ...

请问一下具体的map + list of Map 这里面面的key 和 value 分别是啥呢? 既然无法提高时间复杂度, 为什么面试官还问 “现在怎么处理使call这个get(int listIndex, K key)的时候最快” 呢? 求指教面试官期待的答案。
.1point3acres缃
补充内容 (2015-4-1 11:43):
compressList(List<Map<K,V>> list) 中的list如果是arraylist的话, get(int listIndex, K key)不已经是O(1)了吗?
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-4-1 11:54:18 | 显示全部楼层
106 发表于 2015-4-1 11:40
请问一下具体的map + list of Map 这里面面的key 和 value 分别是啥呢? 既然无法提高时间复杂度, 为什 ...

我也是都写完了之后才讨论出来的
时间复杂度已经最快. from: 1point3acres.com/bbs
为的是节省空间
回复 支持 反对

使用道具 举报

 楼主| 106 发表于 2015-4-2 01:16:24 | 显示全部楼层
kurtwang 发表于 2015-4-1 11:54
我也是都写完了之后才讨论出来的
时间复杂度已经最快
为的是节省空间

谢谢你的回复。 好像就用一个Map<Key, Map<ListIndex, Value>>  就行了, Map<ListIndex, Value> 中同一个value次数最多的搞个默认的, 不知道你的最后的想法是什么? 面试官同意你最后的想法吗?
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-4-2 02:51:30 | 显示全部楼层
106 发表于 2015-4-2 01:16. Waral 鍗氬鏈夋洿澶氭枃绔,
谢谢你的回复。 好像就用一个Map  就行了, Map 中同一个value次数最多的搞个默认的, 不知道你的最后的 ...

跟你的想法差不多,面试官说没问题
回复 支持 反对

使用道具 举报

 楼主| 106 发表于 2015-4-3 01:01:44 | 显示全部楼层
kurtwang 发表于 2015-4-2 02:51
跟你的想法差不多,面试官说没问题

再请问你下你的面试官是这些吗?
10:00am-11:00am PDT: TJ Firpo. Waral 鍗氬鏈夋洿澶氭枃绔,
11:00am-12:00pm PDT: Aasmund Eldhuset
12:00pm-12:30pm PDT: Baolu Shen
12:30pm-1:30pm PDT: Daniel Solmirano
1:30pm-2:30pm PDT: Justin Manduke
2:30pm-3:30pm PDT: David Lu

感激不尽!
回复 支持 反对

使用道具 举报

jiangyaokai 发表于 2015-4-3 05:56:52 | 显示全部楼层
106 发表于 2015-4-3 01:01
再请问你下你的面试官是这些吗?
10:00am-11:00am PDT: TJ Firpo. 鍥磋鎴戜滑@1point 3 acres
11:00am-12:00pm PDT: Aasmund Eldhu ...
-google 1point3acres
TJ Aasmund Daniel are tech interviewers. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Baolu is probably doing a product demo and Justin is the culture interview.
David is the engineering manager, his questions are typically not very technically challenging
Everyone has their own set of questions.
回复 支持 反对

使用道具 举报

kurtwang 发表于 2015-4-3 06:00:45 | 显示全部楼层
106 发表于 2015-4-3 01:01
再请问你下你的面试官是这些吗?
10:00am-11:00am PDT: TJ Firpo
11:00am-12:00pm PDT: Aasmund Eldhu ...

我电面的时候是TJ Firpo. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
别的人不知道了
回复 支持 反对

使用道具 举报

 楼主| 106 发表于 2015-4-3 12:04:28 | 显示全部楼层
jiangyaokai 发表于 2015-4-3 05:56
TJ Aasmund Daniel are tech interviewers
Baolu is probably doing a product demo and Justin is the  ...

大神乃诸葛孔明也, 能否求大神透露点你的面经题目啊?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-4-29 00:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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