Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."] L: 16.
Return the formatted lines as:
[ "This is an", "example of text", "justification. " ]
Note: Each word is guaranteed not to exceed Lin length.
Corner Cases:
A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left-justified.
public List<String> fullJustify(String[] words, int L) { if (words == null || words.length == 0) { return Collections.emptyList(); } List<Line> lines = parseToLines(words, L); return fillLines(lines, L); } private List<String> fillLines(List<Line> lines, int L) { List<String> output = new ArrayList<String>(); for (int i = 0; i < lines.size(); i++) { Line line = lines.get(i); if (line.wordCount() == 1) { StringBuilder sb = new StringBuilder(); sb.append(line.words.get(0)); sb.append(getSlot(L - line.totalNonSpaceLetterLength())); output.add(sb.toString()); } else if (i == lines.size() - 1) { StringBuilder sb = new StringBuilder(); sb.append(line.words.get(0)); for (int j = 1; j < line.wordCount(); j++) { sb.append(' '); sb.append(line.words.get(j)); } sb.append(getSlot(L - line.minimumLength())); output.add(sb.toString()); } else { int space = (L - line.totalNonSpaceLetterLength()) / (line.wordCount() - 1); int remain = (L - line.totalNonSpaceLetterLength()) % (line.wordCount() - 1); StringBuilder sb = new StringBuilder(); sb.append(line.words.get(0)); for (int j = 1; j <= remain; j++) { sb.append(getSlot(space+1)); sb.append(line.words.get(j)); } for (int j = remain+1; j < line.wordCount(); j++) { sb.append(getSlot(space)); sb.append(line.words.get(j)); } output.add(sb.toString()); } } return output; } private String getSlot(int i) { char[] cs = new char[i]; Arrays.fill(cs, ' '); return new String(cs); } private List<Line> parseToLines(String[] words, int L) { List<Line> lines = new ArrayList<Line>(); Line currentLine = new Line(); lines.add(currentLine); for (String word : words) { if (currentLine.minimumLength() + word.length() < L) { currentLine.addWord(word); } else { currentLine = new Line(); lines.add(currentLine); currentLine.addWord(word); } } return lines; } class Line { private List<String> words; private int totalLength; Line() { words = new ArrayList<String>(); totalLength = 0; } void addWord(String word) { words.add(word); totalLength += word.length(); } int wordCount() { return words.size(); } int totalNonSpaceLetterLength() { return totalLength; } int minimumLength() { return totalLength + words.size() - 1; } }
Another FAQ on the programming interview.
Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (eg, if you have a tree with depth D, you’ll have D linked lists).
Cracking the Coding Interview (4ed) (see page 126) provided a non-recursive algorithm. For me, a recursive version is neater and much easier to understand.
Another FAQ on the programming interview.
Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.
Cracking the Coding Interview (4ed) (see page 121) provided an O(N^2) algorithm by using one more stack. The idea is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, the algorithm removes enough items from it so that it’s possible to push the new item. Because of the copyright, I won’t paste her code here, but you can easily find it out online (:P).
Can we do better? I think we can mimic the way of quicksort by picking a pivot from the stack (using pop) first. Then we conduct the partition operation by pushing all elements in the stack with values less than the pivot into one stack, while all elements with values greater than the pivot into the other. After that, we recursively sort two sub-stacks and merge two at last with the pivot in the middle.
Because we can only use the stack structure, I pick the pivot using pop. The merge operation is tricky and I am not sure if we can have a better way to combine two stacks. So if you have any idea, please let me know.
On average, this algorithm makes O(n log n) comparisons to sort items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.
public static Stack<Integer> sort(Stack<Integer> s) { if (s.isEmpty()) { return s; } int pivot = s.pop(); // partition Stack<Integer> left = new Stack<Integer>(); Stack<Integer> right = new Stack<Integer>(); while(!s.isEmpty()) { int y = s.pop(); if (y < pivot) { left.push(y); } else { right.push(y); } } sort(left); sort(right); // merge Stack<Integer> tmp = new Stack<Integer>(); while(!right.isEmpty()) { tmp.push(right.pop()); } tmp.push(pivot); while(!left.isEmpty()) { tmp.push(left.pop()); } while(!tmp.isEmpty()) { s.push(tmp.pop()); } return s; }
This is one of frequently asked questions on the programming interview. There are two kinds of solution: iteration-based and recursion-based.
We first define a toy class for the single linked list.
class LinkedListNode {
int data;
LinkedListNode next;
LinkedListNode(int data, LinkedListNode next) {
this.data = data;
this.next = next;
}
}
The iteration-based solution is quite tricky but I really like it. In Cracking the Coding Interview (4ed), the solution uses two pointers p1 and p2. Her algorithm first increaments p2 by (n-1) times, and then moves both p1 and p2 until p2.next reaches the tail of the list. As the result, p1 points to the th to last element. Because of the copyright, I won’t reproduce her code in this post. If you are interested, please see page 106 for the solution.
The recursion version is straightforward too. We first recursively call a function until we reach the tail of the list. Then we start to count from 0 and increment the counter when a called function is returned. Essentially, it counts the number of popped function calls on the call stack. When the counter equals to , we record the element, which is the th to the last.
An easier way to count the number of times we have returned to a recursive call is using a global variable. My solution attempted to avoid it by creating a class Record which stores the returned element (null if not) and the counter.
class Record {
LinkedListNode node;
Integer i;
Record(LinkedListNode node, int i) {
this.node = node;
this.i = i;
}
}
Then I used a helper function for the recursive purpose.
private static Record nthToLastRurHelper( LinkedListNode head, int n) { if (head == null) { // tail return new Record(null, 0); } Record record = nthToLastRurHelper(head.next, n); record.i++; if (record.i == n) { record.node = head; return record; } else { return record; } }