aonecoding4
BAN USER 5of 5 votes
AnswersFind whether string S is periodic.
 aonecoding4 in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
Given string S, find out the P (repetitive pattern) of S. Report Duplicate  Flag  PURGE
Google Software Engineer  1of 1 vote
AnswersGiven two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
 aonecoding4 in United States
Followup: If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ? Report Duplicate  Flag  PURGE
Google Software Engineer  2of 2 votes
AnswersGiven a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
 aonecoding4 in United States
For example:
input = [(1,4), (2,3)]
return 3
input = [(4,6), (1,2)]
return 3
input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
return 11 Report Duplicate  Flag  PURGE
Facebook Software Engineer  2of 2 votes
AnswersGet the sum of all prime numbers up to N. primeSum(N).
 aonecoding4 in United States
Followup: If primeSum(N) is frequently called, how to optimize it. Report Duplicate  Flag  PURGE
Amazon  1of 1 vote
AnswerGiven a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
 aonecoding4 in United States
and then another series [A != C, D != H, ..., F != A ]
Check whether the equations combined is valid.
For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series. Report Duplicate  Flag  PURGE
Amazon Software Engineer  5of 5 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  2of 2 votes
Answers[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  2of 2 votes
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
private static String getPeriod(String string) { // O(n * n)
//for every possible period size i, check if it's valid
for (int i = 1; i <= string.length() / 2; i++) {
if (string.length() % i == 0) {
String period = string.substring(0, i);
int j = i;
while(j + i <= string.length()) {
if (period.equals(string.substring(j, j + i))) {
j = j + i;
if(j == string.length()) { //period valid through entire string
return period;
}
} else {
break;
}
}
}
}
return null; //string is not periodic
}

aonecoding4
March 01, 2019 public static List<Integer> getAnagrams(String s, String word) {
Map<Character, Integer> letters = new HashMap<>();
int distinct_letters = 0;
for(char c: word.toCharArray()) {
if(!letters.containsKey(c)) distinct_letters++;
letters.put(c, letters.getOrDefault(c, 0) + 1);
}
//search for anagrams with two pointers
List<Integer> res = new ArrayList<>();
int lo = 0, hi = 0;
while(hi < s.length()) {
if(!letters.containsKey(s.charAt(hi))) {
while(lo < hi) {
char c = s.charAt(lo);
if(letters.get(c) == 0) distinct_letters++;
letters.put(c, letters.get(c) + 1);
lo++;
}
hi++;
lo = hi;
} else if(letters.get(s.charAt(hi)) == 0){
char c = s.charAt(lo);
if(letters.get(c) == 0) distinct_letters++;
letters.put(c, letters.get(c) + 1);
lo++;
} else {
char c = s.charAt(hi);
letters.put(c, letters.get(c)  1);
if(letters.get(c) == 0) distinct_letters;
if(distinct_letters == 0) {
res.add(lo);
}
hi++;
}
}
return res;
}

aonecoding4
February 19, 2019 #include <iostream>
#include <string>
#include <vector>
using namespace std;
long factorial(long n){
long fact = 1;
for (long i = 1; i<= n; ++i)
fact *= i;
return fact;
}
void DFS(const string &s1, int m, int i,
const string&s2, int n, int j,
string path,vector<string> &ret){
if(i==m &&j==n) {
ret.push_back(path);
return;
}
if(i < m) DFS(s1, m, i+1, s2, n, j, path+s1, ret);
if(j < n) DFS(s1, m, i, s2, n, j+1, path+s2[j], ret);
}
vector<string> combineTowStrings(const string &s1,const string &s2) {
int m =s1.length(), n = s2.length();
long count =factorial(m+n)/factorial(n)/factorial(m);
cout <<"count:" << count << endl;
vector<string> ret;
DFS(s1, m, 0, s2,n, 0, "", ret);
return ret;
}
int main() {
vector<string> ret = combineTowStrings("AB","CDF");
cout <<ret.size() << endl;
for(string &s: ret) cout << s << endl;
return 0;
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
We provide ONE TO ONE courses that cover everything in an interview including
the latest interview questions categorized by companies,
algorithms,
SYSTEM DESIGN Courses(highly recommended for people interviewing with FLAG)
and mock interviews.
All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work.
Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.
Welcome to email us with any questions. Thanks for reading.
public static int mergeSegments(int[][] segments) {
Arrays.sort(segments, (x, y) > x[0]  y[0]);
int result = 0;
int last = 0;
for(int[] seg : segments) {
result += Math.max(seg[1]  Math.max(last, seg[0]), 0);
last = Math.max(last, seg[1]);
}
return result;
}
Looking for interview questions sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews.
All classes are given by experienced engineers/interviewers from FB, Google and Uber.
Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.
Here has a google online assessment question list: aonecode.com/googleonlineassessment
 aonecoding4 January 15, 2019I. At first find found all primes <= N (sieve of Eratosthenes). Getting the sum will be easy then.
Followup:
Cache the sums for any given N to save time. {N:SUM}
Optimization: Don't have to store sums for every N.
When N = 7, N = 8, N = 9, N = 10, the prime sum remains 17.
For N between 11 to 12, the prime sum is 28.
For N between 13 to 16, the sum is 41.
Use a BST structure as the cache. For N = 16, cache:
{2:3, 4:6, 6:11, 10:17, 12:28, 16:41}
For a given N, call cache.ceilingKey(N) to find the bucket for N.
N/log(n) * log(N)
Complexity
Time:
sieve of Eratosthenes takes O(NloglogN) time.
Insert an element into BST takes O(logN), there are N/logN primes in total to be added.
So building the cache takes logN * N / LogN = O(N) time
requesting primeSum(N) takes O(logN)
Space:
sieve of Eratosthenes takes O(N) extra space which will later be release after the cache is created.
Cache: O(N/logN)
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
import java.util.TreeMap;
public class PrimeSum {
TreeMap<Integer, Integer> sums;
public PrimeSum(int n) { //input the upper limit for all Ns
sums = new TreeMap<>();
// init an array to track prime numbers
boolean[] primes = new boolean[n + 1];
for (int i = 2; i < n; i++)
primes[i] = true;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (primes[i]) {
for (int j = i + i; j < n; j += i)
primes[j] = false;
}
}
// insert sums into cache
int sum = 0;
for(int i = 2; i <= n; i++) {
if(primes[i]) {
sums.put(i  1, sum);
sum += i;
}
}
if(primes[n]) {
sums.put(n, sum);
}
}
public int primeSum(int N) {
Integer ceiling = sums.ceilingKey(N);
//if(ceiling == null) {
//Exception("input value overflows");
//}
return sums.get(ceiling);
}
}

aonecoding4
January 07, 2019 This is a 'merge set' question. Given a graph, figure out which nodes belong to the same connected component and put them into a set.
Since the input comes in as an edge set, UNION FIND will be a good way to solve this.
Initially every node sources to itself. As we read the statement X = Y, we point the source of Y to the source of X so that they join the same set. After all connected components are sorted out. We check the unequal statements X != Y. If any of the X, Y pairs do share the same source, then X != Y contradicts with the equal statements.
public class CheckStatements {
public boolean validStatements(char[][] equal, char[][] unequal) {
int[] sets = new int[26];
for(int i = 0; i < 26; i++) {
sets[i] = i;
}
for(char[] pair: equal) {
mergeSets(sets, pair[0]  'A', pair[1]  'A');
}
for(int i = 0; i < 26; i++) {
findSrc(sets, i);
}
for(char[] pair: unequal) {
if(sets[pair[0]  'A'] == sets[pair[1]  'A']) return false;
}
return true;
}
private int findSrc(int[] sets, int i) {
int src = i;
while(src != sets[src]) {
src = sets[src];
}
int tmp;
while (i != sets[i]) {
tmp = sets[i];
sets[i] = src;
i = tmp;
}
return src;
}
private void mergeSets(int[] sets, int a, int b) {
int srcA = findSrc(sets, a);
int srcB = findSrc(sets, b);
sets[srcB] = srcA;
}
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.
Typical Dynamic Programming
public void printSums(int c1, int c2, int c3) {
Set<Integer> sums = new HashSet<>();
sums.add(0);
for(int sum = 1; sum <= 1000; sum++) {
if(sums.contains(sum  c1)  sums.contains(sum  c2)  sums.contains(sum  c3)) {
System.out.println(sum);
sums.add(sum);
}
}
}
Looking for interview experience sharing and mentors?
Visit 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.
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!