l*********y
发帖数: 142 | 1 第一次用multiset，不知道怎么用
题目应该很简单的，蛮力排序的话会超时。
网上的评论是
Easy. Don't use cin or cout and you could use a multiset :)
实在无语。没想出怎么用multiset。
谁给解释一下。谢谢了！
Problem H: Hoax or what
Each Mal-Wart supermarket has prepared a promotion scheme run by the
following
rules:
* A client who wants to participate in the promotion (aka a sucker) must
write down their phone number on the bill of their purchase and put the
bill into a special urn.
* Two bills are selected from the urn at the end of each day: first the
... 阅读全帖 |
|
b******i
发帖数: 914 | 2 问问，因为multiset实在写习惯了，新的priority_queue反而怕出bug。
请问面试的时候用multiset来代替heap可以吗（如果不要求实现heap本身的话），
multiset是基于红黑树的，复杂度应该都是log(n)的。 |
|
h**6
发帖数: 4160 | 3 multiset和set的用法完全一样，只是允许有多个数重复而已。每天向multiset里insert一行数值，并把最大和最小的去掉即可。 |
|
s*****c
发帖数: 36 | 4 Hi,composite:
As for user defined data type support of Cast, I think it
depends on the specified DBMS.
"Multiset" is unrelated with "Cast". It's not a function,
but a concept. It is the definition of multiset: An
unordered collection of objects that are not necessarily
distinct. The collection may be empty.
Because SQL allows duplicate rows in a table, or applied
aggregate funcitons may result in duplicate rows, by
default,
SQL treats a table generated by select or group by as a
mutliset rather |
|
c**********e
发帖数: 2007 | 5 Associative container 是 set, multiset, map, multimap 这些东西吗？
原来C++容器也分贫下中农：
Sequence Container: vector, deque, list
Container Adaptor: stack, queue, priority_queue
Associative container: set, multiset, map, multimap ??? |
|
l*********y
发帖数: 142 | 6 是可以，但是如果你在最大堆拿掉一个最大值，同时也要拿掉最小堆的这个值。
这样就要implement heap.find，而不能用STL 的 priority_queue了，因为priority_
queue里没有find。
这样编程很累的。我看很多人谈论这道题都是说multiset,所以来问一下。
多谢了 |
|
c****p
发帖数: 6474 | 7 multiset的数据是ordered。
所以 begin()返回最小值的iterator，end()-1返回最大值的iterator，
然后erase()就可以了。
本质上还是某种二叉搜索树。 |
|
b******i
发帖数: 914 | 8 同意，
priority_queue不能update节点。
但我指的情况比如leetcode上面merge K sorted list那题不是要用个heap吗，这种情
况如果我就用multiset面试官会说吗？
() |
|
a*****g
发帖数: 13 | 9 c++ practice (use multiset):
#include
#include
using std::multiset;
using std::string;
int len_p = 4;
bool check_substr(string s, const multiset &L) {
multiset dup_L = L;
for (unsigned i=0; i
string token = s.substr(i, len_p);
multiset::iterator itor = dup_L.find(token);
if (itor == dup_L.end()) {
return false;
}
dup_L.erase(itor);
}
return dup_L.empty();
}
int main(... 阅读全帖 |
|
a*****g
发帖数: 13 | 10 c++ practice (use multiset):
#include
#include
using std::multiset;
using std::string;
int len_p = 4;
bool check_substr(string s, const multiset &L) {
multiset dup_L = L;
for (unsigned i=0; i
string token = s.substr(i, len_p);
multiset::iterator itor = dup_L.find(token);
if (itor == dup_L.end()) {
return false;
}
dup_L.erase(itor);
}
return dup_L.empty();
}
int main(... 阅读全帖 |
|
w*******e
发帖数: 395 | 11 这道题目非常复杂，首先能想到n*log(n)的算法就不简单，即使想到了，能够在面试的
压力下把逻辑coding出来也非常的难。我感觉电面中，问到这种题目而且要coding的，
如果从没有见过，基本就是不让你过。感觉这种题目适合onsite用。
在知道算法后，我大概花了一些时间，写了如下的代码，基本思路就是楼上讨论的。
1. 首先把所有的interval的起点和终点存进一个vector,并且sort
struct timePoint {
int point;
bool startORend;
int vol;
timePoint(int p, bool s, int v): point(p), startORend(s), vol(v) {}
};
2. 建立一个multiset用来存储还没有结束的volume，同时可以用来判断某个时间段是
否被输入的interval cover了。
3. 然后扫描vector开始建立输出的vector：
1）如果碰到start的点，先检查multiset是否为空，如果是，就是i... 阅读全帖 |
|
w*******e
发帖数: 395 | 12 这道题目非常复杂，首先能想到n*log(n)的算法就不简单，即使想到了，能够在面试的
压力下把逻辑coding出来也非常的难。我感觉电面中，问到这种题目而且要coding的，
如果从没有见过，基本就是不让你过。感觉这种题目适合onsite用。
在知道算法后，我大概花了一些时间，写了如下的代码，基本思路就是楼上讨论的。
1. 首先把所有的interval的起点和终点存进一个vector,并且sort
struct timePoint {
int point;
bool startORend;
int vol;
timePoint(int p, bool s, int v): point(p), startORend(s), vol(v) {}
};
2. 建立一个multiset用来存储还没有结束的volume，同时可以用来判断某个时间段是
否被输入的interval cover了。
3. 然后扫描vector开始建立输出的vector：
1）如果碰到start的点，先检查multiset是否为空，如果是，就是i... 阅读全帖 |
|
w*****d
发帖数: 105 | 13 3. 无限数据流，怎样求最近的100万个数字中最大的数？
我觉得应该用multiset + list，每次得到一个数后：
1)insert into multiset, get iterator;
2)list.push_back(iterator);
3)if list.size() > 100w, multiset.erase(list.front()) and list.pop_front();
max value is always (*multiset.begin()); |
|
f******5
发帖数: 104 | 14 BST, O (n*(logW+k))
void printBST(multiset > &BST, int k){
int i=0;
multiset >::iterator it=BST.begin();
for(;i
cout<<(*it)<<",";
++it;
}
cout<
}
void topK_SlideWindow(vector &A, int w, int k){
//use BST tree to record w elems in the windows.
//update BST, add new elem into BST, and delete old elem.
assert(A.size()>=w&&k<=w);
multiset >BST;
for(int i=0;i
... 阅读全帖 |
|
k***e
发帖数: 556 | 15 放什么飞机？npc也搞出来了。
In computer science, the partition problem is an NP-complete problem. The
problem is to decide whether a given multiset of integers can be partitioned
into two "halves" that have the same sum. More precisely, given a multiset
S of integers, is there a way to partition S into two subsets S1 and S2 such
that the sum of the numbers in S1 equals the sum of the numbers in S2?
如果可以多项式时间解决楼主的问题，只要m取2，看得到的subset summation是否等于
sum/2，就可以回答该set是否能够partition的query？
麻烦大侠以后能贴点靠谱的题目。 |
|
w****o
发帖数: 2260 | 16 1. STL中的std::unordered_map是不是等同于（或者是类似）Java中的Hashmap?
2. STL中的std::map是不是等同于（或者是类似）Java中的Treemap?
3. STL中hashtable是哪个类实现的？Java中类似的哪个类叫什么名字？问的就是在STL
和Java下都是叫什么名字。
4. 为什么在我的linux机器上的目录/usr/include/c++/4.1.2下只有set, map而没有
multiset和multimap?你们的系统里有multiset和multimap吗？
另外我发现STL的unordered_map和unordered_set是定义在/usr/include/c++/4.1.2/
tr1下面的。
谢谢！ |
|
M********5
发帖数: 715 | 17 来自主题: JobHunting版 - G家电面筋 第一题如果是用c++实现的话，是不是可以用multiset，先把第一个数组的数hash起来
，然后从前往后遍历第二个数组，如果有的话，就把这个multiset里面的数移除，用这
些移除的数建立的新的array/vector就是所求的答案。
因为两个array都是已经sort好的，所以遍历第二个array的时候确保了这个新的array
是sort好的。。。
这样的话时间就是O(m+n) |
|
w******g
发帖数: 189 | 18
路？
请问第一题你是直接实现一个heap吗？还是用std::multiset？但是std::multiset在内
部是用binary search tree实现的哦。 |
|
k**y
发帖数: 12 | 19 没有特别明白。
然后保持0-9出现的次数
--> 这整个int[10] 存到 hashset里面吗？
这跟multiset有什么关系？难道不是会看到同样的就更新一下counter就好了，不需要
把重复的set存进去？我觉得能用set的东西一定可以用map呀，map的value是0/1就够表
达set了，value是count就能表达multiset了 |
|
C*******e
发帖数: 41 | 20 I have a question here:
What do CAST and MULTISET do in SQL language?
I read in a book that CAST converts a specified scalar value to
a specified scalar data type (maybe a user defined data type),
is that true? Does it take at least two arguments (value and the
data type)?
And I can't find MULTISET. Please give me a hand.
Thanks. |
|
y**b
发帖数: 10166 | 21 ///////////////////////////////////////////////////////////
A:
class Widget {
public:
...
size_t weight() const;
size_t maxSpeed() const;
...
};
bool operator<(const Widget& lhs, const Widget& rhs)
{
return lhs.maxSpeed() < rhs.maxSpeed();
}
multiset widgets;
///////////////////////////////////////////////////////////
B:
class Widget {
public:
...
size_t weight() const;
size_t maxSpeed() const;
...
};
struct MaxSpeedCompare:
public binary_function {
bool operator()(... 阅读全帖 |
|
w****o
发帖数: 2260 | 22 【 以下文字转载自 JobHunting 讨论区 】
发信人: winhao (勇敢的人), 信区: JobHunting
标 题: 问几个关于hash, map, set的问题
发信站: BBS 未名空间站 (Wed Mar 7 14:52:17 2012, 美东)
1. STL中的std::unordered_map是不是等同于（或者是类似）Java中的Hashmap?
2. STL中的std::map是不是等同于（或者是类似）Java中的Treemap?
3. STL中hashtable是哪个类实现的？Java中类似的哪个类叫什么名字？问的就是在STL
和Java下都是叫什么名字。
4. 为什么在我的linux机器上的目录/usr/include/c++/4.1.2下只有set, map而没有
multiset和multimap?你们的系统里有multiset和multimap吗？
另外我发现STL的unordered_map和unordered_set是定义在/usr/include/c++/4.1.2/
tr1下面的。
谢谢！ |
|
w****o
发帖数: 2260 | 23 【 以下文字转载自 JobHunting 讨论区 】
发信人: winhao (勇敢的人), 信区: JobHunting
标 题: 问几个关于hash, map, set的问题
发信站: BBS 未名空间站 (Wed Mar 7 14:52:17 2012, 美东)
1. STL中的std::unordered_map是不是等同于（或者是类似）Java中的Hashmap?
2. STL中的std::map是不是等同于（或者是类似）Java中的Treemap?
3. STL中hashtable是哪个类实现的？Java中类似的哪个类叫什么名字？问的就是在STL
和Java下都是叫什么名字。
4. 为什么在我的linux机器上的目录/usr/include/c++/4.1.2下只有set, map而没有
multiset和multimap?你们的系统里有multiset和multimap吗？
另外我发现STL的unordered_map和unordered_set是定义在/usr/include/c++/4.1.2/
tr1下面的。
谢谢！ |
|
y***a
发帖数: 840 | 24 需求：
有N个int数组 （N未知）， 每个数组里的元素数目也未知， 但大于0， 要求每个
数组里取一个元素,组成一个N个元素的multiset （就是允许元素重复出现）, 要求列
举所有的multiset.
主要问题是N不知，所以只能用递归／FUNCTIONAL PROGRAMMING比较容易。用
PYTHON的
ITERTOOLS能搞定吗？ 就你熟悉的语言写出最简单的程序是什么样子的？ 欢迎赐教。 |
|
g*******y
发帖数: 1930 | 25 不是NPC，题目是分成m段(切m-1刀)，不是m个subset
partitioned
multiset
such |
|
i********s
发帖数: 133 | 26 This is NP complete. Suppose we have only 2 buckets, and a set of numbers.
Then the multiset partitioning problem (NPC) can be reduced to this problem. |
|
m**q
发帖数: 189 | 27 平时都写纯C，STL不熟，现查的写的伪代码，可能有些地方不准确
假设sort后的数组为a，长度是2n，则sweeping line算法大概是这样的
multiset s;
vector v;
for (int i=0; i<2n; i++) {
if (a[i].second) { //start is 1, left edge
add_points(v, a[i].first, *(s.rbegin());
s.insert(a[i].first.second);
} else { //start is 0, right edge
s.erase(s.find(a[i].first.second)); //only removes ONE if
multiple values are the same
add_points(v, a[i].first, *(s.rbegin());
}
}
void add_points... 阅读全帖 |
|
c****p
发帖数: 6474 | 28 用一个最大堆和最小堆就可以了吧。。
或者直接BST也可以。 |
|
S*******0
发帖数: 198 | 29 刚记起还有一道题，问
Does C++ allow multiple inheritance?
What is the potential problem of multiple inheritance?
就说了说继承的ambiguity,举了个例子
class A
class B,C : public A
class D :public B,C
问：怎么解决？
用virtual inheritance: class B,C : virtual public A
B,C共享基类A
----
下午刚面完，说下周一给结果。
大部分是概念题，和behavior题
Why bloomberg?
Why software developer?
Describe the case that you feel press from colleague
How do you manage projects?
1. Ask a C++ project. Describe what features of c++ are used?
Explain encapsulatoin, inheritance, ... 阅读全帖 |
|
S*******0
发帖数: 198 | 30 6. 一开始我用set，然后问了一下list A是否允许duplicate，面试官可能，所以改用
multiset。现在想想，用set也可以，只要找到两个list的intersection就可以了
7.见附件 |
|
q****x
发帖数: 7404 | 31 又想了一下，这个三叉树实际还是二叉树，不过把相同的键放到一个单链表里。
multiset和multimap就是用这个实现的吧？ |
|
p*********b
发帖数: 47 | 32 是，没什么区别，他们造出来的概念而已我觉得，单链表后面的node值都相同，左右指
针都浪费了。
我还真不知道multiset/map是用什么实现的，可能是。 |
|
S**I
发帖数: 15689 | 33 1. yes
2. yes
3. N/A in C++, HashTable in Java
4. Do you know which header file to include when using multiset or multimap?
unordered_map and unordered_set only became part of std recently, the
implementation hasn't been updated yet.
STL |
|
w****o
发帖数: 2260 | 34 谢谢 SETI,
我看了一下，
set文件包含了
#include
#include
#include
map文件包含了
#include
#include
#include
现在明白了multiset和multimap都已经在STL了。非常感谢。
仍有一问题不明白，就是如果写C/C++代码，如何用hashtable?难道要自己实现吗？好
像不太容易吧如果from scratech的话。
好像在tr1/下面有一个文件hashtable,unordered_map, unordered_set的实现都用到了
tr1/hashtable,是不是可以说这个就是STL 扩展中的hashtable的实现呢？
是不是我们写代码的时候可以用tr1/hashtable去用作hashtable?
谢谢了！
multimap? |
|
c****x
发帖数: 15 | 35 just maintain two multi-set, recurse to next layer when two multiset are
equal
leaf |
|
d******9
发帖数: 36 | 36 本来定好这周五第二轮电面，下午接到电话说直接on-site。
这样会不会在on-site的时候多加一轮。
第一轮电面问的题目也不多，下面是面经。
概念题：
garbage collection。
动态分配空间的存储位置。
set的实现，multiset的实现，如果很多重复怎么办，如果数据量很大怎么办。
OOD的特点。
编程题：合并两个排好序的数组，有重复。
应该还有一些概念题，现在忘记了。写代码的时间很短。
看有些电面面经题目很多的样子，我这样子去on-site会不会不太好。感觉考察点不够应
该也会影响最后结果吧。 |
|
p****c
发帖数: 35 | 37 先是各自简单的自我介绍。然后两道很常规的题目:
1. 判断字符串不考虑标点空格的情况下是回文.
2. 给定一组字符串, 按anagram分组后，返回list of list.
当时脑子一片空白，用了半个多小时才搞定。第一题跳过标点空格时忘了检查字符越界
. 写完后，说我先测试一下. 假设输入是一个空格, 自己走了一遍说好像可以.考官问
你的测试真的可以吗？才发现了没有检查字符越界的bug. 赶快加上.考官说可以简化一
下while的条件吗？看了一下去掉了一个多余的条件,说我看看还能再简化吗. 考官说可
以了，你的程序works, 下一个吧.
第二题一开始突然不知道该用什么数据结构。我说就定义一个less_than直接排序就可
以了. 刚想写less_than, 觉得这样太复杂，我说还是用hash或者map吧。考官说key是
什么, 我说没有key,就用hash_set或者multiset吧. 考官说你可以造一个key吗？我说
可以把字符串排序作key. 然后开始定义数据结构. hash_map, 写到
这里看了一下改成multimap阅读全帖 |
|
b*********h
发帖数: 103 | 38 看大家都用优先队列，贴一个 set 的吧 呵呵，用 C++ 的表示声明 priority queue
打字太多。。。继续说 C++ 的 priority queue 又不支持 decrease key，喜欢用 set
当 priority queue 。。。
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
multiset S;
for (int i = 0; i < lists.size(); ++i) {
if (lists[i]) {
S.insert(lists[i]);
}
}
ListNode* head = 0;
ListNode* tail = 0;
while (!S.empty()) {
ListNode* nod... 阅读全帖 |
|
m****1
发帖数: 41 | 39 两个multiset解，保持两边的平衡就行，边界有点暴力 |
|
f*******w
发帖数: 1243 | 40 Substring with Concatenation of All Words
You are given a string, S, and a list of words, L, that are all of the same
length. Find all starting indices of substring(s) in S that is a
concatenation of each word in L exactly once and without any intervening
characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
我的code如下
之前用unordered_set, 如果L里面有重复元素就跑不过
现在改用multiset, 直接出错……
求助求助……
class Solution {
public:
vector findSubstring(string ... 阅读全帖 |
|
n****e
发帖数: 678 | 41 Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。 |
|
g*********e
发帖数: 14401 | 42
。
multiset用来做maxheap貌似不错！
不知道heap在stil里标准的data structure是什么 |
|
n****e
发帖数: 678 | 43 Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。 |
|
g*********e
发帖数: 14401 | 44
。
multiset用来做maxheap貌似不错！
不知道heap在stil里标准的data structure是什么 |
|
w*******e
发帖数: 395 | 45 显然不work啊，当遇到end的时候，需要把该end所属区间的volume从heap里删掉，如果
当前的volume不是最大的话，怎么从heap里删掉？？
novice的就解法是这样的：
“
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。
” |
|
w*******e
发帖数: 395 | 46 显然不work啊，当遇到end的时候，需要把该end所属区间的volume从heap里删掉，如果
当前的volume不是最大的话，怎么从heap里删掉？？
novice的就解法是这样的：
“
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。
” |
|
s**x
发帖数: 7506 | 47 应该可以吧？ multiset, multimap etc. |
|
z****s
发帖数: 409 | 48 谁教你的multiset就是BST了？BST的变形 == BST？自己去wiki下BST定义吧。 |
|
f*****u
发帖数: 308 | 49 我用的HashMap，他最后跟我说应该用MultiSet，我承认没用过。 |
|
k**y
发帖数: 12 | 50 用hashmap数count (i.e. map)，难道跟multiset不是一个效果吗？ |
|
