using System;

using System.Collections.Generic;

​

public interface ICache<TKey, TValue> {

    void Set(TKey key, TValue val);

    TValue Get(TKey key);

    bool ContainsKey(TKey key);

}

​

public class DictionaryCache<TKey, TValue>: ICache<TKey, TValue> {

​

    private Dictionary<TKey, TValue> _cache = new Dictionary<TKey, TValue>();

    public void Set(TKey key, TValue val) {

        _cache[key] = val;

    }

    public TValue Get(TKey key) {

        return _cache[key];

    }

    public bool ContainsKey(TKey key) {

        return _cache.ContainsKey(key);

    }

}

​

public class CommonPath {

​

    private ICache<int, string> _cache;

    public CommonPath(ICache<int, string> cache) { 

        _cache = cache;

    }

    public string FindCommonPath(string[] paths){

        return FindCommonPathFromCache(paths);

    }

    private  int GetCacheKey(string[] paths) {

        var hash = string.Concat(paths).GetHashCode();

        return hash;

    }

    private  string FindCommonPathFromCache(string[] paths) {

        var key = GetCacheKey(paths);

​

        if(_cache.ContainsKey(key)){

            return _cache.Get(key);

        }

​

        return GetCommonPath(paths);

    }

    private  string GetCommonPath(string[] paths){

        var commonPathString = string.Empty;

        bool isPathSet = false;

        var rootPath = "";

        foreach(var path in paths) {

            var pathString = string.Empty;

            var parts = path.Split('/');

​

​

            Console.Write(rootPath);

            for(int i=0; i < parts.Length - 1; i++) {

                pathString += parts[i] + '/';

            }

​

            if(!isPathSet ) {

                isPathSet = true;

                commonPathString = pathString;

            }

            if(commonPathString != pathString){

                commonPathString = rootPath;

            }

        }

        var key = GetCacheKey(paths);

        _cache.Set(key, commonPathString);

        return commonPathString;

    }

}

​

​

public class Program

{

​

    public static void Main()

    {

        string[] paths = new string[]{"web/images/image1.png", "web/images/image2.png"};

        Console.WriteLine();

        string[] paths2 = new string[]{"web/assets/style.css", "web/scripts/app.js",  "home/setting.json"};

        string[] paths3 = new string[]{"/system.dll", "/Program.cs",  "/readme.md"};

        var commonPath = new CommonPath(new DictionaryCache<int, string>());

        var result = commonPath.FindCommonPath(paths);

        Console.WriteLine(result);

    }

}