Amazon Interview Question SDE-2s
Country: India
Interview Type: Phone Interview
Create a HashMap<char, int, int> and Top: char for each position.
1. Say for position i, user enters 'a'.
Enter into map: <a, 0, 1> : 0 is the position of first occurrence of char in that position, 1 is count. Update Top to a.
2. So, for position i 'a' is suggested to user next time. But, say user enters 'b'. Add <b, 1, 1> to map. Now count of Top and current char are same, so look for position. Position of a is less than that of 'b'. So, top remains unchanged.
3. User is suggested 'a' again, but say user enters b again. Update map for 'b' to <b, 1, 2>. Now Top will be updated to 'b'.
My approach would be to use a Map, say positionMap of type <int position, MapAndHeap>
The MapAndHeap class will have a map and root of max-heap:
class MapAndHeap{
Map<char, HeapNode> charToNodeMap; //character in a heap
HeapNode max_heap_root;
}
The inserts will be done like this:
Parsing every new line keep a counter of which character number are you reading from the left. Check positionMap to see if you have a value for the key position number. If not create a MapAndHeap object (set right values) and insert. If present, check in the charToNodeMap if this character has a value in the map, if yes, increment it and do a sift-up. If not, insert a new node with frequency 1 from the root of the max-heap.
Making suggestion / Look-up:
If the user has typed till position p, you want to suggest character for p+1 position. Look up positionMap and get the root of the max-heap.
This is my C++ solution with O(1) lookup. Basically it uses a hashmap to map the character position to a heap of a structure that holds the frequency and word position.
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
class word_suggest {
public:
word_suggest(const std::vector<std::string>& words) {
initialize(words);
}
char suggest(const std::string& str) {
size_t pos = str.length();
const auto it = freq_map_.find(pos);
if (it == freq_map_.end())
return '?';
const frequency_heap& heap = it->second;
const frequency_entry& entry = heap[0];
return entry.c_;
}
private:
struct frequency_entry {
frequency_entry(char c, size_t word_pos) :
c_(c), word_pos_(word_pos), frequency_(1) { }
bool operator==(const frequency_entry& other) {
return c_ == other.c_;
}
bool operator!=(const frequency_entry& other) {
return !operator==(other);
}
bool operator<(const frequency_entry& other) {
// Compare the character
if (c_ == other.c_)
return false;
// Compare the frequency
if (frequency_ < other.frequency_) {
return true;
} else if (frequency_ == other.frequency_) {
// Compare the word position
if (word_pos_ < other.word_pos_)
return false;
else
return true;
} else {
return false;
}
}
char c_;
size_t word_pos_;
size_t frequency_;
};
void initialize(const std::vector<std::string>& words) {
size_t word_pos = 0;
for (const std::string& word : words)
add_word(word, word_pos++);
}
void add_word(const std::string& word, size_t word_pos) {
for (size_t i = 0; i < word.size(); i++) {
// Instantiate the frequency_entry for this character
frequency_entry entry(word[i], word_pos);
// Find the heap of chars of the current position
auto it = freq_map_.find(i);
if (it == freq_map_.end()) {
// There's no heap of this position on map.
// So, create one
frequency_heap heap = frequency_heap();
heap.push_back(entry);
// Add the heap to the map
freq_map_.insert(std::make_pair(i, heap));
} else {
// Found the heap of this position
frequency_heap& heap = it->second;
// Find the frequency_entry related to the current char
auto entry_it = std::lower_bound(heap.begin(), heap.end(), entry);
if (entry_it == heap.end() || *entry_it != entry) {
// Entry not found. Push to the heap
heap.push_back(entry);
std::push_heap(heap.begin(), heap.end());
} else {
// Entry found. Update it
frequency_entry& found_entry = *entry_it;
found_entry.frequency_++;
// Update the heap
std::make_heap(heap.begin(), heap.end());
}
}
}
}
typedef std::vector<frequency_entry> frequency_heap;
typedef std::unordered_map<size_t, frequency_heap> frequency_map;
frequency_map freq_map_;
};
int main() {
std::vector<std::string> words;
words.push_back("ABC");
words.push_back("BCD");
words.push_back("CBA");
word_suggest ws(words);
std::cout << "suggest(A): " << ws.suggest("A") << std::endl;
std::cout << "suggest(AB): " << ws.suggest("AB") << std::endl;
return 0;
}
I solved this in Python using a Trie. When we're done adding a word, we go through all of the nodes used to store the word and increment the frequency of the appropriate child letter. When we want to find out which character to choose next, we navigate down the Trie using the prefix provided, then we simply find which child character has the highest frequency. That last part could be improved by using a max heap, or it could also be modified to return a list of characters in the case that there's a tie for highest frequency.
def getIndex(alphabetLetter) :
return ord(alphabetLetter.lower()) - ord('a')
def getChar(index0To25):
return chr(index0To25 + ord('a'))
class Trie(object):
def __init__(self, parent):
self.parent = parent
self.isWord = False
self.children = [None for i in range(26)]
self.frequencies = [0 for i in range(26)]
# Go through the parents and update frequencies.
def addedDescendantWord(self, originalWord, depth) :
char = originalWord[depth]
charIndex = getIndex(char)
self.frequencies[charIndex] += 1
if self.parent is not None :
self.parent.addedDescendantWord(originalWord, depth - 1)
def addWord(self, word, originalWord=None) :
if originalWord is None : originalWord = word
firstChar = word[0]
childIndex = getIndex(firstChar)
if self.children[childIndex] is None :
self.children[childIndex] = Trie(self)
child = self.children[childIndex]
if len(word) is 1 :
if not child.isWord :
# A new word was added, so alert all parents that they have a
# new descendant.
child.isWord = True
self.addedDescendantWord(originalWord, len(originalWord) - 1)
return
self.children[childIndex].addWord(word[1:], originalWord)
def getNextChar(self, prefix) :
if len(prefix) is 0 :
# Select the highest frequency and return the index
maxIndex = 0
for i in range(26) :
if self.frequencies[i] > self.frequencies[maxIndex] :
maxIndex = i
if self.frequencies[maxIndex] is 0 :
return "[not applicable]"
return getChar(maxIndex)
firstChar = prefix[0]
childIndex = getIndex(firstChar)
child = self.children[childIndex]
if child is None:
return "[not applicable]"
return child.getNextChar(prefix[1:])
def testGetNext(trie, prefix):
choice = trie.getNextChar(prefix)
print "Best choice after \"%s\" is \"%s\"" % (prefix, choice)
def main() :
trie = Trie(None)
# Add some words
map(trie.addWord, ["ac", "ab", "abc", "abc", "abcd", "bcd", "cba"])
# Test some cases
[testGetNext(trie, test) for test in ["a", "ab", "abc", "abcd", "abcde"]]
if __name__ == '__main__':
main()
Output:
Best choice after "a" is "b"
Best choice after "ab" is "c"
Best choice after "abc" is "d"
Best choice after "abcd" is "[not applicable]"
Best choice after "abcde" is "[not applicable]"
Data in file -
ABC
BCD
ABD
ADB
Solution - We could represent the scenario as a tree/graph.
For every position, we need to construct a tree with height = 1.
So, in our case, the maximum length of a word is 3, so we ll have 3 trees with the position number at the root.
So, first tree has the root as 1 representing the first position.
second tree has the root as 2 representing the second position and
third tree has the root as 3 representing the third position.
We ll have 1 map - Map<int,<String,int>>. Each map represents the position and the character with the count of occurences of that character in that posisiton. first int represents the position and the map associated is of type <string, int>. The string represents the character and int represents the count of occurences of that character in that position.
Now, from the file, we start reading each word, character by character and start constructing the trees.
Now, first word is ABC.
when we read the first position, its A, now to the tree with root as 1, add a child node and keep a counter for edge A to B and increment on every occurence of A in first position.
1
1 --------- B
|
3 |
|
A
So, the map will look like <1,<("A",3),("B",1)>>
Similarly, for position 2, after constructing the tree, map will look like
<1,<("A",3),("B",1)>>
<2,<("B",2),("C",1),("D",1)>>
For Position 3, after constructing the tree, map would look like
<1,<("A",3),("B",1)>>
<2,<("B",2),("C",1),("D",1)>>
<3,<("C",1),("D",2),("B",1)>>
Looking at this create, another map - Map<int,String> representing position and string to be prompted.
The final map would look like -
<1,"A">
<2,"B">
<3,"C">
So, when user types A in the first position, we look at the map for second position and pick the character to be prompted.
For each position maintain a count array containing number of occurrences of a particular character and a structure that represents the current maximum count of the character and the character itself. Lets say we read ABC
For pos 1, count['a'] = 1 maxCount=1 and char = 'a'
For pos2, count['b'] = 1 maxCount=1 and char = 'b'
For pos3, count['c'] = 1 maxCount=1 and char = 'c'
Next we read BCD
For pos 1, count['a'] = 1, count['b '] = 1, maxCount=1 and char = 'a' (change only if maxCount is exceeded by incremented count)
For pos2, count['b'] = 1, count['c'] = 1, maxCount=1 and char = 'b'
For pos3, count['c'] = 1, count ['d']=1, maxCount=1 and char = 'c'
Next we read CBA
For pos 1, count['a'] = 1, count['b '] = 1, count['c '] = 1, maxCount=1 and char = 'a'
For pos2, count['b'] = 2, count['c'] = 1, maxCount=2 and char = 'b'
For pos3, count['c'] = 1, count ['d']=1, count ['a']=1, maxCount=1 and char = 'c'
Whenever user types we look at maxCount for position being typed and suggest the character
The following is in C#
class Position
{
List<Alphabet> alphabets = new List<Alphabets>();
public Position(char defaut)
{
alphabets.Add(new Alphabet() { alphabetName = default});
}
internal void OnEnter(char alphabetname)
{
if(!alphabets.Exists((alphabet) => alpabet.alphabetName == alpabetname))
{
alphabets.Add(new Alphabet() { alphabetName = alphabetname});
return;
}
var alphabet = alphabets.FirstOrDefault((alphabet) => alpabet.alphabetName == alpabetname);
alphabet.Entered();
}
internal string GetMaxOccurrence()
{
Alphabet maxOccurrence = alphabets.ElementAt(0);
foreach(var alphabet in alphabets)
{
if(maxOccurrence == alphabet) continue;
if(maxOccurrence.times < alphabet.times)
maxOccurrence = alphabet;
}
return maxOccurrence.alphabetName;
}
}
Class Alpabet
{
char alphabetName;
int times =1;
internal void Entered()
{
times ++;
}
}
void Initialize(List<Position> positions)
{
positions.Add(new Position('A'));
positions.Add(new Position('B'));
positions.Add(new Position('C'));
}
static void Main()
{
List<Position> positions = new List<Positions>();
Initialize(positions);
Console.WriteLine("Defaultly prompted Characters");
Console.WriteLine(string.Format("Prompting on position 1: {0}", positions[0].GetMaxOccurrence());
Console.WriteLine(string.Format("Prompting on position 2: {0}", positions[1].GetMaxOccurrence());
Console.WriteLine(string.Format("Prompting on position 3: {0}", positions[2].GetMaxOccurrence());
position[0].OnEnter(B);
position[0].OnEnter(B);
position[1].OnEnter(C);
position[1].OnEnter(C);
Console.WriteLine("");
Console.WriteLine("After inserting B 2 times in position 1 & C 2 times in position 2");
Console.WriteLine(string.Format("Prompting on position 1: {0}", positions[0].GetMaxOccurrence());
Console.WriteLine(string.Format("Prompting on position 2: {0}", positions[1].GetMaxOccurrence());
Console.WriteLine(string.Format("Prompting on position 3: {0}", positions[2].GetMaxOccurrence());
}
Output:
Defaultly prompted Characters
Prompting on position 1: A
Prompting on position 2: B
Prompting on position 3: C
After inserting B 2 times in position 1 & C 2 times in position 2
Prompting on position 1: A
Prompting on position 2: B
Prompting on position 3: C
The solution is to find out maximum occurring element from second position till last
For example for below input
ABC
BCD
CBA
We need create a map that will have the below
0th index - skipping it as not needed
1st index - 'B' occurs max times count = 2
2nd index - All have same no of occurrence but storing 'C' as it came first
HashMap
-------------
Key - Index
Value - <Character, Count> (although count not required if its not an online algorithm)
Steps:
1. First take all the elements falling in column 2 from (ABC,BCD,CBA) which is 'B', 'C', 'B'
2. Put them in a Hash and increment count for no of occurences and make sure you note down separately the first element you have processed, as it will be used in cases of equal occurences of elements.
3. Note down the max occurring character and count in a structure or Hashmap with key as column index and value as character.
4. Repeat the above steps for all columns.
Now as the user inputs suggest him the next word.
This is a class that will always suggest the same thing for the same position no matter what the user has typed - it is fully determined from the file given. It is best in this case to analyze the words in the file completely and simply store that answer for O(1) access in the future.
This is not an algorithmically hard question, and there is definitely no advantage to pulling out fancy data structures. It's there to see if you consider all the small gotchas (E.g. he wanted you to ask "Can I assume all the files are lowercase? Do you want me to treat lowercase and uppercase differently? etc."
Here is a solution that treats all input as lowercase even if it wasn't. It ignores non-alphabetical letters. It assumes there is at least one alphabetical entry in the list of words. If not, the default char value will be a zero, indicating an error to the user.
class Suggest
{
using size_type = string::size_type;
public:
Suggest(istream &in);
char letter(size_type pos);
private:
string letters;
};
Suggest::Suggest(istream &in)
{
// read in all the words & keep track of longest length
vector<string> words;
string word;
size_type biggest = 0;
while(in >> word)
{
words.push_back(word);
biggest = max(biggest, word.size());
}
// For each position, count occurrences and derive an answer. O(n)
for(int index = 0; index < biggest; ++index)
{
vector<pair<int, int>> alphaCount(26); // letter maps to <count, firstOccurence>
int occurrence = 0;
for(string &word : words)
{
if(index >= word.size() || !isalpha(word[index]))
continue;
auto &record = alphaCount[tolower(word[index]) - 'a'];
if(record.first == 0)
record.second = ++occurrence;
++record.first;
}
// Save the answer
int soonest = occurrence+1;
int most = 0;
char bestLetter;
for(int let = 'a'; let < alphaCount.size() + 'a'; ++let)
{
auto const &p = alphaCount[let-'a'];
if(p.first > most || soonest > p.second)
{
most = p.first;
soonest = p.second;
bestLetter = let;
}
}
letters.push_back(let);
}
}
char Suggest::letter(size_type pos)
{
// If the request is out of bounds, send a non-letter error cod
if(pos >= letters.size())
return 0;
return letters[pos];
}
The if statement is slightly faulty. It should be
if(p.first > most || (p.first == most && soonest > p.second))
Use a _dumbfuck_ trie and store size of subtree in each node like a ordered statistics tree you _dumbfuck_
I am smarter than you because you are a _dumbfuck_ _troll_ and you post _easy_ _dumbfuck_ questions.
One approach could be to store data in char matrix (char[][] ) and then start reading data from second column to n-1 column . Use Dictionary<int,char> to store result of column scan
Here are the rule of reading data in column
- Find max occurrence of character in selected column
- if you find single character having max occurrence then add that character to dictionary with column as key. For example while traverse first column you found A having max occurrence then you will add <1,A>
- In case all character have same occurrence add first character of selected column to dictionary. In case of Column 2 it will <2,C>
Now use this dictionary to get next character.
Space complexity will be O(n) and Time Complexity will be O(n) [as finding max occurrence require traversal of column].
Please let me know if I am missing any logic here...
- zahidbuet106 December 06, 2013public class AutoSuggestion { //assuming max word length to be 80 int frequency[80][26] = {0}; int mostFreequent[80] = {0}; public AutoSuggestion(String filename) { BufferredReader br = new BufferredReader(new FileReader(fileName)); String word = “”; while((word=br.readLine())!=null) { word = word.toLower(); for(int i=0;i<word.length();i++) { frequency[i][word.charAt(i)-’a’]++; } } for(int i=0;i<80; i++) { int maxPos = 0; int maxFreq = -1; for(int j=0;j<26; j++) { if(frequency[i][j] > maxFreq) { maxFreq = frequency[i][j]; maxPos = j; } } mostFrequent[i] = maxPos; } } public String suggest(String text) { if(text.length() > 80) return “”; StringBuilder sb = new StringBuilder(text); sb.append(mostFrequent[text.length()]); return sb.toString(); } }