Bastille Agency Test

Models.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Bastille
{
    /// <summary>
    /// Yes, pretty controversial using inheritance for code reuse! I personally think this approach is demonised unfairly. In giant projects,
    /// it makes sense though - you need that extra insulation. Otherwise its been very convenient in my 20 years of development.
    /// </summary>
    public class StringToStringListMap : Dictionary<string, List<string>>
    {
        /**
        Input: 
        userToken(String), URL(String)

        Return: 
        A boolean value of whether or not the URL was successfully saved. 
        If the URL has been saved for the user previously, this function
        should not save it and return false. 
        */
        public bool saveUrl(string userToken, string url)
        {
            // First off, validate the URL. Ignore the result. This will be GCd easy enough.
            var uri = new Uri(url);
            return saveKeyValue(userToken, url);
        }

        public bool saveDomain(string domain, string userToken)
        {
            return saveKeyValue(domain, userToken);
        }

        public bool saveKeyValue(string key, string value)
        {
            if (!ContainsKey(key))
            {
                this[key] = new List<string>() { value };
                return true;
            }

            var l = this[key];
            if (l.Contains(value))
                return false;

            l.Add(value);
            return true;
        }

        /**
         * getUrls(userToken)

            Input: 
            userToken(String)

            Return: 
            A collection of all the URLs that user has saved, if any.
        */
        public ICollection<string> getUrls(string userToken)
        {
            return getValues(userToken);
        }

        public ICollection<string> getValues(string key)
        {
            var l = new List<string>();     // probably dont need to initialise this.
            TryGetValue(key, out l);
            return l;   // l will be null if the user token wasnt found
        }

        /**
         * removeUrl(userToken, URL)

            Input: 
            userToken(String), URL(String)

            Return: 
            A boolean value of whether or not the URL was successfully deleted. 
            If the URL to be deleted had never been saved, the function should 
            return false.
            NOTE: also returns false if the token was never saved before. Also, should refactor the "is token-url pair known?" logic out.
        */
        public bool removeUrl(string userToken, string url)
        {
            return removeValue(userToken, url);
        }

        public bool removeValue(string key, string value)
        {
            if (!ContainsKey(key))
                return false;   // this isnt mentioned in the spec but makes sense to me.

            var l = getUrls(key);
            return l.Remove(value);

            // TODO should we delete empty lists? Probably not, as long as saveKeyValue() etc. handle empty lists, which they do.
        }
    }
    
    /// <summary>
    /// An encapsulated list of URLs. Why not just use List<Uri>? because invariably down the road youll want some extra method such as
    /// Concat() or Validate() which isnt on List<Uri> and then youll have to write a helper class, which is suboptimal.
    /// </summary>
    // NOTE ended up not using this class but keep around to show my approach.
    [Obsolete]
    public class UrlList
    {
        private List<Uri> Urls { get; set; }

        /// <summary>
        /// Since this constructor calls new Uri(), it will "fail fast" and throw a UriFormatException if the URL isnt valid which is helpful.
        /// </summary>
        /// <param name="urls"></param>
        public UrlList(List<string> urls)
        {
            Urls = urls.Select(x => new Uri(x)).ToList();
        }
    }    
}

Repository.cs

using System.Collections.Generic;

namespace Bastille
{
    /// <summary>
    /// This class is the entry point to the URL-saving system. It has UserTokensToUrls which backs the saving and fetching of usertoken-url 
    /// pairs ( PROBLEM #1 ).
    /// It also has DomainsToUserTokens which backs the getUsersByDomain() method ( PROBLEM #2 )
    /// I spent ~ 1 - 1:30 on this including noodling around with Node.js a bit first and then opting for C#. 
    /// I didnt use any external resources other than SO for looking up time complexity of C# Dictionary methods.
    /// 
    /// The only potentially slow bit of this design is the List<string>.Contains() call in the StringToStringListMap class which will 
    /// be O(N). This shouldnt be an issue unless users are storing millions of URLs each, which would be highly unlikely. 
    /// But you never know with those pesky users always spoiling things... ;)
    /// </summary>
    public class Repository
    {
        private StringToStringListMap UserTokensToUrls = new StringToStringListMap();

        private StringToStringListMap DomainsToUserTokens = new StringToStringListMap();  // see getUsersByDomain()

        /// <summary>
        /// This would call the supplied extractDomain method. You could get all fancy and use DI / IOC to supply the implementation
        /// but thats likely overkill.
        /// </summary>
        /// <param name="url"></param>
        /// <returns></returns>
        private string extractDomain(string url)
        {
            return "";  // TODO
        }

        /**
        Input: 
        userToken(String), URL(String)

        Return: 
        A boolean value of whether or not the URL was successfully saved. 
        If the URL has been saved for the user previously, this function
        should not save it and return false.
        */
        public bool saveUrl(string userToken, string url)
        {
            // Stick the domain in a separate map for O(1) retrieval
            DomainsToUserTokens.saveKeyValue(extractDomain(url), userToken);
            return UserTokensToUrls.saveUrl(userToken, url);
        }

        /**
         * removeUrl(userToken, URL)

            Input: 
            userToken(String), URL(String)

            Return: 
            A boolean value of whether or not the URL was successfully deleted. 
            If the URL to be deleted had never been saved, the function should 
            return false.
            NOTE: also returns false if the token was never saved before. Also, should refactor the "is token-url pair known?" logic out.
        */
        public bool removeUrl(string userToken, string url)
        {
            DomainsToUserTokens.removeValue(extractDomain(url), userToken);     
            return UserTokensToUrls.removeUrl(userToken, url);
        }


        /**
         * getUrls(userToken)

            Input: 
            userToken(String)

            Return: 
            A collection of all the URLs that user has saved, if any.
        */
        public ICollection<string> getUrls(string userToken)
        {
            return UserTokensToUrls.getValues(userToken);
        }


        /**
         * getUsersByDomain(domain)

            Input: 
            domain(String)

            Return: 
            A collection of user tokens who have saved URLs that belong to that domain.

            NOTE: so the trade off here is time v.s. space as usual. These days of enormous amounts of RAM and services like AWS Elasticache,
            I favour using up space since you can easily get more. Well, more easily than you can get "more" speed that is. Hence Im opting 
            for using up more space by storing the domains in addition to the URLs.
        */
        public ICollection<string> getUsersByDomain(string domain)
        {
            return DomainsToUserTokens.getValues(domain);
        }
    }
}

Hi, comments and explanations of my approach are in the code in the appropriate places. In summary I implemented Problems #1 and #2 in 1 - 1:30hrs. I did not have time for unit tests or Problem #3. This solution should meet time complexity requirements, assuming the hash buckets remain sufficiently balanced. Also assuming no one user adds millions of URL's...

With more time I would also refactor the URL-y aspects of StringToStringListMap out into a separate class, they don't belong on a generic-sounding class. That's actually one subtlety where the implementation might be hard to follow. One StringToStringListMap object is used to store UserToken --> [ URL ] and another is used to store Domain --> [ UserToken ].

@sming - thanks so much for taking the time in doing our assessment! I enjoyed your code, as well as your comments about how you thought about the problem. Some feedback:

• Your solutions to #1 and #2 look good and would work. I understand why you used inheritance, but agree with your comment that the StringToStringListMap class has very specific implementations for this problem. So i'd either rename it to something more specific to this exercise, or make the implementation more generic and remove the specific saveUrl and saveDomain functions. Alternatively, I'd imagine you could just use a Dictionary<String, Set> (I assume C# has a Set implementation) - that way, it would take care of not re-adding URLs that have already been saved, and would be able to use hashing so that even if a user had saved a million URLs, you wouldnt have to search through all of them to see if it exists.
• I liked how you stored domains separately in its own datastructure to make run-time more optimal for #2. Also, enjoyed your comments and thoughts

Would love if you could take a pass at #3 (even if its pseudo-code) we have a more holistic sense of your technical abilities when you have a chance! Looking forward to working together!