Amazon Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
My solution:
I lost the code but I did something like this
- Split the String into a String array of usernames
- Create a TreeMap and iterate through the arrays, if the key is existing, then get the value and increment one, if not create a new key with value 1. (The interviewer was not a big fan of this approach, can we do it better in linear approach?)
- Use a comparator to sort the list by values i.e, largest value on top of the list (He's not convinced by that approach either, he want to combine this time with the previous step into something better)
- Iterate through the map to get the top k elements in a List (Map.Entry) (He said define No for that because it will affect the space complexity)
Can we do something better than this? Please advise.
If this is a repititive operation we can save the dictionary in memory.
public Dictionary<string, int> FindNumberOfMostLogins(string input, int minNoOfLogins)
{
Dictionary<string,int> dict=new Dictionary<string, int>();
string[] userNames= input.Split(',');
foreach (var username in userNames)
{
if (!dict.ContainsKey(username))
dict.Add(username, 1);
else
dict[username] += 1;
}
return dict.Where(x => x.Value >= minNoOfLogins).ToDictionary(x => x.Key, x => x.Value);
}
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
public class AmazonLogged {
public static void main(String[] args) {
String input = "user1, user4, user2, user1, user3, user1, user2, user3";
int key = 2;
process ( input, key );
}
public static void process (String input, int key ){
HashMap<String, Integer> hashMap = new HashMap<>();
for (String strSplit : input.split(",") ){
strSplit = strSplit.trim();
if (hashMap.containsKey(strSplit)){
hashMap.put(strSplit, hashMap.get(strSplit).intValue()+1);
}else{
hashMap.put(strSplit, 1);
}
}
Iterator<Entry<String, Integer>> iterator= hashMap.entrySet().iterator();
while (iterator.hasNext()){
Entry<String, Integer> entry= iterator.next();
if (entry.getValue() !=key)
{
iterator.remove();
}else
System.out.println(entry.getKey() + " "+key);
}
}
}
public void testIt() {
String str = "user1, user4, user2, user1, user3, user1, user2, user3"; // sort it first
String str2 = "user1, user1, user1, user2, user2, user3, user3, user4"; // after sorting
int count = 0;
String s = "";
StringTokenizer aTokenizer = new StringTokenizer(str2);
Hashtable<String,Integer> ht = new Hashtable<String,Integer>();
while (aTokenizer.hasMoreElements()) {
String aStr = aTokenizer.nextToken();
if (aStr.equals(s)) {
count++;
}
else {
if (s.equals("")) {
s = aStr;
count = count + 1;
}
else {
ht.put(s, new Integer(count));
s = aStr;
count = 1;
}
}
}
}
}
{
public void testIt() {
String str = "user1, user4, user2, user1, user3, user1, user2, user3"; // sort it first
String str2 = "user1, user1, user1, user2, user2, user3, user3, user4"; // after sorting
int count = 0;
String s = "";
StringTokenizer aTokenizer = new StringTokenizer(str2);
Hashtable<String,Integer> ht = new Hashtable<String,Integer>();
while (aTokenizer.hasMoreElements()) {
String aStr = aTokenizer.nextToken();
if (aStr.equals(s)) {
count++;
}
else {
if (s.equals("")) {
s = aStr;
count = count + 1;
}
else {
ht.put(s, new Integer(count));
s = aStr;
count = 1;
}
}
}
}
}
}
class Solution {
public:
struct mycomp
{
bool operator()(pair<int,int> a,pair<int,int> b)
{
if(a.second<=b.second)
return true;
return false;
}
};
vector<int> topKFrequent(vector<int>& arr, int k) {
unordered_map<int,int> m1;
// map<int,int> m2;
priority_queue<pair<int,int>,vector<pair<int,int>>,mycomp> q;
int n=arr.size();
vector<int> res;
if(n==0)
return res;
for(int i=0;i<n;i++)
{
m1[arr[i]]++;
}
unordered_map<int,int> ::iterator it;
for(it=m1.begin();it!=m1.end();it++)
{
q.push(make_pair(it->first,it->second));
}
int i=0;
//vector<int> res;
while(!q.empty()&&i<k)
{
res.push_back(q.top().first);
q.pop();
i++;
}
return res;
}
};
Another try to give an idea.
public class App {
public static void main(String[] args){
String input = "user1, user4, user2, user1, user3, user1, user2, user3";
int k = 2;
HashMap<String,Integer> answer = new HashMap<String,Integer>(getStatistics(input));
display(answer,k);
}
public static HashMap<String,Integer> getStatistics(String input){
HashMap<String,Integer> result = new HashMap<String,Integer>();
String[] splitIntoArr = input.split(",");
for(int ii=0;ii<splitIntoArr.length;ii++){
String temp = splitIntoArr[ii].trim();
int counter = 1;
if(!result.containsKey(temp)){
result.put(temp, counter);
} else {
counter = counter + result.get(temp);
result.remove(temp);
result.put(temp, counter);
}
}
return result;
}
public static ArrayList<ArrayList<String>> sort(HashMap<String,Integer> hashMap){
ArrayList<ArrayList<String>> unSortedArrOfArr = new ArrayList<ArrayList<String>>();
ArrayList<ArrayList<String>> sortedArrOfArr = new ArrayList<ArrayList<String>>();
Set keySet = hashMap.keySet();
for(Object usr:keySet){
ArrayList<String> element = new ArrayList<String>();
element.add(usr.toString());
int numLogIn = hashMap.get(usr);
element.add(Integer.toString(numLogIn));
unSortedArrOfArr.add(element);
}
boolean done = false;
while(!done){
int removePos=0;
int num = Integer.parseInt(unSortedArrOfArr.get(0).get(1));
String urs = unSortedArrOfArr.get(0).get(0);
ArrayList<String> item = new ArrayList<String>();
for(int ii=0;ii<unSortedArrOfArr.size();ii++){
if(num < Integer.parseInt(unSortedArrOfArr.get(ii).get(1))){
num = Integer.parseInt(unSortedArrOfArr.get(ii).get(1));
urs = unSortedArrOfArr.get(ii).get(0);
removePos = ii;
}
}
item.add(urs);item.add(Integer.toString(num));
sortedArrOfArr.add(item);
unSortedArrOfArr.remove(removePos);
// item.clear();
if(unSortedArrOfArr.size()<1){
done = true;
}
}
return sortedArrOfArr;
}
public static void display(HashMap<String,Integer> hashMap, int topNumUsr){
ArrayList<ArrayList<String>> sortedItems = new ArrayList<ArrayList<String>>(sort(hashMap));
ArrayList<Integer> valArr = new ArrayList<Integer>();
for (int ii = 0 ; ii < sortedItems.size(); ii++){
valArr.add(Integer.parseInt(sortedItems.get(ii).get(1)));
}
boolean simpleEnd = false;
if(valArr.get(topNumUsr-1)>valArr.get(topNumUsr)){
simpleEnd = true;
}
if(simpleEnd){
for(int ii = 0; ii<topNumUsr;ii++ ){
System.out.println(sortedItems.get(ii).get(0)+":"+sortedItems.get(ii).get(1));
}
}else{
for(int ii = 0; ii<topNumUsr;ii++ ){
System.out.println(sortedItems.get(ii).get(0)+":"+sortedItems.get(ii).get(1));
}
int compareVal = valArr.get(topNumUsr);
for(int ii = topNumUsr;ii<valArr.size();ii++){
if(valArr.get(ii)==compareVal){
System.out.println(sortedItems.get(ii).get(0)+":"+sortedItems.get(ii).get(1));
}else{
break;
}
}
}
}
}
package com.test.staticthread;
import java.awt.color.CMMException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
public class MaximumNumberOfusersLoggedin {
public static void main(String[] args) {
// TODO Auto-generated method stub
String users = "user1, user4, user2, user1, user3, user1, user2, user3";
int k = 3;
HashMap<String, Integer> hm = new HashMap<>();
for (String user : users.split(",")) {
String temp = user.trim();
if (hm.containsKey(temp))
hm.put(temp, hm.get(temp) + 1);
else
hm.put(temp, 1);
}
List<Entry<String, Integer>> list=new ArrayList<>(hm.entrySet());
Collections.sort(list, new Comparator<Entry<String, Integer>>() {
@Override
public int compare(Entry<String, Integer> o1,
Entry<String, Integer> o2) {
// TODO Auto-generated method stub
return o2.getValue()-o1.getValue();
}
});
for(int i=0;i<k;i++)
{
Entry<String, Integer> entry=list.get(i);
System.out.println(entry.getKey()+"("+entry.getValue()+")");
}
}
}
This solution uses a trie (or radix tree) to solve this problem. In a trie, each character represents an edge. Complexity to insert any user into this trie is O(m), where m is no. of characters in user's name. At the same time, we are also maintaining another sorted doubly linked list, logins, which keeps track of all login counts by every user, sorted from highest to lowest. Insertion complexity into this linked list is O(n), where n is no. of UNIQUE users. Printing top k users from logins list is O(t), where t is no. of entries in result.
#define CHILD_COUNT 128
typedef struct {
struct node *child[CHILD_COUNT];
unsigned int count;
char *str;
} node;
typedef struct {
unsigned int count;
node *user;
struct login *next;
struct login *prev;
} login;
node *createnode() {
node *n = (node *) calloc(1, sizeof(node));
assert( n != NULL);
unsigned int i;
for (i = 0; i < CHILD_COUNT; i++)
n->child = NULL;
n->count = 0;
n->str = NULL;
}
node *insert(node *head, char *str) {
char *p = str;
assert( str != NULL);
while (*p != '\0' ) {
if (head->child[*p] == NULL)
head->child[*p] = createnode();
head = head->child[*p];
p ++;
}
if (head->str == NULL)
head->str = strdup(str);
head->count ++;
return head;
}
void print_top_users(char *str, unsigned int k) {
login * logins = NULL;
node *head = createnode();
construct_trie(head, &logins, str);
print_logins(logins, k);
free_trie(head);
free_logins(logins);
}
void construct_trie(node *head, login **logins, char *str) {
char *token = strtok(str, ',');
while (token != NULL) {
node *n = insert(head, token);
logins = update_logins(*logins, n);
token = strtok(NULL, ',');
}
}
login *update_logins(login *logins, node *n) {
login *p = find_login(logins, n);
if (p == NULL) {
p = (login *) calloc(1, sizeof(login));
assert(p != NULL);
p->count = 1;
p->user = n;
p->next = p->prev = NULL;
} else {
logins = delete_login(logins, p);
}
p->count = n->count;
logins = insert_login(logins, p);
return logins;
}
login *find_login(login *logins, node *n) {
login *p = logins;
while (p != NULL) {
if (p->user == n)
return p;
p = p->next;
}
return NULL;
}
login *delete_login(login *logins, login *p) {
if (logins == p)
logins = logins->next;
if (p->next != NULL)
p->next->prev = p->prev;
if (p->prev != NULL)
p->prev->next = p->next;
return logins;
}
login *insert_login(login *logins, login *p) {
// logins list is empty, this is the first entry
if (logins == NULL) {
p->next = p->prev = NULL;
return p;
}
login *q = logins, *r;
while ((q != NULL) && (q->count > p->count)) {
r = q;
q = q->next;
}
// insert into last of logins list
if (q == NULL) {
r->next = p;
p->prev = r;
p->next = NULL;
return logins;
}
// insert into middle or start of logins list
p->next = q;
p->prev = q->prev;
q->prev = p;
if (p->prev != NULL)
p->prev->next = p;
return logins;
}
void print_logins(login *logins, unsigned int k) {
while ((logins != NULL) && (k != 0)) {
printf("User: %s count: %u\n", logins->user->str, logins->count);
if ((logins->next != NULL) && (logins->next->count < logins->count))
k --;
logins = logins->next;
}
}
void free_trie(node *head) {
if (head == NULL)
return;
if (head->str != NULL) {
free(head->str);
head->str = NULL;
}
unsigned int i;
for (i = 0; i < CHILD_COUNT; i ++)
free_trie(head->child[i]);
free(head);
head = NULL;
}
void free_logins(login * logins) {
if (logins == NULL)
return;
free_logins(logins->next);
free(logins);
logins = NULL;
}
{
public void countNumberOfLogs() throws Exception{
BufferedReader buf = new BufferedReader(new FileReader("C:\\Users\\Desktop\\username.txt"));
Map<String, Integer> map = new HashMap<String, Integer>();
String line;
while((line = buf.readLine()) != null){
String[] str = line.split(",");
for(int i=0;i<str.length;i++){
if(map.containsKey(str[i])){
map.put(str[i], map.get(str[i])+1);
}
else{
map.put(str[i], 1);
}
}
}
System.out.println(map);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
countUsers cu = new countUsers();
try {
cu.countNumberOfLogs();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
}
public static List<String> topUsers(String users, int k) {
return Arrays.stream(users.split(","))
// group users by occurrence - O(n)
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
.entrySet()
.stream()
// group users with same number of occurrences together - O(n)
.collect(Collectors.groupingBy(user -> user.getValue()))
.entrySet()
.stream()
// sort user occurrences - O(n log n)
.sorted((group1, group2) -> Long.compare(group2.getKey(), group1.getKey()))
// limit results to k most frequent
.limit(k)
.flatMap(group -> group.getValue().stream().map(user -> user.getKey()))
.collect(Collectors.toList());
}
Test:
System.out.println(topUsers("user1,user1,user2,user3,user4,user1,user2,user3,user5,user7", 2));
Imports System.IO
Module Module1
Sub Main()
Dim file As StreamReader = New StreamReader("file.txt")
Dim exampleString As String = file.ReadLine()
'Dim exampleString As String = "Hello my name is Tom , and my hobby is to paint "
Dim wordCount As New Dictionary(Of String, Integer)
Dim seperator() As String = {}
Dim splitString() As String = exampleString.Split(",")
For Each part As String In splitString
If wordCount.ContainsKey(part) Then
wordCount(part) = wordCount(part) + 1
Else
wordCount(part) = 1
End If
Next
For Each part As KeyValuePair(Of String, Integer) In wordCount
Console.WriteLine(part.Key + " : is repeated " + part.Value.ToString() + " time")
Next
Console.ReadLine()
End Sub
End Module
Imports System.IO
Module Module1
Sub Main()
Dim file As StreamReader = New StreamReader("file.txt")
Dim exampleString As String = file.ReadLine()
'Dim exampleString As String = "Hello my name is Tom , and my hobby is to paint "
Dim wordCount As New Dictionary(Of String, Integer)
Dim seperator() As String = {}
Dim splitString() As String = exampleString.Split(",")
For Each part As String In splitString
If wordCount.ContainsKey(part) Then
wordCount(part) = wordCount(part) + 1
Else
wordCount(part) = 1
End If
Next
For Each part As KeyValuePair(Of String, Integer) In wordCount
Console.WriteLine(part.Key + " : is repeated " + part.Value.ToString() + " time")
Next
Console.ReadLine()
End Sub
End Module
Imports System.IO
Module Module1
Sub Main()
Dim file As StreamReader = New StreamReader("file.txt")
Dim exampleString As String = file.ReadLine()
'Dim exampleString As String = "Hello my name is Tom , and my hobby is to paint "
Dim wordCount As New Dictionary(Of String, Integer)
Dim seperator() As String = {}
Dim splitString() As String = exampleString.Split(",")
For Each part As String In splitString
If wordCount.ContainsKey(part) Then
wordCount(part) = wordCount(part) + 1
Else
wordCount(part) = 1
End If
Next
For Each part As KeyValuePair(Of String, Integer) In wordCount
Console.WriteLine(part.Key + " : is repeated " + part.Value.ToString() + " time")
Next
Console.ReadLine()
End Sub
End Module
public class Pair {
String s;
int count;
public Pair(String s, int count){
this.s = s;
this.count = count;
}
}
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
public class TopKUserNames {
public static void main(String args[]){
TopKUserNames t = new TopKUserNames();
try {
FileReader f = new FileReader("/Users/navyan/Desktop/textfile");
BufferedReader br = new BufferedReader(f);
try {
String input = br.readLine();
t.getTopk(input, 2);
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
private void getTopk(String input, int k){
if(input==null||input.length()==0)
return;
String[] inputArray = input.split(",");
HashMap<String, Integer> h = new HashMap<String, Integer>();
for(String s:inputArray){
if(h.containsKey(s)){
h.put(s, h.get(s)+1);
}else{
h.put(s, 1);
}
}
PriorityQueue<Pair> queue = new PriorityQueue<Pair>(10, new Comparator<Pair>(){
public int compare(Pair a, Pair b){
return a.count-b.count;
}
});
for(Map.Entry<String, Integer> m:h.entrySet()){
Pair p = new Pair(m.getKey(),m.getValue());
queue.offer(p);
}
List<String> result = new ArrayList<>();
while(queue.size()>0){
Pair temp = queue.poll();
if(temp.count>=k){
result.add(temp.s);
}
}
Collections.reverse(result);
System.out.println(result.size());
}
}
package com.myfiles;
import java.util.*;
import java.io.*;
public class test {
public static void main(String [] args)
{
try
{
File my_file = new File("C:\\Users\\sg0226733\\Desktop\\myfile.txt");
FileReader filereader = new FileReader(my_file);
BufferedReader reader = new BufferedReader(filereader);
String user;
int k =2 ;
int count=0;
ArrayList<String> list1 = new ArrayList<String>();
TreeSet<String> tset = new TreeSet<String>();
while((user= reader.readLine())!=null)
{
String [] tokens = user.split(",");
for(String s : tokens)
{
list1.add(s);
}
tset.addAll(list1);
for(String s : tset)
{
for( String item : list1)
{
if(s.equals(item))
{
count++;
}
}
if (count>=k)
{
System.out.println(s + "(" + count + ")");
}
count =0 ;
}
}
}
catch(IOException e)
{
e.printStackTrace();
}
}
}
try
{ // C# code
string[] input = "user1,user4,user2,user1,user3,user1,user2,user3".Split(',');
int k = 2;
// Find the number of occurance of string store it into dictionary then print strings having count more than k
int noOfOccurance = 0;
Dictionary<string, int> dictNameOccurance = new Dictionary<string, int>();
for (int i = 0; i < input.Length; i++)
{
noOfOccurance = 0;
if (!dictNameOccurance.ContainsKey(input[i]))
{
for (int j = i; j < input.Length; j++)
{
if (input[i] == input[j])
{
noOfOccurance++;
}
}
dictNameOccurance.Add(input[i], noOfOccurance);
}
}
foreach (var item in dictNameOccurance.Where(o => o.Value >= k))
{
Console.WriteLine("{0} ({1})",item.Key,item.Value);
}
Console.ReadLine();
}
catch(Exception e)
{
Console.WriteLine(e.Message);
Console.ReadLine();
}
try
{
string[] input = "user1,user4,user2,user1,user3,user1,user2,user3".Split(',');
int k = 2;
// Find the number of occurance of string store it into dictionary then print strings having count more than k
int noOfOccurance = 0;
Dictionary<string, int> dictNameOccurance = new Dictionary<string, int>();
for (int i = 0; i < input.Length; i++)
{
noOfOccurance = 0;
if (!dictNameOccurance.ContainsKey(input[i]))
{
for (int j = i; j < input.Length; j++)
{
if (input[i] == input[j])
{
noOfOccurance++;
}
}
dictNameOccurance.Add(input[i], noOfOccurance);
}
}
foreach (var item in dictNameOccurance.Where(o => o.Value >= k))
{
Console.WriteLine("{0} ({1})",item.Key,item.Value);
}
Console.ReadLine();
}
catch(Exception e)
{
Console.WriteLine(e.Message);
Console.ReadLine();
}
try
{
string[] input = "user1,user4,user2,user1,user3,user1,user2,user3".Split(',');
int k = 2;
// Find the number of occurance of string store it into dictionary then print strings having count more than k
int noOfOccurance = 0;
Dictionary<string, int> dictNameOccurance = new Dictionary<string, int>();
for (int i = 0; i < input.Length; i++)
{
noOfOccurance = 0;
if (!dictNameOccurance.ContainsKey(input[i]))
{
for (int j = i; j < input.Length; j++)
{
if (input[i] == input[j])
{
noOfOccurance++;
}
}
dictNameOccurance.Add(input[i], noOfOccurance);
}
}
foreach (var item in dictNameOccurance.Where(o => o.Value >= k))
{
Console.WriteLine("{0} ({1})",item.Key,item.Value);
}
Console.ReadLine();
}
catch(Exception e)
{
Console.WriteLine(e.Message);
Console.ReadLine();
}
import java.util.ArrayList;
import java.util.List;
public class FrequentUserLogins {
String[] users;
int k = 2;
public FrequentUserLogins(String[] userNames) {
users = userNames;
}
public String userName() {
List<String> ans = new ArrayList<>();
for (int i = 0; i < users.length; i++) {
if (!ans.contains(users[i])) {
int count = 0;
for (int j = 0; j < users.length; j++) {
if (users[i].equals(users[j])) {
count++;
}
}
if (count >= k) {
System.out.println(users[i] + " " + count);
}
ans.add(users[i]);
}
}
return ans.get(k);
}
public static void main(String[] args) {
String[] users = { "user1", "user4", "user2", "user1", "user3", "user1", "user2", "user3" };
FrequentUserLogins fql = new FrequentUserLogins(users);
fql.userName();
}
}
import java.util.ArrayList;
import java.util.List;
public class FrequentUserLogins {
String[] users;
int k = 2;
public FrequentUserLogins(String[] userNames) {
users = userNames;
}
public String userName() {
List<String> ans = new ArrayList<>();
for (int i = 0; i < users.length; i++) {
if (!ans.contains(users[i])) {
int count = 0;
for (int j = 0; j < users.length; j++) {
if (users[i].equals(users[j])) {
count++;
}
}
if (count >= k) {
System.out.println(users[i] + " " + count);
}
ans.add(users[i]);
}
}
return ans.get(k);
}
public static void main(String[] args) {
String[] users = { "user1", "user4", "user2", "user1", "user3", "user1", "user2", "user3" };
FrequentUserLogins fql = new FrequentUserLogins(users);
fql.userName();
}
}
O(Nlogk) time, O(N) space
- passenger June 05, 2016