wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Validate String
        
(Message started by: first on Mar 8^th, 2008, 2:05am)

Title: Validate String
Post by first on Mar 8^th, 2008, 2:05am

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.