## acoding167

BAN USER- 1of 1 vote

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

```
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;
);
}
}
}
}
```

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.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Looking for interview experience sharing and mentors?

- acoding167 May 16, 2019Visit 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.