问答

当前位置

请问一个描述比较抽象的题目

  • Ta: 添助教

图片
The content updates and the word cat shifts down a line. However, Person B's
cursor is left in it's original position instead of moving down a line as expected.

Implement the fixCursorRow method don't worry about updating the column.
*/

public class Cursor {
public int column;
public int row;

public Cursor(int row, int column);

}

// diff comes from the other screen.
// content is content of the current screen before diff is applied.
// cursor is the cursor of the current screen.

// diff format:
// The diff contains all content from beginning to end of document.

{{"1", "\n"}, {"0", "cat"}}
// house -> horse = {{"0", "ho"}, {"-1", "u"}, {"1", "r"}, {"0", "se"}}
// "0" -> equality, "1" -> addition, "-1" -> removal
public Cursor fixCursorRow(String[][] diff, String content, Cursor cursor) {
}

面试遇到的,就是两个人(A and B,let's say) 在编辑一个文档,google doc的感觉,但是在例子中,A按回车以后,A的cursor下去了,但B的cursor还留在原地。Expected的结果是B的cursor也应该下去,不应该留在原地,因为原来那行都没有文字了。所以要求实现一个fixCursorRow的方法来修正B的cursor位置,只需要修正row的位置不需要管column。

关于输入:diff是编辑前的文档和编辑后文档的区别,content是B的文档(编辑前),cursor是B的光标位置。

我的想法开始是因为只有对cursorB光标位置之前的编辑才会影响到cursorB的位置,所以遍历diff,纪录并更新cursorA和cursorB的位置,在cursorA的位置超过cursorB之后return结果。但是一是题目说不需要考虑column,二是也没办法更新col因为不知道每行最多能有多少文字。也就是说如果diff里面有一个操作是删除,其中包括删除了一个\n, 我们没法知道cursorB的位置,有可能row减1也有可能不变,而且面试官的描述非常abstract,所以不太清楚这道题应该怎么做,希望老师助教们可以解答,谢谢!

1 个回复

2017-12-05 陆助教

大致讲讲我对这个题目的理解:

要实现的这个方法有三个参数,第一个参数diff是对文档的修改, 第二个参数content是原文档, 第三个参数cursor是光标 B(里面的属性应该是一开始B在原文档中的位置), 这个方法的目的就是来修正 B 在经过了这些个操作后到了哪一行。

那么首先想到的是, 是不是可以把光标 B 用一个或者一些不可能出现在文档中的字符或字符串来表示,直接插入到这个原文档中,
然后经过 diff 里面的修改操作后, 看看这个用来代替 B 的字符串的首字符在第几行, 也就是最终光标 B 的行数

还有就是你得想法,用一个光标 A 来进行修改操作, 直到 A 超过 B, 这应该也是可以实现的, 只不过难点在于当 A 与 B 处于同一行时, 如何判断 A 与 B的相对位置, 也就是A 是否超过 B了(当然这是基于假设:这个文档不会自动换行)。如果 A 所在的行数小于B所在的行数, 那么不管 A 对文档做什么处理,B 的列数都不会发生改变,如果有删除或增加换行符的操作的话,B 的行数做也要同 A 一样的变动, 到同一行每做一次修改就要修正 A 和 B 的 列数, 直到 A 的列数大于 B 的列数,那么 B 的行数也就确定了。

就看这个题是否可以自动换行,如果可以的话,那么第二种想法就不能这么实现(需要找到在光标 B 前面的最近的换行符在哪),这时候用第一种会好一些。

不过这个文档很明显是临界资源,在操作系统中本应该去极力避免同时访问编辑这种情况的出现,可以减小互斥的区域(比如每一段间互斥,一个人在编辑这一段文字时,另一个人不能编辑),但总不能像这个题一样直接没有互斥(可以同时编辑)...

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1