1

I have a question regarding Question 13.12 (page 208) in the book Elements of Programming Interviews by Adnan, Tsung-Hsien and Amit.

The question:

ABC corporation needs to cut payroll expenses to a specified target. The chief executive officer wants to do this by putting a cap on last year's salaries. Every employee who earned more than the cap last year will be paid the cap this year; employees who earned no more than the cap will see no change in their salary.

For example, if there were five employees with salaries last year were $90, $30, $100, $40, and $20, and the target payroll this year is $210, then $60 is suitable salary cap, since 60+30+60+40+20=210.

Design an algorithm for computing the salary cap, given the existing salaries and the targeted payroll.

Textbook solution:

def find_salary_cap(target_payroll, current_salaries):

    current_salaries.sort()
    unadjusted_salary_sum = 0.0
    for i, current_salary in enumerate(current_salaries):
        adjusted_people = len(current_salaries) - i
        adjusted_salary_sum = current_salary * adjusted_people
        if unadjusted_salary_sum + adjusted_salary_sum >= target_payroll:
            return (target_payroll - unadjusted_salary_sum) / adjusted_people
        unadjusted_salary_sum += current_salary
    # No solution, since target_payroll > existing payroll.
    return -1.0

Follow-up question: Can you solve the same problem using only O(1) space.

My question:

Isn't the textbook solution already using O(1) space?

nataman
  • 39
  • 4

2 Answers2

1

No, this uses python's built-in timsort, which can use O(n) additional space, as documented here What is the space complexity of the python sort? and What is the space complexity of the python sort?

Assuming that you meant O(1) additional space, you can just replace the sort, and use the same algorithm.

There are several sorting methods which do not require additional space, unfortunately most of them are pretty bad, having time complexity O(n^2) in the average and worst case. Here's one online list I found http://bigocheatsheet.com/?goback=.gde_98713_member_241501229

Heapsort needs no additional space, and is O(n log n) time. You can implement it pretty easily with the python heapq module. Heapify the list, then pop the minimum elements until you reach the threshold, basically the same as the posted code example.

I assume you mean O(1) additional space, because if you mean O(1) space total, then I don't have an answer at this time. That function can't take a list because that would take up O(n) space. Maybe you could do it with a generator as input, although that's cheating -- the input space might just be hidden.

Kenny Ostrom
  • 5,639
  • 2
  • 21
  • 30
0

The textbook solution is O(n). Worst case scenario, the code loops through every single salary. Therefore, the number of steps this solution must execute is dependent on how many salaries are passed in.

Additionally, as Kenny points out in a comment, sort is called, which also contributes to complexity.

Were this solution O(1), the number of steps to complete this problem would be the same every time, regardless of how many salaries are passed in.

Stephen Leach
  • 99
  • 8