昨天google笔试的题目分析

发信人: elevation(elevation), 信区: CS
标 题: 昨天google笔试的题目分析
发信站: 饮水思源 (2008年04月22日15:49:22 星期二)

选择题+三道算法题

选择题没什么难的 最后一道考的数据库使用什么存储结构不会做。。

算法题
第一题没什么好说
第二题可破坏一个数组A[0..N-1]的条件下使用最少的内存判断是否存在相同的元素
我的做法是堆排序 时间O(NlogN) 空间O(1) 复杂度上来看应该最优了
第三题已知每个点的父节点，求这棵树的最大独立集
用递归求解 类似动态规划 但是不存在重叠子状态 经典算法问题了
预处理每个节点的子节点存在一张表里
时间O(N）空间O(N）

大家做的结果是这样吗？

--

※ 修改内容:?elevation 于 04月22日16:37:47 修改本文?[FROM: ]

※ 修改内容:?elevation 于 04月22日16:40:36 修改本文?[FROM: ]


[回复本文] 发信人: phoenixCA(phoenix), 信区: CS
标 题: Re: 昨天google笔试的题目分析
发信站: 饮水思源 (2008年04月22日15:59:30 星期二)

你接到面试通知了吧？我猜．．．

【 在 elevation 的大作中提到: 】
: 选择题+三道算法题
: 选择题没什么难的 最后一道考的数据库使用什么存储结构不会做。。
: 算法题
: 第一题没什么好说
: 第二题可破坏一个数组A[0..N-1]的条件下使用最少的内存判断是否存在相同的元素
: 我的做法是堆排序 时间O(NlogN) 空间O(1) 复杂度上来看应该最优了
: 第三题已知每个点的父节点，求这棵树的最大独立集
: 用递归求解 类似动态规划 但是不存在重叠子状态 经典算法问题了
: 预处理每个节点的子节点存在一张表里
: 时间O(N）空间O(N）
: 大家做的结果是这样吗？

--
http://bbs.sjtu.edu.cn/file/WarCraft/111633283321730.jpg

http://bbs.sjtu.edu.cn/file/Inter/1150296246172540.jpg




※ 来源:?饮水思源 ?[FROM: ]


[回复本文] 发信人: elevation(elevation), 信区: CS
标 题: Re: 昨天google笔试的题目分析
发信站: 饮水思源 (2008年04月22日16:00:50 星期二)

有人接到了？我没有
那些卷子不会这么快就判好了吧
【 在 phoenixCA 的大作中提到: 】
: 你接到面试通知了吧？我猜．．．
: 【 在 elevation 的大作中提到: 】
: : 选择题+三道算法题
: : 选择题没什么难的 最后一道考的数据库使用什么存储结构不会做。。
: : 算法题
: : 第一题没什么好说
: : 第二题可破坏一个数组A[0..N-1]的条件下使用最少的内存判断是否存在相同的元素

: : 我的做法是堆排序 时间O(NlogN) 空间O(1) 复杂度上来看应该最优了
: : 第三题已知每个点的父节点，求这棵树的最大独立集
: : 用递归求解 类似动态规划 但是不存在重叠子状态 经典算法问题了
: : 预处理每个节点的子节点存在一张表里
: : 时间O(N）空间O(N）
: : 大家做的结果是这样吗？

--

※ 来源:?饮水思源 ?[FROM: ]


[回复本文] 发信人: phoenixCA(phoenix), 信区: CS
标 题: Re: 昨天google笔试的题目分析
发信站: 饮水思源 (2008年04月22日16:01:41 星期二)

parttime版出消息了

【 在 elevation 的大作中提到: 】
: 有人接到了？我没有
: 那些卷子不会这么快就判好了吧
: 【 在 phoenixCA 的大作中提到: 】
: : 你接到面试通知了吧？我猜．．．

--
http://bbs.sjtu.edu.cn/file/WarCraft/111633283321730.jpg

http://bbs.sjtu.edu.cn/file/Inter/1150296246172540.jpg




※ 来源:?饮水思源 ?[FROM: ]


[回复本文] 发信人: elevation(elevation), 信区: CS
标 题: Re: 昨天google笔试的题目分析
发信站: 饮水思源 (2008年04月22日16:05:10 星期二)

莫非选择题错一道就挂？。。。
【 在 phoenixCA 的大作中提到: 】
: parttime版出消息了
: 【 在 elevation 的大作中提到: 】
: : 有人接到了？我没有
: : 那些卷子不会这么快就判好了吧

--

※ 来源:?饮水思源 ?[FROM: ]


[回复本文] 发信人: phoenixCA(phoenix), 信区: CS
标 题: Re: 昨天google笔试的题目分析
发信站: 饮水思源 (2008年04月22日16:05:52 星期二)

bless
据说是，不清楚．．．