一道snapchat onsite题

例子是给你两个文件 文件里内容大概是node1（这是文件名 不是文件内容）
2014-10-19 13:37:48.717 Snapchat[12345:1234567] Something something Foo.
2014-10-19 13:38:50.200 Snapchat[12345:1234567] Somethi

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

排序，外加前面每个一行加上文件名和空格 告诉你这一行来自的文件
要求输入是stream 就是不单单只是两个文件  这里两个只是例子
io不熟悉 求大神写一个给我吧。

就是输出是一行文件名，一行数据，一行文件名，一行数据这样？
上面的例子就是：
node1
2014-10-19 13:37:48.717 Snapchat[12345:1234567] Something something Foo.
node2
2014-10-19 13:38:01.454 Snapchat[12345:7654321] Something something Foo2..
node2
2014-10-19 13:38:02.600 Snapchat[12345:7654321] Something something Bar2.
node1
2014-10-19 13:38:50.200 Snapchat[12345:1234567] Something something Bar.
node2
2014-10-19 13:38:50.201 Snapchat[12345:7654321] Something something Baz2.
node1
2014-10-19 13:38:51.392 Snapchat[12345:1234567] Something something Baz

这样？
那文件名本身如何告诉你啊？

bbmbill 发表于 2016-11-15 10:27
就是输出是一行文件名，一行数据，一行文件名，一行数据这样？
上面的例子就是：
node1

不 文件名和数据在同一行：
node1 2014-10-19 13:37:48.717 Snapchat[12345:1234567] Something something Foo.
node2 2014-10-19 13:38:01.454 Snapchat[12345:7654321] Something something Foo2
输出到一个新文件里面
写出来望po一下

就是merge two sorted list吧，但是要同时操作两个文件流

yangmyfly 发表于 2016-11-15 13:58
就是merge two sorted list吧，但是要同时操作两个文件流

没错，文件有很多的话其实就是merge k sorted list。 其实我是知道的  但我面跪了就懒得再写了  但又想知道怎么写的。。所以在这求一下答案

304671127 发表于 2016-11-15 14:09
没错，文件有很多的话其实就是merge k sorted list。 其实我是知道的  但我面跪了就懒得再写了  但又想知 ...

不同语言不一样吧。。不过大同小异，我想请教下楼主用的啥语言被考了这个？

补充内容 (2016-11-15 14:18):
我面的时候面试官都说的是可以简化，没必要实现文件操作。。。

补充内容 (2016-11-15 14:22):
不过不是这题。。。

yangmyfly 发表于 2016-11-15 14:16
不同语言不一样吧。。不过大同小异，我想请教下楼主用的啥语言被考了这个？

补充内容 (2016-11-15 14:18 ...

人家没问语法，问的是逻辑
这个题说起来简单写起来还真有些麻烦。。。

304671127 发表于 2016-11-15 13:53
不 文件名和数据在同一行：
node1 2014-10-19 13:37:48.717 Snapchat[12345:1234567] Something somethi ...

写了点代码，这题这题其实不难，印象中Leetcode有原题。方便测试就没用System.in和System.out，直接用String[]读进来和读出去，就看个方法就是了。
代码如有问题，还望大神指正。

代码如下：

        public String[] sort(String[] file1, String[] file2) {

               

                // border case

                if(file1 == null || file1.length == 0) return file2;

                if(file2 == null || file2.length == 0) return file1;

               

                // initialization

                int current = 0;

                int current1 = 0;

                int current2 = 0;

                String file1Name = "node1";

                String file2Name = "node2";

                String[] result = new String[file1.length + file2.length];

               

                // sort two files

                Arrays.sort(file1);

                Arrays.sort(file2);

               

                // start merge

                while(current1 < file1.length && current2 < file2.length) {

                        if(file1[current1].compareTo(file2[current2]) < 0) {

                                result[current++] = file1Name + " " + file1[current1++];

                        } else {

                                result[current++] = file2Name + " " + file2[current2++];

                        }

                }

                // add remain logs

                if(current1 == file1.length) {

                        while(current2 < file2.length) {

                                result[current++] = file2Name + " " + file2[current2++];

                        }

                } else {

                        while(current1 < file1.length) {

                                result[current++] = file1Name + " " + file1[current1++];

                        }

                }

                return result;

        }

}

补充内容 (2016-11-16 01:58):
文件Stream的话我觉得可以放入PriorityQueue，然后每次poll出最小的String这样，不知道是否可行。

就是sort k sorted list。我用C++, 就是用std::ifstream读每个文件，用getline(ifstream, line)读一行string，最后用std::ofstream将排序的写到outputfile里。用priority_queue对记录的时间排序，我的排序定义是先比较日期时间，再序列号，再内容（假设每个记录都是严格format好的）。若不是这个顺序定义可稍微改动comparator struct ChatComp, 不影响实现。

1. typedef pair<string, string> ChatRecord; // pair(filename, chat record line)
   
2. struct ChatComp { // comparator of chat records
   
3.   string dateTime(string& s) { return s.substr(0, 23); } // 1st priority
   
4.   string serial(string& s) { return s.substr(34, 46); }  // 2nd priority
   
5.   string content(string& s) { return s.substr(49); }     // 3rd priority
   
6.   bool operator ()(ChatRecord& r1, ChatRecord& r2) { // define r1 ">" r2
   
7.     string s1(r1.second), s2(r2.second);
   
8.     return dateTime(s1) > dateTime(s2) || (dateTime(s1) == dateTime(s2)) && serial(s1) > serial(s2) ||
   
9.       (dateTime(s1) == dateTime(s2)) && (serial(s1) == serial(s2)) && content(s1) > content(s2);
   
10.   }
    
11. };
    
12. 
    
13. void sortChatFiles(vector<string>& filenames, string outfilename) {
    
14.   priority_queue<ChatRecord, vector<ChatRecord>, ChatComp> pq; // min heap to sort records
    
15.   unordered_map<string, std::ifstream> infiles; string line; // a line from a file stream
    
16.   for (auto& fn : filenames) { // initialize infiles and pq
    
17.     if (getline(infiles[fn] = std::ifstream(fn), line)) pq.emplace(fn, line);
    
18.   }
    
19.   std::ofstream outfile; outfile.open(outfilename);
    
20.   while (!pq.empty()) {
    
21.     auto record = pq.top(); pq.pop(); // get and remove earliest record
    
22.     outfile << record.first + " " + record.second << endl;
    
23.     if (getline(infiles[record.first], line)) pq.emplace(record.first, line);
    
24.   }
    
25.   outfile.close();
    
26. }

复制代码

补充内容 (2016-11-16 03:08):
若排序定义是先比较日期时间，再序列号，再内容的话，可以简化直接比较 s1>s2

bbmbill 发表于 2016-11-16 01:56
写了点代码，这题这题其实不难，印象中Leetcode有原题。方便测试就没用System.in和System.out，直接用Str ...

Code没问题。我觉得这个题的意思是说每个文件的string应该是排序好的，然后用priority_queue做就有意义。尤其在实际情况中文件都很大不能把任何单独文件的全部行strings全部放到内存中的时候。用priority_queue时用stream每次只读一个文件的一行，同时在内存上的最大耗费只有O(k) (k=文件个数)。每次将priority_queue的top string立即写到output file中。我写了个general case在第9层C++.