boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 出两道题目大家做做
相关主题
请教fackbook一道题
问道常见题目 clicks in last 60 seconds
问个Facebook 电面题
新鲜G面筋(Fail)
讨论一道面试题
F家题请教
请教一道interval的题目
分享今天做的一道基础题
OnSite经验交流
急问以下问题(信用卡公司-风险管理职位)
相关话题的讨论汇总
话题: event话题: int话题: events话题: end话题: list
进入JobHunting版参与讨论
1 (共1页)
g****y
发帖数: 240
1
就不说哪些公司的了,签了NDA怕有麻烦。其中两道挺有意思的。
1. give a list of events in the following structure. Set the conflict flag
to true if the event conflicts with any other event in the list.
class Event
{
int start;
int end;
bool conflict;
}
2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序
的。输出这个国家的语言的字母顺序。
l*****a
发帖数: 14598
2
你们单位那么好,怎么都跑出来面试

【在 g****y 的大作中提到】
: 就不说哪些公司的了,签了NDA怕有麻烦。其中两道挺有意思的。
: 1. give a list of events in the following structure. Set the conflict flag
: to true if the event conflicts with any other event in the list.
: class Event
: {
: int start;
: int end;
: bool conflict;
: }
: 2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序

b****e
发帖数: 45
3
第一题interval tree可以做。
第二题先根据字母顺序关系建有向图,然后用topological sorting。不知道有没有更
简单的办法。

【在 g****y 的大作中提到】
: 就不说哪些公司的了,签了NDA怕有麻烦。其中两道挺有意思的。
: 1. give a list of events in the following structure. Set the conflict flag
: to true if the event conflicts with any other event in the list.
: class Event
: {
: int start;
: int end;
: bool conflict;
: }
: 2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序

l*******b
发帖数: 2586
4
第二个和昨天的部分比较排序类似?

【在 g****y 的大作中提到】
: 就不说哪些公司的了,签了NDA怕有麻烦。其中两道挺有意思的。
: 1. give a list of events in the following structure. Set the conflict flag
: to true if the event conflicts with any other event in the list.
: class Event
: {
: int start;
: int end;
: bool conflict;
: }
: 2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序

e****e
发帖数: 418
5
Just my 2 cents.
1. Build an interval tree. for each event, check if its start and end are in
direct parent-child relationship. If yes, no conflict for this event.
2. Use a java.util.TreeSet.
for each entry in dict
treeSet.add(entry.firstCharacter).
print out treeSet.
b****e
发帖数: 45
6
光看每一个词的第一个字符不能保证字符集的完整性吧。

in

【在 e****e 的大作中提到】
: Just my 2 cents.
: 1. Build an interval tree. for each event, check if its start and end are in
: direct parent-child relationship. If yes, no conflict for this event.
: 2. Use a java.util.TreeSet.
: for each entry in dict
: treeSet.add(entry.firstCharacter).
: print out treeSet.

l*******b
发帖数: 2586
7
万一有的字母不做开头怎么办

in

【在 e****e 的大作中提到】
: Just my 2 cents.
: 1. Build an interval tree. for each event, check if its start and end are in
: direct parent-child relationship. If yes, no conflict for this event.
: 2. Use a java.util.TreeSet.
: for each entry in dict
: treeSet.add(entry.firstCharacter).
: print out treeSet.

l*****a
发帖数: 14598
8

in
2.
abc
acc
bbc

【在 e****e 的大作中提到】
: Just my 2 cents.
: 1. Build an interval tree. for each event, check if its start and end are in
: direct parent-child relationship. If yes, no conflict for this event.
: 2. Use a java.util.TreeSet.
: for each entry in dict
: treeSet.add(entry.firstCharacter).
: print out treeSet.

g****y
发帖数: 240
9
你咋知道我是哪个厂的。。。。

【在 l*****a 的大作中提到】
: 你们单位那么好,怎么都跑出来面试
g****y
发帖数: 240
10
具体说说怎么根据字母顺序建图?难点在这里。

【在 b****e 的大作中提到】
: 第一题interval tree可以做。
: 第二题先根据字母顺序关系建有向图,然后用topological sorting。不知道有没有更
: 简单的办法。

相关主题
新鲜G面筋(Fail)
讨论一道面试题
F家题请教
请教一道interval的题目
进入JobHunting版参与讨论
g****y
发帖数: 240
11
不太了解interval tree。说说复杂度是多少?
第二个题。。没有这么简单。说不定有的字母没有出现在单词的首字母中

in

【在 e****e 的大作中提到】
: Just my 2 cents.
: 1. Build an interval tree. for each event, check if its start and end are in
: direct parent-child relationship. If yes, no conflict for this event.
: 2. Use a java.util.TreeSet.
: for each entry in dict
: treeSet.add(entry.firstCharacter).
: print out treeSet.

p*****2
发帖数: 21240
12

两两比较,直到只剩一个入度为0, 并且所有字母都包括了。

【在 g****y 的大作中提到】
: 具体说说怎么根据字母顺序建图?难点在这里。
l*****a
发帖数: 14598
13
能,WA的

【在 g****y 的大作中提到】
: 你咋知道我是哪个厂的。。。。
g****y
发帖数: 240
14
two爷太牛了。当时就是开始的时候没有想到两两比较,结果卡在那里了。不过后半句
不对,因为你不知道字母的个数是多少。

【在 p*****2 的大作中提到】
:
: 两两比较,直到只剩一个入度为0, 并且所有字母都包括了。

g****y
发帖数: 240
15
好吧。。。。厂里不好混了,出来看看。你也是WA的?

【在 l*****a 的大作中提到】
: 能,WA的
l*****a
发帖数: 14598
16
不是,想去你们那里,好多牛人在那里
听说工资高,税少,房子便宜,还都是知名厂家

【在 g****y 的大作中提到】
: 好吧。。。。厂里不好混了,出来看看。你也是WA的?
p*****2
发帖数: 21240
17

因为你不知道字母的个数是多少。
这个不可能吧?什么语言的字母数是动态的?

【在 g****y 的大作中提到】
: two爷太牛了。当时就是开始的时候没有想到两两比较,结果卡在那里了。不过后半句
: 不对,因为你不知道字母的个数是多少。

e****e
发帖数: 418
18
I guess it's n*lg(n) to build it. for each lookup, it's lg(n). The total
running time is n*lg(n)
http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22inter
Topo sort should be the way to go for Q2.

【在 g****y 的大作中提到】
: 不太了解interval tree。说说复杂度是多少?
: 第二个题。。没有这么简单。说不定有的字母没有出现在单词的首字母中
:
: in

p*****2
发帖数: 21240
19

那先排序在查找也是nlogn

【在 e****e 的大作中提到】
: I guess it's n*lg(n) to build it. for each lookup, it's lg(n). The total
: running time is n*lg(n)
: http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22inter
: Topo sort should be the way to go for Q2.

g****y
发帖数: 240
20
工资高就算了。房子便宜倒是真的。

【在 l*****a 的大作中提到】
: 不是,想去你们那里,好多牛人在那里
: 听说工资高,税少,房子便宜,还都是知名厂家

相关主题
分享今天做的一道基础题
OnSite经验交流
急问以下问题(信用卡公司-风险管理职位)
Cisco onsite 后 两周无结果
进入JobHunting版参与讨论
g****y
发帖数: 240
21
这个。。。。你假设你不知道是什么语言。

【在 p*****2 的大作中提到】
:
: 那先排序在查找也是nlogn

d*********g
发帖数: 154
22
不太了解interval tree。第一题这样做行么?
1,按start排序(O(nlogn))
2,遍历list,对list[i]来说,如果list[i].end > list[i+1].start,那么list[i].
conflict=true;或者如果list[0]到list[i-1]中end的最大值(endMax)是在list[i].
start到list[i].end之间的,那么list[i].conflict=true;然后更新endMax,++i。(O
(n))
g****y
发帖数: 240
23
第一题有没有不需要用interval tree,比较老少咸宜的解法?
e****e
发帖数: 418
24
You're right. Building the tree is 排序. Lookup the node is 查找. They are
essentially the same.

【在 p*****2 的大作中提到】
:
: 那先排序在查找也是nlogn

g****y
发帖数: 240
25
不对。试试这个【1,9】,【2,3】,【4,5】

].
(O

【在 d*********g 的大作中提到】
: 不太了解interval tree。第一题这样做行么?
: 1,按start排序(O(nlogn))
: 2,遍历list,对list[i]来说,如果list[i].end > list[i+1].start,那么list[i].
: conflict=true;或者如果list[0]到list[i-1]中end的最大值(endMax)是在list[i].
: start到list[i].end之间的,那么list[i].conflict=true;然后更新endMax,++i。(O
: (n))

d*********g
发帖数: 154
26

把endMax 在list[i].start和list[i].end之间的判断改成 endMax > list[i].end 应
该就对了吧?

【在 g****y 的大作中提到】
: 不对。试试这个【1,9】,【2,3】,【4,5】
:
: ].
: (O

g****y
发帖数: 240
27
改成ENDMAX > list[i].begin?

【在 d*********g 的大作中提到】
:
: 把endMax 在list[i].start和list[i].end之间的判断改成 endMax > list[i].end 应
: 该就对了吧?

d*********g
发帖数: 154
28

嗯,你说的这个对~

【在 g****y 的大作中提到】
: 改成ENDMAX > list[i].begin?
i*******e
发帖数: 240
29
第2题好像有问题,如果一本字典只有2个单词,比如:
ab
c
那我怎么知道c的顺序是在b之前还是之后。
原来我的想法是:
能不能从后往前读,并且每个单词也是从后往前读字母,如果第一次读到该字母
则输入,否则继续
好像也不对
l*****a
发帖数: 14598
30
假定给你足够信息吧

【在 i*******e 的大作中提到】
: 第2题好像有问题,如果一本字典只有2个单词,比如:
: ab
: c
: 那我怎么知道c的顺序是在b之前还是之后。
: 原来我的想法是:
: 能不能从后往前读,并且每个单词也是从后往前读字母,如果第一次读到该字母
: 则输入,否则继续
: 好像也不对

相关主题
怎么知道哪个大公司有校招呢?
有人收到AMD 的6/26 的 hiring event 吗?
Amazon直接on-site,奇怪吗?
Amazon Philadelphia Interview Event
进入JobHunting版参与讨论
p*****2
发帖数: 21240
31

sort就可以了。

【在 g****y 的大作中提到】
: 第一题有没有不需要用interval tree,比较老少咸宜的解法?
r*********n
发帖数: 4553
32
Q1:
I'm not familiar with interval tree. But I think you can solve it in the
following way:
put all start times in an array and sort it to get an array of indices with
increasing start times (the value of this array is the index, not the start
time)
similarly build an array of indices with increasing order of end times.
walk through the two arrays, if the values of the two arrays at the same
position are the same, that event is conflict free and mark it false. Mark
all other events true.
complexity O(nlogn)

【在 g****y 的大作中提到】
: 就不说哪些公司的了,签了NDA怕有麻烦。其中两道挺有意思的。
: 1. give a list of events in the following structure. Set the conflict flag
: to true if the event conflicts with any other event in the list.
: class Event
: {
: int start;
: int end;
: bool conflict;
: }
: 2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序

r*********n
发帖数: 4553
33
for Q2, I think an assumption has to be made, that is the alphabet is known.
otherwise, all words in the dictionary need be examined.
d******e
发帖数: 164
34
Q2 Revised:
class Graph:
def __init__(self):
self.out_edges = {}
self.in_degrees = {}
def add_vertex(self, v):
if v not in self.out_edges:
self.out_edges[v] = []
self.in_degrees[v] = 0
def add_edge(self, v_out, v_in):
if v_in not in self.out_edges[v_out]:
self.out_edges[v_out].append(v_in)
self.in_degrees[v_in] += 1
def process_words(cur_word, next_word, graph):
for i in xrange(min(len(cur_word), len(next_word))):
if cur_word[i] != next_word[i]:
graph.add_vertex(cur_word[i])
graph.add_vertex(next_word[i])
graph.add_edge(cur_word[i], next_word[i])
break
def process_dictionary(dictionary):
graph = Graph()
for i in xrange(len(dictionary) - 1):
process_words(dictionary[i], dictionary[i+1], graph)
topological_sort(graph)
def topological_sort(graph):
head = [v for v in graph.out_edges if graph.in_degrees[v] == 0]
if len(head) == 1:
print head[0],
for v in graph.out_edges[head[0]]:
graph.in_degrees[v] -= 1
del graph.out_edges[head[0]]
topological_sort(graph)
if __name__ == '__main__':
dictionary = ['ab', 'ac', 'bc', 'bd']
process_dictionary(dictionary)

【在 g****y 的大作中提到】
: 就不说哪些公司的了,签了NDA怕有麻烦。其中两道挺有意思的。
: 1. give a list of events in the following structure. Set the conflict flag
: to true if the event conflicts with any other event in the list.
: class Event
: {
: int start;
: int end;
: bool conflict;
: }
: 2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序

g****y
发帖数: 240
35
你那个process_dictionary funciton里面,只需要考虑两个相邻的word就可以了。没
必要挨个考虑。例如:ab ac ad 只需要考虑ab ac和ac ad就好了,没必要考虑ab ad。

【在 d******e 的大作中提到】
: Q2 Revised:
: class Graph:
: def __init__(self):
: self.out_edges = {}
: self.in_degrees = {}
: def add_vertex(self, v):
: if v not in self.out_edges:
: self.out_edges[v] = []
: self.in_degrees[v] = 0
: def add_edge(self, v_out, v_in):

g****y
发帖数: 240
36
then check all words.

known.

【在 r*********n 的大作中提到】
: for Q2, I think an assumption has to be made, that is the alphabet is known.
: otherwise, all words in the dictionary need be examined.

g****y
发帖数: 240
37
不对。对于一个event a,如果在其开始之前有k个events开始,在其结束之前有k个
events结束,并不代表这个event a没有conflict。下面一个反例:
[1,9] [6,7] [5,8]

with
start

【在 r*********n 的大作中提到】
: Q1:
: I'm not familiar with interval tree. But I think you can solve it in the
: following way:
: put all start times in an array and sort it to get an array of indices with
: increasing start times (the value of this array is the index, not the start
: time)
: similarly build an array of indices with increasing order of end times.
: walk through the two arrays, if the values of the two arrays at the same
: position are the same, that event is conflict free and mark it false. Mark
: all other events true.

p*****2
发帖数: 21240
38

我准备做做这题,你给几个test case好吗?

【在 g****y 的大作中提到】
: 不对。对于一个event a,如果在其开始之前有k个events开始,在其结束之前有k个
: events结束,并不代表这个event a没有conflict。下面一个反例:
: [1,9] [6,7] [5,8]
:
: with
: start

p*****2
发帖数: 21240
39

那你只能全扫一遍了。不过这个复杂度太高了。

【在 g****y 的大作中提到】
: 这个。。。。你假设你不知道是什么语言。
g****y
发帖数: 240
40
我也都是现想的test case,没有现成的。

【在 p*****2 的大作中提到】
:
: 那你只能全扫一遍了。不过这个复杂度太高了。

相关主题
今天晚上Microsoft Event有谁去吗?
问道流行题目
M家的hiring event
Amazon: Networking/Hiring Event in Santa Clara (got from LinkedIn message)
进入JobHunting版参与讨论
g****y
发帖数: 240
41
也不高, linear的。dictionary不一定包含所有的单词,我只是举了例子。你可以把
它看成list of string。

【在 g****y 的大作中提到】
: 我也都是现想的test case,没有现成的。
p*****2
发帖数: 21240
42

看看这个对不
void setEvents(ArrayList al)
{
Collections.sort(al);
int max=Integer.MIN_VALUE;

for(int i=0;i {
Event e=al.get(i);
if(e.start<=max)
e.conflict=true;
max=Math.max(max, e.end);
}

int min=Integer.MAX_VALUE;

for(int i=al.size()-1;i>=0;i--)
{
Event e=al.get(i);
if(e.end>=min)
e.conflict=true;
min=Math.min(min, e.start);
}
}

【在 g****y 的大作中提到】
: 我也都是现想的test case,没有现成的。
g****y
发帖数: 240
43
第二个for loop是干什么的?感觉只用第一个for loop就可以了,不过要记录一下
event with the maximum end time, 然后每次后面有start time小于maximum end
time的event,就把两个都设成conflict。

【在 p*****2 的大作中提到】
:
: 看看这个对不
: void setEvents(ArrayList al)
: {
: Collections.sort(al);
: int max=Integer.MIN_VALUE;
:
: for(int i=0;i: {
: Event e=al.get(i);

c****m
发帖数: 11
44
同球test case
写了一个,思想是这样的:
按照start 排序,取出当前的element(cur),然后往后check每个element(next),
如果next的end是小于cur.end,说明next这个是被cur完全cover的;直到找到一个next
的end是大于cur.end,这样我们就可以更新cur了,直到遍历完。有点类似于蠕虫爬行
一样。
感觉虽然有两个loop,但是每个Event应该只比较了一次,遍历这块应该还是O(n)的吧
?当然sort的时候是O(nlgN).不知道这样对不对?一直在潜水,求指点,谢谢
int main()
{
Event e1(1, 9);
Event e2(2, 3);
Event e3(4, 5);
vector lVec;
lVec.push_back(e1);
lVec.push_back(e3);
lVec.push_back(e2);
std::sort(lVec.begin(), lVec.end());
int start = 0;
int end = 0;
std::vector::iterator pos = lVec.begin();
for(int i = 0;i < lVec.size(); )
{
start = lVec[i].start;
end = lVec[i].end;
int j = i + 1;
for(; j < lVec.size(); j++)
{
if (lVec[j].end < end)
{
lVec[j].conflict = true;
lVec[i].conflict = true;
}
else
break;
}
if ( j != lVec.size())
{
if (lVec[j].start < start)
{
lVec[j].conflict = true;
lVec[i].conflict = true;
}
}
// update i to next undetermined index
i = j;
}
}【 在 gnahzy (hello) 的大作中提到: 】
p*****2
发帖数: 21240
45

后边的可能跟前边所有的都有overlap

【在 g****y 的大作中提到】
: 第二个for loop是干什么的?感觉只用第一个for loop就可以了,不过要记录一下
: event with the maximum end time, 然后每次后面有start time小于maximum end
: time的event,就把两个都设成conflict。

t**r
发帖数: 3428
46
this one seems good :)

,
next

【在 c****m 的大作中提到】
: 同球test case
: 写了一个,思想是这样的:
: 按照start 排序,取出当前的element(cur),然后往后check每个element(next),
: 如果next的end是小于cur.end,说明next这个是被cur完全cover的;直到找到一个next
: 的end是大于cur.end,这样我们就可以更新cur了,直到遍历完。有点类似于蠕虫爬行
: 一样。
: 感觉虽然有两个loop,但是每个Event应该只比较了一次,遍历这块应该还是O(n)的吧
: ?当然sort的时候是O(nlgN).不知道这样对不对?一直在潜水,求指点,谢谢
: int main()
: {

a****l
发帖数: 8211
47
第二题很有意思。一般来说,一个字典每部分的第一词就是那个开始字母。如果是词不
全的字典,那么就没有底线了,极端的情况是只有一个词,无解。

【在 g****y 的大作中提到】
: 就不说哪些公司的了,签了NDA怕有麻烦。其中两道挺有意思的。
: 1. give a list of events in the following structure. Set the conflict flag
: to true if the event conflicts with any other event in the list.
: class Event
: {
: int start;
: int end;
: bool conflict;
: }
: 2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序

g*******r
发帖数: 44
48
你这个思想是对的,但是感觉程序有问题,在跳出以后
if (lVec[j].start < start)
应该改成
if (lVec[j].start < end)
吧?

,
next

【在 c****m 的大作中提到】
: 同球test case
: 写了一个,思想是这样的:
: 按照start 排序,取出当前的element(cur),然后往后check每个element(next),
: 如果next的end是小于cur.end,说明next这个是被cur完全cover的;直到找到一个next
: 的end是大于cur.end,这样我们就可以更新cur了,直到遍历完。有点类似于蠕虫爬行
: 一样。
: 感觉虽然有两个loop,但是每个Event应该只比较了一次,遍历这块应该还是O(n)的吧
: ?当然sort的时候是O(nlgN).不知道这样对不对?一直在潜水,求指点,谢谢
: int main()
: {

Y********f
发帖数: 410
49
思路不错,练习了一下,去掉了双重循环
void eventConfl2(vector& events)
{
sort(events.begin(), events.end());
int end = events[0].end;
int frontIdx = 0;
for (int i = 1; i < events.size(); i++)
{
if (events[i].start < end)
{
events[frontIdx].conflict = true;
events[i].conflict = true;
if (events[i].end > end)
end = events[i].end;
}
else
{
frontIdx = i;
end = events[i].end;
}
}
}

,
next

【在 c****m 的大作中提到】
: 同球test case
: 写了一个,思想是这样的:
: 按照start 排序,取出当前的element(cur),然后往后check每个element(next),
: 如果next的end是小于cur.end,说明next这个是被cur完全cover的;直到找到一个next
: 的end是大于cur.end,这样我们就可以更新cur了,直到遍历完。有点类似于蠕虫爬行
: 一样。
: 感觉虽然有两个loop,但是每个Event应该只比较了一次,遍历这块应该还是O(n)的吧
: ?当然sort的时候是O(nlgN).不知道这样对不对?一直在潜水,求指点,谢谢
: int main()
: {

e***s
发帖数: 799
50
我也贴一个第一题,不知道对不对。
public static void setConflictEvent(ArrayList list){
Collections.sort(list);
Event temp = new Event(list.get(0).start, list.get(0).end, list.get(
0).conflict);

for(int i = 1; i < list.size(); i++)
{
if(temp.end > list.get(i).start)
{
list.get(i - 1).conflict = true;
list.get(i).conflict = true;

temp.end = Math.max(temp.end, list.get(i).end);
}
else
{
temp.start = list.get(i).start;
temp.end = list.get(i).end;
}
}
}
相关主题
请教fackbook一道题
问道常见题目 clicks in last 60 seconds
问个Facebook 电面题
新鲜G面筋(Fail)
进入JobHunting版参与讨论
w****x
发帖数: 2483
51
第一题不需要build interval tree那么麻烦吧, 把所有结点部分启始还是结束混在一
起排序, 然后扫描一遍, n=0, 遇到开始端点 n++, 遇到结束端点 n--, 遇到开始端
点的时候如果n > 0设置那个开始端点对应的线段conflict flag为true
l*******b
发帖数: 2586
52
得扫两遍吧,一次按开始端点升序排序,扫开始端点在不在之前的区间里,只要保持之
前的区间的结束端点的max就行
第二遍,按结束端点降序排序。扫结束端点在之前的区间里,保持之前区间的开始端点
的min就行。
又想了下,一遍够了。

【在 w****x 的大作中提到】
: 第一题不需要build interval tree那么麻烦吧, 把所有结点部分启始还是结束混在一
: 起排序, 然后扫描一遍, n=0, 遇到开始端点 n++, 遇到结束端点 n--, 遇到开始端
: 点的时候如果n > 0设置那个开始端点对应的线段conflict flag为true

c********t
发帖数: 5706
53
问题相当的严重
【1,3】【1,3】【1,3】
w****x
发帖数: 2483
54

struct EVENT
{
int nStart;
int nEnd;
bool bFlg;
EVENT(int a, int b) : nStart(a), nEnd(b) { bFlg = false; }
};
struct ENDPOINT
{
int nIndex;
bool bStart;
int nVal;
};
bool lessThan(const ENDPOINT& ed1, const ENDPOINT& ed2)
{
return ed1.nVal < ed2.nVal;
}
void setFlg(EVENT events[], int n)
{
if (events == NULL || n <= 0)
return;
ENDPOINT* ends = new ENDPOINT[n*2];
for (int i = 0; i < n; i++)
{
ends[2*i].bStart = true;
ends[2*i].nIndex = i;
ends[2*i].nVal = events[i].nStart;
ends[2*i+1].bStart = false;
ends[2*i+1].nIndex = i;
ends[2*i+1].nVal = events[i].nEnd;
}
std::sort(ends, ends+2*n, lessThan);
int nCount = 0;
for (int i = 0; i < 2*n; i++)
{
if (ends[i].bStart)
{
if (nCount > 0)
events[ends[i].nIndex].bFlg = true;
nCount++;
}
else
{
nCount--;
if (nCount > 0)
events[ends[i].nIndex].bFlg = true;
else if (!ends[i-1].bStart)
events[ends[i].nIndex].bFlg = true;
}
}
delete []ends;
}
void test()
{
EVENT events[] = {EVENT(1, 3), EVENT(2, 7), EVENT(4, 5), EVENT(6, 8),
EVENT(9, 10), EVENT(11, 12), EVENT(13, 16), EVENT(14, 15)};
setFlg(events, sizeof(events)/sizeof(EVENT));
}

【在 l*******b 的大作中提到】
: 得扫两遍吧,一次按开始端点升序排序,扫开始端点在不在之前的区间里,只要保持之
: 前的区间的结束端点的max就行
: 第二遍,按结束端点降序排序。扫结束端点在之前的区间里,保持之前区间的开始端点
: 的min就行。
: 又想了下,一遍够了。

w****x
发帖数: 2483
55

我加了一段end的判断逻辑, 就是在end后平衡再check一下当前这段是否为全部cover
的情况, 比如 [1, 15]全部cover[2,3] [5,7], 除了这种情况以一定会有一种不平衡
的状态出现

【在 c********t 的大作中提到】
: 问题相当的严重
: 【1,3】【1,3】【1,3】

c********t
发帖数: 5706
56
好像可以,感觉只有你和二爷正确,我开始的想法和lucky一样,也是错的。

【在 w****x 的大作中提到】
:
: 我加了一段end的判断逻辑, 就是在end后平衡再check一下当前这段是否为全部cover
: 的情况, 比如 [1, 15]全部cover[2,3] [5,7], 除了这种情况以一定会有一种不平衡
: 的状态出现

l**h
发帖数: 893
57
good idea.
一个Loop就够了。
我开始准备建立一个BST来查,虽然也是nlogn, 但是不如你这个简单。

,
next

【在 c****m 的大作中提到】
: 同球test case
: 写了一个,思想是这样的:
: 按照start 排序,取出当前的element(cur),然后往后check每个element(next),
: 如果next的end是小于cur.end,说明next这个是被cur完全cover的;直到找到一个next
: 的end是大于cur.end,这样我们就可以更新cur了,直到遍历完。有点类似于蠕虫爬行
: 一样。
: 感觉虽然有两个loop,但是每个Event应该只比较了一次,遍历这块应该还是O(n)的吧
: ?当然sort的时候是O(nlgN).不知道这样对不对?一直在潜水,求指点,谢谢
: int main()
: {

l*******b
发帖数: 2586
58
测了下,貌似没问题呀,感觉和merge interval哪个题一样
#include
#include
#include
using namespace std;
struct Interval {
int a;
int b;
bool cf;
Interval() : a(0), b(0), cf(false) {}
Interval(int start, int end) : a(start), b(end), cf(false) {}
};
bool compare(const Interval &s, const Interval &t) {
return s.a < t.a;
}
class Play {
public:
void setflag(vector &list) {
/* same idea as merge intervals, when intervals merge, they conflict
*/
sort(list.begin(), list.end(), compare);
int i = 0, n = list.size();
while(i < n) {
int m = list[i].b;
int j = i + 1;
while(j < n && list[j].a <= m) {
m = max(m, list[j].b);
list[j].cf = true;
++j;
}
if(j != i + 1) //化简了一下
list[i].cf = true;
i = j;
}
}
}
void printEvents(vector &list) {
int n = list.size();
for(int i = 0; i < n; ++i) {
cout << list[i].a << " " << list[i].b
<< (list[i].cf ? " Yes" : " ") << endl;
}
}
};
int main() {
Play pp;
vector l;
int s, t;
while(cin >> s) {
cin >> t;
Interval ev(s,t);
l.push_back(ev);
}
pp.setflag(l);
pp.printEvents(l);

return 0;
}
c********t
发帖数: 5706
59
test case [1,3][4,6][2,5] 能都设为conflict吗?

【在 l*******b 的大作中提到】
: 测了下,貌似没问题呀,感觉和merge interval哪个题一样
: #include
: #include
: #include
: using namespace std;
: struct Interval {
: int a;
: int b;
: bool cf;
: Interval() : a(0), b(0), cf(false) {}

w****x
发帖数: 2483
60

为啥要扫第二次? 谁帮我看看下面这个解法对不对!
struct EVENT
{
int nStart;
int nEnd;
bool bFlg;
EVENT(int a, int b) : nStart(a), nEnd(b) { bFlg = false; }
};
bool lessThan(const EVENT& evt1, const EVENT& evt2)
{
return evt1.nStart < evt2.nStart;
}
void setFlg(EVENT events[], int n)
{
sort(events, events+n, lessThan);
int nMaxEndIndex = 0;
for (int i = 1; i < n; i++)
{
if (events[i].nStart <= events[nMaxEndIndex].nEnd)
{
events[i].bFlg = true;
events[nMaxEndIndex].bFlg = true;
}
if (events[i].nEnd >= events[nMaxEndIndex].nEnd)
nMaxEndIndex = i;
}
}

【在 p*****2 的大作中提到】
:
: 后边的可能跟前边所有的都有overlap

相关主题
新鲜G面筋(Fail)
讨论一道面试题
F家题请教
请教一道interval的题目
进入JobHunting版参与讨论
o***d
发帖数: 313
61
惭愧的说,第二题我以前onsite见过,本行业的一个公司(不说名字了,估计很少有人去面
试),一个烙印,出了n多的算法题,其中一道就是这个.提示了半天,我也没有搞定,完全不
灵光....到现在我也不知道他希望我怎么做.

【在 g****y 的大作中提到】
: 就不说哪些公司的了,签了NDA怕有麻烦。其中两道挺有意思的。
: 1. give a list of events in the following structure. Set the conflict flag
: to true if the event conflicts with any other event in the list.
: class Event
: {
: int start;
: int end;
: bool conflict;
: }
: 2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序

l*****a
发帖数: 14598
62
除了你的ctor长的有点奇怪外,应该没什么问题

【在 w****x 的大作中提到】
:
: 为啥要扫第二次? 谁帮我看看下面这个解法对不对!
: struct EVENT
: {
: int nStart;
: int nEnd;
: bool bFlg;
: EVENT(int a, int b) : nStart(a), nEnd(b) { bFlg = false; }
: };
: bool lessThan(const EVENT& evt1, const EVENT& evt2)

l*******b
发帖数: 2586
63
测了下可以

【在 c********t 的大作中提到】
: test case [1,3][4,6][2,5] 能都设为conflict吗?
c********t
发帖数: 5706
64
哦,那我错了,我开始想的是对的,被2爷带歪了。2爷第二个for loop看来是不需要的。

【在 l*******b 的大作中提到】
: 测了下可以
o***d
发帖数: 313
65
???二爷的是 O(lg(n))+2n,你的是O(lg(n))+n^2阿,我看错了么?

【在 l*******b 的大作中提到】
: 测了下可以
l*******b
发帖数: 2586
66
都是n log n + n,是两个循环,但是每个元素实际上只走一遍。

【在 o***d 的大作中提到】
: ???二爷的是 O(lg(n))+2n,你的是O(lg(n))+n^2阿,我看错了么?
o***d
发帖数: 313
67
???我看的不仔细?
你们的
loop(i=1...n)
loop(i+1...n)
这样每次一个i=1: n steps
i=2: n-1 steps
i=3: n-2 steps
totally: n+(n-1)+(n-2)....+1 = O(n^2)阿

【在 l*******b 的大作中提到】
: 都是n log n + n,是两个循环,但是每个元素实际上只走一遍。
l*******b
发帖数: 2586
68
j < n && list[j].a <= m
j < n这个是虚的,保证不越界
后面 i = j,下个循环就从 j走起了不是 i + 1
1 ... n 分别由i 和 j 走一段一段,不走全程的

【在 o***d 的大作中提到】
: ???我看的不仔细?
: 你们的
: loop(i=1...n)
: loop(i+1...n)
: 这样每次一个i=1: n steps
: i=2: n-1 steps
: i=3: n-2 steps
: totally: n+(n-1)+(n-2)....+1 = O(n^2)阿

o***d
发帖数: 313
69
sorry,没有仔细看你们的程序,刚才仔细看了下,没错的.

【在 l*******b 的大作中提到】
: j < n && list[j].a <= m
: j < n这个是虚的,保证不越界
: 后面 i = j,下个循环就从 j走起了不是 i + 1
: 1 ... n 分别由i 和 j 走一段一段,不走全程的

l*******b
发帖数: 2586
70
没,还是逻辑写得不够清晰。不容易写好呀

【在 o***d 的大作中提到】
: sorry,没有仔细看你们的程序,刚才仔细看了下,没错的.
1 (共1页)
进入JobHunting版参与讨论
相关主题
急问以下问题(信用卡公司-风险管理职位)
Cisco onsite 后 两周无结果
怎么知道哪个大公司有校招呢?
有人收到AMD 的6/26 的 hiring event 吗?
Amazon直接on-site,奇怪吗?
Amazon Philadelphia Interview Event
今天晚上Microsoft Event有谁去吗?
问道流行题目
M家的hiring event
Amazon: Networking/Hiring Event in Santa Clara (got from LinkedIn message)
相关话题的讨论汇总
话题: event话题: int话题: events话题: end话题: list