Facebook Interview Question
Country: India
Interview Type: Written Test
Can You Please Explain what are you doing in the above code. BTW I run your code against some other test cases and I didn't get the expected output.
Here are those inputs
Input#00 : 123232111119232333277777999
Output#00: 7 15 6
Input#01:
751283918273129483751265369875938721253256
384982385781251985354664939832887525615625
665211639491598528185935839473825642193794
184375895489172359871654785647324524354639
289887198715265623845821451815818815252738
638451823475832516531656348728374628574593
847652354612753472165281273645987465847536
642387615238749187265876321827635482776859
871628376457165263745196283764872687654782
635987162983654786253476179834691827567647
382964865167234698172658761946256162516256
1527384273482748237482734827348274827
Output#01: 10 262 229
In both the above test cases your code is giving wrong answers.
This seems like an homework assignment, you cannot remember the whole question as is, as a matter of fact even if they ask you such a long question it will take at least 15-20 minutes to get it and then 20 minutes to design a solution and 20 minutes to code it, depends on your typing speed. Stop asking solutions for your assignments.
1. Make a 2D matrix of size n*n where n is length of string
2. fill matrix while matrix[i][j] has sum of all values from i to j. can be done in n2 using bottom up approach of dynamic programming
3. traverse matrix and put all values in hash table. while key is matrix[i][j] and value is (i,j). if already present, append new (i,j) (dont replace)
4. sort hash table key values from high to low
5. for each key in sorted hash key values, get hash value.
6. if hash value has 1 value go to next. else go to step 7
7. for each (i,j) pair, check if any pair exists such that (j1-i1)==(j2-i2) and they are not overlapping. if exists. return with this pair
def fillMatrix(numList):
solnMatrix = Array2D(len(numList),len(numList))
totalSum=sumOfArray(numList,0,len(numList)-1)
for outIndex in range(len(numList)):
for inIndex in range(len(numList)):
if (outIndex==inIndex):
solnMatrix[outIndex,inIndex]=numList[inIndex]
if (outIndex>inIndex):
solnMatrix[outIndex,inIndex]=-1
if(outIndex<inIndex):
solnMatrix[outIndex,inIndex]=solnMatrix[outIndex,inIndex-1]+numList[inIndex]
return solnMatrix
def makeHashTable(numList):
hashTable = dict()
solnMatrix= fillMatrix(numList)
for outIndex in range(len(numList)):
for inIndex in range(len(numList)):
if (inIndex>=outIndex):
if solnMatrix[outIndex,inIndex] in hashTable.keys():
hashTable[solnMatrix[outIndex,inIndex]].append((outIndex,inIndex))
else:
hashTable[solnMatrix[outIndex,inIndex]]=list()
hashTable[solnMatrix[outIndex,inIndex]].append((outIndex,inIndex))
return hashTable
def getSortedHashKeys(hashTable):
keyList = list()
for key in hashTable.keys():
keyList.append(key)
return sorted(keyList,reverse=True)
def isNonOverlappingSet(set1,set2):
if set1[0]<set2[0]:
if set1[1]<set2[0]:
return True
else:
return False
if set1[0]>set2[0]:
if set2[1]<set1[0]:
return True
else:
return False
def isFit(set1,set2):
set1Len = set1[1]-set1[0]
set2Len = set2[1]-set2[0]
if set1Len==set2Len:
if isNonOverlappingSet(set1,set2):
return True
return False
def isNonOverlappingSetList(setList):
listLen = len(setList)
for outIndex in range(listLen-1):
for inIndex in range(outIndex+1,listLen):
if isFit(setList[outIndex],setList[inIndex])==True:
return ((setList[outIndex][0],setList[outIndex][1],setList[inIndex][0],setList[inIndex][1]))
return False
def finalCode(numList):
myHash = makeHashTable(numList)
sortedKeys = getSortedHashKeys(myHash)
for key in sortedKeys:
hasedVal = myHash[key]
found = isNonOverlappingSetList(hasedVal)
if found!=False:
return found
return False
There are some scopes for optimizing code. But approach will be same. If any one finds optimization, please comment
for your example 131251141231... there are two sets... (1312 and 1231) and (1312 abd 1141)
def fillMatrix(numList):
solnMatrix = Array2D(len(numList),len(numList))
totalSum=sumOfArray(numList,0,len(numList)-1)
for outIndex in range(len(numList)):
for inIndex in range(len(numList)):
if (outIndex==inIndex):
solnMatrix[outIndex,inIndex]=numList[inIndex]
if (outIndex>inIndex):
solnMatrix[outIndex,inIndex]=-1
if(outIndex<inIndex):
solnMatrix[outIndex,inIndex]=solnMatrix[outIndex,inIndex-1]+numList[inIndex]
return solnMatrix
def makeHashTable(numList):
hashTable = dict()
solnMatrix= fillMatrix(numList)
for outIndex in range(len(numList)):
for inIndex in range(len(numList)):
if (inIndex>=outIndex):
if solnMatrix[outIndex,inIndex] in hashTable.keys():
hashTable[solnMatrix[outIndex,inIndex]].append((outIndex,inIndex))
else:
hashTable[solnMatrix[outIndex,inIndex]]=list()
hashTable[solnMatrix[outIndex,inIndex]].append((outIndex,inIndex))
return hashTable
def getSortedHashKeys(hashTable):
keyList = list()
for key in hashTable.keys():
keyList.append(key)
return sorted(keyList,reverse=True)
def isNonOverlappingSet(set1,set2):
if set1[0]<set2[0]:
if set1[1]<set2[0]:
return True
else:
return False
if set1[0]>set2[0]:
if set2[1]<set1[0]:
return True
else:
return False
def isFit(set1,set2):
set1Len = set1[1]-set1[0]
set2Len = set2[1]-set2[0]
if set1Len==set2Len:
if isNonOverlappingSet(set1,set2):
return True
return False
def isNonOverlappingSetList(setList):
listLen = len(setList)
for outIndex in range(listLen-1):
for inIndex in range(outIndex+1,listLen):
if isFit(setList[outIndex],setList[inIndex])==True:
return ((setList[outIndex][0],setList[outIndex][1],setList[inIndex][0],setList[inIndex][1]))
return False
def finalCode(numList):
myHash = makeHashTable(numList)
sortedKeys = getSortedHashKeys(myHash)
for key in sortedKeys:
hasedVal = myHash[key]
found = isNonOverlappingSetList(hasedVal)
if found!=False:
return found
return False
Here is my code:
#include <stdio.h>
#include <stdlib.h>
static void centerweight2(unsigned int *wsum, unsigned int *asum, int len)
{
int count1,count2,count3;
int found;
if(2>len)
return;
count1=len>> 1;
for(found=0;count1;count1--)
{
for(count2=0;count2+(count1<< 1)<=len;count2++)
{
int leftwsum=wsum[count2+count1-1]-wsum[count2-1];
int leftasum1=(asum[count2+count1-1]-asum[count2-1])-leftwsum*count2;
int leftasum2=(count1+1)*leftwsum-leftasum1;
for(count3=count2+count1;count3<=len-count1;count3++)
{
int rightwsum=wsum[count3+count1-1]-wsum[count3-1];
int rightasum1=(asum[count3+count1-1]-asum[count3-1])-rightwsum*count3;
int rightasum2=(count1+1)*rightwsum-rightasum1;
int temp=(leftwsum+rightwsum)*(1+(count1<< 1))-(count1<< 1)*rightwsum;
if(((leftasum1+rightasum1)<< 1)==temp||
((leftasum1+rightasum2)<< 1)==temp||
((leftasum2+rightasum1)<< 1)==temp||
((leftasum2+rightasum2)<< 1)==temp)
{
found=1;
break;
}
}
if(found) break;
}
if(found) break;
}
if(count1)
printf("%d %d %d \n", count2, count3, count1);
else
printf("found non\n");
}
void centerweight(char*p)
{
unsigned int *wsum, *asum;
int count;
int count2;
if(NULL==p)
return;
if(!*p)
return;
wsum=malloc(sizeof(unsigned int)*501);
if(NULL==wsum)
return;
asum=malloc(sizeof(unsigned int)*501);
if(NULL==asum)
{free(wsum); return;}
asum[0]=0;
wsum[0]=0;
for(count=1;*p;count++, p++)
{
int temp;
temp=*p-'0';
if(temp>9||temp<0||count> 500)
{
free(asum);
free(wsum);
return;
}
asum[count]=asum[count-1]+temp*(count);
wsum[count]=wsum[count-1]+temp;
}
centerweight2(wsum+1, asum+1, count-1);
free(wsum);
free(asum);
}
Here is the test code:
int main()
{
char p1[]="41111921111119";
char p2[]="131251141231";
char p3[]="11";
char p4[]="123232111119232333277777999";
char p5[]="751283918273129483751265369875938721253256384982385781251985354664939832887525615625665211639491598528185935839473825642193794184375895489172359871654785647324524354639289887198715265623845821451815818815252738638451823475832516531656348728374628574593847652354612753472165281273645987465847536642387615238749187265876321827635482776859871628376457165263745196283764872687654782635987162983654786253476179834691827567647382964865167234698172658761946256162516256152738427348274823748273482734827482";
centerweight(p1);
centerweight(p2);
centerweight(p3);
centerweight(p4);
centerweight(p5);
}
The idea is as bellow:
1> Use wsum to contain the accumulated weight from start to end.
2> Use asum to contain the accumulated weight*distance from start to the end.
3> For each sub pieces in the string, n to m,
its subweight=wsum[m]-wsum[n-1];
subwegith*length=asum[m]-asum[n-1]-n*subweight.
4> For each pair of same length sub string, you check its four combination to see they could be central weight. Use some algebra you avoid the dividing since dividing may case some floating, and you can under stand the logic.
5> Finally, the search will go from longest string to shortest one to get the goal as soon as possible. There could be some alternative same length combination, but we terminated here immediately.
6> The int is used for computation, i guess would be good enough for 500. If not, we can use long long.
I got the basic idea quickly, but the implementation, especially the integer version of checking cost me quite a time until i sit to check the algebra totally clear. Thanks for the good test vector provided by the guy.
I didn't test this code, but it should be simple to understand.
The question is really asking if there're two same sized continuous segments that has the same sum. so:
1. construct a table T[n/2][n] // longest segment is half the size
2. T[i][j] stores the weight of the segment starting at j, with size i
3. fill the table
4. searching from the last row (longest), if in the array T[i] there are two segment of the same weight, say T[i][k] and T[i][l], return k (first segment start), l (second segment start) and i (length).
Here's the code which I wrote without testing:
// assume it's easy to convert string into int array
void GetStaff(int A[], int N)
{
int *T = new int[N/2][N];
for (int i = 0; i < N/2; i++)
memset(T[i], 0, N);
// build table
for (int i = 0; i < N/2; i++)
{
for (int j = 0; j < (N - (i-1)); j++)
{
// sum of weights for length i
int s = 0;
for (int k = 0; k < i; k++)
{
s += B[j+k];
}
T[i][j] = s;
}
}
// check
for (int i = N/2-1; i >= 0; i--)
{
int *t = T[i];
int k = 0;
while (T[k] > 0) {
int l = k;
while (T[l] > 0) {
if (T[k] == T[l]) {
// found
cout << k << " " << l << " " << i << endl;
}
}
}
}
ok, maybe I don't need to build the full table... just start checking from the N/2 size.
Move a summing box (window) throw the input digit array.
Start with max possible window size=N/2 and decrement it on the next step.
public static void main(String[] args) {
// 41111921111119
// 11119 11119
// 131251141231
// 1312 1231
String input = "41111921111119";
int[] digits = stringToIntArray(input);
StaffInfo staff = findLongestStaff(digits);
System.out.println(staff == null ? "no staff found" : staff);
if (staff != null) {
printStaff(digits, staff.from1, staff.wsize);
printStaff(digits, staff.from2, staff.wsize);
}
}
private static void printStaff(int[] digits, int from, int wsize) {
System.out.println(Arrays.toString(Arrays.copyOfRange(digits, from, from + wsize)));
}
private static int[] stringToIntArray(String input) {
int[] digits = new int[input.length()];
for (char i = 0; i < input.length(); i++) {
int digit = input.charAt(i) - '0';
if (digit < 0 || digit > 9) {
throw new IllegalArgumentException("not a digit, ch=" + input.charAt(i));
}
digits[i] = digit;
}
System.out.println(Arrays.toString(digits));
return digits;
}
private static StaffInfo findLongestStaff(int[] digits) {
int count = 0;
// try to find from max possible window of pieces
for (int wsize = digits.length / 2; wsize > 1; wsize--, count++) {
// move 1st window
int sum1 = 0;
for (int from1 = 0; from1 <= digits.length - wsize * 2; from1++, count++) {
if (from1 == 0) {
// calc start sum
sum1 = getSumForWindow(digits, from1, wsize);
} else {
// move prev sum for 1 piece
sum1 = moveSumForWindow(digits, from1 - 1, wsize, sum1);
}
// move 2nd window
int sum2 = 0;
for (int from2 = from1 + wsize; from2 <= digits.length - wsize; from2++, count++) {
if (from2 == from1 + wsize) {
// calc start sum
sum2 = getSumForWindow(digits, from2, wsize);
} else {
// move prev sum for 1 piece
sum2 = moveSumForWindow(digits, from2 - 1, wsize, sum2);
}
// stop when find window of pieces with the same length
if (sum1 == sum2) {
System.out.println("center weight, digits.length=" + digits.length + ", iterations count=" + count);
return new StaffInfo(from1, from2, wsize);
}
}
}
}
System.out.println("digits.length=" + digits.length + ", iterations count=" + count);
return null;
}
private static int getSumForWindow(int[] digits, int from, int wsize) {
int sum = 0;
for (int i = from; i < from + wsize; i++) {
sum = sum + digits[i];
}
return sum;
}
private static int moveSumForWindow(int[] digits, int from, int wsize, int sum) {
int movedSum = sum - digits[from] + digits[from + wsize];
return movedSum;
}
Maybe this, in Python:
- Jerry K February 25, 2013