Amazon Interview Question
Software Engineer in TestsTeam: SDET
Country: India
Interview Type: Phone Interview
Python code:
char MostCommonChar(String str, int num):
char_count = char_count(string) # returns each char to its count dictionary
chars_dict = sorted(char_count.values())
char_dict = chars_dict[num-1]
print char_dict[0]
#Hasing key is char and value is count
def char_count_dict(string):
char_count = {} #Map each char to its count
for char in string
if char in char_count:
char_count[char] = char_count[char] + 1
else:
char_count[char] = 1
return char_count
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package amazon;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
/**
*
* @author ashok
*/
public class MostCommonChar {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
MostCommonChar main = new MostCommonChar();
System.out.print("character is " + main.mostCommonChar("Aabra ka dabra", 1));
}
private char mostCommonChar(String str, int num) {
char commonChar = 'a';
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < str.length(); i++) {
if (map.containsKey(str.charAt(i))) {
int n = map.get(str.charAt(i));
map.put(str.charAt(i), n + 1);
} else {
map.put(str.charAt(i), 1);
}
}
List<OccuranceClass> oc = new ArrayList<OccuranceClass>();
for (Object obj : map.keySet().toArray()) {
//ystem.out.println(obj + " " + map.get(obj));
oc.add(new OccuranceClass((Character) obj, (Integer) map.get(obj)));
}
Collections.sort(oc, new Sort());
return oc.get(num - 1).getCh();
}
static private final class Sort implements Comparator<OccuranceClass> {
public int compare(OccuranceClass o1, OccuranceClass o2) {
return o2.getI() - o1.getI();
}
}
static private final class OccuranceClass {
public OccuranceClass(char ch, int i) {
this.ch = ch;
this.i = i;
}
private char ch;
private int i;
public char getCh() {
return ch;
}
public void setCh(char ch) {
this.ch = ch;
}
public int getI() {
return i;
}
public void setI(int i) {
this.i = i;
}
}
}
import java.util.HashMap;
public class MostCommonChar {
private static class CharCount {
public char character;
public int count;
CharCount(Character ch, Integer count) {
this.character = ch;
this.count = count;
}
}
public static char mostCommonChar(String str, int num) {
char output = ' ';
HashMap<Character, Integer> charOccuranceHashMap = new HashMap<Character, Integer>();
for(int index = 0; index < str.length(); index++) {
char ch = str.charAt(index);
if(charOccuranceHashMap.containsKey(ch))
charOccuranceHashMap.put(ch, charOccuranceHashMap.get(ch) + 1);
else
charOccuranceHashMap.put(ch, 1);
}
//Converting the HashMap to a Array
CharCount[] sortedCharCount = new CharCount[charOccuranceHashMap.size()];
int index = 0;
for(char key : charOccuranceHashMap.keySet())
sortedCharCount[index++] = new CharCount(key, charOccuranceHashMap.get(key));
//Occurrence sort
for(int outerIndex = 0 ; outerIndex < sortedCharCount.length; outerIndex++) {
for(int innerIndex = 0; innerIndex < outerIndex; innerIndex++) {
if(sortedCharCount[innerIndex].count < sortedCharCount[outerIndex].count) {
//swap the positions
CharCount temp = sortedCharCount[innerIndex];
sortedCharCount[innerIndex] = sortedCharCount[outerIndex];
sortedCharCount[outerIndex] = temp;
}
}
}
if(num <= sortedCharCount.length)
output = sortedCharCount[num - 1].character;
return output;
}
}
public class Main {
public static void main(String args[]) {
System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 1));
System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 2));
System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 3));
System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 4));
System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 5));
System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 6));
System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 7));
System.out.println(MostCommonChar.mostCommonChar("Aabra Ka Daabra", 8));
}
}
package com.DataStr.Question;
import java.util.*;
public class Question1 {
Set<Character> charSet = new HashSet<Character>();
Map<Character,Integer> charMap = new HashMap<Character, Integer>();
Map<Integer, String> sortedMap = new TreeMap<Integer, String>();
public String mostCommonChar(String str, int num){
for(int i = 0; i < str.length(); i++)
charSet.add(str.charAt(i));
for(int i = 0; i < str.length(); i++)
charMap.put(str.charAt(i), 0);
for(int i = 0; i < str.length(); i++)
charMap.put(str.charAt(i), charMap.get(str.charAt(i))+1);
Object []key = charMap.keySet().toArray();
Object []values = charMap.values().toArray();
for(int i = 0; i < values.length; i++){
sortedMap.put(Integer.parseInt((values[i].toString())), (sortedMap.get(values[i]) == null) ? key[i].toString() : sortedMap.get(values[i]) + key[i].toString() );
}
key = sortedMap.keySet().toArray();
if(num <= sortedMap.size())
return sortedMap.get(Integer.parseInt(key[key.length - num].toString()));
else
return "";
}
public static void main(String[] args) {
System.out.println(new Question1().mostCommonChar("aaaaaaaaaabbbbbcccdds", 1));
System.out.println(new Question1().mostCommonChar("aaaaaaaaaabbbbbcccdds", 2));
System.out.println(new Question1().mostCommonChar("aaaaaaaaaabbbbbcccdds", 3));
System.out.println(new Question1().mostCommonChar("aaaaaaaaaabbbbbcccdds", 4));
}
}
Take a 256 integer array. Initialize each of its value to zero. Increment its value according to the character. Now convert this array as a max heap. Get the count of character according to 'num' by removing max element and reduce the length of the heap by 1. Finally get the required count.
Eg: If need third largest, initially we have to remove top element from the heap two times and take third highest element as answer.
Maintain a dictionary with key as the character, the value would be an object of a class with properties like character, count and a position in the list. The list consist of objects to the class defined above i.e. a reference to the object exists in both the list and the dictionary.
Now traverse the string and create these objects. Keep the list sorted according to the new count and update necessary entries in dictionary as well as the list.
Maintain a dictionary with key as the character, the value would be an object of a class with properties like character, count and a position in the list. The list consist of objects to the class defined above i.e. a reference to the object exists in both the list and the dictionary.
Now traverse the string and create these objects. Keep the list sorted according to the new count and update necessary entries in dictionary as well as the list.
1. Create a hash from the string
2. Sort the hash
3. Return the character from the entry num-1 in this sorted array
Time complexity: O(m) + O(nlog(n)) where m is size of string and n is size of hash table/array
Space: O(n) where n is size of hash array
The implementation is Java specific but can be done in other languages
Instead of using char[] as hashMap we can use an array of HashElem[] as the hash where HashElem is
Now we can initialize this hash using the characters of the original string as index. Next step is to sort this hash (which is actually an array) based on the count or individual characters and if counts are same based on the character ascii value. I have overridden the standard comparator interface. Here is a sample code to get you started:
// output: a r b <space> k d
- CodeNameEagle May 04, 2013