s*********a
发帖数: 16 | 1 发个面经, 上周的, 攒rp
算上recruiter六个人
第一个, hr, 简单的问了学校, 专业, 毕业时间, 介绍了一下面试流程
第二个, 两道题:
1. 用stack实现queue, 白板coding
2. 设计问题, 比较复杂, 个人觉得重复考到的可能非常小, 这就不说了, 有特别需要
的同学再找我...
第三个, hiring manager, 吃午饭
先介绍了他们组的基本工作, 问我暑期实习
然后问题是Amazon的shopping experience怎么样, 有什么改进的地方
第四个, 两道题:
1. 一个大小为n的方形矩阵, 按顺时针的方向打印, 白板coding
比如:
1 2 3
4 5 6
7 8 9
打印顺序: 1 2 3 6 9 8 7 4 5
2. 设计题: 一个机器人, 一个迷宫, 有两个team, 一个负责hardware, 一个负责
software, 设计一组API来让两个team协同工作, 使机器人走出迷宫.
Follow-up: 因为hardware的开发较慢, software组自己设计表示迷宫和机器人, 这种
情况怎样改变设计以达到目的 | b******v
发帖数: 1493 | 2 cong!
多谢分享经验
【在 s*********a 的大作中提到】
: 发个面经, 上周的, 攒rp
: 算上recruiter六个人
: 第一个, hr, 简单的问了学校, 专业, 毕业时间, 介绍了一下面试流程
: 第二个, 两道题:
: 1. 用stack实现queue, 白板coding
: 2. 设计问题, 比较复杂, 个人觉得重复考到的可能非常小, 这就不说了, 有特别需要
: 的同学再找我...
: 第三个, hiring manager, 吃午饭
: 先介绍了他们组的基本工作, 问我暑期实习
: 然后问题是Amazon的shopping experience怎么样, 有什么改进的地方
| r****o
发帖数: 1950 | 3 多谢，请问那个方形，row和column都排序，找某元素的O(n)的做法是怎么样的？
这题应该可以用binary search。
【在 s*********a 的大作中提到】
: 发个面经, 上周的, 攒rp
: 算上recruiter六个人
: 第一个, hr, 简单的问了学校, 专业, 毕业时间, 介绍了一下面试流程
: 第二个, 两道题:
: 1. 用stack实现queue, 白板coding
: 2. 设计问题, 比较复杂, 个人觉得重复考到的可能非常小, 这就不说了, 有特别需要
: 的同学再找我...
: 第三个, hiring manager, 吃午饭
: 先介绍了他们组的基本工作, 问我暑期实习
: 然后问题是Amazon的shopping experience怎么样, 有什么改进的地方
| l***r
发帖数: 241 | | g*******4
发帖数: 155 | 5 多谢LZ共享，能问一下怎么投的简历么？是不是有人帮忙refer？ | g**s
发帖数: 76 | 6 求教这题的三种方法:
设计一个特殊的stack, 有三种操作, push, pop, 和returnMin. | b******v
发帖数: 1493 | 7 2. 给定一个方形矩阵, 有正整数组成, 每一行按升序排列, 每一列也按升序排列, 已
经给定整数n, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time
的solution.
这道题可以这么来做：
用binary search分别找到n在最上面一行中的位置top, 在最下面一行中的位置bottom,
在最左边一列中的位置left, 在最右边一列中的位置right
容易验证top>=bottom, left >=right
那么，top右边的列，left下边的行，right上边的行，bottom左边的列都不用考虑
所以我们只要在right行到left行，bottom列到top列围成的中心的小矩阵中找n就行了
所以问题转化为一个递归问题
不过这个时间复杂性我暂时还没想清楚，我想大概是O[(lgN)^2]，
其中N为矩阵的size. | r****o
发帖数: 1950 | 8 我觉得不能这样用binary search,因为
最上面一行的元素很可能都小于n，
最左边一列的元素很可能都小于n,
最下面一行的元素很可能都大于n,
最右边一列的元素很可能都大于n,
可以找出center的那个元素，其映射到第一行，第一列，最下面一行，最右边一列的元素
分别为top,left,bottom,right,
然后再根据center, top, left,bottom, right这五个值与n比较，每次应该可减去一半。
time
bottom,
【在 b******v 的大作中提到】
: 2. 给定一个方形矩阵, 有正整数组成, 每一行按升序排列, 每一列也按升序排列, 已
: 经给定整数n, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time
: 的solution.
: 这道题可以这么来做：
: 用binary search分别找到n在最上面一行中的位置top, 在最下面一行中的位置bottom,
: 在最左边一列中的位置left, 在最右边一列中的位置right
: 容易验证top>=bottom, left >=right
: 那么，top右边的列，left下边的行，right上边的行，bottom左边的列都不用考虑
: 所以我们只要在right行到left行，bottom列到top列围成的中心的小矩阵中找n就行了
: 所以问题转化为一个递归问题
| b******v
发帖数: 1493 | 9 你说的中心那个元素如何映射到四条边上去？
元素
【在 r****o 的大作中提到】
: 我觉得不能这样用binary search,因为
: 最上面一行的元素很可能都小于n，
: 最左边一列的元素很可能都小于n,
: 最下面一行的元素很可能都大于n,
: 最右边一列的元素很可能都大于n,
: 可以找出center的那个元素，其映射到第一行，第一列，最下面一行，最右边一列的元素
: 分别为top,left,bottom,right,
: 然后再根据center, top, left,bottom, right这五个值与n比较，每次应该可减去一半。
:
: time
| r****o
发帖数: 1950 | 10 说复杂了，就是top[n/2], left[n/2], bottom[n/2], right[n/2].
【在 b******v 的大作中提到】
: 你说的中心那个元素如何映射到四条边上去？
:
: 元素
| | | b******v
发帖数: 1493 | 11 明白了，确实是好办法
T(N)=T(N/2)+4
这样算法复杂度是log(N)，其中N为矩阵的size
【在 r****o 的大作中提到】
: 说复杂了，就是top[n/2], left[n/2], bottom[n/2], right[n/2].
| r****o
发帖数: 1950 | 12 不过为啥楼主说的是要求线性的方法呢？
【在 b******v 的大作中提到】
: 明白了，确实是好办法
: T(N)=T(N/2)+4
: 这样算法复杂度是log(N)，其中N为矩阵的size
| b******v
发帖数: 1493 | 13 不过仔细想一下，好像有点问题
如果nbottom，都能切掉左一半或右一半
可是如果top
【在 r****o 的大作中提到】
: 说复杂了，就是top[n/2], left[n/2], bottom[n/2], right[n/2].
| d**e
发帖数: 6098 | 14 我想了一下，应该只跟 center 比较
将区域切成
A B
C D
如果
if n == center then
return true
else n < center then
search n in A
else
search n in B
search n in C
search n in D
end if
【在 b******v 的大作中提到】
: 不过仔细想一下，好像有点问题
: 如果nbottom，都能切掉左一半或右一半
: 可是如果top
| B*****t
发帖数: 335 | 15 Cong！
能把那个复杂的设计问题贴一下么？ thanks
【在 s*********a 的大作中提到】
: 发个面经, 上周的, 攒rp
: 算上recruiter六个人
: 第一个, hr, 简单的问了学校, 专业, 毕业时间, 介绍了一下面试流程
: 第二个, 两道题:
: 1. 用stack实现queue, 白板coding
: 2. 设计问题, 比较复杂, 个人觉得重复考到的可能非常小, 这就不说了, 有特别需要
: 的同学再找我...
: 第三个, hiring manager, 吃午饭
: 先介绍了他们组的基本工作, 问我暑期实习
: 然后问题是Amazon的shopping experience怎么样, 有什么改进的地方
| h****h
发帖数: 75 | 16 not a linear time solution.
【在 d**e 的大作中提到】
: 我想了一下，应该只跟 center 比较
: 将区域切成
: A B
: C D
: 如果
: if n == center then
: return true
: else n < center then
: search n in A
: else
| B*****t
发帖数: 335 | 17 设计一个特殊的stack, 有三种操作, push, pop, 和returnMin.
stack里面搞个单调递减的队列能做到returnMinO(1)
给定一个方形矩阵, 有正整数组成, 每一行按升序排列, 每一列也按升序排列, 已
经给定整数n, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear
time 的solution.
每次cut掉1/2的数，cut点都在主对角线上，直到剩下一行一列，继续二分cut，O(n)
需要
【在 s*********a 的大作中提到】
: 发个面经, 上周的, 攒rp
: 算上recruiter六个人
: 第一个, hr, 简单的问了学校, 专业, 毕业时间, 介绍了一下面试流程
: 第二个, 两道题:
: 1. 用stack实现queue, 白板coding
: 2. 设计问题, 比较复杂, 个人觉得重复考到的可能非常小, 这就不说了, 有特别需要
: 的同学再找我...
: 第三个, hiring manager, 吃午饭
: 先介绍了他们组的基本工作, 问我暑期实习
: 然后问题是Amazon的shopping experience怎么样, 有什么改进的地方
| s********a
发帖数: 1447 | | s******a
发帖数: 103 | 19 Start from top right corner, if a[i][j]n, then i--.
Keep doing this, until a[i][j]==n.
I think this is linear time.
经给定整数n, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time
的solution.
【在 s*********a 的大作中提到】
: 发个面经, 上周的, 攒rp
: 算上recruiter六个人
: 第一个, hr, 简单的问了学校, 专业, 毕业时间, 介绍了一下面试流程
: 第二个, 两道题:
: 1. 用stack实现queue, 白板coding
: 2. 设计问题, 比较复杂, 个人觉得重复考到的可能非常小, 这就不说了, 有特别需要
: 的同学再找我...
: 第三个, hiring manager, 吃午饭
: 先介绍了他们组的基本工作, 问我暑期实习
: 然后问题是Amazon的shopping experience怎么样, 有什么改进的地方
| f****4
发帖数: 1359 | 20 遍历a[0][j]，找到 a[0][j-1] < element < a[0][j]
在a[0][j-1]~a[n-1][j-1]里面找element，有就有，没有就没有
O(N)
-.
time
【在 s******a 的大作中提到】
: Start from top right corner, if a[i][j]n, then i--.
: Keep doing this, until a[i][j]==n.
: I think this is linear time.
:
: 经给定整数n, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time
: 的solution.
| | | k***e
发帖数: 556 | 21 算法题比较常见
不过设计类的太开放了。
【在 s*********a 的大作中提到】
: 发个面经, 上周的, 攒rp
: 算上recruiter六个人
: 第一个, hr, 简单的问了学校, 专业, 毕业时间, 介绍了一下面试流程
: 第二个, 两道题:
: 1. 用stack实现queue, 白板coding
: 2. 设计问题, 比较复杂, 个人觉得重复考到的可能非常小, 这就不说了, 有特别需要
: 的同学再找我...
: 第三个, hiring manager, 吃午饭
: 先介绍了他们组的基本工作, 问我暑期实习
: 然后问题是Amazon的shopping experience怎么样, 有什么改进的地方
| j**l
发帖数: 2911 | 22 第六题是著名的杨氏矩阵（Young Tableau, 可不是杨狰狞提出的哦)
一个组合数学的东西, 早在20世纪初就由英国数学家提出。它的运作方式类似于堆和
BST，插入和查找等操作复杂度在O(m+n)
对本题，查找复杂度为O(2n) = O(n) | r****o
发帖数: 1950 | 23 这个方法好，不过是不是应该从left bottom corner开始？
如果i-row, j-column的话，已经是top right corner，还怎么j++呢?
-.
time
【在 s******a 的大作中提到】
: Start from top right corner, if a[i][j]n, then i--.
: Keep doing this, until a[i][j]==n.
: I think this is linear time.
:
: 经给定整数n, 怎样确定是否在矩阵中, 先说思路, 然后白板coding, 要求linear time
: 的solution.
| s******a
发帖数: 103 | 24 Your algorithm doesn't work for this matrix:
1 2 3
4 5 6
7 8 9
Looking for 8.
【在 f****4 的大作中提到】
: 遍历a[0][j]，找到 a[0][j-1] < element < a[0][j]
: 在a[0][j-1]~a[n-1][j-1]里面找element，有就有，没有就没有
: O(N)
:
: -.
: time
| k***e
发帖数: 556 | 25 搞combinatorics的？
【在 j**l 的大作中提到】
: 第六题是著名的杨氏矩阵（Young Tableau, 可不是杨狰狞提出的哦)
: 一个组合数学的东西, 早在20世纪初就由英国数学家提出。它的运作方式类似于堆和
: BST，插入和查找等操作复杂度在O(m+n)
: 对本题，查找复杂度为O(2n) = O(n)
| s******a
发帖数: 103 | 26 Starting from bottom left corner also works.
You are right. If we are at top right corner, it should be i++ and j--. Sorry about that.
【在 r****o 的大作中提到】
: 这个方法好，不过是不是应该从left bottom corner开始？
: 如果i-row, j-column的话，已经是top right corner，还怎么j++呢?
:
: -.
: time
| j**l
发帖数: 2911 | 27 不是。只是这题频频在MSFT, GOOG, AMZN的面经中出现，又是CLRS堆那章的课后习题(
Young Tableau)，引起了我极大的兴趣。这题要是从来没看过，要在面试的短短时间内
意识到它既像堆（有GetMin/GetMax, Sift操作), 也像BST（查找每次移动到矩阵的下
一行或者下一列，类似每次移动到二叉树的左分支和右分支), 还是需要一种直觉和灵
感吧。不过如果题目做多了, 书看多了，这种直感就会慢慢培养起来的。
【在 k***e 的大作中提到】
: 搞combinatorics的？
| k***e
发帖数: 556 | 28 没必要用到这个吧
多用空间存点额外信息就可以了
不过可以impress面试官
【在 j**l 的大作中提到】
: 不是。只是这题频频在MSFT, GOOG, AMZN的面经中出现，又是CLRS堆那章的课后习题(
: Young Tableau)，引起了我极大的兴趣。这题要是从来没看过，要在面试的短短时间内
: 意识到它既像堆（有GetMin/GetMax, Sift操作), 也像BST（查找每次移动到矩阵的下
: 一行或者下一列，类似每次移动到二叉树的左分支和右分支), 还是需要一种直觉和灵
: 感吧。不过如果题目做多了, 书看多了，这种直感就会慢慢培养起来的。
| r****o
发帖数: 1950 | 29 好像是有问题，呵呵，
我的想法是再用center跟n比较，不过每次只能切1/4.
在 bokertov (早上好) 的大作中提到: 】 | b******v
发帖数: 1493 | 30 嗯，可是那样就是n^(lg3)了
【在 r****o 的大作中提到】
: 好像是有问题，呵呵，
: 我的想法是再用center跟n比较，不过每次只能切1/4.
: 在 bokertov (早上好) 的大作中提到: 】
| | | d**e
发帖数: 6098 | 31 your solution should be the same as mine. but it seems not liner.
let's forget the "liner"
what is the complexity? is this the correct equation?
T(n) = 3T(n/4)
【在 r****o 的大作中提到】
: 好像是有问题，呵呵，
: 我的想法是再用center跟n比较，不过每次只能切1/4.
: 在 bokertov (早上好) 的大作中提到: 】
| r****o
发帖数: 1950 | 32 可能是吧，
我还想用T(n)=T(n/2)+T(n/4)+c，但这样我不知道怎么用master theorem.
【在 d**e 的大作中提到】
: your solution should be the same as mine. but it seems not liner.
: let's forget the "liner"
: what is the complexity? is this the correct equation?
: T(n) = 3T(n/4)
| s*******n
发帖数: 97 | | s*******n
发帖数: 97 | | s*******n
发帖数: 97 | | s*******n
发帖数: 97 | | s*******n
发帖数: 97 | | d**e
发帖数: 6098 | 38 like binary tree traversal, it should be T(n) = 3T(n/4) + O(1), because
there is one more comparation "if n == center"
after calculation by master theorem, it seems to be O(n), too.
don't know if i get sth wrong.
And in CLRS, there is one section about "select k-th element" in a matrix,
whose layout looks like this problem. it recursively finds the median. then
it is still O(n) .
【在 r****o 的大作中提到】
: 可能是吧，
: 我还想用T(n)=T(n/2)+T(n/4)+c，但这样我不知道怎么用master theorem.
| b******v
发帖数: 1493 | 39 如果你的n是矩阵的维数的话，应该是
T(n)=3T(n/2)+O(1)
then
【在 d**e 的大作中提到】
: like binary tree traversal, it should be T(n) = 3T(n/4) + O(1), because
: there is one more comparation "if n == center"
: after calculation by master theorem, it seems to be O(n), too.
: don't know if i get sth wrong.
: And in CLRS, there is one section about "select k-th element" in a matrix,
: whose layout looks like this problem. it recursively finds the median. then
: it is still O(n) .
| r****o
发帖数: 1950 | 40 T(n)=3T(n/4)+O(1),
我算出来的复杂度是O(n^log_(4)3).
then
【在 d**e 的大作中提到】
: like binary tree traversal, it should be T(n) = 3T(n/4) + O(1), because
: there is one more comparation "if n == center"
: after calculation by master theorem, it seems to be O(n), too.
: don't know if i get sth wrong.
: And in CLRS, there is one section about "select k-th element" in a matrix,
: whose layout looks like this problem. it recursively finds the median. then
: it is still O(n) .
| | | d**e
发帖数: 6098 | 41 you are right.. how come i thought log_4(3) = 1 ??!!
but log_4(3) < 1. so it's not liner, but is it better than liner? | d**e
发帖数: 6098 | 42 i mean "the # of elements"
【在 b******v 的大作中提到】
: 如果你的n是矩阵的维数的话，应该是
: T(n)=3T(n/2)+O(1)
:
: then
| b******v
发帖数: 1493 | 43 既然你的n是元素个数，linear的解是trivial的
只要遍历所有的元素，找有没有要找的那个x就好了
题目应该是要找O(矩阵的维数)的解
【在 d**e 的大作中提到】
: you are right.. how come i thought log_4(3) = 1 ??!!
: but log_4(3) < 1. so it's not liner, but is it better than liner?
| r****o
发帖数: 1950 | 44 恩，看来这个不如从顶角线性搜索的那个方法好，那个复杂度是O(n)，n是矩阵维数。
【在 b******v 的大作中提到】
: 既然你的n是元素个数，linear的解是trivial的
: 只要遍历所有的元素，找有没有要找的那个x就好了
: 题目应该是要找O(矩阵的维数)的解
| d**e
发帖数: 6098 | 45 yep..
but i just wanted someone to discuss about the complexity of "check center
and remove 1/4 matrix", not about linear or not.
【在 b******v 的大作中提到】
: 既然你的n是元素个数，linear的解是trivial的
: 只要遍历所有的元素，找有没有要找的那个x就好了
: 题目应该是要找O(矩阵的维数)的解
| d*******8
发帖数: 785 | 46 好牛，Cong
【在 s*********a 的大作中提到】
: 发个面经, 上周的, 攒rp
: 算上recruiter六个人
: 第一个, hr, 简单的问了学校, 专业, 毕业时间, 介绍了一下面试流程
: 第二个, 两道题:
: 1. 用stack实现queue, 白板coding
: 2. 设计问题, 比较复杂, 个人觉得重复考到的可能非常小, 这就不说了, 有特别需要
: 的同学再找我...
: 第三个, hiring manager, 吃午饭
: 先介绍了他们组的基本工作, 问我暑期实习
: 然后问题是Amazon的shopping experience怎么样, 有什么改进的地方
| s*********a
发帖数: 16 | 47 这题我给的解法大家都提到过了, 我是从左下角开始, 如果大于给定数就Move up, 如
果小于给定数就move right, 如果等于就是找到, 如果超出矩阵边界就是不存在.
【在 r****o 的大作中提到】
: 可能是吧，
: 我还想用T(n)=T(n/2)+T(n/4)+c，但这样我不知道怎么用master theorem.
| s*********a
发帖数: 16 | 48 我是在学校的招聘会投的, 2月初的时候. 如果你有兴趣可以把简历发给我, 但是面试
的时候recruiter说我可以推荐我的朋友, 他们很需要人.
【在 g*******4 的大作中提到】
: 多谢LZ共享，能问一下怎么投的简历么？是不是有人帮忙refer？
| s*********a
发帖数: 16 | 49 呃, 其实不难了. 我想的方法都比较直接...
第一种, 用array, 并且用变量记录当前的最小元素index, 没Push一个新的元素, 更新
当前最小元素index, 如果最小元素被pop, 那么遍历数组, 找到新的最小, 这样push o
(1), pop o(n), returnMin o(1)
第二种, 用array和heap来同时maintain这个stack, 每push和pop一个新的元素, 同时
在array和heap中删除和插入, 这样push o(logn), pop我没想清除..., retrunMin o(1)
第三种, 说明白有点困难...
用数组和Hashtable, 每次在数组中push一个新的元素, 在hashtable中插入当前index
以及当前最小值, 这样三种操作都constant.
没什么标准答案, 面试官也比较开放, 只要你说的有道理, 确实efficient, 用什么数
据结构和算法都ok.
【在 g**s 的大作中提到】
: 求教这题的三种方法:
: 设计一个特殊的stack, 有三种操作, push, pop, 和returnMin.
| s*********a
发帖数: 16 | 50 首先有个path的定义, 比如说有个用户visit Amazon.com, 先点了page1, 然后点了
page2, 然后点了page3, 那么page 1, 2, 3就构成了一个path.
现在给你一个logfile, 记录一段时间内所有user的网页点击历史, 每一条记录包括
sessionID, pageID, timestamp.
问题: 统计所有路径的出现次数.
一点说明: 假如现在你从这个Logfile得到了某sessionID的先后访问的页面为page 1,
2, 3, 4, 5, 那么从中你可以得到path有多条, 每个由三个组成,
1, 2, 3
2, 3, 4
3, 4, 5
Follow-up: 回答完上面的问题, 他会问, 现在如果一个user已经访问了page1, page2,
怎样根据以上Path的统计数据预测下面他会点击哪个page.
这题好像是他们的实际工作中遇到的, 是我这个特定的组的, 所以我觉得重复的可能性
基本为零.
【在 B*****t 的大作中提到】
: Cong！
: 能把那个复杂的设计问题贴一下么？ thanks
| | | s*********a
发帖数: 16 | 51 貌似叫catalog quality
【在 s*******n 的大作中提到】
: 楼主面得是哪个group? Thanks.
| b********w
发帖数: 110 | 52 汗，第一题我第一电面就问了。不过不需要coding | c****l
发帖数: 1280 | | c******f
发帖数: 2144 | | l******c
发帖数: 2555 | 55 best solution, simple and practical
【在 s*********a 的大作中提到】
: 这题我给的解法大家都提到过了, 我是从左下角开始, 如果大于给定数就Move up, 如
: 果小于给定数就move right, 如果等于就是找到, 如果超出矩阵边界就是不存在.
| a****r
发帖数: 78 | 56 是Jon？
,
【在 s*********a 的大作中提到】
: 首先有个path的定义, 比如说有个用户visit Amazon.com, 先点了page1, 然后点了
: page2, 然后点了page3, 那么page 1, 2, 3就构成了一个path.
: 现在给你一个logfile, 记录一段时间内所有user的网页点击历史, 每一条记录包括
: sessionID, pageID, timestamp.
: 问题: 统计所有路径的出现次数.
: 一点说明: 假如现在你从这个Logfile得到了某sessionID的先后访问的页面为page 1,
: 2, 3, 4, 5, 那么从中你可以得到path有多条, 每个由三个组成,
: 1, 2, 3
: 2, 3, 4
: 3, 4, 5
| K******g
发帖数: 1870 | 57 第三种情况没有看明白，能解释一下吗？
o
(1)
index
【在 s*********a 的大作中提到】
: 呃, 其实不难了. 我想的方法都比较直接...
: 第一种, 用array, 并且用变量记录当前的最小元素index, 没Push一个新的元素, 更新
: 当前最小元素index, 如果最小元素被pop, 那么遍历数组, 找到新的最小, 这样push o
: (1), pop o(n), returnMin o(1)
: 第二种, 用array和heap来同时maintain这个stack, 每push和pop一个新的元素, 同时
: 在array和heap中删除和插入, 这样push o(logn), pop我没想清除..., retrunMin o(1)
: 第三种, 说明白有点困难...
: 用数组和Hashtable, 每次在数组中push一个新的元素, 在hashtable中插入当前index
: 以及当前最小值, 这样三种操作都constant.
: 没什么标准答案, 面试官也比较开放, 只要你说的有道理, 确实efficient, 用什么数
| i**********e
发帖数: 1145 | 58 有一种方法能使所有 push,pop, returnMin 操作都 O(1).
就是利用多一个 stack 的辅助，只 push minimum 上去。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
o
(1)
index
【在 s*********a 的大作中提到】
: 呃, 其实不难了. 我想的方法都比较直接...
: 第一种, 用array, 并且用变量记录当前的最小元素index, 没Push一个新的元素, 更新
: 当前最小元素index, 如果最小元素被pop, 那么遍历数组, 找到新的最小, 这样push o
: (1), pop o(n), returnMin o(1)
: 第二种, 用array和heap来同时maintain这个stack, 每push和pop一个新的元素, 同时
: 在array和heap中删除和插入, 这样push o(logn), pop我没想清除..., retrunMin o(1)
: 第三种, 说明白有点困难...
: 用数组和Hashtable, 每次在数组中push一个新的元素, 在hashtable中插入当前index
: 以及当前最小值, 这样三种操作都constant.
: 没什么标准答案, 面试官也比较开放, 只要你说的有道理, 确实efficient, 用什么数
|
|
