[八我司] 介绍一下Uber tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3258|回复: 6
收起左侧

求问Two Sigma Text Editor那道题

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

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

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

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

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. From 1point 3acres bbs
text editor需要insert,remove,highlight,需要想办法去index每次插入的object,原po说的interval tree应该就是index的方式吧。
关键点在于text打算怎么存
store highlight?.本文原创自1point3acres论坛
他要求三天后再load这个text,需要可以undo三天前的操作. save的时候 保存成xml类型之类的 把之前的操作也一起存下来


我理解的是. 围观我们@1point 3 acres
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) {
  4.     }
  5.    
  6.     void initialize(const string &str) {. visit 1point3acres for more.
  7.         root = build(str);
  8.     }
  9.    
  10.     char index(int i) {
  11.         return index(root, i);
  12.     }
  13.    
  14. private:
  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. From 1point 3acres bbs
  18.    
  19.     Node * build(const string str) {. more info on 1point3acres
  20.         int n = str.size();
  21.         if (n <= 0).本文原创自1point3acres论坛
  22.             return NULL;
  23.         
  24.         if (n <= 2)
  25.             return new Node(str, str.size()); // creating leaf node
  26.         
  27.         Node * node = new Node();. more info on 1point3acres
  28.         
  29.         node->left = build(str.substr(0, n / 2));
  30.         node->right = build(str.substr(n/2, n - n/2));
  31.         node->size = str.size();. 一亩-三分-地,独家发布
  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);. 1point 3acres 论坛
  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 | 显示全部楼层
.本文原创自1point3acres论坛
就是这个https://en.wikipedia.org/wiki/Rope_(data_structure)
回复 支持 反对

使用道具 举报

wang2579 发表于 2018-3-26 11:22:12 | 显示全部楼层
尝试写了一下,highlight实在懒得实现了,好麻烦。。就是一个数据结构存highlight的区间,最简单是array,听起来最靠谱是interval tree - 要不然在node里存也行呀...然后insert和delete时更新这个highlight的区间
follow up我觉得他会问怎么优化,就说能每过一段时间balance一次,用in-order遍历每个子节点,然后重做一个tree
  1. import java.util.Stack;
  2. -google 1point3acres
  3. import com.leetcode.java.algorithm.util.TextEditorTreeNode;

  4. public class TextEditorImpl implements TextEditor {-google 1point3acres
  5. . 牛人云集,一亩三分地
  6.     private TextEditorTreeNode root;
  7.     private Stack<EditAction> redoStack;
  8.     private Stack<EditAction> undoStack;

  9.     public enum EditType {. 一亩-三分-地,独家发布
  10.         INSERT, DELETE;
  11.     }.本文原创自1point3acres论坛

  12.     public class EditAction {
  13.         public EditType type;
  14.         public int delete_i;
  15.         public int delete_j;
  16.         public String insert;
  17. . 围观我们@1point 3 acres
  18.         public EditAction(EditType type, int delete_i, int delete_j, String insert) {
  19.             this.type = type;. more info on 1point3acres
  20.             this.delete_i = delete_i;
  21.             this.delete_j = delete_j;
  22.             this.insert = insert;
  23.         }
  24.     }

  25.     public TextEditorImpl() {
  26.         redoStack = new Stack<>();
  27.         undoStack = new Stack<>();
  28.     }

  29.     /** Function to clear rope **/
  30.     public void makeEmpty() {
  31.         root = null;
  32.     }.1point3acres网
  33. . 一亩-三分-地,独家发布
  34.     @Override
  35.     public void initialize(String str) {
  36.         String[] strings = str.split(" ");
  37.         for (int i = 0; i < strings.length; i++) {
  38.             if (i + 1 < strings.length) {
  39.                 concat(new TextEditorTreeNode(strings[i] + " "));
  40.             } else {
  41.                 concat(new TextEditorTreeNode(strings[i]));
  42.             }
  43.         }
  44.     }

  45.     /** Function to concat an element **/
  46.     private void concat(TextEditorTreeNode newNode) {
  47.         if (root == null) {
  48.             root = newNode;. 围观我们@1point 3 acres
  49.             return;
  50.         }

  51.         TextEditorTreeNode newRoot = new TextEditorTreeNode();
  52.         newRoot.left = root;
  53.         newRoot.right = newNode;
  54.         newRoot.weight = newRoot.left.weight;
  55.         if (newRoot.left.right != null)
  56.             newRoot.weight += newRoot.left.right.weight;
  57.         root = newRoot;
  58.     }

  59.     /** Function to concat an element **/
  60.     private TextEditorTreeNode split(int ind) {
  61.         if (ind >= root.weight) {
  62.             return root;. 一亩-三分-地,独家发布
  63.         }
  64.         TextEditorTreeNode returnNode = new TextEditorTreeNode();
  65.         TextEditorTreeNode curReturnNode = returnNode;

  66.         TextEditorTreeNode tmp = root;
  67.         while (tmp.data == null) {
  68.             if (tmp.left != null && ind < tmp.left.weight) {
  69.                 tmp.weight -= ind;. 1point 3acres 论坛
  70.                 curReturnNode.weight = ind;
  71.                 curReturnNode.right = tmp.right;
  72.                 curReturnNode.left = tmp.left;
  73.                 tmp.right = null;
  74.                 curReturnNode = curReturnNode.left;
  75.                 tmp = tmp.left;
  76.             } else {
  77.                 tmp.weight -= ind;
  78.                 if (tmp.left != null) {
  79.                     ind -= tmp.left.weight;
  80.                 }
  81.                 curReturnNode.weight = ind;
    -google 1point3acres
  82.                 curReturnNode.right = tmp.right;.1point3acres网
  83.                 curReturnNode = curReturnNode.right;. 一亩-三分-地,独家发布
  84.                 tmp = tmp.right;
  85.             }
  86.         }

  87.         TextEditorTreeNode node_left = new TextEditorTreeNode(tmp.data.substring(0, ind));
  88.         TextEditorTreeNode node_right = new TextEditorTreeNode(tmp.data.substring(ind)); 来源一亩.三分地论坛.
  89.         tmp.data = null;
  90.         tmp.left = node_left;. visit 1point3acres for more.
  91.         curReturnNode.right = node_right;
  92. .1point3acres网
  93.         return returnNode;. 留学申请论坛-一亩三分地
  94.     }

  95.     /** Function get character at a paricular index **/
  96.     @Override
  97.     public char index(int ind) {
  98.         TextEditorTreeNode tmp = root;
  99.         while (tmp.data == null) {
  100.             if (tmp.left != null && ind < tmp.left.weight) {. visit 1point3acres for more.
  101.                 tmp = tmp.left;
  102.             } else {
  103.                 if (tmp.left != null) {
  104.                     ind -= tmp.left.weight;. 牛人云集,一亩三分地
  105.                 }
  106.                 tmp = tmp.right;
  107.             }
  108.         }
  109.         if (ind >= tmp.weight) {
  110.             ind = tmp.weight - 1;
  111.         }
  112.         return tmp.data.charAt(ind);
  113.     }

  114.     @Override
  115.     public void insert(int p1, String s) {
  116.         TextEditorTreeNode newNode = new TextEditorTreeNode(s);
  117.         TextEditorTreeNode lastNode = split(p1);
  118.         concat(newNode);
  119.         concat(lastNode);
  120.         undoStack.push(new EditAction(EditType.DELETE, p1, p1 + s.length(), s));
  121.     }

  122.     @Override
  123.     public void delete(int p1, int p2) {
  124.         if (p1 >= p2) {
  125.             return;
  126.         }. 牛人云集,一亩三分地
  127.         TextEditorTreeNode lastNode = split(p2);
  128.         TextEditorTreeNode deleteNode = split(p1);
  129.         concat(lastNode);
  130.         undoStack.push(new EditAction(EditType.INSERT, p1, p2, print(deleteNode)));. 一亩-三分-地,独家发布
  131.     }

  132.     @Override
  133.     public void highlight(int p1, int p2) {
  134.         // TODO Auto-generated method stub-google 1point3acres

  135.     }

  136.     @Override
  137.     public void redo() throws Exception {
    . 1point 3acres 论坛
  138.         // TODO Auto-generated method stub
  139.         EditAction action = redoStack.pop();
  140.         switch (action.type) {
  141.         case INSERT:
  142.             delete(action.delete_i, action.delete_j);
  143.             break;. visit 1point3acres for more.
  144.         case DELETE:
  145.             insert(action.delete_i, action.insert);
  146.             break;
  147.         default:
  148.             throw new Exception("Invalid Redo Type");
  149.         }.留学论坛-一亩-三分地
  150.     }

  151.     @Override
  152.     public void undo() throws Exception {. from: 1point3acres
  153.         // TODO Auto-generated method stub
  154.         EditAction action = undoStack.pop();
  155.         redoStack.push(action);.本文原创自1point3acres论坛
  156.         switch (action.type) {. 牛人云集,一亩三分地
  157.         case INSERT:
    . more info on 1point3acres
  158.             insert(action.delete_i, action.insert);
  159.             break;-google 1point3acres
  160.         case DELETE:
  161.             delete(action.delete_i, action.delete_j);
  162.             break;.1point3acres网
  163.         default:
  164.             throw new Exception("Invalid Undo Type");
  165.         }. 一亩-三分-地,独家发布
  166.         undoStack.pop();
  167.     }

  168.     /** Function to print Rope **/
  169.     @Override
  170.     public void print() {
  171.         System.out.println(print(root));
  172.     }-google 1point3acres

  173.     private String print(TextEditorTreeNode r) {
  174.         String s = "";
  175.         if (r != null) {. visit 1point3acres for more.
  176.             s = s + print(r.left);. From 1point 3acres bbs
  177.             if (r.data != null). more info on 1point3acres
  178.                 s = s + r.data;
  179.             s = s + print(r.right);
  180.         }
  181.         return s;
  182.     }
  183. }
复制代码

补充内容 (2018-3-26 11:28):. 1point 3acres 论坛
post之后突然想到了,leaf node多加一个isHighlight的boolean,highlight把p1-p2通过两次split截取出来竖个flag再加回去就好了
-google 1point3acres
补充内容 (2018-3-26 11:28):
post之后突然想到了,leaf node多加一个isHighlight的boolean,highlight把p1-p2通过两次split截取出来竖个flag再加回去就好了.留学论坛-一亩-三分地

补充内容 (2018-3-26 11:28):
post之后突然想到了,leaf node多加一个isHighlight的boolean,highlight把p1-p2通过两次split截取出来竖个flag再加回去就好了
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-25 11:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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