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, 用什么数
|
|