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出去，如何才能得到下一个最小元素？
因此仅仅只添加一个成员变量存放最小元素（或最... 阅读全帖 |
|
d******e
发帖数: 2265 | 2 总体来说，至少参差不齐吧。
最近几天用multiprocess包. 居然1000各elments的queue在put还有900多elments时就
会包empty.对了，用一个进程验证。几乎没有在put完时退出的。虽然文档说empty不准
，也不至于不准到这种地步。
然后，多个processes 一个queue，只是put对象会以10%以上概率对每个对象deadlock
。keyboardinpr 发现都在wait。搞了半天，发现换成dict就梅问题了。不知道是挂在
那个class的pickling上了。 |
|
|
r******g
发帖数: 13 | 4 3 way partition first puts the duplicated elements in two ends by scanning
once:
1. moving from let to find element not less < p
2. moving from right to find element not greater > p
3. exchange left and right elemnt
4. if (left elment == p) swap it with left end
5. if (right element == p) swap it with right end
=pivot, p, = pivot
my code got
5, 5, 5, 4, 3, 1, 2, 3, 5, 10, 5, 9
put the duplicated elements in the center by exchanging elements in two ends
and those in the center
3, 2, 1, 4, ... 阅读全帖 |
|
j***y
发帖数: 2074 | 5
It seems p1 and p2 are pointing to two consecutive memory areas respectively, aren't they? For examle, p1 = (int *) calloc(N * sizeof(int)), p2 = ... (similar).
p2[j] = p1[j] + p1[j-1], this I can understand. Except for the outmost
elements, every element is the sum of two neighboring elments in the above
layer. And I also noted that in every row, the column number is equal to row+1, if row starts with 0.
Why swap the two pointers here? Can't understand here... |
|
K*******i
发帖数: 399 | 6 const int M = 4;
const int N = 5;
// si: row of the upper left element of the sub matrix
// sj: col of the upper left elment of the sub matrix
// m: rows of the current sub matrix
// n: cols of the current sub matrix
void PrintMatrix(int A[M][N], int si, int sj, int m, int n)
{
if (m == 0 || n == 0)
return;
if (m == 1)
{
for (int j = 0; j < n; j++)
cout << A[si + 0][sj + j] << " ";
}
else if (n == 1)
{
for (int i = 0; i < m; i+... 阅读全帖 |
|
z********i
发帖数: 568 | 7 The following algorithm for queue with max is correct to me:
http://www.sureinterview.com/wiki/Shwqst/903001
idea:
1 用数据队列保存所有数据X[0]，X[1]，...
2 用辅助队列保存数据中的X[i1],X[i2],etc. such that
2.1 X[i1]>=X[i2]>=...。
2.2 X[i1]是从X[i1]开始最大的数。
3 enque的时候,删除辅助队列中比要插入的数据小（<）的数据。
4 deque的时候，删除数据队列的第一个数据。同时，如果辅助队列的第一个数据等于数据队列的第一个数据，删除辅助队列的第一个数据。
5 max就是辅助队列的第一个数据
例子一。
数据队列：6 5 4。
辅助队列：6 5 4。
1) max: 辅助队列的第一个数据6.
2) deque：
数据队列：5 4。
辅助队列：5 4
max: 5
3) deque:
数据队列：4。
辅助队列：4
max: 4
例子二。
数据队列：4 5 6。
辅助队列：6。
1) max: 辅助... 阅读全帖 |
|
z****h
发帖数: 164 | 8 第一轮的题二的思路是啥？
直接从头开始找sub array，sub array sum 大于target sum就停止，再从第二个
element开始找直到某个elment比target sum大，就结束。
有其他方法吗？ |
|
Y********f
发帖数: 410 | 9 刚做了这道题，leetcode上为了不调用find kth elments两次写了一个比较复杂的。我
写了一个稍微简单点的，实际上也是基于find kth element.
double median2Array(int* arrA, int lenA, int* arrB, int lenB, int k, int
isEven)
{
if (lenA == 0)
return isEven ? (arrB[k-1] + arrB[k]) / 2.0 : arrB[k-1];
else if (lenB == 0)
return isEven ? (arrA[k-1] + arrA[k]) / 2.0 : arrA[k-1];
else if (k == 1)
{
vector vect(min(2, lenA) + min(2, lenB));
copy(arrA, arrA + min(2, lenA), vect.begin());
copy(ar... 阅读全帖 |
|
Y********f
发帖数: 410 | 10 刚做了这道题，leetcode上为了不调用find kth elments两次写了一个比较复杂的。我
写了一个稍微简单点的，实际上也是基于find kth element.
double median2Array(int* arrA, int lenA, int* arrB, int lenB, int k, int
isEven)
{
if (lenA == 0)
return isEven ? (arrB[k-1] + arrB[k]) / 2.0 : arrB[k-1];
else if (lenB == 0)
return isEven ? (arrA[k-1] + arrA[k]) / 2.0 : arrA[k-1];
else if (k == 1)
{
vector vect(min(2, lenA) + min(2, lenB));
copy(arrA, arrA + min(2, lenA), vect.begin());
copy(ar... 阅读全帖 |
|
f*****e
发帖数: 2992 | 11 和数据库差不多，粗粒度lock和细粒度lock，如果要做aggregate operation比如求和，
要把整个list给锁起来，如果写一个elment，和读另一个element，就用基于element的
lock，这样就互不干扰。 |
|
s******g
发帖数: 139 | 12 用个 deque 就可以了, deque 的front() 是 sliding window中的最小的元素. 扫描数
组, 如果当前元素 大于front(), update res as res = max(res, x[i]-dq.front());
if front() is moving out of the L-sliding window, pop_front(), pop all the
elments in the deque starting from the back() that is no less than x[i],
then push x[i] in the deque.
(e.g. while(!dq.empty()) if(dq.back()>=x[i]) dq.pop_back(); dq.push_back(x[
i]);
Should be O(N) since each element gets in/out the deque only once |
|
y***e
发帖数: 6082 | 13 12点才去，离家很近，也没抱想法还能买到，反正去随便转转，到了Target门口，前面
1000多号人，等到12点40才进去（据说是每30s放30个人），到了里面没想到
Westinghouse 46"和Elment 40"都还有剩余（一个剩2台，一个剩5台），店员说先优先
给排队进来的前40号，发了票的，之后到3点随便拿，然后在Target里面乱转，随便买
了个小慢锅和小玩具，到了2点10分再去TV那块重新排队，等了50分钟，抬货走人，这
会结帐的队伍少了很多人了，不到15分钟就出来了，感觉还不错！
这个Westinghouse的牌子质量如何啊 |
|
g*******a
发帖数: 31586 | 14 【 以下文字转载自 PDA 讨论区 】
发信人: dongdongdog (dongdong), 信区: PDA
标 题: 我对Steve Jobs的看法
发信站: BBS 未名空间站 (Thu Feb 17 18:34:30 2011, 美东)
看有人谈Steve Jobs，我也说说我的看法。
Jobs所在的Apple，用Apple ][ 最早的把计算机从实验室大规模的普及到普通百姓家。
你说Jobs完全是依靠Woz也好，
但不能否认的事实是一个大学都没有毕业的Jobs作为CEO在25岁那一年（1980年）带领
Apple上市，AAPL是自从Ford
以来的最大的IPO，Silicon Valley的VC也是从那个时候开始腾飞的。AAPL的故事在电
影阿甘正传中也有提到。
Jobs所在的Apple后来又推出了Macintosh，世界上第一款采用图形界面的电脑，你说
Apple是偷Xerox Parc的技术也
好，但Apple的确是第一个把这个技术普及开来的公司。今天我们每个人在电脑上无论
是在Windows上，Mac上，还是
Gnome或者是KDE，所有的基本图形界面元素（UI E... 阅读全帖 |
|
B*****e
发帖数: 9375 | 15 :)
OK, guys, what is the requiring elment in a "field goal formation" -- one
that you do NOT have to deploy in order to score, but, if you do, affords
extra protection for your long snapper (no DL can directly cover him)? |
|
o******t
发帖数: 68 | 16 "Experience Music Project" in Seattle.
Pretty nice.I spent almost 2 hours there after I finished the tour
to space needle, but far away from finishing viewing the whole thing.I
guess 4 hours is a must if anyone want to take a close and thourough look.
There are whole lot of stuffs about Rock & Roll and Jazz. For
example,the band and their memebers'bibligraph,history of all kind of
instrument,music styles or elments,albums, photos...etc....I found there is a
Guita Gallery..sigh....unfortunat |
|
y***e
发帖数: 6082 | 17 发信人: yueke (小鱼儿~2008BB竞猜王), 信区: shopping
标 题: 买了Westinghouse 46" LCD HDTV
发信站: BBS 未名空间站 (Fri Nov 25 04:10:03 2011, 美东)
12点才去，离家很近，也没抱想法还能买到，反正去随便转转，到了Target门口，前面
1000多号人，等到12点40才进去（据说是每30s放30个人），到了里面没想到
Westinghouse 46"和Elment 40"都还有剩余（一个剩2台，一个剩5台），店员说先优先
给排队进来的前40号，发了票的，之后到3点随便拿，然后在Target里面乱转，随便买
了个小慢锅和小玩具，到了2点10分再去TV那块重新排队，等了50分钟，抬货走人，这
会结帐的队伍少了很多人了，不到15分钟就出来了，感觉还不错！
这个Westinghouse的牌子质量如何啊
发信人: yueke (小鱼儿~2008BB竞猜王), 信区: shopping
标 题: Re: 买了Westinghouse 46" LCD HDTV
发信站: BBS 未名空间站 (Fri Nov ... 阅读全帖 |
|
S**I
发帖数: 15689 | 18 Of course; for example, C++ STL has multiset and multimap, which allow
existence of elments with equivalent keys. Also, both of them have a member
function equal_range, which does exactly what you want.
a |
|
H*****h
发帖数: 300 | 19 刚买了一个2TB element外接硬盘，结果现在台式机在启动阶段就freeze了，Dell的XPS
435t,显示dell标志和进度条就没反应了，拔掉外接硬盘就可以顺利启动了，原来一个
1TB的elment倒是没有这个问题，这会是什么问题呢。
谢谢 |
|
v*****u
发帖数: 1796 | 20 A very inefficiant method:
1. use two queue to calculate the number of elments in queue, say the number
is n
2. use one queue, deque and inque for n times to get the largest number
3. move the largest number into Q2
4. repeat step2, but this time Q1 is one size smaller than before. Until Q1
is empty |
|
g****t
发帖数: 31659 | 21 我十几年前MS Word的VBA很熟。花了不少时间把上海市政府一个部门所有文件做了分析，
提取出来名词术语。尽量让“下岗”这样的词的用法无矛盾。干的多了，我发现写程序
其实应该用word写。但是word虽好，却不支持这个功能。
好在emacs／vim支持。
对编辑器进行程序化操作，可以人机深度融合，改造working flow，提升编程的维度。
编辑器最后其实就是meta－meta－meta－。。。－programming
我举个最简单的例子。例如你有个python pandas s，其中一列为time。
现在想转成一个数组名字为time。
time=np.array(s['time'])
现在想几十列都这么办，怎么最快的做到？在python的空间里这是不容易的。
和之前我提问过的那个找到变量名字的问题有点关系。不是熟练工恐怕搞不定。
而且还容易出bug难维护。python 2 升级这种事再来一次，程序说不定就废了
但是在org－mode里，上面一段程序自动生成一长条程序，几十个
time=np.array(s['time'])
time1=np.array(s['time1'])
t... 阅读全帖 |
|
m******g
发帖数: 467 | 22 基本上就是题目+bulletin point的形式吧，不要纠结我对paper的品味，呵呵。新年快
乐！
PNAS 13.12.03
推荐：
1. Reintroducing domesticated wild mice to sociality induces adaptive
transgenerational effects on MUP expression
promiscuous / monogamous-line
higher MUP (pheromone) expression in pros-line
Male become more attractive
Difference in Mup promoter methylation level
2. High-throughput DNA sequencing errors are reduced by orders of magnitude
using circle sequencing
Previously ~0.1-1x10^-2
Unique library preparation strategy
Copie... 阅读全帖 |
|
m******g
发帖数: 467 | 23 基本上就是题目+bulletin point的形式吧，不要纠结我对paper的品味，呵呵。新年快
乐！
PNAS 13.12.03
推荐：
1. Reintroducing domesticated wild mice to sociality induces adaptive
transgenerational effects on MUP expression
promiscuous / monogamous-line
higher MUP (pheromone) expression in pros-line
Male become more attractive
Difference in Mup promoter methylation level
2. High-throughput DNA sequencing errors are reduced by orders of magnitude
using circle sequencing
Previously ~0.1-1x10^-2
Unique library preparation strategy
Copie... 阅读全帖 |
|
p**e
发帖数: 126 | 24
泥说的这个太复杂，偶看不大明白，偶这个吗，一般的finite elment的书上都有
isoparametric |
|
q**j
发帖数: 10612 | 25 用你的例子，其实最好的办法是这样的：
a1 <- c(1,2,3,3)
a2 <- c(3,2)
common = c(2,3)
then index1=c(NA,1,2,2)
index2=c(2,1)
就是说每个index和原来的向量一样长。每个elment给出和原数据对应的intersect的序
数。如果match不上，就是na，或者0。但是这个东西好像不太好用。anyway, thanks a
lot. |
|
l*****n
发帖数: 72 | 26
It is very trick. When you attach more element -1. You make the mean
closer to the attached -1 value. Then all the attached elments -1 have very
small change over mean, when the change scaled by the sequence standard
deviation, it is even smaller, close to zero. Meanwhile, the only positive
element 1 has large change over the mean and scaled by the standard
deviation will boost it to infinite. Then, sum of the total relative changes
still be close to zero. It has no way to greater than 0. |
|
y***6
发帖数: 46 | 27 Hi all,
I got some new questions about R. Any help is appreciated!
First Question:
If I have the following three row/column vectors:
A=[0, 0 , 0, 0 ,0];
B=[0.1,0.2,0.3,.5,0.6];
C=[1,1,1,1,1];
I want to verify if elments in B are within the corresponding
boundary as defined in vector A and vector C (component-wise), for example,
1st element: 0<0.1<1--> TRUE
2nd element: 0 |
|
t*a
发帖数: 18880 | 28 again, ELMENT 转弯 很不“擅长‘的...
移。 |
|
