一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 572|回复: 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 | 显示全部楼层
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
. from: 1point3acres.com/bbs 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.
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

kurtwang 发表于 2015-4-1 06:11:05 | 显示全部楼层
jiangyaokai 发表于 2015-4-1 05:16
这不是问题,你当然得遍历输入。
关键是最后生成的便于查找的数据结构是什么。
-google 1point3acres
还是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)的时候最快” 呢? 求指教面试官期待的答案。

补充内容 (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 分别是啥呢? 既然无法提高时间复杂度, 为什 ...

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

使用道具 举报

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

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

使用道具 举报

kurtwang 发表于 2015-4-2 02:51:30 | 显示全部楼层
106 发表于 2015-4-2 01:16
谢谢你的回复。 好像就用一个Map  就行了, Map 中同一个value次数最多的搞个默认的, 不知道你的最后的 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
跟你的想法差不多,面试官说没问题
回复 支持 反对

使用道具 举报

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

再请问你下你的面试官是这些吗?
10:00am-11:00am PDT: TJ Firpo
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
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.
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, 2016-12-7 03:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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