p*u
发帖数: 136 | 1 面试官人挺好的，听声音是华人，不过自己表现太烂了，一紧张写代码哆嗦
一个题：
给一堆用户的login logout日志，当在线用户数变化的时候，输出当前时间段的在线用户
算法简单，可是一紧张就写残了。 |
z*********8
发帖数: 2070 | |
n****e
发帖数: 678 | 3 是不是用hashmap把login，logout各扫一遍
hashmap的key是用户id，value是timestamp。 |
g*********e
发帖数: 14401 | |
n****e
发帖数: 678 | 5 是不是用hashmap把login，logout各扫一遍
hashmap的key是用户id，value是timestamp。 |
g***9
发帖数: 159 | 6 没有完全理解清楚题目意思....
要问的是能够实时查询当前的在线用户数吗?
这样就得keep当前在线用户数,并根据login logout更新, 提供O(1)查询吧?
如果是lz说的当前时间段, 又是什么意思呢..? |
s********u
发帖数: 1109 | 7 用linked list+hashmap？如果是当前时刻的话，应该linked list就行了
如果是时间段的话，bst应该是可行的。不过代码面试一紧张都不好写。。 |
b**********5
发帖数: 7881 | 8 不懂。 你linkedlist里面放什么？
【在 s********u 的大作中提到】
: 用linked list+hashmap？如果是当前时刻的话，应该linked list就行了
: 如果是时间段的话，bst应该是可行的。不过代码面试一紧张都不好写。。
|
s********u
发帖数: 1109 | 9 每个node都代表一个人，login就把他插入，login out就把他删除。
当前时刻的人数就是list的size。
好像还是一定要hashmap的，为了找到这个人。他说的log日志应该就像是：
10:16pm 用户id：110 log out
用户id：205 log in
。。。这样
我觉得他应该是这个意思，带点设计的。否则岂不是只要一个变量，有人login就加1，
有人logout就-1？？？？
【在 b**********5 的大作中提到】
: 不懂。 你linkedlist里面放什么？
|
l*n
发帖数: 529 | 10 直接Set就行吧？login就加进set,logout就退出set。
【在 s********u 的大作中提到】
: 用linked list+hashmap？如果是当前时刻的话，应该linked list就行了
: 如果是时间段的话，bst应该是可行的。不过代码面试一紧张都不好写。。
|
|
|
p*****2
发帖数: 21240 | 11
应该是多台server吧？用户不一定在同一台server登陆。
【在 l*n 的大作中提到】
: 直接Set就行吧？login就加进set,logout就退出set。
|
s********u
发帖数: 1109 | 12 是的，但是这样的话是无序的，感觉不太符合实际需要。不像list，会自动的将目前在
线的人按照login的时间来顺序排列。
hashmap主要是为了提供O(1)的检索、删除和插入。
【在 l*n 的大作中提到】
: 直接Set就行吧？login就加进set,logout就退出set。
|
p*****2
发帖数: 21240 | 13
题目没有要求排序呀
【在 s********u 的大作中提到】
: 是的，但是这样的话是无序的，感觉不太符合实际需要。不像list，会自动的将目前在
: 线的人按照login的时间来顺序排列。
: hashmap主要是为了提供O(1)的检索、删除和插入。
|
s********u
发帖数: 1109 | 14 所以不太清楚题意。
比如当前时间段是指当前时刻，还是某一段时间。还有就是是否有其他要求。
如果真的是只要数数，那就只要一个int变量，有人login就+1，有人logout就-1.
list和set比起来，是不是多了不少overhead？
【在 p*****2 的大作中提到】
:
: 题目没有要求排序呀
|
g*********e
发帖数: 14401 | 15 大牛 高瞻远瞩 考虑问题已经是条件反射的大数据了
【在 p*****2 的大作中提到】
:
: 题目没有要求排序呀
|
l*n
发帖数: 529 | 16 这无所谓吧，不可能多个机器单独记录一个登陆状态，肯定是有centralized的log，或
者在登陆期间只由登陆了的server提供后续服务。
【在 p*****2 的大作中提到】
:
: 题目没有要求排序呀
|
p*****2
发帖数: 21240 | 17
how about concurrency?
【在 s********u 的大作中提到】
: 所以不太清楚题意。
: 比如当前时间段是指当前时刻，还是某一段时间。还有就是是否有其他要求。
: 如果真的是只要数数，那就只要一个int变量，有人login就+1，有人logout就-1.
: list和set比起来，是不是多了不少overhead？
|
p*****2
发帖数: 21240 | 18
什么架构？登陆server几台？怎么协调？load balancing?
【在 l*n 的大作中提到】
: 这无所谓吧，不可能多个机器单独记录一个登陆状态，肯定是有centralized的log，或
: 者在登陆期间只由登陆了的server提供后续服务。
|
d**********u
发帖数: 3371 | 19 怎么大家都这么爱用hash 上算法课的时候一提到hash professor都想抽你耳光
有个哥们牙都被抽没了
【在 s********u 的大作中提到】
: 用linked list+hashmap？如果是当前时刻的话，应该linked list就行了
: 如果是时间段的话，bst应该是可行的。不过代码面试一紧张都不好写。。
|
d**********u
发帖数: 3371 | 20 完全没看懂题目。。
是分析log还是分析当前时段啊
用户
【在 p*u 的大作中提到】
: 面试官人挺好的，听声音是华人，不过自己表现太烂了，一紧张写代码哆嗦
: 一个题：
: 给一堆用户的login logout日志，当在线用户数变化的时候，输出当前时间段的在线用户
: 算法简单，可是一紧张就写残了。
|
|
|
s********u
发帖数: 1109 | 21 你给我一个o1检索的数据结构我也不用hash啊。何况lru cache最典型的实现就是hash
加list，java有现成的linkedhashmap。乱用就赖不得别人。
【在 d**********u 的大作中提到】
: 怎么大家都这么爱用hash 上算法课的时候一提到hash professor都想抽你耳光
: 有个哥们牙都被抽没了
|
d**********u
发帖数: 3371 | 22 也没有 就是好奇为啥很少有考obst union find之类的题目呢
hash
【在 s********u 的大作中提到】
: 你给我一个o1检索的数据结构我也不用hash啊。何况lru cache最典型的实现就是hash
: 加list，java有现成的linkedhashmap。乱用就赖不得别人。
|
d**********u
发帖数: 3371 | 23 比如我觉得union find也比较适合这个题目啊 amortize o(1) 不过还是得先用size排序
【在 d**********u 的大作中提到】
: 也没有 就是好奇为啥很少有考obst union find之类的题目呢
:
: hash
|
p*****3
发帖数: 488 | 24 啥叫当前时间段在线数???
拿个int，login +1 logout -1不就得了,haha .... |
p*u
发帖数: 136 | 25 #include
#include
#include
using namespace std;
#define INF 0x7fffffff
struct Log
{
int login_time;
int logout_time;
Log(int in, int out): login_time(in), logout_time(out)
{}
};
struct Node
{
int time;
int value;
Node(int t, int v): time(t), value(v)
{}
};
bool cmp(const Node &a, const Node &b)
{
if (a.time != b.time)
return a.time < b.time;
else
return a.value > b.value;
}
void output(int start, int end, int value)
{
printf("[%d - %d): %d\n", start, end, value);
}
void online_user_num(vector &logs)
{
if (logs.empty())
return;
vector f;
for (vector::iterator it = logs.begin(); it != logs.end(); ++it)
{
f.push_back(Node(it->login_time, 0));
f.push_back(Node(it->logout_time, 1));
}
sort(f.begin(), f.end(), cmp);
vector g;
int prev_time = f.begin()->time;
int current_user = 0;
for (vector::iterator it = f.begin(); it != f.end(); ++it)
{
if (it->time != prev_time)
g.push_back(Node(prev_time, current_user));
prev_time = it->time;
current_user += it->value == 0 ? 1 : -1;
}
g.push_back(Node(prev_time, current_user));
int n = g.size();
prev_time = g.begin()->time;
current_user = g.begin()->value;
for (int i = 1; i < n; ++i)
{
if (g[i].value != current_user)
{
output(prev_time, g[i].time, current_user);
prev_time = g[i].time;
current_user = g[i].value;
}
}
output(prev_time, INF, current_user);
}
int main()
{
vector logs;
logs.push_back(Log(0, 1));
logs.push_back(Log(0, 2));
logs.push_back(Log(1, 3));
online_user_num(logs);
return 0;
}
=============
代码中的vector g是可以优化掉的，只是代码写起来稍微复杂点。面试过程中尝
试这样写，结果越写越乱。如果按照上面这个写法，应该可以很快搞定的。 |
l*n
发帖数: 529 | 26 http://stackoverflow.com/questions/17893163/coordinating-shared
http://blog.exceliance.fr/2012/03/29/load-balancing-affinity-pe
或者loadbalancer aware，或者在别处有state share。每个server分别handle同一个
人的不同login是不可能出现的。
【在 p*****2 的大作中提到】
:
: 什么架构？登陆server几台？怎么协调？load balancing?
|
k****s
发帖数: 16 | 27 是我想简单了么。 一个hash table, key 是时间，value是该时间的人数。
输入的时候
遍历每个用户， 把该用户live时间内，所有key对应的value +1。
输出的时候
key区间内所有value的最小值是就是该时间内同时在线人数。 |
t*********7
发帖数: 255 | 28 这个难道不是先按登录时间排序,然后遍历所有的登录信息,看见登录就+1,看见登出就-
1,只要另外用一个数组存下每个时间点的登录人数就行了? |
z****e
发帖数: 54598 | 29 那用什么？hash效率最高
主要是用了hash，下面没得搞了
你不能让人家教授上课没有东西可以讲
【在 d**********u 的大作中提到】
: 怎么大家都这么爱用hash 上算法课的时候一提到hash professor都想抽你耳光
: 有个哥们牙都被抽没了
|
l*n
发帖数: 529 | 30 确实，跟前面有人问的interal题目是一样的。
就-
【在 t*********7 的大作中提到】
: 这个难道不是先按登录时间排序,然后遍历所有的登录信息,看见登录就+1,看见登出就-
: 1,只要另外用一个数组存下每个时间点的登录人数就行了?
|
|
|
l****h
发帖数: 1189 | 31 这个做的很棒。 我用hash做了一个。和这个比起来弱点在不能stream. 如果log是不断
更新的， 这个方法很容易改成实用的工具。
HASH方法：
一个set 记录顺序时间， hash table 记录时间map到index. buckets记录人数。
直接扫描日志，每个过去，把覆盖的 bucket都加1. 如果用户平均在线时间都是有限的
，这个还是O(N)的。如果用户时间当变量M考虑，就是 O(NM)了。这个应该考虑吗？
【在 p*u 的大作中提到】
: #include
: #include
: #include
: using namespace std;
: #define INF 0x7fffffff
: struct Log
: {
: int login_time;
: int logout_time;
: Log(int in, int out): login_time(in), logout_time(out)
|
l****h
发帖数: 1189 | 32 刚刚注意到你就是楼主， 你后来补的code吗？
你能把code写得这么整洁明快，现场还是不能过吗？
【在 l****h 的大作中提到】
: 这个做的很棒。 我用hash做了一个。和这个比起来弱点在不能stream. 如果log是不断
: 更新的， 这个方法很容易改成实用的工具。
: HASH方法：
: 一个set 记录顺序时间， hash table 记录时间map到index. buckets记录人数。
: 直接扫描日志，每个过去，把覆盖的 bucket都加1. 如果用户平均在线时间都是有限的
: ，这个还是O(N)的。如果用户时间当变量M考虑，就是 O(NM)了。这个应该考虑吗？
|
p*****e
发帖数: 537 | 33 这是compiler里经典的interval graph 的题，先把所有时间排序，排的时候如果有tie
就把login的时间放前面。然后scan一遍，login的时候加1，logout的时候减1. FB好像
特别喜欢问这个题啊。 |
p*u
发帖数: 136 | 34 后来补的code
现场写得很烂，想到算法就下笔了，没想清楚代码结构。
【在 l****h 的大作中提到】
: 刚刚注意到你就是楼主， 你后来补的code吗？
: 你能把code写得这么整洁明快，现场还是不能过吗？
|
s********u
发帖数: 1109 | 35 我现在觉得先想好，或者纸上涂画一下很重要。面试因为时间紧，抬笔就写，碰到问题
就是越写越乱啊。
【在 p*u 的大作中提到】
: 后来补的code
: 现场写得很烂，想到算法就下笔了，没想清楚代码结构。
|
c********p
发帖数: 1969 | |
p*u
发帖数: 136 | 37 是的，这样比较好。
我也准备在纸上先画一画的，电话那头的面试官老问“hey, xxx, what are you doing
?”
我就慌了，直接上shared doc上写，越来越乱。
【在 s********u 的大作中提到】
: 我现在觉得先想好，或者纸上涂画一下很重要。面试因为时间紧，抬笔就写，碰到问题
: 就是越写越乱啊。
|
h******n
发帖数: 14 | 38 正确。不过好像没有必要login排前。每个时间点加减后人数如果有变就输出一个
window,不然将window延长到这个时间点
tie
【在 p*****e 的大作中提到】
: 这是compiler里经典的interval graph 的题，先把所有时间排序，排的时候如果有tie
: 就把login的时间放前面。然后scan一遍，login的时候加1，logout的时候减1. FB好像
: 特别喜欢问这个题啊。
|
p****o
发帖数: 46 | 39 void online_user(vector &logs){
if (logs.empty()) return;
map table;
for (vector::const_iterator it = logs.begin();
it != logs.end(); ++it){
table[it->login_time]++;
table[it->logout_time]--;
}
float prev = table.begin()->first;
int num = table.begin()->second;
for (map::const_iterator it = ++table.begin();
it!=table.end(); ++it) {
if (it->second!=0) {
cout << "[" << prev << " - " << it->first << ") : " << num <<
endl;
num += it->second;
prev = it->first;
}
}
cout << "[" << prev << " - " << "infinite) : 0 " << endl;
}
【在 p*u 的大作中提到】
: 是的，这样比较好。
: 我也准备在纸上先画一画的，电话那头的面试官老问“hey, xxx, what are you doing
: ?”
: 我就慌了，直接上shared doc上写，越来越乱。
|
m**p
发帖数: 189 | 40 你这是 n*log(n)。 可以给个O(n)的解法吗？ |
|
|
m**p
发帖数: 189 | 41 your input is O(n^2)
【在 k****s 的大作中提到】
: 是我想简单了么。 一个hash table, key 是时间，value是该时间的人数。
: 输入的时候
: 遍历每个用户， 把该用户live时间内，所有key对应的value +1。
: 输出的时候
: key区间内所有value的最小值是就是该时间内同时在线人数。
|
m**********e
发帖数: 22 | 42 public void OnlineUsers(List intervals)
{
int totalSeconds = 10000;
int[] delta = new int[totalSeconds];
int[] users = new int[totalSeconds];
foreach (Interval inter in intervals)
{
delta[inter.Start]++;
delta[inter.End]--;
}
int i = 1;
users[0] = delta[0];
while (i < totalSeconds)
{
users[i] = users[i - 1] + delta[i];
++i;
}
int currCount = users[0];
int firstIndex = 0;
for (i = 1; i < totalSeconds; ++i)
{
if (users[i] != currCount)
{
Console.Write(firstIndex + " to " + i + ": " + currCount
+ "n");
firstIndex = i;
currCount = users[i];
}
}
}
【在 p*u 的大作中提到】
: 是的，这样比较好。
: 我也准备在纸上先画一画的，电话那头的面试官老问“hey, xxx, what are you doing
: ?”
: 我就慌了，直接上shared doc上写，越来越乱。
|
y****a
发帖数: 15 | 43 楼主是内推的吗？我做了网上的challenge还找人内推过，还是没人通知面试。 |
a**d
发帖数: 85 | 44 static class Log {
int in,out;
Log(int a,int b) {
in=a;
out=b;
}
}
public String log(Log[] l) {
String[] s=new String[2*l.length];
for(int i=0,j=0;i
s[j++]=l[i].in+"i";
s[j++]=l[i].out+"o";
}
Arrays.sort(s);
LinkedHashMap lh=new LinkedHashMap();
int counter=1;
for(int i=1;i
char cur=s[i].charAt(0),pre=s[i-1].charAt(0);
if(cur!=pre) {
lh.put(pre-'0',counter);
}
if(s[i].charAt(1)=='i')
counter++;
else
counter--;
if(i==s.length-1)
lh.put(cur-'0',counter);
}
String result="";
int pre=-1,j=1;
for(int key:lh.keySet()) {
if(pre==-1)
pre=key;
else if(lh.get(key)!=lh.get(pre)) {
result+=pre+"-"+key+":"+lh.get(pre)+" ";
pre=key;
}
if(j==lh.size())
result+=key+"-infinity:"+lh.get(key);
j++;
}
return result;
} |
p*u
发帖数: 136 | 45 给一堆用户的登陆日志，要求输出各时间段内的在线用户数。
例子：
user1:
login_time: 0
logout_time: 1
user2:
login_time: 0
logout_time: 2
user3:
login_time: 1
logout_time: 3
输出：
[0 - 2): 2
[2 - 3): 1
[3 - infinite): 0
0 - 1不用输出，因为时间点0有2个在线用户，时间点1也有2个在线用户，在线用户数
没有变，所以不用输出。在时间点2在线用户数变为1，所以输出0 - 2: 2
完成函数：
struct Log
{
float login_time;
float logout_time;
};
void online_user(vector &logs);
=====
刚开始是一些behavior question，后来就问了这一个题，算法2分钟就沟通好了，可是
后来代码写得很乱，到最后都还有bug
华人面试官，感觉人挺好的。可惜自己脑抽了，一紧张就出错，一出错更紧张，最后就
搞不定了
最后他建议在面fb之前，先找其他公司的面试，练练状态
这种情况挂了只能怪自己，不能埋怨同胞不留情。move on to next
-----
更新下：刚收到thank you letter @2013-10-29 |
z*********8
发帖数: 2070 | |
n****e
发帖数: 678 | 47 是不是用hashmap把login，logout各扫一遍
hashmap的key是用户id，value是timestamp。 |
g*********e
发帖数: 14401 | |
n****e
发帖数: 678 | 49 是不是用hashmap把login，logout各扫一遍
hashmap的key是用户id，value是timestamp。 |
g***9
发帖数: 159 | 50 没有完全理解清楚题目意思....
要问的是能够实时查询当前的在线用户数吗?
这样就得keep当前在线用户数,并根据login logout更新, 提供O(1)查询吧?
如果是lz说的当前时间段, 又是什么意思呢..? |
|
|
s********u
发帖数: 1109 | 51 用linked list+hashmap？如果是当前时刻的话，应该linked list就行了
如果是时间段的话，bst应该是可行的。不过代码面试一紧张都不好写。。 |
b**********5
发帖数: 7881 | 52 不懂。 你linkedlist里面放什么？
【在 s********u 的大作中提到】
: 用linked list+hashmap？如果是当前时刻的话，应该linked list就行了
: 如果是时间段的话，bst应该是可行的。不过代码面试一紧张都不好写。。
|
s********u
发帖数: 1109 | 53 每个node都代表一个人，login就把他插入，login out就把他删除。
当前时刻的人数就是list的size。
好像还是一定要hashmap的，为了找到这个人。他说的log日志应该就像是：
10:16pm 用户id：110 log out
用户id：205 log in
。。。这样
我觉得他应该是这个意思，带点设计的。否则岂不是只要一个变量，有人login就加1，
有人logout就-1？？？？
【在 b**********5 的大作中提到】
: 不懂。 你linkedlist里面放什么？
|
l*n
发帖数: 529 | 54 直接Set就行吧？login就加进set,logout就退出set。
【在 s********u 的大作中提到】
: 用linked list+hashmap？如果是当前时刻的话，应该linked list就行了
: 如果是时间段的话，bst应该是可行的。不过代码面试一紧张都不好写。。
|
p*****2
发帖数: 21240 | 55
应该是多台server吧？用户不一定在同一台server登陆。
【在 l*n 的大作中提到】
: 直接Set就行吧？login就加进set,logout就退出set。
|
s********u
发帖数: 1109 | 56 是的，但是这样的话是无序的，感觉不太符合实际需要。不像list，会自动的将目前在
线的人按照login的时间来顺序排列。
hashmap主要是为了提供O(1)的检索、删除和插入。
【在 l*n 的大作中提到】
: 直接Set就行吧？login就加进set,logout就退出set。
|
p*****2
发帖数: 21240 | 57
题目没有要求排序呀
【在 s********u 的大作中提到】
: 是的，但是这样的话是无序的，感觉不太符合实际需要。不像list，会自动的将目前在
: 线的人按照login的时间来顺序排列。
: hashmap主要是为了提供O(1)的检索、删除和插入。
|
s********u
发帖数: 1109 | 58 所以不太清楚题意。
比如当前时间段是指当前时刻，还是某一段时间。还有就是是否有其他要求。
如果真的是只要数数，那就只要一个int变量，有人login就+1，有人logout就-1.
list和set比起来，是不是多了不少overhead？
【在 p*****2 的大作中提到】
:
: 题目没有要求排序呀
|
g*********e
发帖数: 14401 | 59 大牛 高瞻远瞩 考虑问题已经是条件反射的大数据了
【在 p*****2 的大作中提到】
:
: 题目没有要求排序呀
|
l*n
发帖数: 529 | 60 这无所谓吧，不可能多个机器单独记录一个登陆状态，肯定是有centralized的log，或
者在登陆期间只由登陆了的server提供后续服务。
【在 p*****2 的大作中提到】
:
: 题目没有要求排序呀
|
|
|
p*****2
发帖数: 21240 | 61
how about concurrency?
【在 s********u 的大作中提到】
: 所以不太清楚题意。
: 比如当前时间段是指当前时刻，还是某一段时间。还有就是是否有其他要求。
: 如果真的是只要数数，那就只要一个int变量，有人login就+1，有人logout就-1.
: list和set比起来，是不是多了不少overhead？
|
p*****2
发帖数: 21240 | 62
什么架构？登陆server几台？怎么协调？load balancing?
【在 l*n 的大作中提到】
: 这无所谓吧，不可能多个机器单独记录一个登陆状态，肯定是有centralized的log，或
: 者在登陆期间只由登陆了的server提供后续服务。
|
d**********u
发帖数: 3371 | 63 怎么大家都这么爱用hash 上算法课的时候一提到hash professor都想抽你耳光
有个哥们牙都被抽没了
【在 s********u 的大作中提到】
: 用linked list+hashmap？如果是当前时刻的话，应该linked list就行了
: 如果是时间段的话，bst应该是可行的。不过代码面试一紧张都不好写。。
|
d**********u
发帖数: 3371 | 64 完全没看懂题目。。
是分析log还是分析当前时段啊
用户
【在 p*u 的大作中提到】
: 面试官人挺好的，听声音是华人，不过自己表现太烂了，一紧张写代码哆嗦
: 一个题：
: 给一堆用户的login logout日志，当在线用户数变化的时候，输出当前时间段的在线用户
: 算法简单，可是一紧张就写残了。
|
s********u
发帖数: 1109 | 65 你给我一个o1检索的数据结构我也不用hash啊。何况lru cache最典型的实现就是hash
加list，java有现成的linkedhashmap。乱用就赖不得别人。
【在 d**********u 的大作中提到】
: 怎么大家都这么爱用hash 上算法课的时候一提到hash professor都想抽你耳光
: 有个哥们牙都被抽没了
|
d**********u
发帖数: 3371 | 66 也没有 就是好奇为啥很少有考obst union find之类的题目呢
hash
【在 s********u 的大作中提到】
: 你给我一个o1检索的数据结构我也不用hash啊。何况lru cache最典型的实现就是hash
: 加list，java有现成的linkedhashmap。乱用就赖不得别人。
|
d**********u
发帖数: 3371 | 67 比如我觉得union find也比较适合这个题目啊 amortize o(1) 不过还是得先用size排序
【在 d**********u 的大作中提到】
: 也没有 就是好奇为啥很少有考obst union find之类的题目呢
:
: hash
|
p*****3
发帖数: 488 | 68 啥叫当前时间段在线数???
拿个int，login +1 logout -1不就得了,haha .... |
p*u
发帖数: 136 | 69 #include
#include
#include
using namespace std;
#define INF 0x7fffffff
struct Log
{
int login_time;
int logout_time;
Log(int in, int out): login_time(in), logout_time(out)
{}
};
struct Node
{
int time;
int value;
Node(int t, int v): time(t), value(v)
{}
};
bool cmp(const Node &a, const Node &b)
{
if (a.time != b.time)
return a.time < b.time;
else
return a.value > b.value;
}
void output(int start, int end, int value)
{
printf("[%d - %d): %d\n", start, end, value);
}
void online_user_num(vector &logs)
{
if (logs.empty())
return;
vector f;
for (vector::iterator it = logs.begin(); it != logs.end(); ++it)
{
f.push_back(Node(it->login_time, 0));
f.push_back(Node(it->logout_time, 1));
}
sort(f.begin(), f.end(), cmp);
vector g;
int prev_time = f.begin()->time;
int current_user = 0;
for (vector::iterator it = f.begin(); it != f.end(); ++it)
{
if (it->time != prev_time)
g.push_back(Node(prev_time, current_user));
prev_time = it->time;
current_user += it->value == 0 ? 1 : -1;
}
g.push_back(Node(prev_time, current_user));
int n = g.size();
prev_time = g.begin()->time;
current_user = g.begin()->value;
for (int i = 1; i < n; ++i)
{
if (g[i].value != current_user)
{
output(prev_time, g[i].time, current_user);
prev_time = g[i].time;
current_user = g[i].value;
}
}
output(prev_time, INF, current_user);
}
int main()
{
vector logs;
logs.push_back(Log(0, 1));
logs.push_back(Log(0, 2));
logs.push_back(Log(1, 3));
online_user_num(logs);
return 0;
}
=============
代码中的vector g是可以优化掉的，只是代码写起来稍微复杂点。面试过程中尝
试这样写，结果越写越乱。如果按照上面这个写法，应该可以很快搞定的。 |
l*n
发帖数: 529 | 70 http://stackoverflow.com/questions/17893163/coordinating-shared
http://blog.exceliance.fr/2012/03/29/load-balancing-affinity-pe
或者loadbalancer aware，或者在别处有state share。每个server分别handle同一个
人的不同login是不可能出现的。
【在 p*****2 的大作中提到】
:
: 什么架构？登陆server几台？怎么协调？load balancing?
|
|
|
k****s
发帖数: 16 | 71 是我想简单了么。 一个hash table, key 是时间，value是该时间的人数。
输入的时候
遍历每个用户， 把该用户live时间内，所有key对应的value +1。
输出的时候
key区间内所有value的最小值是就是该时间内同时在线人数。 |
t*********7
发帖数: 255 | 72 这个难道不是先按登录时间排序,然后遍历所有的登录信息,看见登录就+1,看见登出就-
1,只要另外用一个数组存下每个时间点的登录人数就行了? |
z****e
发帖数: 54598 | 73 那用什么？hash效率最高
主要是用了hash，下面没得搞了
你不能让人家教授上课没有东西可以讲
【在 d**********u 的大作中提到】
: 怎么大家都这么爱用hash 上算法课的时候一提到hash professor都想抽你耳光
: 有个哥们牙都被抽没了
|
l*n
发帖数: 529 | 74 确实，跟前面有人问的interal题目是一样的。
就-
【在 t*********7 的大作中提到】
: 这个难道不是先按登录时间排序,然后遍历所有的登录信息,看见登录就+1,看见登出就-
: 1,只要另外用一个数组存下每个时间点的登录人数就行了?
|
l****h
发帖数: 1189 | 75 这个做的很棒。 我用hash做了一个。和这个比起来弱点在不能stream. 如果log是不断
更新的， 这个方法很容易改成实用的工具。
HASH方法：
一个set 记录顺序时间， hash table 记录时间map到index. buckets记录人数。
直接扫描日志，每个过去，把覆盖的 bucket都加1. 如果用户平均在线时间都是有限的
，这个还是O(N)的。如果用户时间当变量M考虑，就是 O(NM)了。这个应该考虑吗？
【在 p*u 的大作中提到】
: #include
: #include
: #include
: using namespace std;
: #define INF 0x7fffffff
: struct Log
: {
: int login_time;
: int logout_time;
: Log(int in, int out): login_time(in), logout_time(out)
|
l****h
发帖数: 1189 | 76 刚刚注意到你就是楼主， 你后来补的code吗？
你能把code写得这么整洁明快，现场还是不能过吗？
【在 l****h 的大作中提到】
: 这个做的很棒。 我用hash做了一个。和这个比起来弱点在不能stream. 如果log是不断
: 更新的， 这个方法很容易改成实用的工具。
: HASH方法：
: 一个set 记录顺序时间， hash table 记录时间map到index. buckets记录人数。
: 直接扫描日志，每个过去，把覆盖的 bucket都加1. 如果用户平均在线时间都是有限的
: ，这个还是O(N)的。如果用户时间当变量M考虑，就是 O(NM)了。这个应该考虑吗？
|
p*****e
发帖数: 537 | 77 这是compiler里经典的interval graph 的题，先把所有时间排序，排的时候如果有tie
就把login的时间放前面。然后scan一遍，login的时候加1，logout的时候减1. FB好像
特别喜欢问这个题啊。 |
p*u
发帖数: 136 | 78 后来补的code
现场写得很烂，想到算法就下笔了，没想清楚代码结构。
【在 l****h 的大作中提到】
: 刚刚注意到你就是楼主， 你后来补的code吗？
: 你能把code写得这么整洁明快，现场还是不能过吗？
|
s********u
发帖数: 1109 | 79 我现在觉得先想好，或者纸上涂画一下很重要。面试因为时间紧，抬笔就写，碰到问题
就是越写越乱啊。
【在 p*u 的大作中提到】
: 后来补的code
: 现场写得很烂，想到算法就下笔了，没想清楚代码结构。
|
c********p
发帖数: 1969 | |
|
|
p*u
发帖数: 136 | 81 是的，这样比较好。
我也准备在纸上先画一画的，电话那头的面试官老问“hey, xxx, what are you doing
?”
我就慌了，直接上shared doc上写，越来越乱。
【在 s********u 的大作中提到】
: 我现在觉得先想好，或者纸上涂画一下很重要。面试因为时间紧，抬笔就写，碰到问题
: 就是越写越乱啊。
|
h******n
发帖数: 14 | 82 正确。不过好像没有必要login排前。每个时间点加减后人数如果有变就输出一个
window,不然将window延长到这个时间点
tie
【在 p*****e 的大作中提到】
: 这是compiler里经典的interval graph 的题，先把所有时间排序，排的时候如果有tie
: 就把login的时间放前面。然后scan一遍，login的时候加1，logout的时候减1. FB好像
: 特别喜欢问这个题啊。
|
p****o
发帖数: 46 | 83 void online_user(vector &logs){
if (logs.empty()) return;
map table;
for (vector::const_iterator it = logs.begin();
it != logs.end(); ++it){
table[it->login_time]++;
table[it->logout_time]--;
}
float prev = table.begin()->first;
int num = table.begin()->second;
for (map::const_iterator it = ++table.begin();
it!=table.end(); ++it) {
if (it->second!=0) {
cout << "[" << prev << " - " << it->first << ") : " << num <<
endl;
num += it->second;
prev = it->first;
}
}
cout << "[" << prev << " - " << "infinite) : 0 " << endl;
}
【在 p*u 的大作中提到】
: 给一堆用户的登陆日志，要求输出各时间段内的在线用户数。
: 例子：
: user1:
: login_time: 0
: logout_time: 1
: user2:
: login_time: 0
: logout_time: 2
: user3:
: login_time: 1
|
m**p
发帖数: 189 | 84 你这是 n*log(n)。 可以给个O(n)的解法吗？ |
m**p
发帖数: 189 | 85 your input is O(n^2)
【在 k****s 的大作中提到】
: 是我想简单了么。 一个hash table, key 是时间，value是该时间的人数。
: 输入的时候
: 遍历每个用户， 把该用户live时间内，所有key对应的value +1。
: 输出的时候
: key区间内所有value的最小值是就是该时间内同时在线人数。
|
m**********e
发帖数: 22 | 86 public void OnlineUsers(List intervals)
{
int totalSeconds = 10000;
int[] delta = new int[totalSeconds];
int[] users = new int[totalSeconds];
foreach (Interval inter in intervals)
{
delta[inter.Start]++;
delta[inter.End]--;
}
int i = 1;
users[0] = delta[0];
while (i < totalSeconds)
{
users[i] = users[i - 1] + delta[i];
++i;
}
int currCount = users[0];
int firstIndex = 0;
for (i = 1; i < totalSeconds; ++i)
{
if (users[i] != currCount)
{
Console.Write(firstIndex + " to " + i + ": " + currCount
+ "n");
firstIndex = i;
currCount = users[i];
}
}
}
【在 p*u 的大作中提到】
: 给一堆用户的登陆日志，要求输出各时间段内的在线用户数。
: 例子：
: user1:
: login_time: 0
: logout_time: 1
: user2:
: login_time: 0
: logout_time: 2
: user3:
: login_time: 1
|
y****a
发帖数: 15 | 87 楼主是内推的吗？我做了网上的challenge还找人内推过，还是没人通知面试。 |
a**d
发帖数: 85 | 88 static class Log {
int in,out;
Log(int a,int b) {
in=a;
out=b;
}
}
public String log(Log[] l) {
String[] s=new String[2*l.length];
for(int i=0,j=0;i
s[j++]=l[i].in+"i";
s[j++]=l[i].out+"o";
}
Arrays.sort(s);
LinkedHashMap lh=new LinkedHashMap();
int counter=1;
for(int i=1;i
char cur=s[i].charAt(0),pre=s[i-1].charAt(0);
if(cur!=pre) {
lh.put(pre-'0',counter);
}
if(s[i].charAt(1)=='i')
counter++;
else
counter--;
if(i==s.length-1)
lh.put(cur-'0',counter);
}
String result="";
int pre=-1,j=1;
for(int key:lh.keySet()) {
if(pre==-1)
pre=key;
else if(lh.get(key)!=lh.get(pre)) {
result+=pre+"-"+key+":"+lh.get(pre)+" ";
pre=key;
}
if(j==lh.size())
result+=key+"-infinity:"+lh.get(key);
j++;
}
return result;
} |
y****a
发帖数: 15 | 89 我倒是觉得要正确分段的话，样本的输出应该是
［0-1］2
［1-3］1
［3-infinity］0
这样的
具体做法是：
1. 把数据拆开，分成in&out两种。
2. 拆开后的数据按照时间排序。
3. 一个hashtable，相应的时间点in的＋1，out－1。
4. merge数值相同且时间上相邻的点，变成例如｛［0］：2，［1，2］：1，［3］：0｝
5. 输出每段相邻的边界作为时间段，［0-1］，［1-3］，［3-infinity］ |
r**********o
发帖数: 50 | 90 亲！ 这题在你们做呀？ 是有点比较容易乱。。。
【在 p*u 的大作中提到】
: 给一堆用户的登陆日志，要求输出各时间段内的在线用户数。
: 例子：
: user1:
: login_time: 0
: logout_time: 1
: user2:
: login_time: 0
: logout_time: 2
: user3:
: login_time: 1
|
|
|
D**********d
发帖数: 849 | 91 void online_user(vector &logs){
map m;
for(int i = 0; i < logs.size(); ++i){
m[logs[i].login_time] += 1;
m[logs[i].logout_time] -= 1;
}
int c = 0, pi = 0;
for(auto i:m){
if(i->second == 0) continue;
if(i->first != ip) cout <<'[' << pi << '-' << "):" << p << endl;
p+= i->second; pi = i;
}
} |
f********4
发帖数: 988 | 92 好评点赞！！！
我把所有楼层都看了，这是我最喜欢的解法了，撒花~~
【在 p****o 的大作中提到】
: void online_user(vector &logs){
: if (logs.empty()) return;
: map table;
: for (vector::const_iterator it = logs.begin();
: it != logs.end(); ++it){
: table[it->login_time]++;
: table[it->logout_time]--;
: }
: float prev = table.begin()->first;
: int num = table.begin()->second;
|
g*********e
发帖数: 14401 | 93 首先得排序
【在 p*****3 的大作中提到】
: 啥叫当前时间段在线数???
: 拿个int，login +1 logout -1不就得了,haha ....
|
i*********o
发帖数: 52 | 94 感觉是分析一个log然后输出各个时段的在线人数？
求大神指点代码（小弟新手，感觉自己用了太多变量和if判断，是不是理解错了？）
public void online_user(Log[] input)
{
//state is used to store last sec's online user.
//timer is last secs.
//end is used to check if all user is offline.
int time=0,end=0,state=0,timer=0;
LinkedList s = new LinkedList();
while(end
{
for(temp : input)
{
if(temp.login_time ==time) s.add(temp);
if(temp.logout_time == time)
{
s.remove(temp);
end++;
}
}
if(state==0 && timer==0){
state = s.size();
timer++;
}
if(s.size() == state)
timer++;
else{ //when the online user number changes, print the time range
and reset state and timer.
print("["+(time-timer)+"~"+time+"):"+state);
state = s.size();
timer=0;
}
//increase time by 1 sec.
++time;
}
//output the infinite time.
print(time+"->infinite : 0");
} |
e***s
发帖数: 799 | 95 顶大牛完美答案！
【在 p****o 的大作中提到】
: void online_user(vector &logs){
: if (logs.empty()) return;
: map table;
: for (vector::const_iterator it = logs.begin();
: it != logs.end(); ++it){
: table[it->login_time]++;
: table[it->logout_time]--;
: }
: float prev = table.begin()->first;
: int num = table.begin()->second;
|
s********u
发帖数: 1109 | 96 昨天想了下，想到可以用hashtable，然后table[n] += table[n-1]来把增量转换成总
量。其实用array可能就可以，不过如果是float的，就不得不用map。
才看到大牛已经写了这种思路了。而且非常简洁，赞！
【在 D**********d 的大作中提到】
: void online_user(vector &logs){
: map m;
: for(int i = 0; i < logs.size(); ++i){
: m[logs[i].login_time] += 1;
: m[logs[i].logout_time] -= 1;
: }
: int c = 0, pi = 0;
: for(auto i:m){
: if(i->second == 0) continue;
: if(i->first != ip) cout <<'[' << pi << '-' << "):" << p << endl;
|
b*******e
发帖数: 123 | 97 赞。
【在 D**********d 的大作中提到】
: void online_user(vector &logs){
: map m;
: for(int i = 0; i < logs.size(); ++i){
: m[logs[i].login_time] += 1;
: m[logs[i].logout_time] -= 1;
: }
: int c = 0, pi = 0;
: for(auto i:m){
: if(i->second == 0) continue;
: if(i->first != ip) cout <<'[' << pi << '-' << "):" << p << endl;
|
l*n
发帖数: 529 | 98 ？用map在这里不是leverage sorting功能吗？array自己sort？
【在 s********u 的大作中提到】
: 昨天想了下，想到可以用hashtable，然后table[n] += table[n-1]来把增量转换成总
: 量。其实用array可能就可以，不过如果是float的，就不得不用map。
: 才看到大牛已经写了这种思路了。而且非常简洁，赞！
|
s********u
发帖数: 1109 | 99 如果时间段比较密集，用array就可以实现这个功能吧？从0到1，从1到2.。。
【在 l*n 的大作中提到】
: ？用map在这里不是leverage sorting功能吗？array自己sort？
|
f********4
发帖数: 988 | 100 增量转化总量就N方了吧
而且就算很密集，但只要出现一个很大的时间点，array中就会出现大量的浪费
【在 s********u 的大作中提到】
: 昨天想了下，想到可以用hashtable，然后table[n] += table[n-1]来把增量转换成总
: 量。其实用array可能就可以，不过如果是float的，就不得不用map。
: 才看到大牛已经写了这种思路了。而且非常简洁，赞！
|
|
|
c********p
发帖数: 1969 | |
y****a
发帖数: 15 | 102 我倒是觉得要正确分段的话，样本的输出应该是
［0-1］2
［1-3］1
［3-infinity］0
这样的
具体做法是：
1. 把数据拆开，分成in&out两种。
2. 拆开后的数据按照时间排序。
3. 一个hashtable，相应的时间点in的＋1，out－1。
4. merge数值相同且时间上相邻的点，变成例如｛［0］：2，［1，2］：1，［3］：0｝
5. 输出每段相邻的边界作为时间段，［0-1］，［1-3］，［3-infinity］ |
r**********o
发帖数: 50 | 103 亲！ 这题在你们做呀？ 是有点比较容易乱。。。
【在 p*u 的大作中提到】
: 给一堆用户的登陆日志，要求输出各时间段内的在线用户数。
: 例子：
: user1:
: login_time: 0
: logout_time: 1
: user2:
: login_time: 0
: logout_time: 2
: user3:
: login_time: 1
|
D**********d
发帖数: 849 | 104 void online_user(vector &logs){
map m;
for(int i = 0; i < logs.size(); ++i){
m[logs[i].login_time] += 1;
m[logs[i].logout_time] -= 1;
}
int c = 0, pi = 0;
for(auto i:m){
if(i->second == 0) continue;
if(i->first != ip) cout <<'[' << pi << '-' << "):" << p << endl;
p+= i->second; pi = i;
}
} |
f********4
发帖数: 988 | 105 好评点赞！！！
我把所有楼层都看了，这是我最喜欢的解法了，撒花~~
【在 p****o 的大作中提到】
: void online_user(vector &logs){
: if (logs.empty()) return;
: map table;
: for (vector::const_iterator it = logs.begin();
: it != logs.end(); ++it){
: table[it->login_time]++;
: table[it->logout_time]--;
: }
: float prev = table.begin()->first;
: int num = table.begin()->second;
|
g*********e
发帖数: 14401 | 106 首先得排序
【在 p*****3 的大作中提到】
: 啥叫当前时间段在线数???
: 拿个int，login +1 logout -1不就得了,haha ....
|
i*********o
发帖数: 52 | 107 感觉是分析一个log然后输出各个时段的在线人数？
求大神指点代码（小弟新手，感觉自己用了太多变量和if判断，是不是理解错了？）
public void online_user(Log[] input)
{
//state is used to store last sec's online user.
//timer is last secs.
//end is used to check if all user is offline.
int time=0,end=0,state=0,timer=0;
LinkedList s = new LinkedList();
while(end
{
for(temp : input)
{
if(temp.login_time ==time) s.add(temp);
if(temp.logout_time == time)
{
s.remove(temp);
end++;
}
}
if(state==0 && timer==0){
state = s.size();
timer++;
}
if(s.size() == state)
timer++;
else{ //when the online user number changes, print the time range
and reset state and timer.
print("["+(time-timer)+"~"+time+"):"+state);
state = s.size();
timer=0;
}
//increase time by 1 sec.
++time;
}
//output the infinite time.
print(time+"->infinite : 0");
} |
e***s
发帖数: 799 | 108 顶大牛完美答案！
【在 p****o 的大作中提到】
: void online_user(vector &logs){
: if (logs.empty()) return;
: map table;
: for (vector::const_iterator it = logs.begin();
: it != logs.end(); ++it){
: table[it->login_time]++;
: table[it->logout_time]--;
: }
: float prev = table.begin()->first;
: int num = table.begin()->second;
|
s********u
发帖数: 1109 | 109 昨天想了下，想到可以用hashtable，然后table[n] += table[n-1]来把增量转换成总
量。其实用array可能就可以，不过如果是float的，就不得不用map。
才看到大牛已经写了这种思路了。而且非常简洁，赞！
【在 D**********d 的大作中提到】
: void online_user(vector &logs){
: map m;
: for(int i = 0; i < logs.size(); ++i){
: m[logs[i].login_time] += 1;
: m[logs[i].logout_time] -= 1;
: }
: int c = 0, pi = 0;
: for(auto i:m){
: if(i->second == 0) continue;
: if(i->first != ip) cout <<'[' << pi << '-' << "):" << p << endl;
|
b*******e
发帖数: 123 | 110 赞。
【在 D**********d 的大作中提到】
: void online_user(vector &logs){
: map m;
: for(int i = 0; i < logs.size(); ++i){
: m[logs[i].login_time] += 1;
: m[logs[i].logout_time] -= 1;
: }
: int c = 0, pi = 0;
: for(auto i:m){
: if(i->second == 0) continue;
: if(i->first != ip) cout <<'[' << pi << '-' << "):" << p << endl;
|
|
|
l*n
发帖数: 529 | 111 ？用map在这里不是leverage sorting功能吗？array自己sort？
【在 s********u 的大作中提到】
: 昨天想了下，想到可以用hashtable，然后table[n] += table[n-1]来把增量转换成总
: 量。其实用array可能就可以，不过如果是float的，就不得不用map。
: 才看到大牛已经写了这种思路了。而且非常简洁，赞！
|
s********u
发帖数: 1109 | 112 如果时间段比较密集，用array就可以实现这个功能吧？从0到1，从1到2.。。
【在 l*n 的大作中提到】
: ？用map在这里不是leverage sorting功能吗？array自己sort？
|
f********4
发帖数: 988 | 113 增量转化总量就N方了吧
而且就算很密集，但只要出现一个很大的时间点，array中就会出现大量的浪费
【在 s********u 的大作中提到】
: 昨天想了下，想到可以用hashtable，然后table[n] += table[n-1]来把增量转换成总
: 量。其实用array可能就可以，不过如果是float的，就不得不用map。
: 才看到大牛已经写了这种思路了。而且非常简洁，赞！
|
c********p
发帖数: 1969 | |
b*****i
发帖数: 130 | 115 请问这道题有人写过java的解法么？
写了半天还是写不对。。
【在 c********p 的大作中提到】
: mark
|
m*******g
发帖数: 410 | |
