text: hieu.phamBAN USER
  TreeMap sort itself using the keys, which in this case are words, not the frequencies. If you are going to sort it you can use whatever Map available out there, it will take O(nlogn) anyway.
  This 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;
  }
  This should not deserve a down vote. You were almost there. One correction is that you have to kind of "re-sort" 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.
  It's bad actually because String comparison in the sorting is expensive. It is simple because those comparisons already done part of the work for you.
  If we use self balanced binary search tree, we can ensure the O(n*logn) time complexity. It's more complicated though.
  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
  -
  I have quite similar solution, but I maintain the K room sorted by the last ending of the meeting assigned to it.
  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 = b-r = b-a
  --> y = f(x) = (b-a) * 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 k-combination 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.
  Isn't it just doing multiplication of x for n times? The important thing here I think is how you handle double/integer overflow.
  In N-Gram 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.length-n; 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;
  }
  }
  @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.
  Nice solution, but it doesn't seem to me a O(n) solution when I try to calculate a "loose" upper bound complexity. Can somebody prove it pls?
  @iwaow: No, X is a new array that I use as intermediate storage. Maybe better idea is to use X as a new max-heap. Sorry for not being clear enough.
  Solution 1. Using median of median you can find kth largest element in worst case O(n).
  Solution2. Using max-heap property, I came up with the following solution, at least O(n):
  Denote by A the max-heap.
  0. X <-- {new array}, rank r = 1
  1. element at rank 1: e_1 the largest element is the first element in the max-heap
  2. element at rank r+1 = max( X.pop(), leftchild(e_r), rightchild(e_r) ) if any of those exist
  3. insert the not-maximum 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 max-heap, and in step 3 use heap-maxify to insert elements
  Preprocessing: Put the words and their counts (frequencies) into a hashmap: O(n)- hieu.pham July 13, 2015
  Solution 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!