Author |
Topic: Validate String (Read 311 times) |
|
first
Newbie
Posts: 22
|
 |
Validate String
« on: Mar 8th, 2008, 2:05am » |
 Quote  Modify
|
Consider a system with families, features and
entities. A family id is 3 character long. (Eg. AAA,
BBB etc.). Features are 5 character long strings in
which the first 3 characters are the family name. (Eg.
AAA01, BBB01, AAA02 etc.)
An entity can be of two types - simple and complex. A
simply entity is a group of n families. A complex
entity has two types of groups of families. One is the
mandatory group. There can be just one mandatory group
in a complex entity. The other is ordinary groups of
families. There are at most n groups with n families
in each in a complex entity. For eg. a complex entity
would look like -
Mandatory group - consisting of families AAA and BBB
Group 1 consisting of - CCC and EEE
Group 2 consisting of - DDD, FFF and GGG.
Now, the input to your system is a string of features
for eg. AAA01, BBB02, CCC03, AAA02.
A string is considered valid if there is one feature
for every family present in the mandatory group and
one feature of just one family in the other ordinary
groups in a complex entity. For eg. the above string
is invalid for the complex entity described as it had
two features from a family in the mandatory group and no feature from group 2. An eg of a valid string could be AAA01, CCC01, FFF02, BBB01. The features in the string could be in any order.
Now, the system has to validate a given set of strings given an entiy. Design a data structure to represent families, features and entites such that validating the string is an O(n) operation or less. Give the algorithm for validation.
|
|
 IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print