Телефон поставщики услуг стоимость checket


Вопрос:

У вас есть много звонить поставщикам услуг. У каждого из них есть цены и специальные скидки на многие телефоны.

Разработать алгоритм и структура данных для поддержки, дали номер телефона дать самые доступные цены на все заданные поставщиков в базы данных.

Например:

Поставщик услуг партер имеет цену на 20 копеек на все номера, которые начинаются с +15.... однако для +1507... Цена-70 центов.

Provier служба Verizon имеет цену 30 центов за цифры все, которые начинаются с +15...

Лучшая цена на количество 150741799 должно быть 0,3 от Verizon.

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace JobInterviewTests
{


    [TestClass]
    public class BestCallingPriceTest
    {
        [TestMethod]
        public void GetBestPriceTest()
        {
            string givenPhoneNumber = "150741799";
            CallCenter callCenter = new CallCenter();
            double bestPrice = callCenter.GetBestPrice(givenPhoneNumber);
            Assert.AreEqual(0.3, bestPrice);
        }
    }

    public class CallCenter
    {
        private readonly PricesTrie _pricesTrie;
        public CallCenter()
        {
            _pricesTrie = new PricesTrie();
        }

        public double GetBestPrice(string givenPhoneNumber)
        {
            if (String.IsNullOrEmpty(givenPhoneNumber) || _pricesTrie.Head == null)
            {
                return Double.MaxValue;
            }
            Dictionary<string, double> tempCompanyPrice = new Dictionary<string, double>();

            var phoneCharArray = givenPhoneNumber.ToCharArray();
            var currNode = _pricesTrie.Head.Edges[phoneCharArray[0]];
            for (int i = 1; i < phoneCharArray.Length; i++)
            {
                if (currNode.IsTreminal)
                {
                    foreach (var company2Price in currNode.Company2PriceMap)
                    {
                        //there is already a price for this company you need to update it to the new value
                        if (tempCompanyPrice.ContainsKey(company2Price.Key))
                        {

                            tempCompanyPrice[company2Price.Key] = company2Price.Value;

                        }
                        else // there is no price for this company
                        {
                            tempCompanyPrice.Add(company2Price.Key, company2Price.Value);
                        }
                    }
                }
                if (currNode.Edges.ContainsKey(phoneCharArray[i]))
                {
                    currNode = currNode.Edges[phoneCharArray[i]];
                }
                else
                {
                    break;
                }
            }
            return tempCompanyPrice.Values.Min();
        }
    }

    public class PricesTrie
    {
        public TrieNode Head { get; set; }

        public PricesTrie()
        {
            Head = new TrieNode();
            Init();
        }

        private void Init()
        {
            Head.Edges.Add('1', new TrieNode());
            Head.Edges['1'].Edges.Add('5', new TrieNode());
            Head.Edges['1'].Edges['5'].IsTreminal = true;
            Head.Edges['1'].Edges['5'].Company2PriceMap = new Dictionary<string, double>
            {
                {"Partner", 0.2},
                {"Verizon", 0.3}
            };
            Head.Edges['1'].Edges['5'].Edges.Add('0', new TrieNode());
            Head.Edges['1'].Edges['5'].Edges['0'].Edges.Add('7', new TrieNode());
            Head.Edges['1'].Edges['5'].Edges['0'].Edges['7'].Company2PriceMap = new Dictionary<string, double>
            {
                {"Partner", 0.7}
            };
            Head.Edges['1'].Edges['5'].Edges['0'].Edges['7'].IsTreminal = true;
        }
    }

    public class TrieNode
    {
        public Dictionary<char, TrieNode> Edges { get; set; }
        public Dictionary<string, double> Company2PriceMap { get; set; }
        public bool IsTreminal { get; set; }

        public TrieNode()
        {
            Edges = new Dictionary<char, TrieNode>();
            Company2PriceMap = null;
            IsTreminal = false;
        }
    }
}


153
4
задан 3 февраля 2018 в 10:02 Источник Поделиться
Комментарии
1 ответ

Держать его просто с основной структурой в предположении, что данные хранятся в плоском формате.

public class Rate {
public string Provider { get; set; }
public string Prefix { get; set; }
public decimal Price { get; set; }
}

Provider могли бы так же легко было внешним ключом от поставщика столом.

Расчета лучшей цене сделал выбор ставок, что соответствует префикс, группируя их по поставщику, заказ на длинный соответствующий префикс и с лучшей цене из первой подгруппы

public class CallCenter {

public Rate GetBestPrice(string givenPhoneNumber) {
var available = getRates()
.Where(r => givenPhoneNumber.StartsWith(r.Prefix))
.GroupBy(r => r.Provider)
.Select(g => g
.GroupBy(r2 => r2.Prefix.Length)
.OrderByDescending(g2 => g2.Key)
.First()
.OrderBy(r => r.Price)
.First()
);

return available.OrderBy(r => r.Price).FirstOrDefault();
}

public IEnumerable<Rate> getRates() {
var rates = new List<Rate>() {
new Rate{ Provider = "Parter", Prefix = "15", Price = 0.2M },
new Rate{ Provider = "Parter", Prefix = "1507", Price = 0.7M },
new Rate{ Provider = "Verizon", Prefix = "15", Price = 0.3M },
};
return rates;
}
}

А вот тест на полноту

[TestClass]
public class BestCallingPriceTest {
[TestMethod]
public void GetBestPriceTest() {
//Arrange
var givenPhoneNumber = "150741799";
var expectedPrice = 0.3M;
var expectedProvider = "Verizon";
var callCenter = new CallCenter();

//Act
var actual = callCenter.GetBestPrice(givenPhoneNumber);

//Assert
Assert.IsNotNull(actual);
Assert.AreEqual(expectedPrice, actual.Price);
Assert.AreEqual(expectedProvider, actual.Provider);
}
}

2
ответ дан 4 февраля 2018 в 04:02 Источник Поделиться