Apple Interview Question
Software Engineer in TestsCountry: United States
there is more efficient way because sorting hashmap based on values is not optimised way , manage heap sort with hashmap , top of heap will give the most occured word. Also, since heap will be based on number of occurence, each node of heap can maintain the list of words with same number of occurence and keep it sorted.
2 functions. One sort occurrence. One sort alphabet.
<?php
/**
* Suppose we are given an array of strings over some finite alphabet(say the
* letters a to z). Each string can have a different number of characters, but
* the total number of characters in all the strings is n. Show how to sort
* the strings in alphabetical order in O(n) time.
*/
function linearSort($s, $p) {
$t = [];
foreach ($s as $u) {
if (!isset($u[$p])) $c = 0;
else $c = $u[$p];
if (!isset($t[$c])) $t[$c] = [];
$t[$c][] = $u;
}
$s = isset($t[0]) ? $t[0] : [];
foreach (range('a', 'z') as $c) {
if (!isset($t[$c])) continue;
if (count($t[$c]) == 1) {$s[] = $t[$c][0]; continue;}
$u = linearSort($t[$c], $p + 1);
$s = array_merge($s, $u);
}
return $s;
}
$s = ['test', 'something', 'test', 'apple', 'what'];
var_dump(linearSort($s, 0));
/**
* There are several words in a file. Get the occurrence of every word and sort
* it based on the occurrence, if more than one word is having same occurrence
* then sort it alphabetically.
*/
function occurrenceSort($s) {
$t = [];
foreach ($s as $u) {
if (!isset($t[$u])) $t[$u] = 0;
$t[$u]++;
}
$p = [];
$max = 1;
foreach ($t as $u => $c) {
if (!isset($p[$c])) $p[$c] = [];
$p[$c][] = $u;
$max = $max < $c ? $c : $max;
}
$s = [];
for ($i = $max; $i > 0; $i--) {
if (!isset($p[$i])) continue;
if (count($p[$i]) == 1) {
$s[] = $p[$i][0];
continue;
}
$t = linearSort($p[$i], 0);
$s = array_merge($s, $t);
}
return $s;
}
var_dump(occurrenceSort($s));
/**
* @author Dany
*
*There are several words in a file. Get the occurrence of every word and sort it based on the
*occurrence, if more than one word is having same occurrence than sort it alphabetically.
*
*ALGORITHM:
* 1. Get the input list
* 2. Put it in a hashmap and update the word occurrence count as value in the map
* 3. Iterate through the hash map and add word and count to the max heap which is implemented based on count priority
* 3. Iterate through the max heap and sort the words which has same occurrence count.
* Then add the words to result list.
* 4. return the result list
*
*/
public class SortListBasedOnOccurrance {
/**
* @param args
*/
public static void main(String[] args) {
ArrayList<String> wordList = new ArrayList<String>();
wordList.add("Dinesh");
wordList.add("Poornesh");
wordList.add("Rahul");
wordList.add("Dinesh");
wordList.add("Moezhi");
wordList.add("Rahul");
ArrayList<String> res = new SortListBasedOnOccurrance().getSortedWordList(wordList);
for(String word : res)
{
System.out.println(word);
}
}
class WordObj{
String word;
int count;
public WordObj(String word, int count)
{
this.word = word;
this.count = count;
}
}
public PriorityQueue<WordObj> implementMaxHeap()
{
PriorityQueue<WordObj> pq = new PriorityQueue<WordObj>(11, new Comparator<WordObj>() {
public int compare(WordObj o1, WordObj o2)
{
int p1=o1.count;
int p2=o2.count;
return (p2-p1);
}
});
return pq;
}
public ArrayList<String> getSortedWordList(ArrayList<String> wordList)
{
ArrayList<String> resultList = new ArrayList<String>();
HashMap<String, Integer> wordMap = new HashMap<String, Integer>();
//HashMap<Integer, ArrayList<String>> valueWordMap = new HashMap<Integer, ArrayList<String>>();
for(String word : wordList)
{
if(wordMap.containsKey(word))
{
wordMap.put(word, wordMap.get(word)+1);
}else
{
wordMap.put(word, 1);
}
}
PriorityQueue<WordObj> maxHeap = implementMaxHeap();
for(String word : wordMap.keySet())
{
int count = wordMap.get(word);
maxHeap.add(new WordObj(word, count));
}
int lastCountValue =0;
ArrayList<String> wordArrList = new ArrayList<String>();
WordObj firstWord = maxHeap.poll();
wordArrList.add(firstWord.word);
lastCountValue = firstWord.count;
while(!maxHeap.isEmpty())
{
WordObj wObj = maxHeap.poll();
if(wObj.count==lastCountValue)
{
wordArrList.add(wObj.word);
lastCountValue = wObj.count;
}else
{
Collections.sort(wordArrList);
resultList.addAll(wordArrList);
wordArrList = new ArrayList<String>();
wordArrList.add(wObj.word);
lastCountValue = wObj.count;
}
}
Collections.sort(wordArrList);
resultList.addAll(wordArrList);
return resultList;
}
}
simple groovy solution.
def myFile ="""hola como esta esa hola que viene por esa casa de casa asi lo queria con aaa\nNext line aaa"""
Map strMap = myFile.replaceAll('\n',' ').split(' ').countBy{it}
strMap.sort{a, b -> b.getValue() <=> a.getValue() ?: a.getKey() <=> b.getKey()}.each{
println it
}
@import Foundation;
int main() {
@autoreleasepool {
NSMutableDictionary *wordsCount = [[NSMutableDictionary alloc] init];
NSArray *words = @[@"john", @"doe", @"jane", @"doe"];
for (NSString *s in words)
{
NSNumber *count = [wordsCount objectForKey:s];
wordsCount[s] = [NSNumber numberWithInt: count ? [count intValue] + 1 : 1];
}
NSLog(@"%@", wordsCount);
} return 0;
}
public static SortedSet<WordCount> computeWordCount(BufferedReader reader) {
SortedSet<WordCount> wordCounts = new TreeSet<>();
Map<String,WordCount> map = new HashMap<>();
try {
while(reader.ready()) {
String line = reader.readLine();
StringTokenizer st = new StringTokenizer(line, "\t ");
st.countTokens();
while(st.hasMoreTokens()) {
String token = st.nextToken();
token = token.trim();
WordCount wordCount =null;
if(map.containsKey(token)) {
wordCount = map.get(token);
wordCount.addCount(1);
} else {
wordCount = new WordCount(token);
}
map.put(token, wordCount);
}
}
for(Entry<String,WordCount> wc: map.entrySet()) {
wordCounts.add(wc.getValue());
}
} catch (IOException e) {
e.printStackTrace();
}
return wordCounts;
}
Use TreeMap
public static void main(String[] args){
try {
TreeMap<String,Integer> tree = new TreeMap<>();
FileReader fd = new FileReader("input_file.txt");
BufferedReader file = new BufferedReader(fd);
String line;
while((line =file.readLine())!=null){
for(String temp: line.split("\\s+")){
if(tree.keySet().contains(temp))
tree.put(temp,tree.get(temp)+1);
else
tree.put(temp,1);
}
}
for(String temp:tree.keySet()){
System.out.println(String.format(temp + " : " + tree.get(temp)));
}
}
catch ( IOException e){
System.out.print(e.getCause());
}
}
1. Make a HashMap of word,count
2. Create a WordObject class as [word, count]
3. Create a Max heap (Priority Queue), which is fort sorted by count and then by word alphabetically
4. One by one add from Map to PQ
5. One by One remove from PQ to get the result
import java.util.*;
public class WordCount {
public static void getWordCount(List<String> list){
HashMap<String,Integer> wordToCountMap = new HashMap<String,Integer>();
//Build word,count map
for(String word : list){
if(wordToCountMap.containsKey(word)){
int count = wordToCountMap.get(word);
wordToCountMap.put(word, count+1);
}else{
wordToCountMap.put(word, 1);
}
}
//Make max count Priority Queue which is sorted by counts and then by string alphabetically
PriorityQueue<WordObject> maxPQ = new PriorityQueue<WordObject>(new Comparator<WordObject>(){
public int compare(WordObject o1, WordObject o2){
// sort on count and the alphabetically
if(o1.count > o2.count){
return -1;
}else if(o1.count < o2.count){
return 1;
}else{
return o1.word.compareTo(o2.word); // sort alphabetically
}
}
});
//add one by one to Max PQ
for(String word : wordToCountMap.keySet()){
maxPQ.add(new WordObject(word, wordToCountMap.get(word)));
}
//Build the result
List<String> result = new ArrayList<String>();
while(!maxPQ.isEmpty()){
result.add(maxPQ.remove().word);
}
//Print
System.out.println(result.toString());
}
public static void main(String[] args) {
List<String> wordList = new ArrayList<String>();
wordList.add("Dinesh");
wordList.add("Poornesh");
wordList.add("Rahul");
wordList.add("Dinesh");
wordList.add("Moezhi");
wordList.add("Rahul");
getWordCount(wordList);
}
}
//Occurrences
class WordObject{
String word;
int count;
WordObject(String word , int count){
this.word = word;
this.count = count;
}
}
cat <filename> | tr -s [:space:] '\n' | grep -v "^\s*$" | sort | uniq -c | sort -bnr
- David February 26, 2015