Two problems, 75 minutes.
The first problem was counting triplets. You're given an array and a number d, and you have to return the number of triplets that satisfy a condition: in each triplet, the difference between the largest number and the smallest number can't be greater than d.
My first solution was to sort the whole array and then use two nested for loops to find the smallest and largest numbers. Loop 1 goes over the whole array. Loop 2 starts from loop 1's pointer and scans to the right until it hits the first number whose difference is greater than d. From the second pass on, loop 2 starts from the index where the previous pass stopped, the first one with a difference greater than d.
This solution was correct and solved half of the cases, but the other half got TLE.
After I finished the second problem I came back to optimize this one. I tried two pointers and binary search too, but my head was foggy from the pressure and I never got the pointers straight. I was fixated on getting rid of the sort, and it never occurred to me that the real problem was the O(n^2). Sorting is O(n log n), so it could simply stay, it's not a big deal, and maybe O(n log n) would have been enough to pass the remaining cases. But I was so stubborn about removing the sort that time ran out and I never solved it.
Now that I write it out, it's actually really clear. Sort first, same as before. Then run a while loop with i, and whenever the difference is greater than d, move i one position to the right. That's at most O(2n), which is O(n), so the whole algorithm is O(n log n).
The second problem was an access system. Each employee id has a time limit T. If [id, t] is set at time t, that employee has access until t+T, but there can't be any gap in between or the access becomes invalid. After everything is set, you count how many are still valid at the last time point.
The solution is a dictionary with key: id and value: max access time. Then you go through them one by one and check whether any expired in the middle, and at the end count how many ids have a value greater than the last timestamp. Time complexity is O(N).
Anyway, I still passed this one. I only failed at a behavioral OA afterwards.
Discussion
Loading comments…