h*****7
发帖数: 60 | 1 面试的人问了一些基础问题然后丢下这么一道让我写好发给他，也不知是写得比较慢还
是说有bug什么的，电面一轮一周多没下文应该是挂了吧？不过倒是可以讨论下这道题。
一般的树（几个child都可以），节点存的是string，string里面可以包括任何可以打
印出来的字符包括换行。要求将其序列化为csv文件还有反序列化。
我的做法是BFS，除了写csv之外再写一个header，里面记录每层有几个元素，每个元素
的string分别是多长。这个解法也是受本版某位牛人某篇回复的启发。读序列的时候就
两个文件配合。不知有没有更优的解法？
不知A会电面一面就挂人吗？快两周没消息了。 |
p*****2
发帖数: 21240 | |
l***i
发帖数: 1309 | |
l*********8
发帖数: 4642 | 4 trie tree层次遍历吧？
题。
【在 h*****7 的大作中提到】
: 面试的人问了一些基础问题然后丢下这么一道让我写好发给他，也不知是写得比较慢还
: 是说有bug什么的，电面一轮一周多没下文应该是挂了吧？不过倒是可以讨论下这道题。
: 一般的树（几个child都可以），节点存的是string，string里面可以包括任何可以打
: 印出来的字符包括换行。要求将其序列化为csv文件还有反序列化。
: 我的做法是BFS，除了写csv之外再写一个header，里面记录每层有几个元素，每个元素
: 的string分别是多长。这个解法也是受本版某位牛人某篇回复的启发。读序列的时候就
: 两个文件配合。不知有没有更优的解法？
: 不知A会电面一面就挂人吗？快两周没消息了。
|
p*****2
发帖数: 21240 | 5
哪里看出来是trie？
【在 l*********8 的大作中提到】
: trie tree层次遍历吧？
:
: 题。
|
l*********8
发帖数: 4642 | 6 "一般的树（几个child都可以），节点存的是string", 这就暗示是trie tree吧？
【在 p*****2 的大作中提到】
:
: 哪里看出来是trie？
|
p*****2
发帖数: 21240 | 7
trie节点寸的是character吧？
【在 l*********8 的大作中提到】
: "一般的树（几个child都可以），节点存的是string", 这就暗示是trie tree吧？
|
o***d
发帖数: 313 | 8 让你写了多久?
题。
【在 h*****7 的大作中提到】
: 面试的人问了一些基础问题然后丢下这么一道让我写好发给他，也不知是写得比较慢还
: 是说有bug什么的，电面一轮一周多没下文应该是挂了吧？不过倒是可以讨论下这道题。
: 一般的树（几个child都可以），节点存的是string，string里面可以包括任何可以打
: 印出来的字符包括换行。要求将其序列化为csv文件还有反序列化。
: 我的做法是BFS，除了写csv之外再写一个header，里面记录每层有几个元素，每个元素
: 的string分别是多长。这个解法也是受本版某位牛人某篇回复的启发。读序列的时候就
: 两个文件配合。不知有没有更优的解法？
: 不知A会电面一面就挂人吗？快两周没消息了。
|
l*********8
发帖数: 4642 | 9 我怀疑面试官的意思是：每个leaf节点代表一个字符串。
【在 p*****2 的大作中提到】
:
: trie节点寸的是character吧？
|
k***a
发帖数: 1199 | 10 csv每行记录节点string,和其孩子们所在的行
内存序列化到文件类似问题的关键就是怎么用文件来记录指针,指针其实就是个位置,对
csv文件来说行数就可以当指针
碰到这样的问题就是bonus
题。
【在 h*****7 的大作中提到】
: 面试的人问了一些基础问题然后丢下这么一道让我写好发给他，也不知是写得比较慢还
: 是说有bug什么的，电面一轮一周多没下文应该是挂了吧？不过倒是可以讨论下这道题。
: 一般的树（几个child都可以），节点存的是string，string里面可以包括任何可以打
: 印出来的字符包括换行。要求将其序列化为csv文件还有反序列化。
: 我的做法是BFS，除了写csv之外再写一个header，里面记录每层有几个元素，每个元素
: 的string分别是多长。这个解法也是受本版某位牛人某篇回复的启发。读序列的时候就
: 两个文件配合。不知有没有更优的解法？
: 不知A会电面一面就挂人吗？快两周没消息了。
|
|
|
h*****7
发帖数: 60 | 11 我跟他确认了， 是每个节点存了一个string, 不是trie
我写了前前后后3个小时，包括辅助函数包括注释能有200多行吧，一看时间用太久也就
发给他了，头疼的要死也没写unit test。感觉就是要玩我啊。
【在 l*********8 的大作中提到】
: 我怀疑面试官的意思是：每个leaf节点代表一个字符串。
|
h*****7
发帖数: 60 | 12 因为string可以包括换行符，所以不能用换行来分别吧
【在 k***a 的大作中提到】
: csv每行记录节点string,和其孩子们所在的行
: 内存序列化到文件类似问题的关键就是怎么用文件来记录指针,指针其实就是个位置,对
: csv文件来说行数就可以当指针
: 碰到这样的问题就是bonus
:
: 题。
|
k***a
发帖数: 1199 | 13 没搞懂,换行在csv field中是必须转义的......弄个csv的lib,都给你处理好了
置,对
【在 h*****7 的大作中提到】
: 因为string可以包括换行符，所以不能用换行来分别吧
|
h*****7
发帖数: 60 | 14 原来如此，我也觉得这个有点怪，原来是自己不了解。
【在 k***a 的大作中提到】
: 没搞懂,换行在csv field中是必须转义的......弄个csv的lib,都给你处理好了
:
: 置,对
|
p*****2
发帖数: 21240 | 15
如果csv可以解决这个了。
那么一层存一行不久行了吗？做BFS。
【在 k***a 的大作中提到】
: 没搞懂,换行在csv field中是必须转义的......弄个csv的lib,都给你处理好了
:
: 置,对
|
h*****7
发帖数: 60 | 16 就算是一层存一行，怎么知道怎么分隔呢？理论上没法光凭csv的逗号判断也无法自己
插入任何分隔符，因为什么字符都可以包含
【在 p*****2 的大作中提到】
:
: 如果csv可以解决这个了。
: 那么一层存一行不久行了吗？做BFS。
|
o***d
发帖数: 313 | 17 个人觉得3个小时太久了,宁可1个小时写个大概,然后跟他说一下剩余的case的idea就好
了.
我自己猜阿....
【在 h*****7 的大作中提到】
: 我跟他确认了， 是每个节点存了一个string, 不是trie
: 我写了前前后后3个小时，包括辅助函数包括注释能有200多行吧，一看时间用太久也就
: 发给他了，头疼的要死也没写unit test。感觉就是要玩我啊。
|
e****e
发帖数: 418 | 18 IMHO, if we can make one double quote never appear in csv, then we can use
it as 分隔符.
Since Java uses escape like i.e. System.out.print( "\"" ) -> "
When writing into csv, we replace " with \" to make every " appeared in
string become \", so no single " will be in cvs.
It can be done by String method .replace( "\"", "\\\"" )
i.e. a"b -> a\"b
" -> \"
i.e.
tree:
1
" 3
csv
1
\", ", 3 ( The second element is delimiter.)
When deserializing, replace \" back to ".
【在 h*****7 的大作中提到】
: 就算是一层存一行，怎么知道怎么分隔呢？理论上没法光凭csv的逗号判断也无法自己
: 插入任何分隔符，因为什么字符都可以包含
|
o***d
发帖数: 313 | 19 还是不是很确定到底他要你怎么做.
综合上面的各位,那么solution:
1) PostOrder traverse
2) At each record of csv file, save children's line number first, then, use
another special token (say, :) to start string, which means the record saved
will look like this:
-1,-1:"first left"
-1,-1:"first right"
1,2: "root"
this is how it should work? |
e****e
发帖数: 418 | 20 Breadth First Traversal. Don't need to save the line number. It's more like
the print by level with a delimiter inserted.
use
saved
【在 o***d 的大作中提到】
: 还是不是很确定到底他要你怎么做.
: 综合上面的各位,那么solution:
: 1) PostOrder traverse
: 2) At each record of csv file, save children's line number first, then, use
: another special token (say, :) to start string, which means the record saved
: will look like this:
: -1,-1:"first left"
: -1,-1:"first right"
: 1,2: "root"
: this is how it should work?
|
|
|
o***d
发帖数: 313 | 21 这个不成把?你怎么判断这一层的字节点输出完毕?关键是string的内容可能跟
dilimiter一样.
like
【在 e****e 的大作中提到】
: Breadth First Traversal. Don't need to save the line number. It's more like
: the print by level with a delimiter inserted.
:
: use
: saved
|
e****e
发帖数: 418 | 22 read the my previous post on this thread.
The delimiter is ".
【在 o***d 的大作中提到】
: 这个不成把?你怎么判断这一层的字节点输出完毕?关键是string的内容可能跟
: dilimiter一样.
:
: like
|
s*******n
发帖数: 97 | 23 考虑简单一点
serialize: bfs 便利，每行第一个格存这个节点有多少个children，第二个格存节点
的内容
deserialize: 从第一行开始读文件line by line, 构造node 节点(包括内容和节点数)
，放到queue中。同时如果queue里面第一个node没满，那么当前的node就是它的一个
child。否则就是下一个node的children, if it is not full. |
