May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

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

compressList 面经题目讨论

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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

compressList(List<Map<K,V>> list)
有一个list,里面存了很多map,但这些map里大部分entry都是一样的,大部分对应的value也是一样的,现在怎么处理使call这个get(int listIndex, K key)的时候最快。
. Waral 鍗氬鏈夋洿澶氭枃绔,
求大牛指教。
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.
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

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

使用道具 举报

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

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

使用道具 举报

 楼主| 106 发表于 2015-4-1 11:40:16 | 显示全部楼层
kurtwang 发表于 2015-4-1 06:11
还是map。。跟一个list of map,跟那个小哥讨论过。。时间复杂度是不变的,空间复杂度得看原list里面存的 ...
. 1point 3acres 璁哄潧
请问一下具体的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 分别是啥呢? 既然无法提高时间复杂度, 为什 ...

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

使用道具 举报

 楼主| 106 发表于 2015-4-2 01:16:24 | 显示全部楼层
kurtwang 发表于 2015-4-1 11:54. visit 1point3acres.com for more.
我也是都写完了之后才讨论出来的
时间复杂度已经最快. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
为的是节省空间

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

使用道具 举报

kurtwang 发表于 2015-4-2 02:51:30 | 显示全部楼层
106 发表于 2015-4-2 01:16. visit 1point3acres.com for more.
谢谢你的回复。 好像就用一个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. From 1point 3acres bbs
再请问你下你的面试官是这些吗?
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.鏈枃鍘熷垱鑷1point3acres璁哄潧
TJ Aasmund Daniel are tech interviewers
Baolu is probably doing a product demo and Justin is the  ...

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-27 20:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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