CareerCup

Well i think the Question is simple we need to match a pattern in O(1)
and the pattern is simple. Its starting with a number and next number is equal to current number or current number+1.
now we need to design a data structure to do that.
so
1ques to interviewer : is there a max size of cheque number.
most probably ans should be yes. say n (makes our life easy)
2. do i have a constrain in memory
most probably he would say consider u have 2-4 gig (cool)
3.since this is a system where we need O(1) sol. there must be large number of cheque to be validated. am i rite?
ans should be yes.

Now problem is a combination question
we need to find all possible unique combinations that can be generated with size less than or equal to n and digits (1-9) and the numbers should be in increasing order.

when ever we create such combination we create it and add to hash table.
and this data is finite set
so 1s we create such table we are done.

example N = 3 and number of digits are 1-2
so possible unique values are
1,
11,
111
2
22
222
12
112
122

I am guess good enough to create a hash table and find it in O(1)
i

First of all I cannot aasume from the problem statement that we are dealing with prefix or suffixes, so I think we could imagine that any check number containing any pattern would be considered a fraud.
Taking this into account, we could apply String matching with finite automata instead of using a Trie. If the automata accepts the string we are done. The running time, without the automata construction preprocessing, is Θ(k) where k is the length of the input to be checked. Neither Trie nor DAFSA provides O(1) running time and the Hash solution proposed by JerryC do not work for suffixes or prefixes because it will only match the exact string.

let me clear the confusion about the question the interviewer asked me:

first of all, the numbers in the pattern are not consecutive so, 36512 could be a prefix. Interviewer asked me first what data structure would you use for efficiently detecting a new cheque. I answered Trie. He said, good, that's the best choice to go. Now, If I say you need to match in O(1) time does your solution still correct. I said yes as we know that number of digits in a cheque number is fixed. SO length of prefixes are constant. That means traversing the trie for a prefix is of constant order i.e. O(1). It is a easy stuff guys, not that complex!!

Hashmap??

Specifically, those are prefixes. So, you want to find any prefix that matches with the new cheque to detect fraud. Straight forward answer is to use a Trie.

Use trie.

with Hashmap you can not do it because prefixes may contain other prefix. it'll take O(n) ultimately.

Eugene is right... .we don't want the runtime to be proportional to the number of patterns... in that sense it is order of constant time actually.

Since we have variable string length, we pin down the length of each string we're checking and only check it against strings of that length. Store the fraud values in linked lists, within a hashtable <integer, linkedlist> The key value integer represents the length of the string. For example, the hashtable entry under key value 8 in this case would be a linked list of 22334455-->11111111-->etc. Then your search is just value.length and run the O(1) search through that list.

Or is that considered O(2) - once for the hashtable and once for the linked list?

using stack>use top[stack] for pushing next element
a[]={let our input is in form of array}
x=each element of array
if(x==top[stack] || x==top[stack]+1)
stack[top]=stack[top]+1
stack[top]=x
else "say invalid"

It has to be a hashtable of patterns

No O(1) solution exists

If you have static keys (they are predefined somewhere), you can use PERFECT HASHING (this is hash of hashes without collissions, see wiki for more details). This allow us to do lookup in O(1) worth time.

Here's my understanding of the problem.

Since the numbers in question are cheque numbers and we can very safely assume that the check numbers are of fixed length which would be around 10. The second thing that I can figure out from this is that the pattern can occur anywhere in the cheque. So it would mean that we cannot use a prefix tree, instead we'll use a suffix tree. The run time for search in a suffix tree is O(n).
Since the length of check is constant, it would be O(c), where c is a constant. And thus constant run time can be easily represented as O(1).
The run time would be O(n) only if the length of the cheque was not a constant, but that is not the case because cheque are of constant length.

@abhisek, you are wrong... the patterns are prefixes from beginning . See my comment above.

Suffix tree requires O(substring length) in this case since the length of check string has an upper bound we will get this in O(1).. The substring cannot exeed the max length string.

How about Rabin–Karp multiple pattern search?

What about Regex??
we can simply define regex patterns for the given strings. It can be one of the answers, can't it??

use trie or suffix tree

What about "bloom filter"? There is a possibility of "False positive" but no "False negative". In fact bloom filter is used for situations such as these

Total digits in Cheque is fixed. Create a trie of all such fraud numbers and for a given number, do lookup in trie to check its existence. This comparison is O(1)

/*The following code will work if the cheque number is a unsigned integer */

BOOL isValid(unsigned long int nL)
{
	int nCR, nPR =nL%10;
	nL/=10;
	while(nL)
	{
		nCR=nL%10;
		if(nPR<nCR)
			return TRUE;
		nPR = nCR;
		nL/=10;
	};
	return FALSE;
}