一亩三分地论坛

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

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

求问Two Sigma Text Editor那道题

[复制链接] |试试Instant~ |关注本帖
feichangh 发表于 2016-10-10 07:45:28 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@TwoSigma - 猎头 - Onsite |Other在职跳槽

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

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

x
请教大神们理解Text Editor那道题具体的问题是什么吗?找了很多贴也没有具体描述

text editor..设计题..要实现..insert(position), delete(p1, p2), highlight(p1, p2), redo ,undo….等..问你用什么数据机构之类的。
我一开始说要用char[][]。 但是給批评了好久…最后用了arraylist> 貌似…勉强通过了….然后…用什么储存..hightlight的…我一开始用hashset了..但是有个问题就是.delete的东西里面.刚好是hightlight的..那你怎么知道..你delete 的东西..也在hashset里面…所以.后来我用interval tree了…..他说…有道理多了….然后最后问了redo 和undo 怎么做…我用两个stack 储存operation…..
insert(p), delete(p1, p2), highlight(p1, p2),redo/undo, save/load update, search
text editor需要insert,remove,highlight,需要想办法去index每次插入的object,原po说的interval tree应该就是index的方式吧。
关键点在于text打算怎么存
store highlight?
他要求三天后再load这个text,需要可以undo三天前的操作. save的时候 保存成xml类型之类的 把之前的操作也一起存下来
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我理解的是. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
insert(int position, char c)在position位置插入一个字符
delete(int p1, int p2) 删除所有在p1和p2之间的字符
highlight(int p1, int p2)这个highlight 到底是干什么?是把p1,p2之间的字符放到一个数据结构,然后有个函数类似getAllHighLight可以返回所有highlight区间么?如果在现有highlight区间插入新的字符,删除旧的字符需要更新highlight么?比如 abcde, 一开始是bcd hightlight, 之后加一个f在bc之间变成abfcde,由于之前存的是index那现在highlight区间变成什么了呢?如果不更新的话就是bfc了
search 这个search是找一个字符呢,还是找多个连续字符呢?

我理解的解法就是普通的arraylist存全部字符,增加删除查找都用自带的api方法,highlight区间存成interval tree,删除时候如果发现删除区间和highlight区间有交集就禁止删除,在highlight区间插入还没有想明白。。。

看了面经中的解,这个解法是可以快速的搜索到index上的字符是多少,感觉对其他的功能也没有太多帮助,附面经中的解代码:
  1. class TextEditor {
  2. public:
  3.     TextEditor() : root(NULL) {.1point3acres缃
  4.     }
  5.     . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.     void initialize(const string &str) {
  7.         root = build(str);
  8.     }
  9.     . visit 1point3acres.com for more.
  10.     char index(int i) {
  11.         return index(root, i);. From 1point 3acres bbs
  12.     }
  13.    
  14. private:. 1point3acres.com/bbs
  15.     Node * root;
  16.     stack<Operation> undo; // whenever executed an operation, put the reverse operation in undo
  17.     stack<Operation> redo; // whenever undo an operation, put the reverse operation of the undo (essentially the original operation) in redo
  18.    
  19.     Node * build(const string str) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.         int n = str.size();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  21.         if (n <= 0)
  22.             return NULL;. 1point 3acres 璁哄潧
  23.         -google 1point3acres
  24.         if (n <= 2). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  25.             return new Node(str, str.size()); // creating leaf node
  26.         
  27.         Node * node = new Node();
  28.         
  29.         node->left = build(str.substr(0, n / 2));-google 1point3acres
  30.         node->right = build(str.substr(n/2, n - n/2));
  31.         node->size = str.size();. 鍥磋鎴戜滑@1point 3 acres
  32.         
  33.         return node;
  34.     }
  35.    
  36.     char index(Node * node, int i) {
  37.         if (!node || i >= node->size) return 'x';
  38.         
  39.         if (!node->left) { // is leaf
  40.             return node->text[i];
  41.         }
  42.         
  43.         if (i < node->left->size)
  44.             return index(node->left, i);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  45.          鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  46.         return index(node->right, i - node->left->size);
  47.     }
  48. };
复制代码

本帖被以下淘专辑推荐:

yuranrobin 发表于 2016-10-16 12:17:19 | 显示全部楼层
highlight估计就是类似于加粗加黑之类的吧 在加黑区间中insert应该也是保持highlight的
search会不会是说查找的历史记录啊 这样需要另一个stack
LZ我觉得不需要两个stack 只需要一个 加一个reverse func就好
回复 支持 反对

使用道具 举报

huai10 发表于 2016-10-23 16:56:00 | 显示全部楼层
那个代码是错的,但非常接近
回复 支持 反对

使用道具 举报

luochenhuan 发表于 2016-11-13 05:50:59 | 显示全部楼层

请问神马意思?
回复 支持 反对

使用道具 举报

 楼主| feichangh 发表于 2016-11-13 07:19:36 | 显示全部楼层

就是这个https://en.wikipedia.org/wiki/Rope_(data_structure)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 03:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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