Massive Algorithms

http://www.1point3acres.com/bbs/thread-139997-1-1.html
给定一段英文消息，以及一个固定的长度，要求将消息分割成若干条，每条的最后加上页码如 (2/3)，然后每条总长度不超过给定的固定长度。典型的应用场景就是短信发送长消息。
经过询问之后得到更多详细要求及假设：（1）消息数量尽可能少，不必凑整句，可以在任意空格处分页；（2）这个固定长度可能非法，比如某个词很长导致一条消息放不下，要判断并抛出异常；（3）假设空格分割，不会出现连着两个空格的情况。

这题比较tricky，没想到什么1 pass的方法，用了2 pass，第一遍判断总页数，第二遍生成预期的结果
public class TextSpliter {
    public List<String> splitText(String txt, int len) {
        List<Integer> startList = new ArrayList<Integer>();
        List<Integer> lenList = new ArrayList<Integer>();
        String[] words = txt.split(" ");
        boolean violate;
        do {
            violate = false;
            int pLen0 = 3 + digits(startList.size()); //length needed for (ab/cd), not including ab.
            int curPage = 1;
            int curStart = 0;
            int curLen = 0;
            while (curStart < words.length) {
                int curPageLenMax = len - pLen0 - digits(curPage);
                int curPageLen = 0;
                while (curStart + curLen < words.length &&
                        ((curLen == 0 && curPageLen + words[curStart + curLen].length() < curPageLenMax) ||
                                (curLen > 0 && curPageLen + words[curStart + curLen].length() + 1 < curPageLenMax))) {

                    curPageLen += words[curStart + curLen].length();
                    if (curLen > 0) {
                        curPageLen++; // space
                    }
                    curLen++;
                }
                if (curLen == 0) {
                    throw new Error("word is too long");
                }
                if (curPage - 1 >= startList.size()) {
                    //if it's a new page, add it to the end
                    violate = true;
                    startList.add(curStart);
                    lenList.add(curLen);
                } else if (startList.get(curPage - 1) != curStart || lenList.get(curPage - 1) != curLen) {
                    //if it's updating existing page, then update the list.
                    violate = true;
                    startList.set(curPage - 1, curStart);
                    lenList.set(curPage - 1, curLen);
                }
                curStart += curLen;
                curLen = 0;
                curPage++;
            }
        } while (violate);
        List<String> rst = new ArrayList<String>();
        for (int i = 0; i < startList.size(); ++i) {
            StringBuilder sb = new StringBuilder();
            for (int j = startList.get(i); j < startList.get(i) + lenList.get(i); ++j) {
                if (j > startList.get(i)) {
                    sb.append(" ");
                }
                sb.append(words[j]);
            }
            int page = i + 1;
            sb.append("(" + page + "/" + startList.size() + ")");
            rst.add(sb.toString());
        }
        return rst;
    }
    //return how many digits for the number n
    private int digits(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n /= 10;
        }
        return count == 0 ? 1: count;
    }
}
https://github.com/lichuanr/Python-practise/blob/master/2016%20interview/r%20practise/messaging.py
#implementation step
#First -> detect the white space, store a list of string
    #checking the max length, if length exceed the max, return error
#Second -> create an empty list, iterate the loop and add the element in the list and add the number at the end
def step(string):
    list1 = []
   
    length = 0
    for x in string.split(' '):
        item = x.strip()
        list1.append(item)
        length += len(item)
   
    maxlength = 16
   
    #-> length
    total = length/maxlength
    if (length%maxlength) != 0:
        total += 1
   
   
    newstring, list2 = "", []
    i = 0
    Pnum = 0
    while i < len(list1)-1:
        #corner cases
        if len(list1[i]) > maxlength-3:
            print "eee"
            return False
        newstring = ""
        #temp and j are used to store the pre step's result
        while i < len(list1):
            temp = newstring
            newstring = newstring + list1[i]
            j = i
            i += 1
            if len(newstring) > maxlength-3:
                break
   
        i = j
        Pnum+=1
    list2.append(temp + str(Pnum) + "/" + str(total))
    #used for adding the last string
    if list1[-1] not in list2[-1]:
        list2.append(list1[-1]+ str(Pnum+1) + "/" + str(total))

print list1
    print list2