d**s
发帖数: 98 | 1 http://zhedahht.blog.163.com/blog/static/2541117420071289522817
程序员面试题精选100题(02)－设计包含min函数的栈[数据结构]
2007-02-28 21:52:28| 分类： 栈 | 标签：编程 就业 找工作 |字号大中小 订阅
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数
min、push以及pop的时间复杂度都是O(1)。
分析：这是去年google的一道面试题。
我看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。
这样栈顶元素将是最小元素。但由于不能保证最后push进栈的元素最先出栈，这种思路
设计的数据结构已经不是一个栈了。
在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次push一个新元素进
栈的时候，如果该元素比当前的最小元素还要小，则更新最小元素。
乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素
被pop出去，如何才能得到下一个最小元素？
因此仅仅只添加一个成员变量存放最小元素（或最... 阅读全帖 |
|
n**********2
发帖数: 214 | 2 算法为王，数据结构更为王冠上最璀璨的宝石
本群致力于高级数据结构与算法学习，临摹，演练
目前已经有Google，Facebook，Microsoft顶尖高手在加盟路上，高级数据结构算法群
即日起航
高手优先，低手有热情有动力有悟性有恒心，任选其一同样优先
很多时候人的智力到达一定阶段，是否能实现本质的飞跃，就要看你周围的人的成色和
能量
这个群就是你身边最优秀的一群人，是每天与你相伴的自己人
实时交流，共同进步
群招募500人，最终目标80-100人，建立基本的选择和优化准则
给大家足够的动力思考新问题，尝新难问题，攻克重要问题
群号：229623621 |
|
z***u
发帖数: 105 | 3 面试中遇到的数据结构设计题，请教有没有更好的办法。还有最后一问没有打上来，请
教如何设计最后一题。
问题： 有很多不同型号的汽车要测试，每分钟采集一个数据，比如实时的MPG(假设都
是整数), 数据格式如下：["car1", 19], ["car2" 22], ["car3" 21]...
1. 问： 设计一个数据结构来存储每个车最新的数据
答： unordered_map
2. 问： 如何改进来存一天的数据， 并且支持返回某时间段的MPG值，比如get("car1"
, 12：00，13：00）
答： unordered_map 加 map， 如unordered_map< string/*car name*/, map
time stamp*/, int/*MPG data*/> >.
map 是排好序的，用lower_bound，和upper_bound找出时间的区间返回值
3. 如果需要找出N个车，它们的平均MPG最高。如何改进已有的数据结构。
我给出的答案是multimap阅读全帖 |
|
l****u
发帖数: 1764 | 4 哪种数据结构search最高效？
我觉得是binary search tree，因为如果是balanced BST，O(lgN)的复杂度就能找到一
个element
哪种数据结构sort最高效？
这个我就不知道怎么答了，只听过哪种algorithm，没听过哪种数据结构的。基本上
sort一组数据，最快也得要O(NlgN)吧，用quick sort或者merge sort的话。但这几种
algorithm都能针对各种不止一种data structure吧，比如 array， ArrayList，
linkedlist
求大神指点 |
|
g*********s
发帖数: 1782 | 5 【 以下文字转载自 Programming 讨论区 】
发信人: gandjmitbbs (Nothing), 信区: Programming
标 题: 请教双键的动态结构用什么数据结构比较好？
发信站: BBS 未名空间站 (Thu Jun 19 21:42:50 2008)
比如一个记录，id和name都是unique的，都可以用来做key。现在有这样一组记录，插
入/删除/查询的操作很频繁，而且可能用name也可能用id作key。用什么数据结构比较
好？
最简单的想法是两个balanced BST，一个用id作key，一个用name，但这样等于时间空
间都double了，虽然复杂度不变。
两个hash table的话也是同样的问题。另外因为记录是动态变化的，hash table的size
也不太好定。
有没有dual-key binary search tree之类的数据结构呢？ |
|
k**l
发帖数: 2966 | 6 【 以下文字转载自 JobHunting 讨论区 】
发信人: kjbl (看家本领), 信区: JobHunting
标 题: 求推荐数据结构的书
发信站: BBS 未名空间站 (Tue Apr 21 16:56:42 2015, 美东)
理科半路出家做着CS, 凭着大学学过算法的算法与数据结构（10+ years ago）所以大
多数基本感念都懂, 但是感觉好像比较outdated。程序(c++)自以为写得不错，但工作
数据结构中用的太少，太不系统
现在打算换个热门点的公司，求推荐本当代的好书看看？
包子答谢 |
|
|
a*****y
发帖数: 11 | 8 问题是这样的，我们有几套.c和.h文件，每套文件里其实只定义了一些structures,没
有函数和类， 也就是说，这个文件只是用来存储数据结构和一些数据结构的实例，像
一个小的database。我想编一个算法用,在load一套.c和.h文件后（其实就像是一个文
本文件），识别出这个文件里定义的数据结构和那些实例。
请问哪位知道是否有比较好的算法来实现这个功能， 谢谢。 |
|
b*********n
发帖数: 1258 | 9 【 以下文字转载自 Programming 讨论区 】
发信人: babyfacenan (黑土), 信区: Programming
标 题: C++动态2维数组用什么数据结构比较好？
发信站: BBS 未名空间站 (Mon Jan 25 21:37:01 2010, 美东)
程序是这样的
有一个动态长度的vector
然后对这个vector做DP
想问问那个DP结果的2维数组用什么数据结构比较好？
谢谢 |
|
m******9
发帖数: 968 | 10 1. linkedin和facebook都有好友自动推荐的功能，系统会自动提示你可能认识的某某
人。怎么为这个设计数据结构？
2. 怎么为ms office word设计数据结构？
大家有啥好主意么？ |
|
I**A
发帖数: 2345 | 11 随便进了topcoder的practice room，点第一个（估计是最简单的），玩了250 和 500
的之后，就点了1000的进去了
看了题之后，想了两分钟，数据结构愣是没想出来，灰溜溜滴我又退了出来。。
就是选课问题
输入String[]
"CSE210: CSE112 CSE113 MATH201",
"MATH201: MATH110",
"CSE113: CSE112",
"CSE112:"
"MATH110:"
要求输出String[], 就是排一个课程表，需要修的课程的顺序，如果科目一样，那么
number小的先修，如果number一样，那么按科目字母顺序来排。。
还有些别的details，不用管了
比如，以上的输出应该是:
MATH110, CSE112, CSE113, MATH201, CSE210
用什么样的数据结构好？Graph么？ |
|
w****o
发帖数: 2260 | 12 看到很多题都是跟dictionary有关的，面试时问到的话，通常是用什么数据结构表示的？
还是面试官已经告诉你了已经有一个用某种数据结构建好的dictionary,你就不用担心
了？ |
|
d****o
发帖数: 1055 | 13 构造数据结构，实现两个function
int getProcessID()
void freeProcessID(int id)
要求，如果getProcessID 调用6次，那么系统里面会有6个process在运行，(id 从 1到
6)如果,freeprocessid(x)调用，系统里面对应得process x会被释放。
但是，如果再一次调用getProcessID(), 会返回最小的之前被释放得processID.
举例:调用顺序:
getProcessID()
getProcessID()
getProcessID()
getProcessID()
getProcessID()
getProcessID()//系统里面会有6个process
free(5)//系统process 1,2,3,4,6
free(3)//系统process 1,2,4,6
free(6) //系统process 1,2,4
getProcessID() //系统process 1,2,3,4
getProcessID() //系统process 1,2,3,4,5
请问用什么数据结构实现，使得这两... 阅读全帖 |
|
d**s
发帖数: 98 | 14 非常规的解法：
http://blog.csdn.net/anchor89/article/details/6055412
经典面试题:设计包含min函数的栈,O(1)空间实现方法
分类： 数据结构和算法 2010-12-04 22:20 2102人阅读 评论(10) 收藏 举报
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数
min、push以及pop的时间复杂度都是O(1)。
注:这是06年一道Google的面试题.
先来说个常规解和他的一个优化,常规解的时间复杂度符合要求,但需要线性的额外空间.
常规解(参考 http://zhedahht.blog.163.com/blog/static/25411174200712895228171/):
除了题目要求的栈之外新开一个栈,用来记录最小值,每当在原栈中push数据后,与最小
值栈中的栈顶元素比较,如果新值较小,则在最小值栈中push新值;否则再次push栈顶元
素.
pop的时候,只要将最小值栈也pop一下就行了.
这样,min函数只需要返回最小值栈的栈顶元素即可.
常规解空间上的一个优化:
一般... 阅读全帖 |
|
d*********k
发帖数: 1239 | 15 有没有算法和数据结构速成的书？
就是应对一个面试，不是什么IT公司，所以一些经典的算法和数据结构就够用了，大家
伙有没有什么推荐的？
谢谢啦啊 |
|
f********4
发帖数: 988 | 16 今天做longest consecutive 那个题，觉得用treeset很简单
版上有人面试时候用过这种数据结构嘛？
好像从来没看到有solution用TreeSet或者TreeMap。。到底能不能用呢。。甚纠结。。
是不是用了还要知道这个数据结构咋实现的之类的。。。 |
|
b**a
发帖数: 1118 | 17 【 以下文字转载自 Programming 讨论区 】
发信人: buaa (ming), 信区: Programming
标 题: 如何设计一个支持 survey or questionnaire 的数据结构？
发信站: BBS 未名空间站 (Tue Mar 25 21:01:19 2014, 美东)
我当前的一个项目，是一个内部 online questionnaire or survey. 每一页首先显示
是一个问题。根据用户不同的选择，（单选或多选），同一页再显示此问题的若干子问
题。可能有几层。这个总问题答完后，同一页将显示第二个问题。 大致有十几个最多
几十个问题。
这些问题经常会变化，因此我们希望能同时有一个工具来让 survey 的设计者来输入问
题及逻辑，即根据用户的选择，下一个问题或子问题是什么。
应该设计一个什么样的数据结构最好？ |
|
p****2
发帖数: 518 | 18 包括各种常用的数据结构：
Linked list
Doubly linked list
有这些数据结构后，接着看算法 |
|
C****e
发帖数: 27 | 19 嗨，大家好，数据结构和算法是我的薄弱项，理解很困难。目前在刷leetcode，想用
java来先理解经典算法和数据结构的题目，大家有没有用比较通俗易懂语言或图解方法
的blog文章资料的学习渠道，推荐推荐给小妹哈，先谢谢各位啦~ |
|
S*******C
发帖数: 822 | 20 given a manager find all its subordinates, given a subordinate find all its
supervisors; 应用题一样，给定问题，选用数据结构去解
follow-up 还有没有别的数据结构可以用？怎么解？比较一下这两个方法，说一下
时间和空间的big O;
我怎么感觉用RDBMS容易多了 |
|
j******8
发帖数: 105 | 21 设计一个数据结构，包括两个操作
void insert(int d): 插入一个int
int query(int d): 查询d在数据结构中的排名
example:
Insert: 4, 5, 3
query(4) gives 2;
insert: 1
query(4) gives 3;
如何设计保证两个操作都是O(log(n))? |
|
h*******n
发帖数: 2052 | 22 【 以下文字转载自 Programming 讨论区 】
发信人: honestman (snail), 信区: Programming
标 题: 自学算法与数据结构
发信站: BBS 未名空间站 (Sun Mar 30 22:29:26 2008)
一片空白的人自学算法与数据结构， 看哪本书比较好？
1. Introduction.to.Algorithms
2. Algorithms in C Sedgewick
3. else？
谢谢！ |
|
w***g
发帖数: 5958 | 23 是刚好名字相同。数据结构中的heap本质上是一种树结构。内存中的heap本质上是一种
线性结构。内存中的heap是和stack相对的，heap往上长，stack往下长，heap用来存全
局动态数据，stack用来存局部动态数据。不过内存中的stack倒是按照数据结构的
stack存放的。 |
|
g*********s
发帖数: 1782 | 24 比如一个记录，id和name都是unique的，都可以用来做key。现在有这样一组记录，插
入/删除/查询的操作很频繁，而且可能用name也可能用id作key。用什么数据结构比较
好？
最简单的想法是两个balanced BST，一个用id作key，一个用name，但这样等于时间空
间都double了，虽然复杂度不变。
两个hash table的话也是同样的问题。另外因为记录是动态变化的，hash table的size
也不太好定。
有没有dual-key binary search tree之类的数据结构呢？ |
|
c*********3
发帖数: 197 | 25 其实是个数据问题。想构建一个可快速查询的字典。很n久没有用比较复杂的数据结构
了。
插入和删除估计不多，所以性能要求不高。对查询要求比较高。字典估计有50万左右的
词。
第一想法是用B+树。不知道合适不？有别的更好的数据结构和算法没有？
谢谢 |
|
n***o
发帖数: 68 | 26 请问一下智能输入法采用的是什么数据结构？
以英文的为例，就比如你输入头几个字母，那么就提示以这几个字母开头的词。
假如有了一个按照词频排列的单词表了，那么该用什么数据结构来保存这个词表呢？
此外，这个提示算法的设计上面该注意些什么？ |
|
n****e
发帖数: 43 | 27 【 以下文字转载自 JobHunting 讨论区 】
发信人: njhome (njhome), 信区: JobHunting
标 题: 一道关于数据结构的面试题
发信站: BBS 未名空间站 (Thu Aug 1 17:49:47 2013, 美东)
如果每天接受上百万的股票交易信息，但是只想储存某个公司的股票在时间上最近的前
十次交易的信息，其他信息都不要，应该最好用什么样的数据结构？比如今天头十个微
软股票交易， MSFT $31.67 100 shares 17:30:01,MSFT $31.67 200 shares 17:20:
01, MSFT $31.67 300 shares 16:30:01... |
|
a*******8
发帖数: 156 | 28 各位大神好，
我现在需要跳槽。 很多工作要考 算法 和 数据结构。 我是半到出家的所以基本功相
当不扎实。 我搜了很多网站公开课，算法和 数据结构很多资料 都是c, c++, java,
python 的。 我只会 c#。 远水不解近渴。我需要一个好的书让我快速的知道个大概。
现在跟个SB 一样面试肯定废！！！
万谢！ |
|
发帖数: 1 | 29 写了一个小的Python的程序。 在单机上比较慢。现在准备在好多个机器上同时跑这个
程序。
问题：有没有现成的Python库，让这些在不同的机器上的Python程序共享数据结构？
如果其中的一个程序更新了这个数据结构， 别的程序应当能马上看到。
谢谢。 |
|
n******g
发帖数: 2201 | 30 Serialization
Pickle
[在 dailygrind16 (天天绞肉机) 的大作中提到：]
:写了一个小的Python的程序。 在单机上比较慢。现在准备在好多个机器上同时跑这个
:程序。
:问题：有没有现成的Python库，让这些在不同的机器上的Python程序共享数据结构？
:如果其中的一个程序更新了这个数据结构， 别的程序应当能马上看到。
:谢谢。 |
|
发帖数: 1 | 31 谢谢大伙的回复。
Shared logging file 对于我的这个应用好像不太合适（不够快？）。在这个应用里，
那些Python 程序要共享的数据结构是动态增长的和无法提前预测的； 如果一个Python
程序产生了一个新的节点（到那个数据结构里的话）， 别的Python程序就不应当再重
复这个劳动。这个有点像多个计算机程序之间shared data structure。
另外， 这是一个小应用，所以能够不用大的， 复杂的库是最理想的。
我先试试哥们推荐的几个库看看。 |
|
h*i
发帖数: 3446 | 32 函数式编程本来就是用来追求更高层的抽象，更面向应用的，为什么要用函数式语言自
己实现这些数据结构？
常用数据结构应该是在语言层面提供的功能。下面是如何实现的，应用程序员不用管那
么多。同样，矩阵操作，这些都应该用标准的库，或是硬件厂商提供的库来做。
函数式编程是在底层库基础上提供的方便应用编程的一种用户界面而已。 |
|
m*********u
发帖数: 1491 | 33 生物背景 零CS基础的人想转行,跟本不需要搞什么数据结构和操作系统,没有多少地方
用这些. 你也不用费那劲找这类工作.
世界上好公司很多.生物人遵循正确方向,转行根本不用去搞什么数据结构和操作系统. |
|
c*******a
发帖数: 1879 | 34 【 以下文字转载自 JobHunting 讨论区 】
发信人: centralla (central LA), 信区: JobHunting
标 题: 设计一个数据结构用来快速
发信站: BBS 未名空间站 (Mon Sep 11 19:09:22 2017, 美东)
更新 NODES 的排序， 每个NODE里有(KEY，VALUE）, 排序按照VALUE降序排。
NODES的数量很大， 是实时 STREAM过来， VALUE值是不停变化。 |
|
发帖数: 1 | 35 TBT, 尼玛，都不记得作者了，记得数据结构还是类似Pascal的伪代码，黄皮Pascal还
是高中用的。C程序设计是谭浩强吧？ |
|
m********e
发帖数: 1156 | 36 【 以下文字转载自 CS 讨论区 】
发信人: molvillage (摩尔庄园), 信区: CS
标 题: 哪儿能下载数据结构教学视频？
发信站: BBS 未名空间站 (Sun Feb 26 07:12:06 2012, 美东)
MIT 公开课好像只有算法课。
以前记得有个伯克利的，找不到了。
谢了先 |
|
H*M
发帖数: 1268 | 37 这个数据结构有可能是tree, graph, or anything.
你不知道。如何make a copy呢？ |
|
m******9
发帖数: 968 | 38 抱歉，忘了明确一下，这个是设计data structure，不是针对pattern的。
尤其是第2题，该怎么设计数据结构呢？ |
|
c****a
发帖数: 11 | 39 我觉得我现在用的书 写的不好
算法和数据结构 有没有像 学C++就要看C++ primer 和effective c++
一样经典的书啊？ |
|
s*******n
发帖数: 1018 | 40 看了很多讨论算法的帖子，感觉大家都好牛，我怎么就想不到。需要好好恶补一下了。
所以想知道哪里能够找到比较集中的算法和数据结构的练习题。重新复习书本来不及了。大家有何建
议？
谢谢先！ |
|
P*****o
发帖数: 294 | 41
这是java上的区分吧,单纯从数据结构角度有什么区别吗? |
|
f*******4
发帖数: 1401 | 42 请问有没有为面试的数据结构复习大纲之类的东东？就是列出所有面试会遇到的数据结
构就行了，如果
有总结的优点缺点之类的就更好了。。。
谢谢！！！ |
|
M7
发帖数: 219 | 43 如果不问算法和数据结构。那问什么？Sr. level的面试也可能结合简历上的经验，问此
类问题， |
|
H**d
发帖数: 152 | 44 C#，。NET 面银行还是会问到算法和数据结构的。
喜欢问TREE，HASH 。。。不常问LINKED LIST |
|
c*******n
发帖数: 72 | 45 有篇讲 minmax heap的文章说了怎么用这种数据结构找中数，不是两个heap，但是我没
看明白。 |
|
z****4
发帖数: 194 | 46 如果每个词要求存additional information，比如释义的话，那么trie是最优的；如果
只要求存这个词，不存其他任何information，那么最优的数据结构是dawg
to |
|
h****e
发帖数: 928 | 47 什么算是高级数据结构？k-d tree算是吗？
我看得迷迷糊糊，还好Leetcode说面试不会考的。 |
|
w********d
发帖数: 7 | 48 QQ 群号：229623621 特此诚邀您加盟
群成立之初，有超过100位同仁加盟，经过统一群名片和实名验证现优化为60位
群内有全球Top500 ACMer 三位，Google Amazon Ms 同仁数位
群刚刚成立，正在积极调整优化，力争实力稳步提升，为加群的同仁提供实实在在的帮助
另外也要诚意致歉之前因为无互动，没改群名片被请出的同仁，欢迎你们随时回来，群
的大门永远向你们敞开。
算法为王，数据结构更为王冠上最璀璨的宝石
高手优先，低手有热情有动力有悟性有恒心，任选其一同样优先
很多时候人的智力到达一定阶段，是否能实现本质的飞跃，就要看你周围的人的成色和
能量；这个群就是你身边最优秀的一群人，是每天与你相伴的自己人
实时交流，共同进步
给大家足够的动力思考新问题，尝新难问题，攻克重要问题
群号：229623621 |
|
f*******5
发帖数: 9 | 49 要准备一轮tech phone 面试， 很多数据结构基本概念都清楚，但是希望做一些经典的
题目，哪里有这样的资料？
sound understanding of Data Structures (Array, Stack/Queue, Hashset/ Hashmap
/ Hashtable/ Dictionary, Tree/Binary Tree, Heap, Graph), and Algorithms. |
|
l******9
发帖数: 26 | 50 应聘SDE职位，星期三考试180分钟除了算法和数据结构,还会考什么
还有一天多点的时间临时报抱佛脚下 |
|
