## Facebook Interview Question

SDE1s**Country:**United States

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
}
```

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();

int additionalLength = 0;

while (startIndex < length) {

if (count < 10) {

additionalLength = 6;

} else if (count < 100) {

additionalLength = 7;

}

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);

if (i == list.length - 1) addPart = addPart.trim();

list[i] = list[i] + addPart;

}

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));

}

}

```
private static int numberOfSegments(int length, int k)
{
List<int> blockLength = new List<int>();
blockLength.Add(5);
List<int> numberOfSegs = new List<int>();
numberOfSegs.Add(1);
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++;
blockLength.Add(blockLength[i - 1]+1);
numberOfSegs.Add(numberOfSegs[i - 1] + 1);
}
return -1;
```

}

```
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++;
blockLength.Add(blockLength[i - 1]+1);
numberOfSegs.Add(numberOfSegs[i - 1] + 1);
}
return -1;
}
```

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:

- Matviy Ilyashenko November 12, 2017