hieu.pham
BAN USERThis implementation illustrate what I said above:
public int concatMinCost(String[] arr){
if (arr==null  arr.length<= 1)
return 1;
if (arr.length == 2) return arr[0].length() + arr[1].length();
Arrays.sort(arr, new Comparator<String>(){
public int compare(String s1, String s2){
return s1.length()  s2.length();
}
});
LinkedList<String> queue = new LinkedList();
int cost = 0;
int id = 2;
queue.addLast(arr[0] + arr[1]);
cost += queue.getLast().length();
while (id<arr.length  queue.size()>1){
String[] s = new String[2]; int c = 0;
while (c<2){
if (!queue.isEmpty()){
if (id < arr.length && queue.getFirst().length() > arr[id].length()){
s[c++] = arr[id++];
}
else
s[c++] = queue.pollFirst();
}
else {
s[c++] = arr[id++];
}
}
System.out.println(s[0].length()+" + " + s[1].length());
queue.addLast(s[0]+s[1]);
cost += queue.getLast().length();
}
return cost;
}

hieu.pham
July 11, 2015 This should not deserve a down vote. You were almost there. One correction is that you have to kind of "resort" the new list of array after each calculation. But maybe not necessarily a full sort or an insertion, but use an extra queue to store the temporary result and only need to check the first in the queue.
That way you may have a O(n*logn) solution.
My solution is O(n*logn) average and O(n^2) worst case time complexity and O(n) space: using Binary search tree where each node maintain a bit of information of number of nodes on its right, denoted as num_right
From right to left of the array: take an element a[i] to add to the tree by traverse from root, find the suitable place to add a[i], like BST insert, and do the following extra work at each node k:
 if need to go right child of k: (node k).num_right++
 if need to go left of k: surpassers[i] += (node k).num_right+1
Since each step take O(h), average is O(logn) and worst case is O(n), so in the end it is O(nlogn) avg and O(n^2) worst case

Don't read this if you haven't given it a try
.
This is an interesting question. I think the interviewer want to check if we have kind of rigid thinking or not.
y = f(x)
f(0) = a
f(1) = b
> simplest solution would be a linear equation: f(x) = k*x + r
k*0 + r = a > r = a
k*1 + r = b > k = br = ba
> y = f(x) = (ba) * x + a
I came up with a solution that has O(E) time complexity and O(E) space complexity, with E is the set of edge.
Assume that the set E doesn't contain duplicate edge, i.e. (B,A) should not exist if (A,B) already existed, as the graph is undirected.
0. Initialize hashmap V<Integer, ArrayList<Integer>>
1. Loop through the set E: let say at the edge (a,b), we add to the value list V.get(max(a,b)) the vertex min(a,b), this take O(E)
2. Number of triangles: num = 0
3. Loop through the value set of V: num += C(2, V.get(i).length()), where C(k,n) is a kcombination of a set size n. This take O(E)
A priority queue is a max/min heap itself. If you insert all the elements into a priority queue and dequeue one by one, the output will automatically sorted. This way you just need one priority queue and O(nlogn) time complexity.
If we need to use two queues, then insert half of the array to each queue, then dequeue them following the "merge" method in merge sort. But I don't think it will be faster this way.
In NGram problems, n is often very small compare to M and N, where M and N are size of the documents in words.
Ignoring the case that words are separated with multiple space, I've written a simple code that implements a O((M+N)n) time complexity
public class Interview {
private void process(String file, HashMap<String, Boolean> cmap, int n){
String[] words = file.split(“ “);
if (words.length < n)
return;
for (int i = 0; i<words.lengthn; i++){
StringBuilder sb = new StringBuilder();
for (int j = i; j<n+i; j++)
sb.append(words[j] + “ “);
String key = sb.toString();
if (cmap.containsKey(key))
cmap.put(key, Boolean.True);
else
cmap.put(key, Boolean.False);
}
}
public List<String> intersectionNGram(String file1, String file2, int n){
List<String> result = new ArrayList();
HashMap<String, Boolean> cmap = new HashMap();
process(file1, cmap, n);
if (cmap.size()==0)
return result;
process(file2, cmap, n);
for (String key : cmap.keySet()){
if (cmap.get(key))
result.add(key);
}
return result;
}
}

hieu.pham
June 20, 2015 @um01: solution 2, as I estimate max of k is at level of O(logn), probably not up to O(n).
I also don't like the solution 1 because since we are not allowed to modify the heap, we have to make a copy of it, which doesn't make much sense. But that's the only way I know to achieve O(n) time complexity, and also O(n) space complexity.
Solution 1. Using median of median you can find kth largest element in worst case O(n).
Solution2. Using maxheap property, I came up with the following solution, at least O(n):
Denote by A the maxheap.
0. X < {new array}, rank r = 1
1. element at rank 1: e_1 the largest element is the first element in the maxheap
2. element at rank r+1 = max( X.pop(), leftchild(e_r), rightchild(e_r) ) if any of those exist
3. insert the notmaximum element(s) in 2 into X at the right place (insertion sort)
4. r++
5. if r<k go to 2, else return e_r
There might be room for improvement here, but I haven't found it yet.
Edit: An idea for improvement is to maintain X as a new maxheap, and in step 3 use heapmaxify to insert elements
Open Chat in New Window
Preprocessing: Put the words and their counts (frequencies) into a hashmap: O(n)
 hieu.pham July 13, 2015Solution 1: using random quick selection to find kth most frequent word, this method take O(n) best and average case, and O(n^2) worst case.
Solution 2: using median of median method, take O(n) worst case to find kth most frequent word
PostProcessing: after having kth most frequent word, run the partition method that used in quick sort to get the k words that most frequent, not known which order. Takes O(n)
> can be solve with O(n) time complexity!