Amazon Interview Question
Software EngineersTeam: Amazon Alexa
Country: United States
Interview Type: In-Person
All you have to do is to maintain a dictionary of customerID and the list od dates.
You read the file line by line and for each line, put an entry into the dictionary.
Now, let's assume that data are sorted in the file by the date.assuming each date are written in the file in increasing order only.
You will start like this.
Public static List<int> GetConsecutiveCustomer(string filepath)
{
var customeDateMap = new Dictionary<int,List<Date>>();
var streamReader = new StreamReader(new FileStream(filepath, FileMode.Open, FileAccess.Read), Encoding.UTF8);
var consecutiveCustomers = new HashSet<int>();
while((var line = streamReader.ReadLine()) != null)
{
var customerId = Int32.Parse(line.Split('\t')[1]);
var date = Date.Parse(line.Split('\t')[0]);
if(customeDateMap.ContainsKey(customerId)
{
if(customeDateMap[customerId].Length == 3)
{
customeDateMap[customerId].RemoveAt(2);
}
customeDateMap[customerId].Add(date);
if(!consecutiveCustomers.Contains(customerId))
{
if(customeDateMap[customerId].Length == 3
&& customeDateMap[customerId][0] == customeDateMap[customerId][1].AddDays(1)
&& customeDateMap[customerId][0] == customeDateMap[customerId][2].AddDays(2))
{
consecutiveCustomers.Add(customerId);
}
}
}
else
{
customeDateMap.Add(customerId, new List<date>(){date});
}
}
return consecutiveCustomers.ToList<int>();
}
The time complaxity of this Algorithm is O(N) and the space complexity is O(N) only. Where N is is number of lines in the file.
/*
This is the one which should do it
*/
def has_3_consecutive( dates ){
if ( size(dates) < 3 ) return false
ld = list(dates)
// in long form 3 consecutive date are (D - d), D, (D + d)
exists([2: size(dates)]) where { 2 * ld[$.o -1 ] == ( ld[$.o-2] + ld[$.o] ) }
}
ms = mset( file( 'logfile.txt' ) ) as { #(date,key) = $.o.split('\t') ; key }
users_cons = select( ms ) where {
dates = sset ( $.o.value ) as { #(date,key) = $.o.split('\t') ; int( time(date,'MM/dd/yyyy') ) }
has_3_consecutive( dates )
} as { $.o.key }
public Set<String> getLoggedInUsersForConsecutiveThreeDays() throws IOException {
Map<String, Map<Date, Integer>> dataStruc = new HashMap<String, Map<Date, Integer>>();
Path path = Paths.get("c:\\tmp", "test_cc.txt");
Set<String> users = new HashSet<String>();
try (Stream<String> lines = Files.lines(path, StandardCharsets.UTF_8)) {
for (String line : (Iterable<String>) lines::iterator) {
StringTokenizer st = new StringTokenizer(line, "\t");
Date currDate = new Date((String) st.nextElement());
String user = (String) st.nextElement();
if (dataStruc.containsKey(user)) {
Map<Date, Integer> dateDays = dataStruc.get(user);
Date lastDate = dateDays.keySet().iterator().next();
int consecutiveDays = dateDays.get(lastDate);
if (currDate.getTime() - lastDate.getTime() == (24 * 60 * 60 * 1000)) {
consecutiveDays++;
dateDays.remove(lastDate);
dateDays.put(currDate, consecutiveDays);
if (consecutiveDays >= 3) {
users.add(user);
}
} else {
dateDays.remove(lastDate);
dateDays.put(currDate, 1);
}
dataStruc.put(user, dateDays);
} else {
Map<Date, Integer> dateDays = new HashMap<Date, Integer>();
dateDays.put(currDate, 1);
dataStruc.put(user, dateDays);
}
}
}
return users;
}
Public static List<int> GetConsecutiveCustomer(string filepath)
{
var customeDateMap = new Dictionary<int,List<Date>>();
var streamReader = new StreamReader(new FileStream(filepath, FileMode.Open, FileAccess.Read), Encoding.UTF8);
var consecutiveCustomers = new HashSet<int>();
while((var line = streamReader.ReadLine()) != null)
{
var customerId = Int32.Parse(line.Split('\t')[1]);
var date = Date.Parse(line.Split('\t')[0]);
if(customeDateMap.ContainsKey(customerId)
{
if(customeDateMap[customerId].Length == 3)
{
customeDateMap[customerId].RemoveAt(2);
}
customeDateMap[customerId].Add(date);
if(!consecutiveCustomers.Contains(customerId))
{
if(customeDateMap[customerId].Length == 3
&& customeDateMap[customerId][0] == customeDateMap[customerId][1].AddDays(1)
&& customeDateMap[customerId][0] == customeDateMap[customerId][2].AddDays(2))
{
consecutiveCustomers.Add(customerId);
}
}
}
else
{
customeDateMap.Add(customerId, new List<date>(){date});
}
}
return consecutiveCustomers.ToList<int>();
}
how to run it from main method
package hashmaps.careercup.amazon;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;
/**
* Created by Sibendu Dey on 4/25/2017.
*/
class Employee {
String id;
Date lastLogin;
int consecutiveDays;
static final int SECONDS_IN_DAY = 24*60*60*1000;
public Employee(String id, Date date) {
this.id = id;
lastLogin = date;
}
public void incrementConsecutiveDays(Date date) {
if ( consecutiveDays == 3)
return;
if ( (date.getTime() - lastLogin.getTime()) <= SECONDS_IN_DAY) {
consecutiveDays++;
}
else {
consecutiveDays = 1;
}
lastLogin = date;
}
public boolean isConsecutive() {
return consecutiveDays == 3 ? true : false;
}
}
public class ConsecutiveLogin {
public static void main( String args[]) {
Scanner sc = new Scanner(System.in);
int input = sc.nextInt();
sc.nextLine();
HashMap<String , Employee> list = new HashMap<>();
for ( int i = 0 ; i < input ; i++) {
SimpleDateFormat sdf = new SimpleDateFormat("dd/MM/yyyy");
try {
String line = sc.nextLine();
System.out.println(line);
String values[] = line.split("/t");
String dateValue = values[0];
Date date = sdf.parse(dateValue);
String employeeID = values[1];
Employee employee = null;
if ( list.containsKey(employeeID)) {
employee = list.get(employeeID);
employee.incrementConsecutiveDays(date);
}
else {
employee = new Employee(employeeID, date);
list.put(employeeID , employee);
employee.incrementConsecutiveDays(date);
}
} catch (ParseException e) {
e.printStackTrace();
}
}
findEmployeeWithConsecutiveLogin(list);
}
private static void findEmployeeWithConsecutiveLogin(HashMap<String, Employee> list) {
for (Map.Entry<String , Employee > entry : list.entrySet()) {
Employee employee = entry.getValue();
if ( employee.isConsecutive()) {
System.out.println( entry.getKey());
}
}
}
}
Implementation in Java8
required imports
- Mike L April 19, 2017