一小时内access多次
给 list of [name, time], time is string format: '1300' //下午一点
return: list of names and the times where their swipe badges within one hour. if there are multiple intervals that satisfy the condition, return any one of them.
name1: time1, time2, time3...
name2: time1, time2, time3, time4, time5...
example:
input: [['James', '1300'], ['Martha', '1600'], ['Martha', '1620'], ['Martha', '1530']]
output: {
'Martha': ['1600', '1620', '1530']
}/ We are working on a security system for a badged-access room in our company's building.
// We want to find employees who badged into our secured room unusually often. We have an unordered list of names and entry times over a single day. Access times are given as numbers up to four digits in length using 24-hour time, such as "800" or "2250".
// Write a function that finds anyone who badged into the room three or more times in a one-hour period. Your function should return each of the employees who fit that criteria, plus the times that they badged in during the one-hour period. If there are multiple one-hour periods where this was true for an employee, just return the earliest one for that employee.
// badge_times = [
// ["Paul", "1355"], ["Jennifer", "1910"], ["Jose", "835"],
// ["Jose", "830"], ["Paul", "1315"], ["Chloe", "0"],
// ["Chloe", "1910"], ["Jose", "1615"], ["Jose", "1640"],
// ["Paul", "1405"], ["Jose", "855"], ["Jose", "930"],
// ["Jose", "915"], ["Jose", "730"], ["Jose", "940"],
// ["Jennifer", "1335"], ["Jennifer", "730"], ["Jose", "1630"],
// ["Jennifer", "5"], ["Chloe", "1909"], ["Zhang", "1"],
// ["Zhang", "10"], ["Zhang", "109"], ["Zhang", "110"],
// ["Amos", "1"], ["Amos", "2"], ["Amos", "400"],
// ["Amos", "500"], ["Amos", "503"], ["Amos", "504"],
// ["Amos", "601"], ["Amos", "602"], ["Paul", "1416"]
// ];
// Expected output (in any order)
// Paul: 1315 1355 1405
// Jose: 830 835 855 915 930
// Zhang: 10 109 110
// Amos: 500 503 504
// n: length of the badge records array给一堆input, String[][] badgeTime = {{"Paul", "1355"}, "Amy", "1015", "Paul", "1315", ...}，然后要求找出在一个小时的范围内，三次或者三次以上进入的用户，如果用户有多个解，就输出第一个。假如说，Paul有四个时间，13:15， 13:55， 14:05, 14:16，然后就输出 “Paul: 1315, 1355, 1405”，然后对于所有满足要求的用户都要输出第一个解
https://leetcode.com/discuss/interview-experience/1504226/indeed-karat-interview https://leetcode.com/problems/alert-using-same-key-card-three-or-more-times-in-a-one-hour-period/
import java.util.LinkedList;
import java.util.Collections;
import java.util.List;
import java.util.*;
public class frequentAccess {
public static void main(String[] argv) {
String[][] badgeTimes = new String[][] {
{ "Paul", "1355" }, { "Jennifer", "1910" }, { "Jose", "835" },
{ "Jose", "830" }, { "Paul", "1315" }, { "Chloe", "0" },
{ "Chloe", "1910" }, { "Jose", "1615" },{ "Jose", "1640" },
{ "Paul", "1405" }, { "Jose", "855" }, { "Jose", "930" },
{ "Jose", "915" },{ "Jose", "730" }, { "Jose", "940" },
{ "Jennifer", "1335" }, { "Jennifer", "730" }, { "Jose", "1630" },
{ "Jennifer", "5" }, { "Chloe", "1909" }, { "Zhang", "1" },
{ "Zhang", "10" }, { "Zhang", "109" },{ "Zhang", "110" },
{ "Amos", "1" }, { "Amos", "2" }, { "Amos", "400" },
{ "Amos", "500" },{ "Amos", "503" }, { "Amos", "504" },
{ "Amos", "601" }, { "Amos", "602" }, { "Paul", "1416" }};
String[][] badgeTimes1 = new String[][] { { "Zhang", "1" }, { "Zhang", "10" }, { "Zhang", "109" },
{ "Zhang", "110" } };
Map<String, List<Integer>> res = frequentAccessMethod(badgeTimes);
System.out.println(res);
// Sample outout:
//{Jose=[830, 835, 855, 915, 930], Paul=[1315, 1355, 1405], Amos=[500, 503, 504]}
}
public static Map<String, List<Integer>> frequentAccessMethod(String[][] records)
{
Map<String, List<Integer>> res = new HashMap<>();
// Build the Map from user --> access records
Map<String, List<Integer>> userRecords = new HashMap<>();
for(int i = 0; i< records.length; i++)
{
String name = records[i][0];
int ts = Integer.parseInt(records[i][1]);
userRecords.putIfAbsent(name, new ArrayList<Integer>());
userRecords.get(name).add(ts);
}
for(Map.Entry<String, List<Integer>> entry : userRecords.entrySet())
{
List<Integer> access = entry.getValue();
if(access.size() < 3) continue;
Collections.sort(access);
System.out.println(entry.getKey());
System.out.println(access);
LinkedList<Integer> oneHourSlot = new LinkedList<>();
oneHourSlot.addLast(access.get(0));
int startTime = access.get(0);
for(int j = 1; j< access.size(); j++)
{
if(timeDiff(startTime, access.get(j)) <=60 )
{
oneHourSlot.addLast(access.get(j));
}
else
{
if(oneHourSlot.size() >= 3)
{
if(!res.containsKey(entry.getKey()))
{
res.put(entry.getKey(), oneHourSlot);
}
break;
}
while(!oneHourSlot.isEmpty() && timeDiff(access.get(j), oneHourSlot.getFirst()) > 60)
{
oneHourSlot.removeFirst();
}
oneHourSlot.add(access.get(j));
startTime = oneHourSlot.getFirst();
}
}
}
return res;
}
// b is bigger that a
public static int timeDiff(int a, int b)
{
int hourA = a / 100;
int hourB = b / 100;
int minA = a % 100;
int minB = b % 100;
return Math.abs((hourB*60+minB) - (hourA*60+minA));
}
}
Last updated