D**f
发帖数: 439 | 1 一开始就让我介绍自己做得project，我bla bla说了半天，发现那边没回声，hello了
半天他来一句connection太差了，我只好换个电话。换了之后也没要我重复，直接做题
吧。
题目很简单，就是假设有一很长的数字，比如11224444,被压缩存储为pairs，如(1, 2)
, (2, 2), (4, 4).然后让我写个Iterator，要求有constructor（to take pairs as
input），next() to give out the digit and move to the next position, hasNext
() to indicate if there's any more digit left.
我花了很长时间去搞清楚他到底要做什么，以至于写完后，回答完了有什么输入我不能
处理之后，只剩20分钟，虽然写得还算快。他说没时间了，你问我问题吧，然后就完了
。感觉这题就是个warmup，真正的难题因为时间关系没出，我估计是game over了。感
觉google的面试官对简历都不感兴趣，他们相信题目能够决定一切。 |
D**f
发帖数: 439 | 2 看看我的解答吧。他说有什么输入我不能处理，我没看出来，只要输入是有效的digit
和有限范围的count，应该没问题。
class Iterator
{
public:
Iterator(const unordered_map& m);
int next();
bool hasNext();
private:
unordered_map mp;
unordered_map::const_iterator it;
int count;
};
Iterator::Iterator(const unordered_map& m):mp(m),count(0)
{
it=mp.begin();
}
int Iterator::next()
{
if(it->second > count)
{
count++;
return it->first;
}
else
{
++it;
if(it!=mp.end())
{
count = 1;
return it->first;
}
else
return -1;
}
}
bool Iterator::hasNext()
{
if(it->second > count)
return true;
++it;
bool b = (it!=mp.end());
--it;
return b;
}
int main()
{
unordered_map m;
m.insert(pair(1,2));
m.insert(pair(2,2));
m.insert(pair(4,4));
Iterator it(m);
while(it.hasNext())
{
cout << it.next() << endl;
}
} |
w****x
发帖数: 2483 | 3 Google以前有个类似的题是写vector>的iterator. 其中考虑到vector<
int>可以为空的话其实很不好写, 如果不考虑为空要简单些.
不过这题不用考虑(1, 0)这种情况. 感觉其实电面考这题也不算简单了, Onsite也不算
简单了.不过你用map可能不对吧, 把顺序都打乱了 |
g****y
发帖数: 240 | 4 为什么要用unordered_map？这样的话，顺序不能保证把？ |
e******o
发帖数: 757 | 5 同问，难道不应该是 vector< pair > ？
【在 g****y 的大作中提到】
: 为什么要用unordered_map？这样的话，顺序不能保证把？
|
D**f
发帖数: 439 | 6 unordered_map 可以保证顺序的，这就是为什么叫unordered，其实也就是hash，我已
经测试过了，至于vector>,当然也行，但当时心急，加上刚做过一个unordered
_map的题目，顺手就写了。
的确，输入count为0或者负数，其实没有意义。
最郁闷的是他解释了半天我也没明白要干嘛，后来他在google Doc上给出一个例子，我
才明白。 |
y*******g
发帖数: 6599 | 7 看不懂你的话
unordered
【在 D**f 的大作中提到】
: unordered_map 可以保证顺序的，这就是为什么叫unordered，其实也就是hash，我已
: 经测试过了，至于vector>,当然也行，但当时心急，加上刚做过一个unordered
: _map的题目，顺手就写了。
: 的确，输入count为0或者负数，其实没有意义。
: 最郁闷的是他解释了半天我也没明白要干嘛，后来他在google Doc上给出一个例子，我
: 才明白。
|
i***h
发帖数: 12655 | 8 你这话什么意思？
每个字我都懂
连起来不知道你在说什么
【在 D**f 的大作中提到】
: unordered_map 可以保证顺序的，这就是为什么叫unordered，其实也就是hash，我已
: 经测试过了，至于vector>,当然也行，但当时心急，加上刚做过一个unordered
: _map的题目，顺手就写了。
: 的确，输入count为0或者负数，其实没有意义。
: 最郁闷的是他解释了半天我也没明白要干嘛，后来他在google Doc上给出一个例子，我
: 才明白。
|
D**f
发帖数: 439 | 9 我集中回答了几个问题，也许有点乱。重新改写如下：
unordered_map 可以保证插入元素原有顺序的，（如果有conflict也许不能保证局部的
顺序，但本题应该没有conflict），这就是为什么叫这个结构叫做unordered_map,以区
别于原有的map。unordered_map其实也就是C++ 新标准中hash map的实现.
【在 i***h 的大作中提到】
: 你这话什么意思？
: 每个字我都懂
: 连起来不知道你在说什么
|
y*******g
发帖数: 6599 | 10 看晕了，夜深了，我还是睡觉吧
【在 D**f 的大作中提到】
: 我集中回答了几个问题，也许有点乱。重新改写如下：
: unordered_map 可以保证插入元素原有顺序的，（如果有conflict也许不能保证局部的
: 顺序，但本题应该没有conflict），这就是为什么叫这个结构叫做unordered_map,以区
: 别于原有的map。unordered_map其实也就是C++ 新标准中hash map的实现.
|
|
|
h****e
发帖数: 928 | 11 不够努力啊。
【在 y*******g 的大作中提到】
: 看晕了，夜深了，我还是睡觉吧
|
i***h
发帖数: 12655 | 12 我诚实地讲
我怎么觉得你在说胡话呢
【在 D**f 的大作中提到】
: 我集中回答了几个问题，也许有点乱。重新改写如下：
: unordered_map 可以保证插入元素原有顺序的，（如果有conflict也许不能保证局部的
: 顺序，但本题应该没有conflict），这就是为什么叫这个结构叫做unordered_map,以区
: 别于原有的map。unordered_map其实也就是C++ 新标准中hash map的实现.
|
s*********6
发帖数: 261 | 13 unordered_map在visual studio的哪个版本才有啊? |
t***j
发帖数: 2620 | 14 电面怎么看到你写的code?
[发表自未名空间手机版 - m.mitbbs.com] |
i***h
发帖数: 12655 | 15 share google doc
【在 t***j 的大作中提到】
: 电面怎么看到你写的code?
: [发表自未名空间手机版 - m.mitbbs.com]
|
s*****f
发帖数: 200 | 16 电面 用电话还是skype比较好
2)
hasNext
【在 D**f 的大作中提到】
: 一开始就让我介绍自己做得project，我bla bla说了半天，发现那边没回声，hello了
: 半天他来一句connection太差了，我只好换个电话。换了之后也没要我重复，直接做题
: 吧。
: 题目很简单，就是假设有一很长的数字，比如11224444,被压缩存储为pairs，如(1, 2)
: , (2, 2), (4, 4).然后让我写个Iterator，要求有constructor（to take pairs as
: input），next() to give out the digit and move to the next position, hasNext
: () to indicate if there's any more digit left.
: 我花了很长时间去搞清楚他到底要做什么，以至于写完后，回答完了有什么输入我不能
: 处理之后，只剩20分钟，虽然写得还算快。他说没时间了，你问我问题吧，然后就完了
: 。感觉这题就是个warmup，真正的难题因为时间关系没出，我估计是game over了。感
|
g****y
发帖数: 240 | 17 既然你明白unordered_map是hash的,为什么还说它是可以保证原有顺序的。。。。。。
【在 D**f 的大作中提到】
: 我集中回答了几个问题，也许有点乱。重新改写如下：
: unordered_map 可以保证插入元素原有顺序的，（如果有conflict也许不能保证局部的
: 顺序，但本题应该没有conflict），这就是为什么叫这个结构叫做unordered_map,以区
: 别于原有的map。unordered_map其实也就是C++ 新标准中hash map的实现.
|
D**f
发帖数: 439 | 18 As I said, there's no conflict, so the order is kept. Check this:
unordered_map Class
The template class describes an object that controls a varying-length
sequence of elements of type std::pair. The sequence is
weakly ordered by a hash function, which partitions the sequence into an
ordered set of subsequences called buckets. Within each bucket a comparison
function determines whether any pair of elements has equivalent ordering.
【在 g****y 的大作中提到】
: 既然你明白unordered_map是hash的,为什么还说它是可以保证原有顺序的。。。。。。
|
g****y
发帖数: 240 | 19 没有哪一句说original order is kept. 只是说the sequence is weekly ordered by
a hash function. 但是有可能你第一个元素被hash到最后一个bucket里面去了；第二
个元素被hash到第一个bucket里面去了。你应该好好理解一下hash。
comparison
【在 D**f 的大作中提到】
: As I said, there's no conflict, so the order is kept. Check this:
: unordered_map Class
: The template class describes an object that controls a varying-length
: sequence of elements of type std::pair. The sequence is
: weakly ordered by a hash function, which partitions the sequence into an
: ordered set of subsequences called buckets. Within each bucket a comparison
: function determines whether any pair of elements has equivalent ordering.
|
y*******g
发帖数: 6599 | 20 你别said了
写个code试一下吧
comparison
【在 D**f 的大作中提到】
: As I said, there's no conflict, so the order is kept. Check this:
: unordered_map Class
: The template class describes an object that controls a varying-length
: sequence of elements of type std::pair. The sequence is
: weakly ordered by a hash function, which partitions the sequence into an
: ordered set of subsequences called buckets. Within each bucket a comparison
: function determines whether any pair of elements has equivalent ordering.
|
|
|
y****e
发帖数: 20 | 21 unordered_map does not keep the original order.
Try this code on your machine and see the output.
#include
#include
using namespace std;
int main() {
unordered_map um;
for (int i = 100; i >= 0; i--) {
um.insert(make_pair(i, i));
}
for (unordered_map::iterator it = um.begin(); it != um.end(); it
++)
cout << it->first << " ";
cout << endl;
}
comparison
【在 D**f 的大作中提到】
: As I said, there's no conflict, so the order is kept. Check this:
: unordered_map Class
: The template class describes an object that controls a varying-length
: sequence of elements of type std::pair. The sequence is
: weakly ordered by a hash function, which partitions the sequence into an
: ordered set of subsequences called buckets. Within each bucket a comparison
: function determines whether any pair of elements has equivalent ordering.
|
i***h
发帖数: 12655 | 22 你这段话给个出处？
comparison
【在 D**f 的大作中提到】
: As I said, there's no conflict, so the order is kept. Check this:
: unordered_map Class
: The template class describes an object that controls a varying-length
: sequence of elements of type std::pair. The sequence is
: weakly ordered by a hash function, which partitions the sequence into an
: ordered set of subsequences called buckets. Within each bucket a comparison
: function determines whether any pair of elements has equivalent ordering.
|
y*******g
发帖数: 6599 | 23 他这段话没错，意思是 排序是按照hash order排序的，不是大小也不是插入顺序
【在 i***h 的大作中提到】
: 你这段话给个出处？
:
: comparison
|
i***h
发帖数: 12655 | 24 恩，看到了， "weakly ordered by a hash function"
和LZ理解的完全不是一个东西
【在 y*******g 的大作中提到】
: 他这段话没错，意思是 排序是按照hash order排序的，不是大小也不是插入顺序
|
D**f
发帖数: 439 | 25 hmm，的确如此，但只有前面几个顺序不对，不知道这个hash function是怎样的，如果
只是0-9的话我想不会改变顺序的吧。当然，vector的确更好。
【在 y****e 的大作中提到】
: unordered_map does not keep the original order.
: Try this code on your machine and see the output.
: #include
: #include
: using namespace std;
: int main() {
: unordered_map um;
: for (int i = 100; i >= 0; i--) {
: um.insert(make_pair(i, i));
: }
|
H****s
发帖数: 247 | 26 一般来讲， 你不能对hash function 做任何的假定， it is implementation
dependent.
【在 D**f 的大作中提到】
: hmm，的确如此，但只有前面几个顺序不对，不知道这个hash function是怎样的，如果
: 只是0-9的话我想不会改变顺序的吧。当然，vector的确更好。
|
n******n
发帖数: 567 | 27 难道你说的unordermap是linkedHashMap??如果那样的话就可以了。。。。。 |
