Weekly Problem #14

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


Problem Statement

You are writing software to help someone understand their very complicated family. Your task is to determine all aunts and uncles of a given person. An aunt or uncle of a person is defined as a sibling of that person's parent. Two people are siblings if they have one or more parents in common.

Create a class AuntUncle that contains a method list which receives a tvector<string>, with each element containing a record of a person's birth - in the form of "PARENT1 PARENT2 CHILD" (quotes for clarity only), and a single String with the target person's name, and returns a tvector<string> of all aunts and uncles for that target person, sorted alphabetically.

Definition

Class

#include<string> using namespace std; #include "tvector.h" class AuntUncle { public: tvector<string> list(const tvector<string>& parents, const string& target) { // fill in code here } };

Notes

Constraints

Inputs are valid (you don't need to check) if all of the following criteria are met:

Examples

In each of these examples, quotes ('"'), commas (','), and curly braces ('{' and '}') are included for clarity only. They are never part of the input or output.
  1. parents = {"JOE JANE ROB"}
    target = "ROB"
    
    Returns: {}

    Target "ROB"'s parents do not have parents, let alone siblings. "ROB" has no uncles or aunts.

  2.     
    parents = {"JOE MARY FRANK", "BOB JANE MARTHA", "FRANK MARTHA ROB", 
               "BOB AMANDA TROY"}
    target = "ROB"
    

    Returns: {"TROY"}

    Target "ROB"'s parent "MARTHA" has a parent "BOB" who has a child other than either of "ROB"'s parents. This child is named "TROY", and must be "ROB"'s Uncle (or Aunt).

  3. parents = {"HECTOR DANA ROB", "ROB MARY JOE", "JOE MARY FRANK"}
    target = "FRANK"
    
    Returns:{}

    Target "FRANK"'s parent "MARY" is also his parent "JOE"'s parent. Be careful you don't think "FRANK" is his own Uncle (or Aunt).

  4. parents = {"A B E", "C D F", "E F G", "A P Z", "B P Y", "C P X", "D P W", 
               "A B V", "B C U", "A C T", "B D S", "A D R", "B C Q"}
    target = "G"
    
    return: {"Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"}

    Note that the answer is sorted alphabetically.


Owen L. Astrachan
Last modified: Wed Jul 23 10:30:05 EDT 2003