Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
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 )
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
}
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));
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;
}
};
};
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();
}
}
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;
}
}
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());
}
}
}
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());
}
}
}
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());
}
}
}
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;
}
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;
}
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;
}
}
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;
}
}
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!
- aonecoding March 17, 2018public 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; } }