y1426i
BAN USERpattern = "aba"
matches = [];
while(1) {
var c = getStream();
var i = matches.length;
while (i--) {
var rx = new RegEx("^" + matches[i] + c);
if (pattern.match(rx)) {
matches[i] += c;
if (pattern === matches[i]) {
console.log("Match Found");
matches.splice(i,1);
}
} else {
matches.splice(i,1);
}
}
if (c===pattern[0]) matches.push(c);
}
The problem requires us to maintain a searchable queue since I not only have to access the LRU, but also search for a key value in the queue optimally.
One way to attain O(log(n)) search with a well ordered queue is to assign a running number to every item in the queue, which is stored against the hash value of the key.
Let us say for cache size of 3, my input is A, B, C, B.
My queue at the end of 4th input will look like: A, C, B
Searching for B linearly is very expensive. One way to get O(log n) is to add ordered numbering to this queue. One way to do is by assigning every item that is added to the queue a number +1 of the number assigned to MRU.
Thus for this queue, I will have: A1, B2, C3, B4
My queue at the end of 4th input will look like: A1, C3, B4. My hash will look like:
A(1):A Value
B(4): B Value
C(3); C Value
Thus while accessing any key value, I will know the number assigned to it in the queue, and since the way numbering is assigned is in incremental order, I will be able to located that in O(log n) to be able to put it at the end of the queue. The item will then get a new number and the hash key will be updated with that number as well.
Here's a solution in JavaScript:
A working version at - codepen.io/yusufnb/pen/veDBx?editors=001
- y1426i June 05, 2014