Jason
BAN USER- 5of 5 votes
AnswersSay you have a keypad that has keys for the numbers 0 through 9 and the correct code is some sequence of 5 digits. This keypad does *not* reset after entering an incorrect sequence of 5 digits. ie. If the correct sequence is 12345, entering 7512345 will succeed in opening it because it ends in the correct sequence. If the keypad actually resets after every 5 digits pressed, then it would not succeed b/c it would interpret the above sequence as "75123" then "45".
- Jason in United States
1. Write an algorithm that will try to find the correct code for this keypad. Assume you have an API similar to KeyPad.pressKey(int n) where you pass in a number (0...9) and it returns true if the keypad unlocks and false if it's still locked.
Note that you could easily enter all digits of all numbers 00000 through 99999 resulting in 5*100000 key presses, but remember that the panel does not reset after every sequence of 5 digits, so find a way to do this more efficiently. Notice for example that entering the stream 3791283780 will test the length 5 sequences 37912, 79128, 91283, 12837, 28378, 83780; not only the two disjoint sequences 37912 and 83780.
Think of this keypad as remembering the last 4 keys pressed (and the order pressed); when the next key is pressed, if the last 4 keys + the current key equal the correct code, the keypad will unlock. Assume the keypad does all this internally, so you can just keep feeding it keypresses and it will eventually unlock if the last 5 keypresses entered is the correct code.
2. Generalize your algorithm to work for a keypad where you don't know the length of the correct sequence in advance.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
One thing people miss is 0 is an even number, so 0 odd digits also counts (ex. 88, 20, 860)
Here are the answers for various number ranges:
(0 to 9): 5
(0 to 99): 50
(0 to 999): 500
(0 to 9999): 5000
(0 to 99999): 50000
Explanation utilizes combinatorics:
Odd digits: 1, 3, 5, 7, 9 = count of 5
Even digits: 0, 2, 4, 6, 8 = count of 5
For 1 digit, can only have 1 even digit, so answer is 5
For 2 digits, can have 2 odd digits or 2 even digits, so answer is 5*5 + 5*5 = 50
For 3 digits, can have any combination of 2 odd and 1 even digit or 3 even digits = 5^3 + 5^3 + 5^3 + 5^3 = 500
For 4 digits, can have any combination of 2 odd and 2 even digits or 4 even digits or 4 odd digits = 6*5^4 + 5^4 + 5^4 = 5000
For 5 digits, same logic yields 50000
The answer for 100000 is 50000, solves in O(1) time via equation above.
This pattern can be expanded to any provided range to solve the problem in O(k) time where k is the number of digits (length of equation being computed does slowly increase as the number of digits increases).
Ex. write code to calculate count in range [x, y] that contain an even number of odd digits
Brute force code below to check answers I wrote out above:
// Return number of numbers in [0, n] with an even number of odd digits
public static int numEvenOddDigits(int n) {
int total = 0;
for (int i = 0; i <= n; i++) {
int j = i;
int numOddDigits = 0;
while (j > 0) {
if ((j % 10) % 2 == 1) {
numOddDigits++;
}
j /= 10;
}
if ((numOddDigits % 2) == 0) {
System.out.println(i);
total++;
}
}
return total;
}
One approach is to compare based on a secondary value (like a counter for each primary value) in addition to the primary value. This however requires an aux data structure to track this info for each unique heap element, which is fine if there are few unique values.
- Jason June 04, 2015With insertion sort, you're always finding the min element in a range, and putting it at the beginning. This is similar, but you know the min element is within a range of 2k positions from the current. However, if we have a sliding window of size k that moves left to right, we ever only need to look at k elements each time (since anything to the left will be implicitly sorted).
Iow, for each element, search up to k-1 elements to the right of it, find min, swap with current element. Keep going until you hit the 2nd to last element.
This solves a portion of the problem where you need to track the sequence of keys being tested so you can return it (the code) if it's correct. However, what is the sequence of keypresses you will enter to eventually find the correct code in an efficient manner in terms of the number of keypresses?
- Jason May 30, 2015This can be done in O(n) time and space with a selection-rank algorithm.
Ex.
In this context, ith most popular element will have rank i.
Use quicksort's partition to find the location of a random pivot in the list
If rank == pivot location, then return pivot element
If the target rank is < pivot location, recurse on the left half of the list
Otherwise recurse on the right half of the list
I've tried to reword the question a bit to be clearer.
The sequence will never reset. Perhaps a better way to think of this is you are feeding a long stream of keypresses to the keypad where the keypad always remembers the last 4 digits entered (in the order they were entered). Every time you press another key, the keypad looks at the last 4 digits entered and sees if these 4 digits plus your current keypress yield the correct sequence. If so, the API returns true, else false.
1. Have a linked list of timestamps that have at least 1 photo; ordered by time
2. Have a hash that maps from t to:
a) the corresponding timestamp in the linked list above
b) a set of photos taken at t that are not favourite
c) a set of photos taken at t that are marked as favourite
The linked list of timestamps is to quickly find the next available timestamp in O(1) time.
The hash allows for finding a timestamp along with the next available timestamp and photos taken at t, all in O(1) time.
insert(x,t,m): add timestamp t to LL and hash if not exists. Add x to set of photos taken at t (which set depends on m).
search(t) and nextFavourite(t): use hash to find t in linked list, then call next() to get the next timestamp t' if exists. Can then use hash to find t' and the next photo after time t that has a favourite or non-favourite.
Overall, every type of operation (add, remove, search) will be O(1) time.
Space is O(n) where n is the number of photos.
String subtract(Stream s_a, Stream s_b) {
StringBuffer sb = new StringBuffer();
int a, b, c;
while (s_a.hasNext()) {
a = s_a.next();
b = (s_b.hasNext()) ? s_b.next() : 0;
if (a > b) {
sb.add(a - c - b);
c = 0;
} else {
sb.add(10 + a - c - b);
c = 1;
}
}
return sb.reverse().toString();
}
The question didn't say that the result couldn't be stored in memory, but if s_a and s_b can't, then it's possible that we need to read/write the result to disk rather than a StringBuffer.
- Jason May 30, 2015
Because of the 'cost' for each move, this can be reduced to a weighted graph traversal where you want to find the min cost path. Each node is a position on either staircase and has at most 2 outgoing and 2 incoming edges. At that point, something like Dijkstra would work nicely.
- Jason August 07, 2015