## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

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

Create a matrix that stores the centre of gravity for all i<=j. cg(i,j) = weighted sum from i to j. Not that c(i,j) is a number between [0, (j-i)]. Now, start iterating over the matrix, while inserting c(i,j) in the set and check if the set already has c(i,j) or (j-i)-c(i,j) (inverted staff section) and update the max_length seen so far (=j-i). This is because you can contruct final staff with two sections [i,j] and [p,q] if j-i == q-p, c(i,j) == c(p,q) or p - q - c(p,q).

Time complexity: O(n^2) constructing and traversing cg matrix
Space complexity: O(n^2) for matrix and Set

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

Create a matrix that stores the centre of gravity for all i<=j. cg(i,j) = weighted sum from i to j. Not that c(i,j) is a number between [0, (j-i)]. Now, start iterating over the matrix, while inserting c(i,j) in the set and check if the set already has c(i,j) or (j-i)-c(i,j) (inverted staff section) and update the max_length seen so far (=j-i). This is because you can contruct final staff with two sections [i,j] and [p,q]
-- if p>j
-- if j-i == q-p,
-- if c(i,j) == c(p,q) or p - q - c(p,q).

Time complexity: O(n^2) constructing and traversing cg matrix
Space complexity: O(n^2) for matrix and Set

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

Excellent! I used your method and verified with the two sequences in the problem description.

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

The base idea is good but first, if you store c(i,j) values in a set then you won't know the start and end of the section that value belongs to, second, every time you check whether there was already a section with the same center of gravity, the number of possible candidates is more than 1 thus overall time complexity is not O(n^2) rather O(n^4).

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

You can solve this be creating a weight grid.
w[0][0] .. w[0][n] contains will be mass of n sections.
w[1][0] = w[0][0] + w[0][1]
w[1][1] = w[0][1] + w[0][2]
.....
w[i][j] = w[i-1][j] + w[0][j+i]

where w[i][j] represents wt of section j + j+1... + j+i.
i will vary from 0 to n/2.

Now start traversing weight grid row by row starting from i=n/2.
If you find two weights weights in row which are non overlapping, return it otherwise go to lower row.

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

O(N^4)

for l = N/2 downto 0
pick N^2 possible combination of subarray
calculate if ballance is in hte middle.

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

``````#include <stdlib.h>
#include <stdio.h>

void reverse(int *st, int len)
{
int i,tmp;

for(i=0; i<len/2; i++) {
tmp = st[i];
st[i] = st[len - 1 - i];
st[len - 1 -i] = tmp;
}
}

int balanced(int *s1, int *s2, int len)
{
float sum, w_sum;
int i, tlen = len*2;

sum = 0;
w_sum = 0;
for(i=0;i<tlen;i++) {
if(i < len) {
sum += s1[i];
w_sum += (i+1)*s1[i];
} else {
sum += s2[i - len];
w_sum += (i+1)*s2[i - len];
}
}

printf("s1 ");
for(i=0;i<len;i++) {
printf("%d ", s1[i]);
}

printf(" s2 ");
for(i=0;i<len;i++) {
printf("%d ", s2[i]);
}

if (sum == 0) {
printf("all 0s\n");
return(0);
} else {
w_sum = w_sum/sum;
printf("balanced weighted center:%7.2f\n", w_sum);

if (w_sum == len + 0.5) {
return(1);
}
}

return(0);
}

int *int_dup(int *s, int len)
{
int *s2 = malloc(len*sizeof(int));
if(!s2) {
printf(":ut of mem\n");
exit(0);
}
memcpy(s2, s, len*sizeof(int));
return(s2);
}

int can_balance(int *s1, int *s2, int len) {
int rc;
int *st1, *st2;

rc = balanced(s1, s2, len);
if(rc) {
return(rc);
}
st1 = int_dup(s1, len);
reverse(st1,len);
rc = balanced(st1, s2, len);
if(rc) {
free(st1);
return(rc);
}

st2 = int_dup(s2, len);
reverse(st2, len);
rc = balanced(s1, st2, len);
if(rc) {
free(st1);
return(rc);
}

rc = balanced(st1, st2, len);
free(st1);
free(st2);
return(rc);

}

//center of the gravity of each str should be of
//same distance from the middle, or one end
//len must be no more than half of strlen(str);
int cut_staff (int *str, int *stf1, int *stf2, int *plen)
{
int slen, p1, p2, tlen;
int *s1, *s2;

tlen = *plen;
slen =  tlen/2;

for (;slen>1; slen--) {
printf("\nslen = %d\n",slen);
for(p1 = 0; p1 <= tlen - 2*slen; p1++){
s1 = &str[p1];
for(p2 = p1 + slen; p2 <= tlen - slen; p2++) {
s2 = &str[p2];
if(can_balance(s1, s2, slen)) {
*stf1 = p1;
*stf2 = p2;
*plen = slen;
return(0);
}
printf("\n");
}//p2
}//p1
}//slen

return(-1);
}

int main(int argc, char **argv) {
int pos1, pos2, len,rc;

int branch[12] = {1,3,1,2,5,1,1,4,1,2,3,1};

len = 12;
rc = cut_staff(branch, &pos1, &pos2, &len);
if(rc < 0) {
printf("Sorry, we are not able to cut a staff from this branch\n");
return(0);
}
printf("the two staffs of len %d are from pos %d and %d\n", len, pos1, pos2);
return(1);
}``````

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

``````import java.io.BufferedReader;
import java.io.IOException;

class Solution {

void check(String s) {

int fullLength = s.length();

int slider = fullLength/2;

while(slider > 0) {

for(int i = 0, s1Index = i+slider;
slider > 0 && s1Index < (fullLength-2);
i++, s1Index = i+slider) {

String s1 = "";
String s2 = "";

s1 = s.substring(i, s1Index);

for(int j = (i+slider), s2Index = (j + slider);
j < (fullLength-1) && s2Index <= fullLength;
j++, s2Index = (j + slider)) {

s2 = s.substring( j, s2Index);

boolean result = calcSum(s1, s2);
if(!result) {
result = calcSum(s2, s1);
}
if(result) {
System.out.println( i + " " + j +" " + slider);
return;
}
}

}
slider--;
}
}

boolean testWAvg(int count, double wavg) {
if(wavg == ((double)(count+1)/2)) return true;
return false;
}

boolean calcSum(String s1, String s2) {

String s = s1 + s2;
final int N = s.length();
int[] arr = new int[N];

for(int i=0; i < N; i++) {
arr[i] = Integer.parseInt(s.substring(i,i+1));

}

int total = 0;
for(int i = 0; i < N; i++) {
total += arr[i];
}

int wsum = 0;
for(int i=1; i <= N; i++) {
wsum += i * arr[i-1];
}

return testWAvg(s.length(), ((double)wsum/total));
}

public static void main(String[] args) throws IOException {
Solution sm = new Solution();

sm.check(line);

//		sm.check("123232111119232333277777999");
//		sm.check("7512839182731294837512653698759387212532563849823857812519853546649398328875256156256652116394915985281859358394738256421937941843758954891723598716547856473245243546392898871987152656238458214518158188152527386384518234758325165316563487283746285745938476523546127534721652812736459874658475366423876152387491872658763218276354827768598716283764571652637451962837648726876547826359871629836547862534761798346918275676473829648651672346981726587619462561625162561527384273482748237482734827348274827");

}
}``````

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

The solution:
all permutations and combinations are done on INDICES not on items such that we can return the index at the end of the program

My solution is highly inefficient and can be improved, but this gives you an idea.

Find all combinations of even length
for each combination above find all permutation
for each permutation check if the staff is valid
if staff valid check if it is longer then previous one
if longer than save length, 0 index of the permutation and len/2 index of the permutation

``````from itertools import permutations, combinations

def is_staff_valid(staff):
if len(staff) % 2 != 0:
return False

i = 1
reg_sum = w_sum = float(0)

while i <= len(staff):
w_sum += i * staff[i - 1]
reg_sum += staff[i - 1]
i += 1

center_of_mass = w_sum / reg_sum
expected_center_of_mass = (float(i)) / 2.0
if center_of_mass == expected_center_of_mass:
return True
return False

def make_a_staff(indices, bamboo):
staff = list()
for index in indices:
staff.append(bamboo[index])
return staff

def return_longest_valid_staff(bamboo):
bamboo_len = len(bamboo)
max_len = 0
sindex = 0
s2index = 0
indices = xrange(0, bamboo_len)
for group_size in range(1, bamboo_len + 1):
for combination in combinations(indices, group_size):
perms = permutations(combination)
for perm in perms:
staff_to_verify = make_a_staff(perm, bamboo)
if is_staff_valid(staff_to_verify):
if len(staff_to_verify) > max_len:
max_len = len(staff_to_verify)
sindex = perm[0]
s2index = perm[len(perm)/2]
print "{0},{1},{2}".format(max_len, sindex, s2index)

bambooo = [1,3,1,2,5,1,1,4,1,2,3,1]

return_longest_valid_staff(bambooo)``````

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

Slightly improvised version which uses combination of Even length only and starts from the biggest groups instead of going up.

early version : would go 1 12 122 1221
This version would go 1221 break

``````def return_longest_valid_staff(bamboo):
bamboo_len = len(bamboo)
max_len = 0
sindex = 0
s2index = 0
indices = xrange(0, bamboo_len)
bamboo_combinations = [x for x in xrange(1, bamboo_len + 1) if x % 2 == 0]
for group_size in bamboo_combinations[::-1]:
for combination in combinations(indices, group_size):
perms = permutations(combination)
for perm in perms:
staff_to_verify = make_a_staff(perm, bamboo)
if is_staff_valid(staff_to_verify):
if len(staff_to_verify) > max_len:
max_len = len(staff_to_verify)
sindex = perm[0]
s2index = perm[len(perm)/2]
break
print "{0},{1},{2}".format(max_len, sindex, s2index)``````

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

``````package facebook;

import org.junit.Test;

import java.util.Arrays;

import static org.junit.Assert.*;

public class Staff {
public static final double OMEGA = 0.000000001d;

@Test
public void test() {
assertArrayEquals(new int[]{1, 9, 5}, findLongestStaff("41111921111119"));
assertArrayEquals(new int[]{0, 8, 4}, findLongestStaff("131251141231"));
}
private static int[] findLongestStaff(String s) {
return findLongestStaff(toIntArray(s));
}

private static int[] toIntArray(String s) {
int[] res = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
res[i] = s.charAt(i) - '0';
}
return res;
}

private static int[] findLongestStaff(int[] c) {
for (int len = c.length / 2; len > 0; len--) {
int elemCount = c.length - len + 1;

int[][] a = new int[3][elemCount];
for (int i = 0; i < len; i++) {
a[0][0] += c[i] * (i + 1);
a[1][0] += c[len - i - 1] * (i + 1);
a[2][0] += c[i];
}
for (int i = 1; i < elemCount; i++) {
a[0][i] = a[0][i - 1] - a[2][i - 1] + c[i + len - 1] * len;
a[1][i] = a[1][i - 1] + a[2][i - 1] - c[i - 1] * (len + 1) + c[i + len - 1];
a[2][i] = a[2][i - 1] - c[i - 1] + c[i + len - 1];
}

double[][] w = new double[2][elemCount];
for (int i = 0; i < elemCount; i++) {
w[0][i] = (double) a[0][i] / a[2][i];
w[1][i] = (double) a[1][i] / a[2][i];
}

for (int i = 0; i <= elemCount - len; i++) {
for (int j = i + len; j < elemCount; j++) {
if (Math.abs(w[0][i] - w[0][j]) < OMEGA
|| Math.abs(w[1][i] - w[0][j]) < OMEGA
|| Math.abs(w[0][i] - w[1][j]) < OMEGA
|| Math.abs(w[1][i] - w[1][j]) < OMEGA
) {
return new int[]{i, j, len};
}
}
}
}
return null;
}
}``````

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

Iterate for each valid two start of staves and each valid stave length. Start from bigger length to smaller though. During iteration store sum, weighted sum, and weighted sum of reverse in matrices. So, the calculation requires iteration only at edges and can be computed otherwise in constant time. Time complexity : O(n^3), Space complexity O(n^2):

``````//staff.h:
#include <iostream>
#include <string>
#include <vector>

class Staff
{
size_t pos0;
size_t pos1;
size_t len;
std::string str;
bool reverse;
std::vector<std::vector<size_t> > sum;	//sum for a postion with a length [postion][length]
std::vector<std::vector<size_t> > weighted_sum;	//weighted sum for a postion with a length [postion][length]
std::vector<std::vector<size_t> > reverse_weighted_sum;	//if the sequence is reversed, weighted sum
// for a postion with a length [postion][length]
bool mass_center();
void max();
public:
operator bool() const;
Staff(const string m_str);
Staff(const Staff& staff);

friend ostream& operator<<(ostream& stream, const Staff& a);
};
std::ostream& operator<<(std::ostream& stream, const Staff& a);

//staff.cc:
#include <string>
#include <cassert>

using namespace std;

#include "staff.h"

ostream& operator<<(ostream& stream, const Staff& a)
{
if (a)
stream<< a.pos0<< " "<< a.pos1<< " "<< a.len;
else
cout<< "No Staff"<< endl;
return stream;
}
Staff::Staff(const string m_str): pos0(0), pos1(0), len(0), str(m_str)
, sum(m_str.length(), vector<size_t>(m_str.length())), weighted_sum(m_str.length(), vector<size_t>(m_str.length())),
reverse_weighted_sum(m_str.length(), vector<size_t>(m_str.length()))
{
max();
}
Staff::Staff(const Staff& staff): pos0(staff.pos0), pos1(staff.pos1), len(staff.len),
str(staff.str), reverse(staff.reverse)
{}
Staff::operator bool() const
{
return pos1 && len;
}
bool Staff::mass_center()
{
if (len == str.length() / 2 || pos1 + len == str.length())
{
sum[pos0][len]= 0;
sum[pos1][len]= 0;
weighted_sum[pos0][len]= 0;
weighted_sum[pos1][len]= 0;
reverse_weighted_sum[pos0][len]= 0;
reverse_weighted_sum[pos1][len]= 0;
for(size_t d= 1; d<= len; d++)
{
int m= str[pos0 + d - 1] - '0';
int m1= str[pos1 + d - 1] - '0';
sum[pos0][len]+= m;
sum[pos1][len]+= m1;
weighted_sum[pos0][len]+= m * d;
weighted_sum[pos1][len]+= m1 * (d + len);
reverse_weighted_sum[pos0][len]+= m * (len - d + 1);
reverse_weighted_sum[pos1][len]+= m1 * (2 * len - d + 1);
}
}
else
{
int m= str[pos0 + len] - '0';	// number just after this stave
int m1= str[pos1 + len ] - '0';
int prev_len= len + 1;
int d= 1;
sum[pos0][len]= sum[pos0][prev_len] - m;
sum[pos1][len]= sum[pos1][prev_len] - m1;
weighted_sum[pos0][len]= weighted_sum[pos0][prev_len] - m * d;
weighted_sum[pos1][len]= weighted_sum[pos1][prev_len] - m1 * (d + prev_len);
reverse_weighted_sum[pos0][len]= reverse_weighted_sum[pos0][prev_len] - m * (prev_len - d + 1);
reverse_weighted_sum[pos1][len]= reverse_weighted_sum[pos1][prev_len] - m1 * (2 * prev_len - d + 1);
}
int whole_sum= sum[pos0][len] + sum[pos1][len];
float center= (float)(weighted_sum[pos0][len] + weighted_sum[pos1][len]) / whole_sum;
float center1= (float)(reverse_weighted_sum[pos0][len] + weighted_sum[pos1][len]) / whole_sum;
float ideal_center= len + .5;
if (center == ideal_center /*< 0.000000000001*/)
{
reverse= false;
return true;
}
else if (center1 == ideal_center /*< 0.000000000001*/)
{
reverse= true;
return true;
}
else
return false;
}
void Staff::max()
{
Staff max_staff(*this);
size_t str_len= str.length();
for(pos0= 0; pos0< str_len; pos0++)
{
for(len= (str_len - pos0)/ 2; len>= 1 && max_staff.len< len; len--)
{
for(pos1= pos0+ len; pos1< str_len - len + 1; pos1++)
{
if (pos0 == 0 && pos1 == 8 && len == 4)
cout<< len<< endl;
if (mass_center() && max_staff.len< len)
{
//printf("\tpos0 %d pos1 %d len %d reverse %d\n", pos0, pos1, len, reverse);
max_staff= *this;
break;
}
}
}
}
*this= max_staff;
}

int main(int argc, char* argv[])
{
/*123456789 1234*/
Staff a("41111921111119");
cout<< a<< endl;
Staff a1("131251141231");
cout<< a1<< endl;
}``````

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

Every possible candidate for the staff can be recognized by the tuple (mass , <i>.mass), where <i>.mass is the product of index vector and the mass vector, just like stated in the question.Lets call this tuple profile of the candidate.
Now, given a candidate, its other half will either have the same profile, or the profile with same mass, but the dot product as <i>.reverse(mass). So, iterate through all such candidates, store their profile in a list of dictionaries(dicts based on profile tuple) and return the pair with max length. Here is a simple implementation in python.

``````def com(mass):
pos = 0
m = 0
n = len(mass)
for i in xrange(n):
x = int(mass[i])
m += x
pos += x*i
return (m,pos)
def get_staff(mass):
n = len(mass)
lookup = [{} for x in xrange(n/2+1)]

max_len = 0
max_val = None
for i in xrange(n):
for j in xrange(i+1 , n+1):
l = j-i
if l>n/2 : break
cg = com(mass[i:j])
comp_cg = com(mass[j-1:i+1:-1])

if cg in lookup[l]:
x = lookup[l][cg][0]
y = lookup[l][cg][1]
if max_len<l and (x<i or x>j) and (y<i or y>j):
max_val = (mass[i:j] , mass[x:y])
max_len = l

if comp_cg in lookup[l]:
x = lookup[l][comp_cg][0]
y = lookup[l][comp_cg][1]
if max_len<l and (x<i or x>j) and (y<i or y>j):
max_val = (mass[i:j] , mass[x:y])
max_len = l

lookup[l][cg] = (i,j)

return max_val

print get_staff("9913125114123199")``````

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

``````#include <iostream>
#include <stdlib.h>

int main()
{
const uint L = 12;
const uint branch[L] = {1,3,1,2,5,1,1,4,1,2,3,1};
uint mass0, mass1;
double cog0, cog1;
for (int i = L - 2; i >= 0; i--) {
const uint len = i+1;
for (uint j = 0; j < (L - i); j++) {
mass0 = cog0 = 0;
for (uint m = 0; m < len; m++) {
mass0 += branch[j+m];
cog0 += m * branch[j+m];
}
cog0 /= mass0;
for (uint k = j + 1; k < (L - i); k++) {
mass1 = cog1 = 0;
for (uint m = 0; m < len; m++) {
mass1 += branch[k+m];
cog1 += m * branch[k+m];
}
cog1 /= mass1;

if (mass0 == mass1 && (cog0 == cog1 || cog0 == (len + 1 - cog1)) && k - j >= len) {
std::cout << j << " " << k << " " << len << std::endl;
return 0;
}
}
}
}
std::cout << "No match found" << std::endl;

return 0;
}``````

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

``````// took 27 minutes

import java.util.Arrays;
import java.util.List;

public class MartialArtsStaff {

public MartialArtsStaff() {
}

/**
* result: leftStart, rightStart, L
*/
public List<Integer> getCutsWithMaxBalancedStaff(int[] a){
int maxLength = 0;
if(a != null){
int n = a.length;

int leftStart = -1, rightStart = -1;
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
int wl = 0, wr = 0;
double coml = 0, comr = 0;
int limit = j-i;
if(j+limit >= n){
limit = n-j;
}
for(int l = 0; l < limit; l++){
wl += a[i+l];
wr += a[j+l];
coml += a[i+l]*(l+1);
comr += a[j+l]*(l+1);

if(l+1 > maxLength){
if(wl == wr){
//System.out.println("DEBUG " + i + " " + j + " " + l + " " + wl);
if(coml == comr || coml == (wl*(l+1) - comr)){
maxLength = l+1;
leftStart = i;
rightStart = j;
}
}
}
}
}
}

}
if(maxLength == 0){
}
return res;
}

public static void main(String[] args){
MartialArtsStaff wrapper = new MartialArtsStaff();

int[] testcase = {1,3,1,2,5,1,1,4,1,2,3,1};

List<Integer> res = wrapper.getCutsWithMaxBalancedStaff(testcase);
System.out.println(Arrays.toString(testcase));

System.out.println(res.get(0) + " " + res.get(1) + " " + res.get(2));
}
}``````

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

O(n^3) time and O(n) space

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

Just save the matrix c(i,j)= sum(a[i]..a[j]) where "a" is the original array. c(i,j) can be computed in O(n^2) time.

The just for each tuple (i,j) check whether c(i,j) = c(j+1,j+1+j-i) find the one with max(j-i)

Total time and space complexity O(n^2)

is anyone has a n.log(n) solution?

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.

### 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.