Disclosure: Hackr.io is supported by its audience. When you purchase through links on our site, we may earn an affiliate commission. Facebook is a social media website company founded by Mark Zuckerberg along with fellow Harvard College students and roommates Eduardo Saverin, Andrew McCollum, Dustin Moskovitz and Chris Hughes in 2004. Facebook is a company where everyone wants to work in as it works best perks for the employees and a good experience for its employees.

Cracking a Facebook interview can be a tough pill to swallow. However, with a tight technical preparation and a cool head, you can gain a working opportunity at the world’s biggest social media giant.

Typically, a Facebook interview process involves:

• 2 telephonic rounds – Focuses on basic problem solving and data structures
• 2 or 3 coding on-site rounds – Involves whiteboarding solutions for slightly above average data structures/algorithmic problems. More rounds for the lesser experienced
• 1 or 2 system design on-site rounds – Aims at gauging the ability of the interviewee in coming up with efficient high-level design architectures for real-life products. The more experienced candidates will face more of these rounds
• 1 cultural fit on-site round – Meant for evaluating whether the interviewee will be a good cultural fit for Facebook or not. Doesn’t require any technical expertise

While the telephonic rounds will involve questioning about data structures and problem-solving, system design is meant for only a few candidates. So, that leaves with the on-site coding rounds, which are the most important.

Here are 16 most important Facebook interview questions that you can expect coming your way in the coding on-site rounds:

### Question: How will you rotate a square (N x N) matrix by 90 degrees in the anti-clockwise direction without using any extra space?

Answer: Suppose we have the following matrix:

1 2 3
4 5 6
7 8 9

Then, rotating it by 90 degrees in the anti-clockwise direction will result in the following matrix:

3 6 9
2 5 8
1 4 7

Following deductions can be made after examining the aforementioned resultant matrix:

• The first row of the source matrix will result in the first column of the obtained matrix in the reverse order
• The second row of the source matrix will result in the second column of the obtained matrix in the reverse order
.
.
.
• The last row of the source matrix will result in the last column of the obtained matrix in the reverse order

Any N x N matrix will have floor(N/2) square cycles. For each square cycle, elements in the corresponding cell will be swapped in the anti-clockwise direction; from top to left, left to bottom, bottom to the right, and from right to the top.

For achieving the aforementioned we need nothing more than a temporary variable. Here is how to achieve rotation of an N x N matrix by 90 degrees in the anti-clockwise direction in C++:

```#include <bits/stdc++.h>
#define N 4
using namespace std;
void displayMatrix(int mat[N][N]);
void rotateMatrix(int mat[][N])
{
for (int x = 0; x < N / 2; x++)
{
for (int y = x; y < N-x-1; y++)
{
int temp = mat[x][y];
mat[x][y] = mat[y][N-1-x];
mat[y][N-1-x] = mat[N-1-x][N-1-y];
mat[N-1-x][N-1-y] = mat[N-1-y][x];
mat[N-1-y][x] = temp;
}
}
}
void displayMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf("%2d ", mat[i][j]);
printf("\n");
}
printf("\n");
}
int main()
{
int mat[N][N] =
{
,
,
,

};
rotateMatrix(mat);
displayMatrix(mat);
return 0;
}
```

Output:

4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13

### Question: You are given an array with positive numbers. Explain how you will find the largest subset of the array containing elements that are Fibonacci numbers.

Answer: A simple approach for finding out the largest subset of an array of positive numbers that contain Fibonacci numbers is to iterate through all the elements of the array. Then, check for every number whether it is a Fibonacci number or not. If it then adds it to the result.

Although the aforementioned approach is simple, it isn’t efficient. Following steps can be followed for devising an efficient way of achieving the same:

• Find the max in the array
• Generate Fibonacci numbers until the max of the array and store the same in a hash table
• Traverse the array again and add all numbers present in the array and the hash table to the result

Following C++ code demonstrates an effective solution:

```#include<bits/stdc++.h>
using namespace std;
void findFibSubset(int arr[], int n)
{
int max = *std::max_element(arr, arr+n);
int a = 0, b = 1;
unordered_set hash;
hash.insert(a);
hash.insert(b);
while (b < max)
{
int c = a + b;
a = b;
b = c;
hash.insert(b);
}
for (int i=0; i<n; i++)
if (hash.find(arr[i]) != hash.end())
printf("%d ", arr[i]);
}
int main()
{
int arr[] = ;
int n = sizeof(arr)/sizeof(arr);
findFibSubset(arr, n);
return 0;
}
```

Output:

8 5 2 1 13

### Question: Suppose you have an integer array and a positive integer k. How will you count all distinct pairs with a difference equal to k?

Answer: There can be several approaches to achieving the required. We will discuss two of them:

Approach 1 – Considering All Pairs (NOTE: Will not work for an array with duplicates)

This basic approach involves considering all pairs in the integer array one by one and checking whether their difference is equal to the given positive integer k or not. If yes, then add them to the result. Following is the implementation of the approach in C++:

```#include
using namespace std;
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0;
for (int i = 0; i < n; i++)
{
for (int j = i+1; j < n; j++)
if (arr[i] - arr[j] == k || arr[j] - arr[i] == k )
count++;
}
return count;
}

int main()
{
int arr[] = ;
int n = sizeof(arr)/sizeof(arr);
int k = 3;
cout << "Total number of pairs with the given difference is: "
<< countPairsWithDiffK(arr, n, k);
return 0;
}
```

Output:

Total number of pairs with the given difference is: 2

Approach 2 – Using Sorting

Another approach of finding the pair count is by using an O(nLogn) sorting algorithm, such as Heap Sort and Merge Sort. Following steps describe the approach:

• Initialize the count to 0
• Sort the array elements in increasing order
• Eliminate duplicates from the array (if any)
• For each element arr[i]:
• Binary Search for arr[i] + k in the subarray from i+1 to n-1
• If arr[i] + k is found, increment the count
• Return count

Here is the C++ code for implementing the aforementioned approach:

```#include
#include
using namespace std;
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low)
{
int mid = low + (high - low)/2;
if (x == arr[mid])
return mid;
if (x > arr[mid])
return binarySearch(arr, (mid + 1), high, x);
else
return binarySearch(arr, low, (mid -1), x);
}
return -1;
}
int countPairsWithDiffK(int arr[], int n, int k)
{
int count = 0, i;
sort(arr, arr+n);
for (i = 0; i < n-1; i++)
if (binarySearch(arr, i+1, n-1, arr[i] + k) != -1)
count++;
return count;
}
int main()
{
int arr[] = ;
int n = sizeof(arr)/sizeof(arr);
int k = 3;
cout << "Total number of pairs with the given difference is: "
<< countPairsWithDiffK(arr, n, k);
return 0;
}
```

Output:

Total number of pairs with the given difference is: 2

### Question: Can you explain how to find the nth term in Count and Say sequence.

Answer: To begin with, we need to generate all terms from 1 to n. The first two terms are initialized as 1 and 11. The third term is generated from the second, fourth from the third, and so on. To generate the next term, we need to scan the previous term.

While scanning the previous term, we need to keep track of the count of all consecutive characters. For a sequence of the same characters, we will append the count followed by the character to generate the next term.

Here is the C++ code for finding the nth term in Count and Say sequence:

```#include <bits/stdc++.h>
using namespace std;
string countnndSay(int n)
{
if (n == 1) return "1";
if (n == 2) return "11";
string str = "11";
for (int i = 3; i<=n; i++)
{
str += '\$';
int len = str.length();
int cnt = 1;
string tmp = "";
for (int j = 1; j < len; j++)
{
if (str[j] != str[j-1])
{
tmp += cnt + '0';
tmp += str[j-1];
cnt = 1;
}
else cnt++;
}
str = tmp;
}
return str;
}
int main()
{
int N = 4;
cout << countnndSay(N) << endl;
return 0;
}
```

Output:

1211

### Question: If you are given a string containing uppercase alphabets and integers, how will you print the string with alphabets following the lexicographic order followed by the sum of the integers?

Answer: Here is the step-by-step description of how to achieve the desired:

• Traverse the given string
• (For an alphabet) Increment its occurrence count into a hash table
• (For an integer) Store it separately and add it to the previous sum
• Use a hash table to append all the alphabets first into a string following lexicographic order and then append the sum of the integers at the end
• Return the resultant string

Following code demonstrates implementing the output in C++:

```#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
string arrangeString(string str)
{
int char_count[MAX_CHAR] = ;
int sum = 0;
for (int i = 0; i < str.length(); i++)
{
if (str[i]>='A' && str[i] <='Z')
char_count[str[i]-'A']++;
else
sum = sum + (str[i]-'0');
}
string res = "";
for (int i = 0; i < MAX_CHAR; i++)
{
char ch = (char)('A'+i);
while (char_count[i]--)
res = res + ch;
}
if (sum > 0)
res = res + to_string(sum);
return res;
}
int main()
{
cout << arrangeString(str);
return 0;
}
```

Output:

AAABDHHIKLLW8

### Question: Convert a roman numeral into its corresponding integer number.

Answer: We will use the following algorithm for converting Roman Numerals into the equivalent integer number:

• Split the available Roman Numeral string into Roman Symbols
• Convert each Roman Symbol into its equivalent integer value
• For each symbol, starting from index 0:
• (If the current value of the Roman Symbol is greater than or equal to the value of the next Roman Symbol) Add this value to the total
• (If the current value of the Roman Symbol is less than the value of the next Roman Symbol) Subtract this value by adding the value of the next symbol to the total

Following C++ code demonstrates the algorithm:

```#include<bits/stdc++.h>
using namespace std;
int value(char r)
{
if (r == 'I')
return 1;
if (r == 'V')
return 5;
if (r == 'X')
return 10;
if (r == 'L')
return 50;
if (r == 'C')
return 100;
if (r == 'D')
return 500;
if (r == 'M')
return 1000;
return -1;
}
int romanToDecimal(string &str)
{
int res = 0;
for (int i=0; i<str.length(); i++)
{
int s1 = value(str[i]);
if (i+1 < str.length())
{
int s2 = value(str[i+1]);
if (s1 >= s2)
{
res = res + s1;
}
else
{
res = res + s2 - s1;
i++;
}
}
else
{
res = res + s1;
i++;
}
}
return res;
}
int main()
{
string str ="MMCDXXII";
cout << "Integer equivalent for the Roman Numeral is: "
<< romanToDecimal(str) << endl;
return 0;
}
```

Output:

Integer equivalent for the Roman Numeral is: 2422

### Question: Find the count of the smallest subarray of a given array with a sum greater than the given value x.

Answer: We will use two nested loops for finding the smallest subarray of a given array with a sum greater than the given value x. While the outer loop will pick a starting element, the inner loop will consider all elements as the ending element.

Each time the sum of the elements present between the current start and end becomes greater than the given number x, the result is updated if the present length is smaller than the previous smallest length.

The approach can be implemented in C++ using the following code:

```#include
using namespace std;
int smallestSubWithSum(int arr[], int n, int x)
{
int min_len = n + 1;
for (int start=0; start<n; start++)
{
int curr_sum = arr[start];
if (curr_sum > x) return 1;
for (int end=start+1; end<n; end++)
{
curr_sum += arr[end];
if (curr_sum > x && (end - start + 1) < min_len)
min_len = (end - start + 1);
}
}
return min_len;
}
int main()
{
int arr1[] = ;
int x = 51
int n1 = sizeof(arr1)/sizeof(arr1);
int res1 = smallestSubWithSum(arr1, n1, x);
(res1 == n1+1)? cout << "Not possible\n" :
cout << res1 << endl;
return 0;
}
```

Output:

3

### Question: From the given array, find a subarray that has at least k numbers and has the largest possible sum.

Answer: We will first compute the maximum sum until every index is covered and store it in an array named maxSum[]. Next, we will use the sliding window concept of size k. Then we will keep track of the sum of the current k elements.

For computing the sum of the current window, we need to remove the first element of the previous window and add the current element. Once we get the sum of the current window, we will add the maxSum[] of the previous window, if it will be greater than the current maxSum[].

Here is a C++ program for implementing the aforementioned idea:

```#include<bits/stdc++.h>
using namespace std;
int maxSumWithK(int a[], int n, int k)
{
int maxSum[n];
maxSum = a;
int curr_max = a;
for (int i = 1; i < n; i++)
{
curr_max = max(a[i], curr_max+a[i]);
maxSum[i] = curr_max;
}
int sum = 0;
for (int i = 0; i < k; i++)
sum += a[i];
int result = sum;
for (int i = k; i < n; i++)
{
sum = sum + a[i] - a[i-k];
result = max(result, sum);
result = max(result, sum + maxSum[i-k]);
}
return result;
}
int main()
{
int a[] = ;
int k = 2;
int n = sizeof(a)/sizeof(a);
cout << maxSumWithK(a, n, k);
return 0;
}
```

Output:

46

The subarray is 22, 24

### Question: How will you convert a ternary expression to a binary tree?

Answer: We will start with traversing the string, making the first character as the root and then:

• Add the next character as the left child of the root (when encountering the ‘?’ symbol)
• Add the next character as the right child of the root (when encountering the ‘.’ symbol)
• Repeat steps 1 and 2 until all elements of the string are traversed

Following is the demonstration of the approach using C++ code:

```#include<bits/stdc++.h>
using namespace std;
struct Node
{
char data;
Node *left, *right;
};
Node *newNode(char Data)
{
Node *new_node = new Node;
new_node->data = Data;
new_node->left = new_node->right = NULL;
return new_node;
}
Node *convertExpression(string str, int & i)
{
Node * root =newNode(str[i]);
if(i==str.length()-1) return root;
i++;
if(str[i]=='?')
{
i++;
root->left = convertExpression(str,i);
i++;
root->right = convertExpression(str,i);
return root;
}
else return root;
}
void printTree( Node *root)
{
if (!root)
return ;
cout << root->data <<" ";
printTree(root->left);
printTree(root->right);
}
int main()
{
string expression = "a?b?c:d:e";
int i=0;
Node *root = convertExpression(expression, i);
printTree(root) ;
return 0;
}
```

Output:

a b c d e

### Question: Explain various methods for finding all triplets in an array that has a total sum of 0.

Answer: There can be three different ways in which we can find all triplets in an array with a total sum of 0. Let’s discuss them in a brief:

Method 1 – The simplest approach will be to run three loops. Each triplet of the array will be checked whether the sum of their elements is 0 or not. If found, then print the triplets otherwise, print no triplets found. The time complexity for this approach will be O(n3).

Method 2 – This method makes use of hashing. While iterating through each element arr[i] of the array, we will find a pair with the sum -arr[i]. The time complexity for this approach will be O(n2).

Method 3 – The third method involves using sorting and will require an extra space. Although the time complexity of this method will be O(n2), compared to the O(n) auxiliary space required by the other two methods, this method only requires O(1) auxiliary space. This method works in the following steps:

• Sort all elements of the given array
• Run loop from i=0 to n-2
• Initialize two index variable l = i+1 and r = n-1
• While (l<r), check the sum of arr[i], arr[l], and arr[r] then:
• If the sum is less than zero then l++
• If the sum is greater than zero then r--
• If the sum is zero then print the triplet and do l++ and r--

Following C++ program implements Method 3:

```#include<bits/stdc++.h>
using namespace std;
void findTriplets(int arr[], int n)
{
bool found = false;
sort(arr, arr+n);
for (int i=0; i<n-1; i++)
{
int l = i + 1;
int r = n - 1;
int x = arr[i];
while (l < r)
{
if (x + arr[l] + arr[r] == 0)
{
printf("%d %d %d\n", x, arr[l], arr[r]);
l++;
r--;
found = true;
}
else if (x + arr[l] + arr[r] < 0)
l++;
else
r--;
}
}
if (found == false)
}
int main()
{
int arr[] = ;
int n = sizeof(arr)/sizeof(arr);
findTriplets(arr, n);
return 0;
}
```

Output:

-43 1 42
-10 0 10

### Question: Suppose you are given a binary tree. Explain how you will find its minimum depth?

Answer: The approach to finding the minimum depth of a binary tree involves traversing the given binary tree. For each node, check if it’s a leaf node:

• If yes, then return 1
• If no, then:
• Recur for the right subtree if the left subtree is NULL
• Recur for the left subtree if the right subtree is NULL
• Take the minimum of the two depths if both the left and right subtrees are not NULL

Here is an implementation of the aforementioned approach using C++ code:

```#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* left, *right;
};
int minDepth(Node *root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
if (!root->left)
return minDepth(root->right) + 1;
if (!root->right)
return minDepth(root->left) + 1;
return min(minDepth(root->left), minDepth(root->right)) + 1;
}
Node *newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int main()
{
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->left = newNode(6);
root->left->left->right = newNode(7);
cout <<"The minimum depth of the given binary tree is: "<< minDepth(root);
return 0;
}
```

Output:

The minimum depth of the given binary tree is: 2

### Question: Pleaseexplain how you will convert any integer value between 1 and 3999 into its Roman numeral equivalent.

Answer: Following algorithm will be used for converting any integer value between 1 and 3999 to its Roman numeral equivalent:

• Compare the given number with base values 1000, 900, 500, 400, 50, 40, 10, 9, 5, 4, and 1 in the respective order
• The value that will be the closest, smaller or equal, will serve as the initial base value
• Now, divide the given number with the initial base value
• The corresponding Roman Symbol for the initial base value will be repeated quotient times, while the remainder will follow Step 1
• The process will be iterated until the remainder becomes 0

The algorithm can be implemented in C++ using the following code:

```#include <bits/stdc++.h>
using namespace std;
int sub_digit(char num1, char num2, int i, char *c)
{
c[i++] = num1;
c[i++] = num2;
return i;
}
int digit(char ch, int n, int i, char *c)
{
for (int j = 0; j < n; j++)
c[i++] = ch;
return i;
}
void printRoman(int number)
{
char c;
int i = 0;
if (number <= 0)
{
printf("Invalid number");
return;
}
while (number != 0)
{
if (number >= 1000)
{
i = digit('M', number/1000, i, c);
number = number%1000;
}
else if (number >= 500)
{
if (number < 900)
{
i = digit('D', number/500, i, c);
number = number%500;
}
else
{
i = sub_digit('C', 'M', i, c);
number = number%100 ;
}
}
else if (number >= 100)
{
if (number < 400)
{
i = digit('C', number/100, i, c);
number = number%100;
}
else
{
i = sub_digit('C','D',i,c);
number = number%100;
}
}
else if (number >= 50 )
{
if (number < 90)
{
i = digit('L', number/50,i,c);
number = number%50;
}
else
{
i = sub_digit('X','C',i,c);
number = number%10;
}
}
else if (number >= 10)
{
if (number < 40)
{
i = digit('X', number/10,i,c);
number = number%10;
}
else
{
i = sub_digit('X','L',i,c);
number = number%10;
}
}
else if (number >= 5)
{
if (number < 9)
{
i = digit('V', number/5,i,c);
number = number%5;
}
else
{
i = sub_digit('I','X',i,c);
number = 0;
}
}
else if (number >= 1)
{
if (number < 4)
{
i = digit('I', number,i,c);
number = 0;
}
else
{
i = sub_digit('I', 'V', i, c);
number = 0;
}
}
}
printf("The Roman Numeral equivalent for the given number is: ");
for (int j = 0; j < i; j++)
printf("%c", c[j]);
}
int main()
{
int number = 2422;
printRoman(number);
return 0;
}
```

Output:

The Roman Numeral equivalent to the given number is: MMCDXXII

### Question: How will you check whether the given string is K-Palindrome or not?

Answer: We will start with finding the longest palindromic subsequence of the given string. If the difference between the aforementioned and the given string is less than or equal to k, then the given string will be k-palindrome, otherwise, it will not be.

We can use the following C++ program to check whether a given string is K-Palindrome or not:

```#include <bits/stdc++.h>
using namespace std;
int lcs( string X, string Y, int m, int n )
{
int L[m + 1][n + 1];
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1] == Y[j - 1])
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = max(L[i - 1][j], L[i][j - 1]);
}
}
return L[m][n];
}
bool isKPal(string str, int k)
{
int n = str.length();
string revStr = str;
reverse(revStr.begin(), revStr.end());
int lps = lcs(str, revStr, n, n);
return (n - lps <= k);
}
int main()
{
string str = "abvcdeca";
int k = 3;
isKPal(str, k) ? cout << "Yes" : cout << "No";
return 0;
}
```

Output:

Yes

### Question: Could you explain how to multiply large numbers represented as strings?

Answer: We will start by multiplying the last digit of the second number with the first number, followed by multiplying the second last digit of the second number with the first number, and adding the two. The process will continue until all digits of the second number are done.

Here’s how to achieve the same in C++:

```#include<bits/stdc++.h>
using namespace std;
string multiply(string num1, string num2)
{
int n1 = num1.size();
int n2 = num2.size();
if (n1 == 0 || n2 == 0)
return "0";
vector result(n1 + n2, 0);
int i_n1 = 0;
int i_n2 = 0;
for (int i=n1-1; i>=0; i--)
{
int carry = 0;
int n1 = num1[i] - '0';
i_n2 = 0;
for (int j=n2-1; j>=0; j--)
{
int n2 = num2[j] - '0';
int sum = n1*n2 + result[i_n1 + i_n2] + carry;
carry = sum/10;
result[i_n1 + i_n2] = sum % 10;
i_n2++;
}
if (carry > 0)
result[i_n1 + i_n2] += carry;
i_n1++;
}
int i = result.size() - 1;
while (i>=0 && result[i] == 0)
i--;
if (i == -1)
return "0";
string s = "";
while (i >= 0)
s += std::to_string(result[i--]);
return s;
}
int main()
{
string str1 = "24224620578";
string str2 = "98055650629857338077";
if((str1.at(0) == '-' || str2.at(0) == '-') &&
(str1.at(0) != '-' || str2.at(0) != '-' ))
cout<<"-";
if(str1.at(0) == '-' && str2.at(0)!='-')
{
str1 = str1.substr(1);
}
else if(str1.at(0) != '-' && str2.at(0) == '-')
{
str2 = str2.substr(1);
}
else if(str1.at(0) == '-' && str2.at(0) == '-')
{
str1 = str1.substr(1);
str2 = str2.substr(1);
}
cout << multiply(str1, str2);
return 0;
}
```

Output:

2375360932037220733184397148506

### Question: How will you check that the sum of 2 elements in an array equal to the given number x?

Answer: We can use the following algorithm for checking whether the sum of 2 elements in an array equals the given number x or not:

• Sort the given array in decreasing order
• Initialize two index variables:
• l = 0 to the leftmost index
• r = ar_size-1 to the rightmost index
• While l<r:
• Return 1, if A[l] + A[r] == sum
• l++, if A[l] + A[r] < sum
• Otherwise r--
• Continue looping step 3 until all elements in the array are exhausted

Here is a C++ program demonstrating the aforementioned approach:

```#include <bits/stdc++.h>
using namespace std;
bool hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
int l, r;
sort(A, A + arr_size);
l = 0;
r = arr_size - 1;
while (l < r)
{
if(A[l] + A[r] == sum)
return 1;
else if(A[l] + A[r] < sum)
l++;
else // A[i] + A[j] > sum
r--;
}
return 0;
}
int main()
{
int A[] = ;
int x = 32;
int arr_size = sizeof(A) / sizeof(A);
if (hasArrayTwoCandidates(A, arr_size, n))
cout << "The array has two elements with the given sum!";
else
cout << "The given array doesn't have two elements with the given sum!";
return 0;
}
```

Output:

The given array has two elements with the given sum!

### Question: You are given an input stream of N integers that you need to insert in a new stream. How will you find the median of the new stream formed by each insertion of x to the new stream?

The Input - The first line of the input contains an integer N that represents the total number of elements in the stream. Next N lines contain integer x that represents the number to be inserted into the stream.

The Output - For each of the element added to the stream print the floor of the new median in a new line.

For the output to be correct we need to follow two constraints;

• N is greater than or equal to 1 and less than or equal to 106
• x is greater than or equal to 1 and less than or equal to 106

An example:

Input:

4 (Number of elements i.e. N)
5*
15*
1*
3*
* = The elements of the stream

The output will be:

5
10
5
4

Explanation:

5 goes to stream -> median 5 (5)
15 goes to stream -> median 10 (5, 15)
1 goes to stream -> median 5 (5, 15, 1)
3 goes to stream -> median 4 (5, 15, 1, 3)

## Conclusion

Looking for more interview questions? This is an excellent udemy course that can prepare you for programming interviews:

Here is a great book with top generic coding questions and answers to help with your preparation:

All the best! #### Shruti Kaushik

Shruti is a professionally accredited content specialist and works closely with brands to identify their disconnect in content marketing, then further strategizing the same. She started pursuing her independent journey as a consultant after leaving her decent 9 to 5 job with Google News as an editor, and have worked withSony, Ministry of Skills and Entrepreneurship Ma Foi Group, TOI, Indochine International, Kakaku, Inc in the past. View all posts by the Author Dnaish Patel 10 Points 