0
\$\begingroup\$

I was given the below Exercise as part of a coding Exercise to do at home for a technical interview, and I did not get through past this round.

I would like to get some input on what i could have done wrong. Appreciate your time and effort in providing valuable feedback !!

Exercise : Given the following text file(of a possibly much larger file) as input, write a standalone executable or standalone script that will print to the console or write to a text file the following:

  1. Each household and number of occupants

"Dave","Smith","123 main st.","seattle","wa","43"
"Alice","Smith","123 Main St.","Seattle","WA","45"
"Bob","Williams","234 2nd Ave.","Tacoma","WA","26"
"Carol","Johnson","234 2nd Ave","Seattle","WA","67"
"Eve","Smith","234 2nd Ave.","Tacoma","WA","25"

"Frank","Jones","234 2nd Ave.","Tacoma","FL","23"

"George","Brown","345 3rd Blvd., Apt.200","Seattle","WA","18"

"Helen","Brown","345 3rd Blvd. Apt.200","Seattle","WA","18"

"Ian","Smith","123 main st","Seattle","Wa","18"

"Jane","Smith","123 MainSt.","Seattle","WA","13"


Solution as provided by me>

The List of Households has been modeled as Binary Tree.

Binary Tree has been chosen because the input list of person Records from CSV is not sorted and the Occupants of each HouseHold are scattered across the file.

Apart from this it is quite possible that the sample input provided is only a subset of large dataset and the Binary Tree is easiest way to assign each occupant to his respective HouseHold as the records are read from the CSV file.

Not All Tree datastructure methods are implemented , Nor has been any effort made to ensure the tree is balanced. May be an improvement left in case we need to handle large datasets.

Code :

//Reprsents a Node in the BST with left and Right SubTrees and HouseHold object to hold the Data represented by the Node.

public class Node
{
    public HouseHold houseHold = new HouseHold();
    public Node left;
    public Node right;        
}

class HouseHoldList
{
    public Node root = null;          

    public Node Insert(Record person)
    {
        return root = TreeInsert(root, person);
    }               

    //Inserts Root, Left and Right Nodes in to the Tree Datastructure.
    private Node TreeInsert(Node current ,Record person)
    {
        //NewHouseHold Node
        if (current == null)
        {
            current = new Node();     
            current.houseHold.HomeAddress = person.HomeAddress.ToString();
            current.houseHold.Occupants.Add(new Occupant { FirstName = person.FirstName, LastName = person.LastName, Age = person.Age });

        }

        //Existing HouseHold Node, Add Occupant to the list of Occupants.
        else if (string.Compare(person.HomeAddress.ToString(), current.houseHold.HomeAddress) == 0)
        {
            current.houseHold.Occupants.Add(new Occupant { FirstName = person.FirstName, LastName = person.LastName, Age = person.Age });
        }

        //New Household with Address Alphabetically lower than current, Insert in the left subtree
        else if (string.Compare( person.HomeAddress.ToString(),current.houseHold.HomeAddress) < 0)
        {
           current.left = TreeInsert(current.left, person);                
        }

        //New Household with Address Alphabetically Higher than current, insert in the right subtree
        else if (string.Compare( person.HomeAddress.ToString(),current.houseHold.HomeAddress) > 0)
        {
            current.right = TreeInsert(current.right, person);
        }

        return current;

    }


//Recursive Print All the Tree Nodes and HouseHold information as per the requirements (InOrder Tree Traversal).

    public void Print(Node h)
    {
        if (h != null)
        {
            Print(h.left);
            h.houseHold.PrintHouseHoldInformation();         
            Print(h.right);

        }
    }

// Various Classes to Represent a single Personnel Record, HouseHold and Occupants and address available in CSV Input

public class Record
{
    public string FirstName;
    public string LastName;
    public Address HomeAddress;
    public int Age;

}

/// <summary>
/// Class to Represent the Address
/// </summary>
public class Address
{
    public string Street;
    public string City;
    public string State;

    private static string PunctuationSymbols = "[?!,.;/\']";

    //Default Object Method Overridden to Provide Single Line Representation of Given Address. Punctuaton Symbols Removed, Spaces at extremes Trimmed  
    //and String Converted to UpperCase to Ensure Similar Addresses with Punctuated differences are not intrepeted as Different.


    public override string ToString()
    {
        string unpunctuatedStreet = Regex.Replace(Street.Trim(), PunctuationSymbols, "");
        return string.Concat(unpunctuatedStreet, ',', City, ',', State).ToUpper();
    }
}

public class Occupant : IComparable
{
    public string FirstName;
    public string LastName;
    public int Age;

    //Icomparable Interface implemented to Custom Sort each Occupant. First by LastName, Then by FirstName.

    public int CompareTo(Object obj)
    {
        Occupant other = obj as Occupant;

        if (other is Occupant)
        {

            int returnValue = string.Compare(this.LastName, other.LastName);

            if (returnValue > 0)
                return returnValue;

            else if (returnValue == 0)
            {
                return string.Compare(this.FirstName, other.FirstName);
            }
            else
                return returnValue;
        }

        else
        {
            throw new ArgumentException("Object is not an Occupant");
        }
    }
}


//Class to Hold the Information of Each HouseHold. The Address represented by the HouseHold and Occupants of the HouseHold.

public class HouseHold
{
    public string HomeAddress;
    public List<Occupant> Occupants = new List<Occupant>();

    //Prints Household Information. First sorts the Occupants, and then     prints the Count of Occupants in each HouseHold.

    public void PrintHouseHoldInformation()
    {
        Occupants.Sort();

        Console.WriteLine("\nThe HouseHold at Address:  {0,-20} has {1,-2} Occupants", HomeAddress, Occupants.Count());


        }

    }
}

}

Then Finally the Main method to print the output.

  static void Main(string[] args)
    {
        //Datastructure(BST) to Hold the HouseHold Records as they are read from CSV File.
        HouseHoldList HHList = new HouseHoldList();

        //Read all the Lines from Csv File to a String Array (assumed for now for the path of INPUT File to be the root of the same Directory.)
        string[] Lines = File.ReadAllLines("INPUT_Coding_Excercise.TXT");

        //Format each Line and Map to Csv Record.
        foreach (string line in Lines)
        {
            //Split each line by Dimiliter (which in this case includes Quotes with Escape Character along with the seperator : ',' ,                
            //Regular Expression to Split the Input Line by \" followed by Zero or One Occurence of ,\"
            string[] record = Regex.Split(line, "\"(,\")?");


            //Map the csv fields to a Record Object,Add to the Collection/BST.
            Record csvRecord = new Record {
                                        FirstName = record[1],
                                        LastName = record[3],
                                        HomeAddress = new Address
                                        {
                                            Street = record[5],
                                            City = record[7],
                                            State = record[9]
                                        },
                                        Age = int.Parse(record[11])
                                    };

            HHList.Insert(csvRecord);

        }


        //Print Unique Households and Count of Its Members
        HHList.Print(HHList.root);            

    }
}

}

\$\endgroup\$
1
\$\begingroup\$

Some comments:

Class Properties

Generally, in C# properties are preferred over public variables. This applies to all of your classes.

public class Record
{
    public string FirstName { get; set; }
    public string LastName; { get; set; }
    public Address HomeAddress; { get; set; }
    public int Age; { get; set; }
}

Naive CSV Parsing

Unless specifically disallowed, you should have used a CSV Parser library rather than attempting to handle it yourself. CSV output escaping can get complicated; using a library shows that you recognize that and that you aren't wasting time reinventing the wheel.

Inconsistent Class support

Your Occupant class supports IComparable but your Address class does not. Neither overrides Equals() (and GetHashCode()). Your address class relies heavily on ToString() but then uses a regex to reconstruct itself each time without caching the result. This is a potential slowdown.

Lack of Error Handling

You have none. Especially for things like Age, you are parsing to an int and assuming it works. You should have used Int32.TryParse(). Additionally, your handling of string case is inconsistent in Occupant. Someone with the same name in different cases would be treated as different people.

Unnecessary Work

You sort Occupants alphabetically, to no purpose. You only need to return the count.

Unchecked Recursion

If the CSV file has millions of records, your recursive functions are likely to run out of stack space. Your choice of binary tree shows knowledge of data structures, but I'm not sure it is the best choice for this problem.

\$\endgroup\$
2
  • \$\begingroup\$ I do agree with all your points, Thank for the input !!. But on the last one, as u mentioned i should have chosen may be iterative over recursion to print the nodes. But any idea what other datastructure would be appropriate ? I thought about it a lot and the Binary Tree seemed most appropriate at that point of time. \$\endgroup\$ May 5 '16 at 15:31
  • \$\begingroup\$ I probably would have gone with either a Dictionary<Address, List<Occupants>> or a SQL Lite database. \$\endgroup\$
    – Zack
    May 5 '16 at 16:16
0
\$\begingroup\$

I try to avoid implementing IComparable because CompareTo() is verbose, and, as Zack mentioned, you also have to override Equals() and GetHashCode(). Instead of implementing IComparabale and writing this:

Occupants.Sort();

You could write this:

Occupants = Occupants.OrderBy(x => x.LastName).ThenBy(x => x.FirstName).ToList();

This uses Enumerable.OrderBy() and Enumerable.ThenBy().

Edit: If LINQ isn't allowed, here is an alternate solution:

Occupants.Sort((x, y) => string.Compare(x.LastName, y.LastName) != 0 ? string.Compare(x.LastName, y.LastName) : string.Compare(x.FirstName, y.FirstName));

It's technically not LINQ. If they still object, you can declare the method separately:

private int CompareByLastNameThenFirstName(Occupant x, Occupant y)
{
    int lastNameComparison = string.Compare(x.LastName, y.LastName);
    if(lastNameComparison != 0)
    {
        return lastNameComparison;
    }
    return string.Compare(x.FirstName, y.FirstName);
}

And then use it in place of the lambda expression:

Occupants.Sort(CompareByLastNameThenFirstName);
\$\endgroup\$
2
  • \$\begingroup\$ I did exactly this on my first attempt. They rejected the solution and asked me to not use Linq. It was pretty straight forward with Linq. Thanks for the input though !! \$\endgroup\$ May 5 '16 at 15:20
  • \$\begingroup\$ @EricArthurBlair I added some alternatives. \$\endgroup\$ May 5 '16 at 21:13
0
\$\begingroup\$

Is something wrong with the standard collections provided by the .NET core libraries? Just implementing the binary tree was probably enough to be considered a bad implementation.

Your binary tree could be fantastically good, but it was totally unnecessary to write it. When you are implementing a library, you do this.

It would be equivalent to me assigning you to drill a hole, and laying a drill on the bench right next to where the hole must be. You then say, "hang on while I wind the motor armature in this custom made drill I fabricated for drilling that hole"

\$\endgroup\$
1
  • \$\begingroup\$ I tried using Dictionary<string address, list<occupants>(); but we cannot add the items to the list as we sort through the records. we can add only the list. May be i am missing something ? Can you suggest which standard collection fits this requirement. \$\endgroup\$ May 7 '16 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.