k***g
发帖数: 166 | 1 网上都是2维DP的，我半年前用一个一维数组做出来了，现在却怎么也想不起来是什么
思路，上代码请教一下大家：
int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
if (n1 + n2 != n3) return false;
deque M(n2+1); M[n2] = true;
for (int j=n2-1; j>=0; j--)
if (!(M[j] = s3[n1+j] == s2[j] && M[j+1]))
break;
for (int i=n1-1; i>=0; i--) {
for (int j=n2-1; j>=0; j--) {
if ( s3[i+j] == s1[i] && M[j] )
M[j] = true;
else if ( s3[i+j] == s2[j] && M[j+1] )
M[j] = true;
else
M[j] = fals... 阅读全帖 |
|
M*****1
发帖数: 37 | 2 解这个题要deque, 和sliding window maximum那题思路很类似 |
|
t**r
发帖数: 3428 | 3 贴个答案
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
|
|
j********l
发帖数: 325 | 4 ms onsite interview面经
因为是hiring event，面试流程更紧，一轮只有45分钟，所有人都是4轮，全是白人面
试官
1st: implement queue by array assuming the size of array is enough, write
the enque and deque methods;
2st: implement c#'s dictionary, both k and v are generic, write put(k,
v), get(k) and remove(k) methods;
3rd,
a. insert an integer into an sorted linked list, implement the linked list
and write the insert method;
b. find the first occurrence of second string from the first string (
actually, it's the Implement strStr ... 阅读全帖 |
|
t**r
发帖数: 3428 | 5 java直接用deque.
push新东西。
pop过期的。
.size() 可以得到大小 |
|
y*****e
发帖数: 712 | 6 这题我第一次看到是在板上，在这里
http://www.mitbbs.com/article_t/JobHunting/32876295.html
Tasks: AABABCD
Cooldown Time: 2
A__AB_ABCD
Output: 10
后来发现这题很快变成fb的新欢，各种follow up啊。。。今天看到一个实在心塞的，
越想越复杂，想发上来问问大家有啥好主意
follow up是给你一个task队列， 要求你自己排列要求最后的总时间最小，比如
aaaabbbccd，可以排成abcabcabda。
看到有人建议说每次排gap + 1个任务，取distinct tasks，也就是尽量分开同种任务
，放的时候从frequency高的开始，我觉得这就需要一个treemap了吧，先abc放完，然
后再放一轮abc，放一个减少count,count == 0的时候从treemap里去掉。如果是aaab怎
样的呢？放完ab只能再空等一次才能再放a，这样的话是不是应该有个deque来实现？ |
|
L***s
发帖数: 1148 | 7 object models, metaclass, decorators, enhanced generators / coroutines
threading models, GIL, asyncio & alternative async libs like gevent/twisted
writing C/C++ extensions
writing 2/3 compatible Python code
(for web developers) familiar with django, flask, twisted or tornado
implementation of dict, OrderedDict, deque, etc. in CPython & implications
memory management & fragmentation prevention in CPython
PVM internals and optimization, opcodes and AST hacking
alternative implementations like PyPy... 阅读全帖 |
|
J*********a
发帖数: 50 | 8 lz是不是面的时候紧张啊。。。
紧张的时候思路容易混乱，这题可以用stack加个list吧：
public static void printTreeNodeLeafToRoot(TreeNode root) {
if (root == null) return;
Deque stk = new LinkedList<>();
stk.push(root);
List list = new ArrayList<>();
list.add(root);
while (!list.isEmpty()) {
List curr = new ArrayList<>();
for (TreeNode tn : list) {
if (tn.right != null) {
stk.push(tn.right);
... 阅读全帖 |
|
b***e
发帖数: 1419 | 9 灰常简单：
从所有1所在的位置开始做parallel BFS。具体的讲就是：
// assume input matrix is A
for each (i,j) {
if (A[i,j] == 1) {
M[i,j] = 0;
Q.enque((i, j));
} else {
M[i,j] = null;
}
}
while (Q.notEmpty()) {
(i, j) = Q.deque();
if (M[i+1,j] is null) {
Q.enque(i+1,j);
M[i+1,j] = M[i,j] + 1;
}
if (M[i-1,j] is null) {
Q.enque(i-1,j);
M[i-1,j] = M[i,j] + 1;
}
if (M[i,j+1] is null) {
Q.enque(i,j+1);
M[i,j+1] = M[i,j] + 1;
}
if (M[i,j-1] is null) {
Q.enque(i,j-1... 阅读全帖 |
|
S********t
发帖数: 3431 | 10 deque 存non decreasing sequence |
|
f*******r
发帖数: 976 | 11 您说的是non－increasing deque吧 |
|
f*******r
发帖数: 976 | 12 这个解法其实不好，最坏时间是O(k). heap的最坏时间只要lg k。用deque的优势是平
均时间少，最坏时间比较差。
heap保证最坏时间都只是lg k。 |
|
c********t
发帖数: 5706 | 13 blockingqueue已经讨论过不少次了。我想问一下有可能执行enque的thread 和deque的
thread同时在wait吗？还有就是如何保证 enque顺序呢，比如三个enque threads都先
后wait, 唤醒的时候能保证唤醒的是第一个thread吗？Thread scheduling并不能保证
吧？那么不久违反了queueFIFO的性质吗？ |
|
c********t
发帖数: 5706 | 14 多谢！1，3明白了。2 我的意思是会不会同时 执行deque的thread 进入 while(queue.
isEmpty()) { wait();}, 而另一个执行enque的thread进入while(queue.size()==
limit){ wait();} ？ limit capacity大于等于1。
我觉得应该不会吧。 |
|
c********t
发帖数: 5706 | 15 多谢！
我想明白了。我原来想如果deque 和enque thread不会同时等待的话，synchronized +
notify不就行吗？(不是notify all) 后来想到由于synchronized, 他们其实会同时等
待，光notify就不行了。
还有一个问题就是 为什么要用循环array来做，而不用一个local的queue呢？ |
|
g****g
发帖数: 1828 | 16 SGI Logo
vector
Category: containers Component type: type
Description
A vector is a Sequence that supports random access to elements, constant
time insertion and removal of elements at the end, and linear time insertion
and removal of elements at the beginning or in the middle. The number of
elements in a vector may vary dynamically; memory management is automatic.
Vector is the simplest of the STL container classes, and in many cases the
most efficient.
Example
vector V;
... 阅读全帖 |
|
w***g
发帖数: 5958 | 17 CPU的优化主要是在cache和lock contention两方面，需要针对具体的code手工实现，
不是-O3就能搞定的。一个程序跑的快不快，首先看算法，然后看实现上的优化，比如C
++用vector还是deque还是直接上int[]之类的,然后是一般性的cache和lock的优化，最
后还是不够快才做针对CPU的优化，比如手工上SSE指令，手工调cache line长度之类的
。到了这一步想要提高即使一倍的速度也是千难万难了。GPU的优化远比CPU的优化难，
而且真正有效的应用领域也远小于CPU，除了游戏以外的市场实在太小。而且即便在这
些有限的领域，CPU跟GPU的差距也在不断缩小。我自己觉得GPGPU在五年之内就会死掉
。同时在Intel的CPU里会出现越来越多GPU的技术。现在在GPGPU上面投资钱和精力，即
使一时能有收效，从长期看来也是不值得的。【 在 shingoxlf (shingo) 的大作中提
到: 】 |
|
w***g
发帖数: 5958 | 18 CPU的优化主要是在cache和lock contention两方面，需要针对具体的code手工实现，
不是-O3就能搞定的。一个程序跑的快不快，首先看算法，然后看实现上的优化，比如C
++用vector还是deque还是直接上int[]之类的,然后是一般性的cache和lock的优化，最
后还是不够快才做针对CPU的优化，比如手工上SSE指令，手工调cache line长度之类的
。到了这一步想要提高即使一倍的速度也是千难万难了。GPU的优化远比CPU的优化难，
而且真正有效的应用领域也远小于CPU，除了游戏以外的市场实在太小。而且即便在这
些有限的领域，CPU跟GPU的差距也在不断缩小。我自己觉得GPGPU在五年之内就会死掉
。同时在Intel的CPU里会出现越来越多GPU的技术。现在在GPGPU上面投资钱和精力，即
使一时能有收效，从长期看来也是不值得的。【 在 shingoxlf (shingo) 的大作中提
到: 】 |
|
w*********n
发帖数: 439 | 19 A calculator application that allows prefix, infix, and postfix expressions
to be evaluated (i.e., allows all 3 types of expressions).
List
Queue
Deque
Binary tree
Binary search tree
B tree
HashMap
HashSet
Priority Queue
Graph |
|
vi
发帖数: 309 | 20 Although I vaguely know the differences between private and protected,
but I am not sure on exactly where should I use which. For an example,
STL list is declared as:
template >
class stack {
public:
bool empty() const;
size_type size() const;
value_type& top();
const value_type& top() const;
void push(const value_type& val);
void pop();
protected:
Container c;
};
Question: why 'protected' is used here?
Thanks! |
|
k***s
发帖数: 277 | 21 我用deque作为基类, 写了一个管理指针的container,
不过我只需要push_back, pop_back, size的几个接口。 |
|
j********e
发帖数: 7 | 22 Let me try:
step 1: traverse the string once, and count the occurance of each key
characters in the search string: i.e. a:3, c:3, d:1, e:1
step 2 : Recursion
/*"count" maps key characters to the # of occurance*/
/*"stringPath" is the longest string path so far containing all key characters
*/
void checkShortest(deque& stringPath, Map& count)
{
char head = stringPath.front();
char tail = stringPath.back();
/*Head character is not a key character*/
/*Or it is a key character, and h |
|
m***t
发帖数: 254 | 23 the original post does not make much sense to me. so
udp connection -> unpack -> filter -> makebook,
so if there is error in udp packet, you donot clear the buffer till the new
response comes in to correct the error? then thread stack overflow happens
at unpack stage?
if i were you i will test first part first. given If that does not give you
problem, i think it might be you are not dequeing thread buffer incorrectly
at latter stages. |
|
D*******a
发帖数: 3688 | 24 能不能只插入object的指针
而且，感觉你这种情况用list比deque快 |
|
v*****u
发帖数: 1796 | 25 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 |
|
d****n
发帖数: 130 | 26 用C-style string不安全, 用STL string效率不高啊, 因为string是immutable, 插入
字符什么的很不方便, 用vector, deque也看着很笨.
大家一般用什么? |
|
c**a
发帖数: 316 | 27 ....
vector<> does not support front_inserter.
deque ? |
|
|
b***y
发帖数: 2799 | 29 那这个pointer是怎么定义的? 我一直以为iterator就是用pointer实现的. 用pointer来
访问container的东西, 具体怎么操作? |
|
S**I
发帖数: 15689 | 30 我记得只有vector和string的iterator是用pointer实现的；用pointer访问container
应该是这样子：T* = &(*iter)
pointer来 |
|
t****t
发帖数: 6806 | 31 It is correct. But you need to know how to read it. It said: "The underlying
*container* ..." where "container" is explicitly defined in the standard.
Container is defined in 23.1 -- it requires ::value_type and ::size_type
defined.
The original wording on the standard is:
"Any sequence supporting operations back(), push_back() and pop_back() can
be used to instantiate stack. In particular, vector (23.2.4), list (23.2.2)
and deque (23.2.1) can be used."
Similarly, the important word here is "seq |
|
e*l
发帖数: 37 | 32 但是你可以使用deque,这个满足标准容器的要求,而且存储是真正的bool类型
bitset的大小是编译期常量,不能动态指定,且不是标准容器 |
|
c**********e
发帖数: 2007 | 33 Which one of the following standard containers does NOT invalidate iterators
when elements are inserted within the existing sequence?
a) queue
b) deque
c) list
d) stack
e) valarray |
|
M*******r
发帖数: 165 | 34 【 以下文字转载自 Quant 讨论区 】
发信人: Morphiner (Ninja Turtle), 信区: Quant
标 题: 借人气问个c＋＋的overflow
发信站: BBS 未名空间站 (Mon Nov 15 12:40:52 2010, 美东)
stack overflow在main后面的{
会是怎么回事？
附上code：
//#include
#include
#include
#include
#include "BarGame.h"
#include
#include
//#include "randomc.h"
//#include "mersenne.cpp" // code for random number generator of
type Mersenne twister
#include "require.h"
//#inclu... 阅读全帖 |
|
t****t
发帖数: 6806 | 35 the second form allow generic container. first form only allow random
accessed container, such as vector or deque.
Is
prorammer? |
|
r****t
发帖数: 10904 | 36 非 template 情况似乎比较清楚了，class template 里面的 static data
member 的定义和初始化有没有啥龟腚？
举个例子：
template
class StackWithCapacity : public stack_adapter
{
public:
typedef typename stack_adapter< Container>::size_type size_type;
private:
static const size_type capacity = 5;
};
capacity 是个 static const member, 我就直接在 class body 里面初始化了，
据 c++ primer，class body 外面还必须 define without initializer (虽然我我不这么做也能编译并运行正常). 这样我就在外面加
template
StackWithCapacity... 阅读全帖 |
|
J*****n
发帖数: 4859 | 37
这个倒是对的，时间是要砸进去的。
不过lz如果是真的要应付面试的话，时间有限，能找个高手还是能省下不少时间的。
我当年半年内被我的朋友把我的C++面试技巧提高了N各层次。
不过时间就算砸进去了，如果没有真正做过相关的project,其实还是用处不大。
列一些我当年碰到过的很triky的题目吧：
1。sort的使用注意事项。
2。map和hash table的使用，C++ map的数据结构是什么,hash table是怎么实现的。
3。list和vector的不同，deque的实现方式。
4。vector 的a[10,10]和a[100]有什么不同。
5。vector和数组有什么不同，vector里面能不能放ref，为什么？
6。多态在C++中的实现。
7。估计class的大小，空vector多大。怎么清空vector。
8。哪几种情况必须要用Init list，其优点是什么。
9。smart ptr的实现，intrustive和non-intrustive的区别。Boost里面那些smart ptr
的用处。
10。 线程池是什么，allocator是什么。
11。register，... 阅读全帖 |
|
t****t
发帖数: 6806 | 38 why do you want to use queue/stack in the first place, if you don't need a
queue or stack?
in other words, queue and stack are supposed to visited FIFO or LIFO. if you
want iterator, use deque or vector; they have all the functions of queue or
stack, while having iterators.
queue |
|
w****o
发帖数: 2260 | 39 谢谢！
1. 其实吧，在看别人的代码，想加点自己的代码，试些东西，他们用了queue,我想在
某个特定的情况下，想看一下到底queue放了些什么东西，或者是想看看里面有没有满
足某些条件的元素。
2. 你说的对，vector, deque都有iterator,如果要方便的话，就用这些好了。
还有，我得出了结论，stl里的container并不是每个都有iterator的。
谢谢啦！
you
or |
|
|
h*******s
发帖数: 8454 | 41 我每次想用queue的时候，最后好像都用了deque。。。 |
|
c**********e
发帖数: 2007 | 42
我哪里会知道？但是他们难道不是在同一个领导班子知道下工作的吗？
这只是一个标准的库而已，谈不上什么实力吧。 |
|
d****n
发帖数: 1637 | 43 这些人都是白天餐馆打工，晚上熬夜垒码。哪有领导。 |
|
c**********e
发帖数: 2007 | 44 This is very very interesting information. Thank you very much.
top
name.
queue |
|
r****t
发帖数: 10904 | 45 queue 是 adaptor, 啥都有，前面 thrust 答过这问题，记得是问 random access
stack 的。 |
|
|
|
l*********s
发帖数: 5409 | 48 I cannot help wondering if careerchange is actually an interview officer.
Hard to believe anyone cannot to land a coding job, if he/she is so devoted. |
|
|
