acoding167
BAN USER- 1of 1 vote
AnswersCard Game
- acoding167 in United States
Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true.| Report Duplicate | Flag | PURGE
Google Software Engineer - 1of 1 vote
AnswersGet the sum of all prime numbers up to N. primeSum(N).
- acoding167 in United States
Follow-up: If primeSum(N) is frequently called, how to optimize it.| Report Duplicate | Flag | PURGE
Amazon - 2of 2 votes
AnswerSelect a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).
- acoding167 in United States
Follow-up: Given multiple non-overlapped rectangles on the 2D grid, uniformly select a random point from the rectangles.| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersFind whether string S is periodic.
- acoding167 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"
follow up:
Given string S, find out the P (repetitive pattern) of S.| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 2of 2 votes
AnswersGive m balls and n bins. Find out how many ways to assign balls to bins. Notice the buckets has no order. Like (1,2,3) and (3,2,1) are considered the same.
- acoding167 in United States
eg, m = 3, n = 2, return 2. (1, 2) and (3, 0)| Report Duplicate | Flag | PURGE
Amazon Software Engineer - 1of 1 vote
AnswersLonely Pixel
- acoding167 in United States
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM))| Report Duplicate | Flag | PURGE
Google Software Engineer - 2of 2 votes
AnswersGenerate random max index
- acoding167 in United States
Given an array of integers, randomly return an index of the maximum value seen by far.
e.g.
Given [11,30,2,30,30,30,6,2,62, 62]
Having iterated up to the at element index 5 (where the last 30 is), randomly give an index among [1, 3, 4, 5] which are indices of 30 - the max value by far. Each index should have a ¼ chance to get picked.
Having iterated through the entire array, randomly give an index between 8 and 9 which are indices of the max value 62.| Report Duplicate | Flag | PURGE
Facebook Software Engineer - 2of 2 votes
AnswersCreate an iterator class that stores a list of the built-in Iterators.
- acoding167 in United States
Implement the next() and hasNext() methods in a Round Robin pattern (pops next element in a circle).
Example:
Given a list [iterator1,iterator2, iterator3...]
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next() if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
until there is no more element in any of the iterators| Report Duplicate | Flag | PURGE
Google
I. At first find found all primes <= N (sieve of Eratosthenes). Getting the sum will be easy then.
Follow-up:
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)
public class PrimeSum {
TreeMap 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);
}
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught 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, Greed and other advanced algo problems),
and mock interviews.
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 class RandomSelectFromRectangle {
class Rectangle {
int x1, x2, y1, y2; //top left (x1, y1), bottom right (x2, y2)
}
class Point {
int x, y;
public Point(int a, int b) {
x = a;
y = b;
}
}
final Random rand = new Random();
//Round2
public Point randomSelectFrom(Rectangle rectangle) {
return new Point(rectangle.x1 + rand.nextInt(rectangle.x2 - rectangle.x1 + 1),
rectangle.y2 + rand.nextInt(rectangle.y1 - rectangle.y2 + 1));
}
//Round2 follow-up
//first of all decide which rectangle yields the point (randomly select a rectangle based on area as the weight)
//then apply randomSelectFrom(rectangle) on the selected rectangle
public Point randomSelectFrom(Rectangle[] rectangles) {
int selected = -1, total = 0;
for(int i = 0; i < rectangles.length; i++) {
int area = (rectangles[i].x2 - rectangles[i].x1) * (rectangles[i].y1 - rectangles[i].y2);
if(rand.nextInt(total + area) >= total) {
selected = i;
}
total += area;
}
return randomSelectFrom(rectangles[selected]);
}
}
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.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution to follow-up: Randomly select a rectangle based on the areas as the weights (larger weights leads to higher probability). Then randomly find a point from the chosen rectangle.
boolean isPeriod(String s) {
StringBuilder str = new StringBuilder(s s);
str.deleteCharAt(0);
str.deleteCharAt(str.length() - 1);
return strStr(str.toString(), s); //KMP strStr(T, S) to find if T has S in it.
}
//Solution to follow-up
//This method looks for the repeating pattern in string
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
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught 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, Greed and other advanced algo problems),
and mock interviews.
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.
static int[] maxLCS(int[] a, int[] b) {
int[][] op = new int[a.length + 1][b.length + 1];
for(int i = 1; i < a.length + 1; i++) {
for(int j = 1 ;j < b.length + 1; j++) {
if(a[i-1] == b[j-1]){
op[i][j] = op[i-1][j-1] + 1;
}else {
op[i][j] = Math.max(op[i-1][j], op[i][j-1]);
}
}
}
int maxLen = op[a.length][b.length];
int[] result = new int[maxLen];
int ap = a.length;
int bp = b.length;
while(ap > 0 && bp > 0) {
if(a[ap-1] == b[bp-1]) {
result[maxLen-1] = a[ap-1];
maxLen--;
ap--;
bp--;
}else if(op[ap-1][bp] <= op[ap][bp-1]) {
bp--;
}else {
ap--;
}
}
return result;
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught 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, Greed and other advanced algo problems),
and mock interviews.
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.
int assignBalls(int m, int n) {
if (m == 0 || n == 1) {
return 1;
}
if (n > m) {
return assignBalls(m, m);
} else {
return assignBalls(m, n - 1) + assignBalls(m - n, n);
}
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught 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, Greed and other advanced algo problems),
and mock interviews.
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.
static int[] maxLCS(int[] a, int[] b) {
int[][] op = new int[a.length + 1][b.length + 1];
for(int i = 1; i < a.length + 1; i++) {
for(int j = 1 ;j < b.length + 1; j++) {
if(a[i-1] == b[j-1]){
op[i][j] = op[i-1][j-1] + 1;
}else {
op[i][j] = Math.max(op[i-1][j], op[i][j-1]);
}
}
}
int maxLen = op[a.length][b.length];
int[] result = new int[maxLen];
int ap = a.length;
int bp = b.length;
while(ap > 0 && bp > 0) {
if(a[ap-1] == b[bp-1]) {
result[maxLen-1] = a[ap-1];
maxLen--;
ap--;
bp--;
}else if(op[ap-1][bp] <= op[ap][bp-1]) {
bp--;
}else {
ap--;
}
}
return result;
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught 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, Greed and other advanced algo problems),
and mock interviews.
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.
class Node:
def __init__(self, ID, parent):
self.ID = ID
self.parentID = parent
self.left = None
self.right = None
#function to identify if given is preorder
'''
Create a stack to store nodes in the current path when traversing.
Push node[i] into stack once node[i] is verified to be valid (valid only when parent of node[i] is in stack.
In preorder a parent must show up earlier than its child)
Whenever stack top is not the parent of node[i], pop until parent of node[i] is at stack top. Push node[i].
If all nodes popped but parent of node[i] still not found, then node[i] is not in preorder sequence.
'''
def isPreorder(nodes):
if not nodes:
return True
st = [nodes[0].ID]
i = 1
while i < len(nodes):
if not st:
return False
if st[-1] is nodes[i].parentID:
st.append(nodes[i].ID)
i += 1
else:
st.pop()
return True
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught 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, Greed and other advanced algo problems),
and mock interviews.
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 void main(String[] args) {
System.out.println(lonelyPixelCount(new int[][]{ //1: black, 0: white
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
}));
}
static int lonelyPixelCount(int[][] picture) {
int m = picture.length, n = picture[0].length;
//First traversal sum up the count of black pixels by column
for(int i = 1; i < m; i++){
for(int j = 0; j < n; j++){
picture[i][j] += picture[i - 1][j];
}
}
int result = 0;
//Then traverse row by row from the bottom, count the black pixels in current row.
//If there is only 1 black pixel in current row, verify whether it is also the only in the column.
for(int i = m - 1; i >= 0; i--) {
int pixel_count_in_row = 0;
boolean only_pixel_in_column = false;
for(int j = n - 1; j >= 0; j--) {
if(picture[i][j] > 0 && (i == 0 || picture[i - 1][j] + 1 == picture[i][j])) { //verify if current cell number is a black pixel, by method in blue text above
pixel_count_in_row++;
if((i < m - 1 && picture[i + 1][j] == 1) || (i == m - 1 && picture[i][j] == 1)) {
only_pixel_in_column = true;
}
}
if(i < m - 1) {
//overwrite current cell with the number below it
picture[i][j] = picture[i + 1][j];
}
}
if(pixel_count_in_row == 1 && only_pixel_in_column) {
result++;
}
}
return result;
}
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 of FB, LinkedIn, Amazon, Google & Uber etc.)
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.
public void sampleIdx(int[] array){
if(array == null || array.length == 0){
return;
}
Random rnd = new Random();
int res = 0, max = Integer.MIN_VALUE, count = 0;
for(int i = 0; i < array.length; i++){
if(max < array[i]){
max = array[i];
res = i;
count = 1;
}else if(max == array[i]){
count++;
int idx = rnd.nextInt(count); //(0, k - 1)
if(idx == 0){
res = i;
System.out.print(“A max value index up to the ”+i +”th element is ” + res;
);
}
}
}
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught 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, Greed and other advanced algo problems),
and mock interviews.
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 class RoundRobinIterator {
List<Iterator> iterators;
int index; //current element
int size;
public RoundRobinIterator(List<Iterator> iter) {
iterators = iter;
size = iterators.size();
index = 0;
if(size > 0) locateNext();
}
public Object next() {
locateNext();
if(size == 0) return null;
return iterators.get(index).next();
}
public boolean hasNext() { // tradeoff - O(1) or O(n) ?
if(size == 0) return false;
return true;
}
private void locateNext() {
if(iterators.get(index).hasNext()) {
index = (index + 1) % size;
}
while(size > 0 && !iterators.get(index).hasNext()) {
Iterator tmp = iterators.get(index);
iterators.set(index, iterators.get(size - 1));
iterators.set(size - 1, tmp);
size--;
if(index == size) index = 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 contact us with any questions. Thanks for reading.
Looking for interview experience sharing and coaching?
- acoding167 July 12, 2019Visit aonecode.com for private lessons by FB, Google and Uber senior 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 Google, Facebook, Amazon, LinkedIn and other top tier companies after weeks of training.