Facebook Interview Question
SDE1sCountry: 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