## Facebook Interview Question for Software Engineers

• 2
of 2 votes

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

``````public class MovingAvg {

int[] q;  // a circular queue of size N
int head; //queue head
int tail; //queue tail
int size; // queue size
int sum;

public MovingAvg(int N) {
q = new int[N];
}

//@param num - the next number from data stream
//@return - new average with num included and expired number excluded
public double getAverage(int num) {
double avg = 0;
sum += num;
if(size == q.length) {
sum -= q[head];
head = (head + 1) % q.length;
} else {
size++;
}
q[tail] = num;
tail = (tail + 1) % q.length;
return 1.0 * sum / size;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is against the question.
Question says "consider last N values" and you are considering all values in the given array using Size.
You should divide based on either N or current size ( when current size is < N )

Comment hidden because of low score. Click to expand.
0
of 0 votes

``````public double getAverage(int item) {

this.sum += item;

//if this reach max sized then, remove head element from sum
if (this.size == maxSize) {

this.sum -= circularQueue[head];

//proceed the head pointer to next cell
head = (head + 1) % this.maxSize;
} else {
//update this size
this.size++;
}

//add this element in queue
circularQueue[tail] = item;
tail = (tail + 1) % this.maxSize;

/**
*  considers the last N values.
*/
if (this.size < this.maxSize)
return ((double) sum / this.size); //Note here we divide by the current size of array
else
return ((double) sum / this.maxSize); //Note here we divide by the max size of array

}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

another way would be using modulo

``````/**
*  considers the last N values.
*/
//            if (this.size < this.maxSize)
//                return ((double) sum / this.size); //Note here we divide by the current size of array
//            else
//                return ((double) sum / this.maxSize); //Note here we divide by the max size of array

//considers the last N values.
return (double) sum / (this.size % (this.maxSize + 1));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````const CircularQueue = function(items) {
this.items = items;

this.nextIndex = 0;

return {
getAll: () => this.items,

add: (item) => {
this.items.push(item);
return this;
},

nextElement: () => {
const element = this.items[this.nextIndex];

if (this.nextIndex === this.items.length - 1) {
this.nextIndex = 0; // back to begins
} else {
this.nextIndex = this.nextIndex + 1;
}

return element;
}
};
};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Don't think we can get away with not storing all N elements, but can reduce time to calculate average to O(1) if we keep the accumulated sum and update it when new element comes in.

``````class CalcAvgN {
public:
vector<int> array;
long sum;

void insert(int value) {
this->sum -= this->array.pop_front();
this->sum += value;
this->array.push_back(value);
}

float average() {
return static_cast<float>(this->sum) / this->array.size();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class MovingAverage {
int[] data;
int size, last;
long sum;

MovingAverage(int capacity) {
data = new int[capacity];
}

double average(int value) {
int next = (last + 1) % data.length;
sum += value - data[next];
data[next] = value;
last = next;
size = size == data.length ? size : size + 1;

return ((double) sum) / size;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Queue {
int[] elements;
int N;
int size=0;

Queue(int N_) {
elements = new int[N_];
N = N_;
}

int replace(int last) {
if (size == N) {
int first = elements[0];
for (int i = 0; i < N - 1; i++) {
elements[i] = elements[i + 1];
}
elements[N - 1] = last;
return last-first;
} else {
elements[elements.length - 1] = last;
size++;
return last;
}
}

int length() {
return size;
}
}

public class Main {

static int[] intArray = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
static Queue q = new Queue(3);
static int sum =0;

public static void main(String[] arg) {
int sum = 0;
// write your code here
for (int e : intArray) {
sum += q.replace(e);
System.out.printf("Avg is %d/%d = %d\n",sum,q.length(),sum/q.length());
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Queue {
int[] elements;
int N;
int size=0;

Queue(int N_) {
elements = new int[N_];
N = N_;
}

int replace(int last) {
if (size == N) {
int first = elements[0];
for (int i = 0; i < N - 1; i++) {
elements[i] = elements[i + 1];
}
elements[N - 1] = last;
return last-first;
} else {
elements[elements.length - 1] = last;
size++;
return last;
}
}

int length() {
return size;
}
}

public class Main {

static int[] intArray = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
static Queue q = new Queue(3);
static int sum =0;

public static void main(String[] arg) {
int sum = 0;
// write your code here
for (int e : intArray) {
sum += q.replace(e);
System.out.printf("Avg is %d/%d = %d\n",sum,q.length(),sum/q.length());
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Queue {
int[] elements;
int N;
int size=0;

Queue(int N_) {
elements = new int[N_];
N = N_;
}

int replace(int last) {
if (size == N) {
int first = elements[0];
for (int i = 0; i < N - 1; i++) {
elements[i] = elements[i + 1];
}
elements[N - 1] = last;
return last-first;
} else {
elements[elements.length - 1] = last;
size++;
return last;
}
}

int length() {
return size;
}
}

public class Main {
static int[] intArray = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
static Queue q = new Queue(3);
static int sum =0;

public static void main(String[] arg) {
int sum = 0;
// write your code here
for (int e : intArray) {
sum += q.replace(e);
System.out.printf("Avg is %d/%d = %d\n",sum,q.length(),sum/q.length());
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int* queue = 0;
int N = 0;
int tail = 0;
double sum = 0;

void init(int n) {
N = n;
queue = malloc(sizeof(int)*N);
for(int i = 0; i < N; i++)
queue[i] = 0;
}

void addentry(int newentry) {
tail %= N;
sum -= queue[tail];
queue[tail++] = newentry;
sum += newentry;
}

double movingavg() {
return sum/N;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int* queue = 0;
int N = 0;
int tail = 0;
double sum = 0;

void init(int n) {
N = n;
queue = malloc(sizeof(int)*N);
for(int i = 0; i < N; i++)
queue[i] = 0;
}

void addentry(int newentry) {
tail %= N;
sum -= queue[tail];
queue[tail++] = newentry;
sum += newentry;
}

double movingavg() {
return sum/N;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class CircularBuffer {
constructor(size) {
this.buffer = new Array(size);

this.pointer = 0;
this.length  = 0;
this.sum     = 0;
}

push(value) {
if(this.buffer[this.pointer]) {
this.sum -= this.buffer[this.pointer];
}

this.buffer[this.pointer] = value;
this.sum += value;

this.pointer = (this.pointer + 1) % this.buffer.length;
this.length  = Math.min(this.length + 1, this.buffer.length);
}

getAvarage() {
if(this.length === 0) {
return 0;
}

return this.sum / this.length;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class MovingAverageWithCircularLinkedList {
class Link {
int data;
public Link next = null;

public Link(int data) {
this.data = data;
}
}
int numElements = 0;
int sum = 0;
int N;
Link current = null;

public MovingAverageWithCircularLinkedList(int N){
this.N = N;
}

public static void main(String[] args){
int testcase[] = new int[] {-1, 5, 4, -3, 0, 7, 2};
MovingAverageWithCircularLinkedList streamaggregator = new MovingAverageWithCircularLinkedList(3);

for (int v : testcase) {
double avg = streamaggregator.update(v);
System.out.println("" + v + " avg: " + avg);
}
}

/**
* update and return running average
* approach does not pad at the beginning , rather returns sum(0..l-1)/l when l < N
*/
public double update(int e) {
if (numElements < N) {
Link l = new Link(e);
if (numElements == 0){
l.next = l;
} else {
l.next = current.next;
current.next = l;
}
current = l;
sum += e;
numElements++;
} else {
current = current.next;
sum = sum + e - current.data;
current.data = e;
}

return ((double) sum )/ numElements;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Any reason you won't consider Stackstrcuture.It will happily give u last n items added to stack.peek it and find average.for(int m=0;m<n;m++){
sum+=stack.peek();
}

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More