## Facebook Interview Question for SDE1s

• 0

Country: United States

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

Well... You can find out that if there are less then 10 segments, each segment number will spend 5 characters. If there more then 9 segments, then first 9 will spend 6 characters and next (up to 90) will spend 7 characters. And so on. This leads us to next table of segmentation tests length:
- 5*9 (up to 9 segments)
- 6*9 + 7*90 (up to 99 segments)
- 7*9 + 8*90 + 9*900 (up to 999 segments)
- 8*9 + 9*90 + 10*900 + 11*9000 (up to 9999 segments)
Also you should take into account that it should be true: k-segment.length > 0, just to have at least 1 character for actual test in segment.
So in total you need to have two arrays:
- segments lengths
- base - how many segments with such segment length
Update those values on each iteration while your string length will not fit number of segments of k-segment.length == 0 (that means it is impossible to build such segmentation).
I assume that if it is impossible to build such segmentation - program will return -1:

``````private static int numberOfSegments(String str, int k) {
List<Integer> segLens = new ArrayList<Integer>();
List<Integer> bases = new ArrayList<Integer>();

while(k-segLens.get(segLens.size()-1)>0) {
int length = str.length();
int i, segments=0;
for(i=0;i<segLens.size()-1;i++) {
length-=(k-segLens.get(i))*bases.get(i);
segments+=bases.get(i);
}
if(length <= (k-segLens.get(i))*bases.get(i)) {
segments+=(length + k-segLens.get(i)-1)/(k-segLens.get(i));
return segments;
}
for(int j=0;j<segLens.size();j++)
segLens.set(j, segLens.get(j)+1);
}
return -1;
}

private static void doTest(String str, int k, int expectedSegments) {
int segments = numberOfSegments(str, k);
System.out.println(str+"\t"+expectedSegments+"\t"+segments);
}

public static void main(String[] args) {
doTest("That is a cat",8,5);
doTest("That is a cat and this is a dog",9,8);
doTest("That is a cat and this is a dog",8,22);
doTest("That is a cat and this is a dog",7,-1);
}``````

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

O(log n * log n) time, O(1) space, where n is size of the text to split.

``````#include <iostream>
#include <string>

using namespace std;

int SuffixesSize(int n)
{
int size = n * (3 + to_string(n).size());
int top = 9;
while (n > 0) {
size += n;
n -= top;
top *= 10;
}
return size;
}

int Cut(int text_size, int k)
{
int l = 1;
int r = text_size;

int best_blockes_count = -1;
int best_delta = numeric_limits<int>::max();

while (l <= r) {
int blocks_count = (l + r) / 2;
int split_text_size = SuffixesSize(blocks_count) + text_size;
if (split_text_size > (blocks_count - 1) * k &&
split_text_size <= blocks_count * k)
{
int delta = blocks_count * k - split_text_size;
if (delta < best_delta) {
best_blockes_count = blocks_count;
}
}
if (split_text_size > blocks_count * k) {
l = blocks_count + 1;
} else {
r = blocks_count - 1;
}
}
return best_blockes_count;
}

int main()
{
cout << Cut(18, 10) << "\n";	// 4
cout << Cut(13, 8) << "\n";		// 5
cout << Cut(31, 9) << "\n";		// 8
cout << Cut(31, 8) << "\n";		// 22
cout << Cut(31, 7) << "\n";		// -1

}``````

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

@Matviy Ilyashenko. "That is a cat and this is a dog",8 gets split into 22 pieces, not 11.

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

the word itself should not be split to 2 lines

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

@xinlf. If we need to observe word breaking, it looks like minimum O(n) time. For O(n), we can just actually try to split the text. For each block we know it's size and we know how long the suffix is. Looks too easy for an FB question.

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

import java.util.*;

class StringSegmentation {

static String[] getSegments(String string, int segmentLength) {
ArrayList < String > ls = new ArrayList < String > ();
int startIndex = 0;
int count = 1;
int length = string.length();

while (startIndex < length) {
if (count < 10) {
} else if (count < 100) {
}
int endIndex = startIndex + segmentLength - additionalLength;
String seg;
try {
seg = string.substring(startIndex, endIndex + 1);
} catch (Exception e) {
seg = string.substring(startIndex);
}

System.out.println(seg);
ls.add(seg); // +1 as substring is exclusive
startIndex = endIndex + 1;
System.out.println(startIndex);
count++;

}
String list[] = new String[ls.size()];
list = ls.toArray(list);
System.out.println(Arrays.toString(list));
for (int i = 0; i < list.length; i++) {
String addPart = String.format(" (%d/%d)", (i + 1), list.length);
}
return list;
}
public static void main(String[] args) {
String str = "This is a good day";
int k = 10; // segment length
String segments[] = getSegments(str, k);
int segmentsCount = segments.length;
System.out.println(segmentsCount);
System.out.println(Arrays.toString(segments));

}
}

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

@Alex, Program actually prints 22, it was my mistake in code (I didn't updated expected value)

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

@Matviy Ilyashenko. Great!

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

Alex, do you have any explanation for your work?

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

``````private static int numberOfSegments(int length, int k)
{
List<int> blockLength = new List<int>();
List<int> numberOfSegs = new List<int>();

int i = 0;
int @base = 9;
int segmentCount = 0;
while (k - blockLength[blockLength.Count - 1] > 0)
{

while (numberOfSegs[i] < @base && length> k- blockLength[i])
{
numberOfSegs[i] += 1;
length -= k - blockLength[i];
}

segmentCount += numberOfSegs[i];

if (length <= k - blockLength[i])
{
return segmentCount;
}

@base *= 10;
i++;

}

return -1;``````

}

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

``````private static int numberOfSegments(int length, int k)
{
List<int> blockLength = new List<int> {5};
List<int> numberOfSegs = new List<int> {1};
int i = 0;
int @base = 9;
int segmentCount = 0;
while (k - blockLength[i] > 0)
{

while (numberOfSegs[i] < @base && length> k- blockLength[i])
{
numberOfSegs[i] += 1;
length -= k - blockLength[i];
}

segmentCount += numberOfSegs[i];

if (length <= k - blockLength[i])
{
return segmentCount;
}

@base *= 10;
i++;

}

return -1;
}``````

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

Text justification problem. (DP)

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.