aonecoding4
BAN USER 2of 2 votes
Answers[Google] Design Text Editor (Doubly Linked List)
 aonecoding4 in United States
Build a text editor class with the following functions,
moveCursorLeft(),
moveCursorRight(),
insertCharacter(char) //insert the char right before cursor
backspace() //delete the char right before cursor
Followup
Implement undo() //undo the last edit. Can be called multiple times until all edits are cancelled.
All functions above should take O(1) time.
Example
( '' denotes where the cursor locates. 'text' shows what's been written to the text editor. )
Start with empty text
text = ""
insertCharacter('a')
text = "a"
insertCharacter('b')
text = "ab"
insertCharacter('c')
text = "abc"
moveCursorLeft()
text = "abc"
moveCursorLeft()
text = "abc"
backspace()
text = "bc"
moveCursorLeft()
text = "bc" (nothing happens since cursor was on the leftmost position)
undo()
text = "abc"
undo()
text = "abc"
undo()
text = "abc"
undo()
text = "ab"
undo()
text = "a" Report Duplicate  Flag  PURGE
Google Software Engineer  1of 1 vote
Answer[Google Onsite 2018 Winter]
 aonecoding4 in United States
Set Matrix Zeroes II
There are orbs on an NxM board ('O' denotes orb. 'X' denotes empty slot).
Whenever two orbs are in the same column or the same row, you get to erase one of them.
Try to erase as many orbs as possible.
Find the minimum number of orbs remained on board eventually.
e.g.
OXOXXO
XXXXXO
XXXXOX
erase (0,0) and get
XXOXXO
XXXXXO
XXXXOX
erase (2,0) and get
XXXXXO
XXXXXO
XXXXOX
erase (5,0) and get
XXXXXX
XXXXXO
XXXXOX
no more moves available. Return 2 e.g.
OXOXXO
XXXXXO
XXOXOX
erase(4,2), (2,2), (0,0), (2,0), (5,0)
Return 1
e.g.
OXOXXX
XOXXXO
XXXOOX
erase(0,0), (1,1), (3,2)
Return 3
Followup Build a solver for this board game that erases the as many orbs as possible. Report Duplicate  Flag  PURGE
Google Software Engineer  1of 1 vote
AnswersGiven a tree with n nodes. Each node has k coins, where 0 <= k <= n . There are total n coins on the tree.
 aonecoding4 in United States
The goal is to move the coins such that each node has exactly one coin. What's the minimum moves required?
Each move can only move one coin to an adjacent node. Report Duplicate  Flag  PURGE
Google Software Engineer
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONEONONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
import java.util.Stack;
class CharNode {
char ch;
CharNode prev;
CharNode next;
public CharNode(char ch) { this.ch = ch; }
}
class Edit {
String edition; //"DEL", "INS", "LEFT", "RIGHT"
CharNode data;
public Edit(String edition, CharNode cur) {
data = cur;
this.edition = edition;
}
}
public class TextEditor {
private Stack<Edit> undo_stack;
private CharNode cursor;
private CharNode end;
public TextEditor() {
undo_stack = new Stack();
end = new CharNode('\0');
cursor = end;
}
public void moveCursorLeft() {
if(cursor.prev == null) return;
cursor = cursor.prev;
undo_stack.push(new Edit("RIGHT", null));
}
public void moveCursorRight() {
if(cursor == end) return;
cursor = cursor.next;
undo_stack.push(new Edit("LEFT", null));
}
public void insertCharacter(char ch) {
CharNode n = new CharNode(ch);
insert(n);
undo_stack.push(new Edit("DEL", null));
}
public void backspace() {
if(cursor.prev == null) return;
undo_stack.push(new Edit("INS", delete(cursor.prev)));
}
public void undo() {
if(undo_stack.isEmpty()) return;
Edit edit = undo_stack.pop();
switch(edit.edition) {
case "LEFT":
cursor = cursor.prev; break;
case "RIGHT":
cursor = cursor.next; break;
case "DEL":
delete(cursor.prev); break;
case "INS":
insert(edit.data); break;
default:
return;
}
}
public String toString() {
StringBuilder text = new StringBuilder();
CharNode n = end.prev;
if(cursor == end) text.append('');
while(n != null) {
text.insert(0, n.ch);
if(cursor == n) text.insert(0, '');
n = n.prev;
}
return text.toString();
}
private void insert(CharNode node) {
CharNode prev = cursor.prev;
node.next = cursor;
cursor.prev = node;
if(prev != null) {
prev.next = node;
node.prev = prev;
}
}
private CharNode delete(CharNode del) {
if(del.prev != null) {
del.prev.next = cursor;
}
cursor.prev = del.prev;
return del;
}
}

aonecoding4
December 04, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONEONONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
def solve(board):
m, n = len(board), len(board[0])
'''create adjacency list
rows[0] has all the nodes in 1st row
rows[1] has all the nodes in 2nd row
etc.
cols[0] has all the nodes in 1st column
cols[1] has all the nodes in 2nd column
etc.'''
rows, cols = [set() for i in range(m)], [set() for j in range(n)]
for i in range(m):
for j in range(n):
if board[i][j] is 'O':
rows[i].add(j)
cols[j].add(i)
#count the degree (number of neighbors) of every orb
degrees = dict()
for i in range(m):
for j in rows[i]:
degree = len(rows[i]) + len(cols[j])  2
if degree > 0:
degrees[(i, j)] = degrees
#erase the node with minimum positive degree until all nodes have 0 degree
while degrees:
erase_orb(degrees, board, rows, cols)
#output
for row in board:
print row
#erase the orb with the minimum degree
def erase_orb(degrees, board, rows, cols):
#find the node with minimum positive degree
i, j = min(degrees.items(), key=lambda x: x[1])[0]
#erase this node
rows[i].remove(j)
cols[j].remove(i)
degrees.pop((i, j))
board[i][j] = 'X'
print 'erase ', (i, j)
#remove one degree from every neighbor of the node erased
for y in rows[i]:
degrees[(i, y)] = 1
if degrees[(i, y)] is 0:
degrees.pop((i, y))
for x in cols[j]:
degrees[(x, j)] = 1
if degrees[(x, j)] is 0:
degrees.pop((x, j))
solve([
['X', 'X', 'X', 'X', 'X', 'O'],
['O', 'X', 'X', 'X', 'X', 'X'],
['O', 'X', 'X', 'X', 'X', 'O'],
['X', 'X', 'O', 'X', 'O', 'X'],
['X', 'O', 'X', 'X', 'X', 'O']
])

aonecoding4
November 28, 2018 Solution:
int moveCoins(TreeNode root) {
return dfs(root, new HashMap<>());
}
int dfs(TreeNode n, Map count) {
if(!count.containsKey(n)) {
count.put(n, n.val);
}
int coinsNum = count.get(n);
int res = 0;
for(TreeNode kid : n.children) {
res += dfs(kid, count);
coinsNum += count.get(kid);
res += Math.abs(count.get(kid));
}
count.put(n, coinsNum  1);
return res;
}
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONEONONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
Open Chat in New Window
Typical Dynamic Programming
Looking for interview experience sharing and mentors?
 aonecoding4 December 16, 2018Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amzn, Yahoo and other top companies after a few weeks of training.
Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.