Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Written Test
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
Excellent! I used your method and verified with the two sequences in the problem description.
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).
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.
#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);
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
sm.check(line);
// sm.check("123232111119232333277777999");
// sm.check("7512839182731294837512653698759387212532563849823857812519853546649398328875256156256652116394915985281859358394738256421937941843758954891723598716547856473245243546392898871987152656238458214518158188152527386384518234758325165316563487283746285745938476523546127534721652812736459874658475366423876152387491872658763218276354827768598716283764571652637451962837648726876547826359871629836547862534761798346918275676473829648651672346981726587619462561625162561527384273482748237482734827348274827");
}
}
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)
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)
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;
}
}
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;
}
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")
#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;
}
// took 27 minutes
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class MartialArtsStaff {
public MartialArtsStaff() {
}
/**
* result: leftStart, rightStart, L
*/
public List<Integer> getCutsWithMaxBalancedStaff(int[] a){
List<Integer> res = new LinkedList<Integer>();
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;
}
}
}
}
}
}
res.add(leftStart);
res.add(rightStart);
res.add(maxLength);
}
if(maxLength == 0){
res.add(0); res.add(0); res.add(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));
}
}
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).
- Anonymous August 08, 2014Time complexity: O(n^2) constructing and traversing cg matrix
Space complexity: O(n^2) for matrix and Set