高频题（0）
1. Rotate Image by 90 Degrees In-Place
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Constraints:
- n == matrix.length == matrix[i].length
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
2. 设计in-memory database
| 设计in-memory database，一共4个level，所有test都过才能解锁下一个level。level 1是要写set,get 和delete三个func:
set:["SET","A","B","5"]，return "5"； database: {"A":{"B":"5"}};
set:["SET""A","B","6"]，return "11",database:{"A":{"B":11"}};如果data已经在database里的话要加之前的value;
set:["SET","A","C","1"],return "1"； database:{"A":{"B":"11","C":"1"}}
get就是value，没有在database里的话返回“”；
delete是删除给定的field
如果database里面没有field了，这个database也要删除掉
get就是value，没有在database里的话返回""；
delete是删除给定的field，如果database里面没有field了，这个database好像也要删除掉
level2是写TOPNKEYS，返回最新编过过的N个file。
level3 写users，不同user的database也不一样
level 4是undo和logout
set:["SET","A","B","5"]，return "5"； database: {"A":{"B":"5"}};
set:["SET""A","B","6"]，return "11",database:{"A":{"B":11"}};如果data已经在database里的话要加之前的value;
set:["SET","A","C","1"],return "1"； database:{"A":{"B":"11","C":"1"}}
get就是value，没有在database里的话返回“”；
delete是删除给定的field
如果database里面没有field了，这个database也要删除掉
get就是value，没有在database里的话返回""；
delete是删除给定的field，如果database里面没有field了，这个database好像也要删除掉
level2是写TOPNKEYS，返回最新编过过的N个file。
level3 写users，不同user的database也不一样
level 4是undo和logout
3. File System
一个file system，如果parent有access的话child file 也有access。给了input是
1.array representing child to parent relationship,
2. a set contains all the files have access. 问一个hasAccess(String fileName) API。建好hashmap就很顺利做完，trick是从child往parent/root方向看。
1.array representing child to parent relationship,
2. a set contains all the files have access. 问一个hasAccess(String fileName) API。建好hashmap就很顺利做完，trick是从child往parent/root方向看。
Follow up是remove redundant access，比如说下面的example，如果file1, file2, file3 都有access，我们就把原先input的那个set只保留file1
FILE1 -> File2
|
- ---> File3
4. Dom tree
Given a DOM tree, implement two functions.
1. getNodeByClassName
2. getNodeByClassNameHierarchy 给你一个root node和 string代表的css classname, 从树中找出符合classname的target node
1. getNodeByClassName
2. getNodeByClassNameHierarchy 给你一个root node和 string代表的css classname, 从树中找出符合classname的target node
5. Implement text editor(2)
写一个text editor， 有append， move， backspace， select，copy paste等功能
Level 3
Level 3
The text editor should allow document changes to be tracked and reverted. Consider only operations that actually modify the contents of the text document, which are (APPEND, BACKSPACE, PASTE, UNDO, and REDO).
1. UNDO should restore the document to the state before the previous modification or REDO operation. The selection and cursor position should be also restored.
For example,
queries = [
["APPEND", "Hello, world!"], | "" -> "Hello, world!"
["SELECT", "7", "12"], | selects "world"
["BACKSPACE"], | "Hello, world!" -> "Hello, !"
["UNDO"], | restores "Hello, world!" with "world" selected
["APPEND", "you"] | "Hello, world!" -> "Hello, you!"
]
// returns: [ "Hello, world!",
// "Hello, world!",
// "Hello, !",
// "Hello, world!",
// "Hello, you!" ]
2. REDO can only be performed if the document has not been modified since the last UNDO operation. REDO should restore the state before the previous UNDO operation, including the selection and cursor position. Multiple UNDO and REDO operations can be performed in a row.
For example,
queries = [
["APPEND", "Hello, world!"], | "" -> "Hello, world!"
["SELECT", "7", "12"], | selects "world"
["BACKSPACE"], | "Hello, world!" -> "Hello, !"
["MOVE", "6"], | moves the cursor to after the comma
["UNDO"], | restores "Hello, world!" with "world" selected
["UNDO"], | restores initial ""
["REDO"], | restores "Hello, world!" with "world" selected
["REDO"] | restores "Hello, !" with the cursor after the comma
]
// returns: [ "Hello, world!",
// "Hello, world!",
// "Hello, !",
// "Hello, !",
// "Hello, world!",
// "",
// "Hello, world!",
// "Hello, !" ]
Level 4
Level 4
The text editor should support multiple text documents with a common clipboard.
1. CREATE <name> should create a blank text document name. If such a file already exists, ignore the operation and return empty string. Modification history is stored individually for each document.
2. SWITCH <name> should switch the current document to name. If there is no such file, ignore the operation and return empty string. When switching to a file, the position of the cursor and selection should return to the state in which they were left.
Note: it is guaranteed that all operations from previous levels will be executed on the active document. For backward compatibility, assume for Levels 1-3 there is a single, initially active document.
For example,
queries = [
["CREATE", "document1"], | creates document1
["CREATE", "document2"], | creates document2
["CREATE", "document1"], | ignores the operation
["SWITCH", "document1"], | switches to document1
["APPEND", "Hello, world!"], | document1: "" -> "Hello, world!"
["SELECT", "7", "12"], | selects "world"
["COPY"], | copies "world" to the clipboard
["SWITCH", "document2"], | switches to document2
["PASTE"], | document2: "" -> "world"
["SWITCH", "document1"], | switches to document1
["BACKSPACE"] | document1: "Hello, world!" -> "Hello, !"
]
// returns: [ "",
// "",
// "",
// "",
// "Hello, world!",
// "Hello, world!",
// "Hello, world!",
// "",
// "world",
// "Hello, world!",
// "Hello, !" ]
Example
For
queries = [
["APPEND", "Hey"],
["APPEND", " you"],
["APPEND", ", don't"],
["APPEND", " "],
["APPEND", "let me down"]
]
the output should be
textEditor2_2(queries) = [
"Hey",
"Hey you",
"Hey you, don't",
"Hey you, don't ",
"Hey you, don't let me down"
]
