Facebook Interview Question for SDE1s


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>(); 
    segLens.add(5);
    List<Integer> bases = new ArrayList<Integer>();
    bases.add(9);
    
    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);
      segLens.add(segLens.get(segLens.size()-1)+1);
      bases.add(bases.get(bases.size()-1)*10);
    }
    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);
  }

- Matviy Ilyashenko November 12, 2017 | Flag Reply
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

}

- Alex November 12, 2017 | Flag Reply
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.

- Alex November 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the word itself should not be split to 2 lines

- xinlf November 13, 2017 | Flag Reply
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.

- Alex November 13, 2017 | Flag Reply
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();
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));

}
}

- theajr November 13, 2017 | Flag Reply
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)

- Matviy Ilyashenko November 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Matviy Ilyashenko. Great!

- Alex November 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Alex, do you have any explanation for your work?

- Daniel November 15, 2017 | Flag Reply
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>();
            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;

}

- Daniel November 16, 2017 | Flag Reply
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++;
                blockLength.Add(blockLength[i - 1]+1);

                numberOfSegs.Add(numberOfSegs[i - 1] + 1);
            }
            
            return -1;
        }

- Daniel November 17, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More