Debu
BAN USERWe can also say this question as
find all subsets of set {1-9} where all numbers are repeated m (max size of cheque num) times in the set i.e. {m1s, m2s....m9s} such that the subset is increasing order with difference of 1 or equal and size m.
max number of subset is 2^n. but while creating a subset we can validate if the subset matches the pattern and size is <= m.
creating subset can be done with bit pattern matching from 0-2^n,
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
I agree with autometa.. what do think about my solution below
- Debu February 14, 2013