Как эффективно найти диапазон, в который попадает число? - PullRequest
Новая
       27

Как эффективно найти диапазон, в который попадает число?

0 голосов
/ 06 марта 2019

В ходе собеседования мне был задан следующий вопрос:

С учетом системы градуированного подоходного налога:

  • До 10000 облагается налогом по10%

  • 10001–50000 облагается налогом по ставке 20%

  • 50001 и выше облагается налогом по ставке 30%

Напишите программу для расчета налогов на данный доход.

Пример:

  • Налоги на 15000 будут (20% от 5000 + 10% от10000) = 2000

  • Налоги на 60000 будут (30% от 10000 + 20% от 40000 + 10% от 10000) = 12000

Я придумал следующий псевдокод: 

list = (
    (1, 10000, 0.1)
    (10001, 50000, 0.2)
    (50001, infinity, 0.3)
)

taxableIncome = income
taxes = 0
while taxableIncome > 0
    find e in list such that taxableIncome is in range [e[1], e[2]]
    taxes += taxableIncome - e[1] + 1
    taxableIncome = e[1] - 1

return taxes

Вышеописанное работает, но в наихудшем случае занимает квадратичное время по количеству элементов в списке.Рассмотрим случай для дохода = 60000;код повторяется 3 раза, каждый раз потенциально сканируя весь список.

Есть ли более быстрый способ узнать, в какой диапазон попадает доход? Этот вопрос имеет несколько решений на Python, но меня интересует общее алгоритмическое решение, а не библиотека.

Ответы [ 2 ]

4 голосов
/ 06 марта 2019

Пересчитайте значение налога для начала каждого диапазона и включите это значение в список.

Также я убрал чрезмерный верхний предел, как заметил в комментариях Диллон Дэвис, и изменил нижнее значение на конец предыдущего диапазона, чтобы сделать формулу более точной 

 list = (
        (0, 0, 0.1)
        (10000, 1000, 0.2)
        (50000, 9000, 0.3)
    )

Для данного дохода найти подходящий диапазон с линейным поиском (если количество диапазонов мало) или с двоичным поиском (если много диапазонов - десятки, сотни и т. Д.)

Тогда просто рассчитайте налог по простой формуле 

  tax  = e[2] + (income - e[1]) * e[3]

enter image description here

Для дохода 15000 мы можем найти 

range = 2nd interval (10000, 1000, 0.2)
tax = 1000 + (15000 - 10000) * 0.2 = 
      1000 + 5000 * 0.2 = 2000

Или (используя предложение Диллона Дэвиса) 

  tax  = income * e[3] + (e[2] -  e[1]) * e[3])
  tax  = income * e[3] + e[2]'

с предварительно рассчитанным значением e2' = (e[2] - e[1]) * e[3]) для каждого диапазона

Общая сложность линейная или логарифмическая (с БС)

0 голосов
/ 07 марта 2019

ОП здесь: ответ @ MBo заставил меня задуматься (за это проголосовал за него), но, к сожалению, он не объяснил это так, как мне показалось достаточно ясным, поэтому мы идем.

ПозвольтеN будет числом скобок.

НАИВНЫЙ ПОДХОД: Линейный поиск соответствующей налоговой скобки, вычисление налога на избыточный доход в скобке, а затем рекурсивное вычисление налогов наналогооблагаемый доход ниже скобки.Например, доход 15000 попадает в скобку, которая начинается с 10001;налоги на эту скобку составляют (15000 - 10000) * 0.2 = 1000 + налоги на 10000.Это работает, но линейный поиск может занять O(N) в худшем случае, и если начальный доход падает в наивысшей скобке, код будет повторяться N раз.В итоге мы получаем алгоритм O (N ^ 2).

ЛУЧШИЙ ПОДХОД: Двоичный поиск скобки, а затем продолжаем, как в наивном подходе.O(N log(N)).

ДИНАМИЧЕСКИЙ ПОДХОД К ПРОГРАММИРОВАНИЮ: В этой задаче присутствуют оба критерия применения динамического программирования, оптимальной подструктуры и перекрывающихся подзадач.Зачем?Суммарные налоги для каждой скобки представляют собой сумму налогов для текущей скобки и налогов для оставшегося налогооблагаемого дохода.Для каждой скобки рекурсивное решение вычисляет налоги для нижних скобок снова и снова.

Таким образом, мы предварительно вычисляем и запоминаем налоги для налогооблагаемой прибыли до предыдущего сегмента снизу вверх.Это займет O(N) времени.Двоичный поиск для скобки занимает log(N) времени.Вычисление налогов теперь занимает O(1) раз, что дает нам общий линейный алгоритм времени.

Scala code: Не стесняйтесь адаптироваться к вашему любимому языку программирования. 

def taxes(income: Int, brackets: IndexedSeq[(Int, Double)]): Double = {
    val dp = brackets
      .zipWithIndex
      .foldLeft((0d, IndexedSeq.empty[(Int, Double, Double)])) { case ((sum, acc), (cur, i)) =>
        val taxesOnPrevBracket = if (i > 0) {
          val prev = brackets(i - 1)
          (cur._1 - prev._1) * prev._2
        } else 0d
        val cumulativeTaxes = sum + taxesOnPrevBracket

        (cumulativeTaxes, acc :+ (cur._1, cur._2, cumulativeTaxes))
      }
      ._2

    @tailrec
    def findBracket(start: Int, end: Int): Int = {
      if (end - start <= 1) start
      else {
        val mid = start + (end - start) / 2
        if (income > brackets(mid)._1) findBracket(mid, end)
        else findBracket(start, mid)
      }
    }

    val br = dp(findBracket(0, brackets.size - 1))
    val inc = income - br._1 + 1
    val tx = inc * br._2 + br._3
    println(s"Taxable income: $income, bracket: $br, taxes: $tx")
    tx
}

brackets вот последовательность кортежей, начальных значений (спасибо @Dillon Davis за идею) и налоговой ставки.

...