Amazon Interview Question
SDE1sCountry: United States
We can use a trie data structure storing the count of the sequence followed to reach the node.
The element nodes store a pointer to a linked list. Whenever we get a sequence we move through the trie and increment the count at the specific node in the linked list using the pointer.
We can traverse the linked list in O(n) to find the most repeated sequence.
Assuming there can be more than 1 three set sequences:
- Anonymous January 07, 2014have a hash table with key as a string (based on sequence of pages, say strcat of the 3) and value as count(integer value).
have a struct having 2 elements-integer value for max count and vector of strings for the 3 page sequence.
if key exists in hashmap increase count, else add to map with value as 1
if (hashmap_count>struct_count)
{
//first call vector.erase
//update struct_count value
// then push back the new sequence string
}
else if (hashmap_count==struct_count)
//push back this string also to the vector. no need to worry about duplicate as it will never happen