CSPrasad
BAN USERIts a classic anagram check problem with a twist. Assuming that the letters are alphabets, you can declare a integer array of size 26, increment the character count as you scan the note. Decrements the count as you scan the magazine. Finally when you scan the character count array, it should have values >=0
- CSPrasad January 06, 2012In database table (and corresponding class) holding user info, a field of incorrect_attempts_count is declared.
A thread (say login thread) monitors this class/table and When the incorrect attempts are made by user it increments the count.
A Queue (underlying implemenation using LinkedList ) is maintained where each node of queue contains 2 feilds as
Struct Node
{
unsigned int userid;
datetime timeInserted;
}
When user does 5 consecutive incorrect attempts a node having user id and current time info is inserted into Queue.
A timer thread runs every minute and peeps into the front-end of Queue. If currenttime -Insertion time < 1 Hr it leaves queue as it is. Otherwise it keeps on removing the nodes until it finds a node whose duration is < 1 Hr or it hits the front of the list.
Now for all the removed nodes,
1. It can only set the incorrect_attempt_count_to 0;
2. If timer is generic, post these nodes to different thread
3. on a good design note, user info class should have a thread function which can be signaled by this thread to reset its incorrect_attempt_count
The advantage of Queue is looking at the front node, we can confirm that all the nodes inserted after that have not exceeded 1 hour time limit (i.e. O(1) complexity)
I think Lazy deletion should not happen in an array list. The expectation from array list is
Access = O(1)
Insertion/deletion = O(n)
When you delete an element, all the elements to the right have to be left shifted by 1 element . The reason is, again next access to the array list is O(1). If you flag the deleted elements this cannot meet that..
Also I think threshold should always be n (with capacity increment of kn where k is the number of times u exceed the size). However this is implementation dependent.
RepMariaHobbs, Consultant at Adobe
Hi, I am Maria Hobbs from NewYork.Teach career development courses for designated areas. Develop, evaluate and revise course materials ...
Excellent!!
- CSPrasad January 06, 2012