Interview Question
Country: United States
Interview Type: Phone Interview
public class MyChar implements Comparable {
public char c;
public int count;
public MyChar(char c, int count) {
this.c = c;
this.count = count;
}
@Override
public int compareTo(Object arg0) {
// TODO Auto-generated method stub
int res = count-((MyChar)arg0).count;
if(res != 0) {
return res;
}
return ((MyChar)arg0).c-c;
}
}
public static String reorder(String s){
char[] arr = s.toCharArray();
HashMap<Character, MyChar> map = new HashMap<Character, MyChar>();
TreeSet<MyChar> set = new TreeSet<MyChar>();
for(char c:arr){
MyChar my_c = map.get(c);
if(my_c == null){
my_c = new MyChar(c,0);
map.put(c, my_c);
}
set.remove(my_c);
my_c.count++;
set.add(my_c);
}
MyChar prev = null;
for(int i =0; i<arr.length;++i){
if(set.size() == 0){
System.out.println("n"+i);
return "no solution found";
}
MyChar curr = set.last();
set.remove(curr);
curr.count--;
arr[i]=curr.c;
if(prev!=null && prev.count>0){
set.add(prev);
}
prev = curr;
}
return String.valueOf(arr);
}
- Anonymous October 10, 2015