一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 482|回复: 10
收起左侧

一道snapchat onsite题

[复制链接] |试试Instant~ |关注本帖
304671127 发表于 2016-11-15 05:51:52 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Snapchat - 内推 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
例子是给你两个文件 文件里内容大概是node1(这是文件名 不是文件内容)
2014-10-19 13:37:48.717 Snapchat[12345:1234567] Something something Foo.
2014-10-19 13:38:50.200 Snapchat[12345:1234567] Something something Bar.
2014-10-19 13:38:51.392 Snapchat[12345:1234567] Something something Baz..鏈枃鍘熷垱鑷1point3acres璁哄潧
.1point3acres缃

node2(这是文件名 不是文件内容)
2014-10-19 13:38:01.454 Snapchat[12345:7654321] Something something Foo2.
2014-10-19 13:38:02.600 Snapchat[12345:7654321] Something something Bar2.
2014-10-19 13:38:50.201 Snapchat[12345:7654321] Something something Baz2.

输出一个文件是按照给你的时间从小到大排序,外加前面每个一行加上文件名和空格 告诉你这一行来自的文件
要求输入是stream 就是不单单只是两个文件  这里两个只是例子
io不熟悉 求大神写一个给我吧。. more info on 1point3acres.com



bbmbill 发表于 2016-11-15 10:27:18 | 显示全部楼层
就是输出是一行文件名,一行数据,一行文件名,一行数据这样?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
上面的例子就是:
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.鏈枃鍘熷垱鑷1point3acres璁哄潧
2014-10-19 13:38:51.392 Snapchat[12345:1234567] Something something Baz
-google 1point3acres
这样?
那文件名本身如何告诉你啊?
回复 支持 反对

使用道具 举报

 楼主| 304671127 发表于 2016-11-15 13:53:57 | 显示全部楼层
bbmbill 发表于 2016-11-15 10:27
就是输出是一行文件名,一行数据,一行文件名,一行数据这样?
上面的例子就是:
node1

不 文件名和数据在同一行:
node1 2014-10-19 13:37:48.717 Snapchat[12345:1234567] Something something Foo.
.1point3acres缃node2 2014-10-19 13:38:01.454 Snapchat[12345:7654321] Something something Foo2. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
输出到一个新文件里面
写出来望po一下
回复 支持 反对

使用道具 举报

yangmyfly 发表于 2016-11-15 13:58:56 | 显示全部楼层
就是merge two sorted list吧,但是要同时操作两个文件流
回复 支持 反对

使用道具 举报

 楼主| 304671127 发表于 2016-11-15 14:09:17 | 显示全部楼层
yangmyfly 发表于 2016-11-15 13:58
就是merge two sorted list吧,但是要同时操作两个文件流
-google 1point3acres
没错,文件有很多的话其实就是merge k sorted list。 其实我是知道的  但我面跪了就懒得再写了  但又想知道怎么写的。。所以在这求一下答案
回复 支持 反对

使用道具 举报

yangmyfly 发表于 2016-11-15 14:16:02 | 显示全部楼层
304671127 发表于 2016-11-15 14:09
没错,文件有很多的话其实就是merge k sorted list。 其实我是知道的  但我面跪了就懒得再写了  但又想知 ...

不同语言不一样吧。。不过大同小异,我想请教下楼主用的啥语言被考了这个?. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2016-11-15 14:18):
我面的时候面试官都说的是可以简化,没必要实现文件操作。。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

补充内容 (2016-11-15 14:22):
不过不是这题。。。
回复 支持 反对

使用道具 举报

freemail165 发表于 2016-11-16 00:18:00 | 显示全部楼层
yangmyfly 发表于 2016-11-15 14:16
不同语言不一样吧。。不过大同小异,我想请教下楼主用的啥语言被考了这个?

. From 1point 3acres bbs补充内容 (2016-11-15 14:18 ...

人家没问语法,问的是逻辑. From 1point 3acres bbs
这个题说起来简单写起来还真有些麻烦。。。
回复 支持 反对

使用道具 举报

bbmbill 发表于 2016-11-16 01:56:29 | 显示全部楼层
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[]读进来和读出去,就看个方法就是了。
代码如有问题,还望大神指正。. 鍥磋鎴戜滑@1point 3 acres

代码如下:

        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这样,不知道是否可行。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-16 01:59:53 | 显示全部楼层
就是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. 鍥磋鎴戜滑@1point 3 acres
  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. void sortChatFiles(vector<string>& filenames, string outfilename) {
  13.   priority_queue<ChatRecord, vector<ChatRecord>, ChatComp> pq; // min heap to sort records. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.   unordered_map<string, std::ifstream> infiles; string line; // a line from a file stream
  15.   for (auto& fn : filenames) { // initialize infiles and pq
  16.     if (getline(infiles[fn] = std::ifstream(fn), line)) pq.emplace(fn, line);
  17.   }
  18.   std::ofstream outfile; outfile.open(outfilename);
  19.   while (!pq.empty()) {
  20.     auto record = pq.top(); pq.pop(); // get and remove earliest record
  21.     outfile << record.first + " " + record.second << endl;
  22.     if (getline(infiles[record.first], line)) pq.emplace(record.first, line);
  23.   }
  24.   outfile.close();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  25. }
复制代码

补充内容 (2016-11-16 03:08):.1point3acres缃
若排序定义是先比较日期时间,再序列号,再内容的话,可以简化直接比较 s1>s2
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-16 03:05:55 | 显示全部楼层
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++.
回复 支持 反对

使用道具 举报

 楼主| 304671127 发表于 2016-11-16 03:30:55 | 显示全部楼层
yangmyfly 发表于 2016-11-15 14:16
不同语言不一样吧。。不过大同小异,我想请教下楼主用的啥语言被考了这个?.鐣欏璁哄潧-涓浜-涓夊垎鍦

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

我面试时候就是要求我实现文件操作 不然我也不会写不出来
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 11:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表