# Simple Algorithm feedback

Hello, I have a task at hand and would like to discuss with you what you think of my solution and whether would you do it completely differently or just change a thing here and there. Problem: Imagine you have a to-do list including tasks like the one below:

``````to_do_list = [
{priority: 2, name: "Take out trash"},
{priority: 1, name: "Go running"},
{priority: 20, name: "Do homework"},
{priority: 5, name: "Feed a dog"},
{priority: 20, name: "Water plants"},
]
``````

where `priority >= 0`.
Your task is to reduce `priority` values to minimum while persisting their priority order. eg: Right now, there are 5 tasks with priorities `1, 2, 5, 20`. The goal is to reduce these numbers to look like `0, 1, 2, 3` without changing the order of tasks in the `to_do_list`.

Expected outcome:

``````to_do_list = [
{priority: 1, name: "Take out trash"},
{priority: 0, name: "Go running"},
{priority: 3, name: "Do homework"},
{priority: 2, name: "Feed a dog"},
{priority: 3, name: "Water plants"},
]
``````

My solution:

1. Create a dictionary for unique priority values
2. Store all tasks of the same priority in a list under its corresponding section(key) in the dictionary
3. Create a list of sorted keys(priorities) from the dictionary in ascending order
4. Initialise `new priority` to 0
5. Iterate for each priority in the sorted keys(priorities)
• access list of tasks with the same priority
• change all the tasks’ priority attribute to `new priority`
• increase `new priority` by 1
``````        # Step 1
# Step 2 - start
for task in to_do_list:
# if first occurance of task's priority in the dictionary
# initialise it with empty list
if priority not in tasks_by_priority:
# add item to the list
# Step 3
# Step 4
new_priority = 0
# Step 5
for priority in sorted_priorities:
new_priority += 1
``````

Thank you for you feedback

There are two serious problems. First, it’s not clear that it’s correct. The expected output for the example looks wrong but I have no way of knowing. Second, you’re copying the dictionaries from one list to another list, changing the values there, and end up changing the values in the original list of dictionaries. This isn’t wrong but it is confusing and unnecessary. You could rewrite it like this:

``````priorities = []
priorities.sort()
priority_map = {}
for new_priority, priority in enumerate(priorities):
priority_map[priority] = new_priority
``````

Hello,

I appreciate that you took your time and gave me a feedback.

Could you please help me understand how could I make it more clear that my solution is correct?
What would I need to do?
Why do you think the expected outcome looks wrong?
I’ve changed the names for now.

The expected outcome is 1, 0, 4, 3, 4. Why? What happened to 2? Is your code wrong or is the example/description wrong? I don’t know.

Apart of the main goal of this algorithm, I also want it to perform well—doing as few steps as possible. The idea is to “scan” the `to_do_list` first and create categories of priority and assign each task to its category. Let’s say the size of `to_do_list` is N. In that case, the time complexity of the scan takes N time.
View of `tasks_by_priority` after the initial scan:

``````tasks_by_priority = {
1: [{priority: 1, name: "Go running"}],
2: [{priority: 2, name: "Take out trash"}],
20: [{priority: 20, name: "Do homework"}, {priority: 20, name: "Water plants"}],
5: [{priority: 5, name: "Feed a dog"}],
}
``````

And it does not really copy the tasks, only the references to the tasks in the `to_do_list`.
Another thing is that I want the lowest priority to start with 0 and I can’t tell ahead whether there already are tasks with that priority or not. Also, I don’t really care what their values are, I only need to reduce their values while persisting the priority order. That’s why I take the keys and sort them. That will take (n log n) time on average.
Finally, I can loop through the `sorted_priorities`, accessing keys from the `tasks_by_priority` dictionary in order I need. That will also take N time as I need to iterate just once.
I just realised, I am losing a little time with creating the `sorted_priorities` from the dictionary keys so I could initialise `priorities = []` at the beginning and append them during the scan, like this:

``````if priority not in tasks_by_priority:
priorities.append(priority)
``````

and sort them after.

From the point of view of time taken, the algorithm look like this:

1. Scan => n time
2. Sort priorities => n log n time
3. Modify priorities => n time

You are right, I made a mistake there for some reason… Stupid me.
When you look at the description again, is that more clear now?
I would not be asking If I didn’t know I need to work on describing things in a clearer way.
Thanks

Code after revision:

``````# Step 1
priorities = list()
# Step 2 - start
for task in to_do_list:
# if first occurance of task's priority in the dictionary
# initialise it with empty list
if priority not in tasks_by_priority:
priorities.append(priority)
# add item to the list
# Step 3
priorities.sort()
# Step 4 & 5
for new_priority, priority in enumerate(priorities):
new_priority += 1
``````

Okay. I’ve just learn that adding an item to a `set()` takes O(1) time on average. I understand why you think my code was unreasonably confusing. I had been thinking of your implementation too, but I was trying to avoid the is member of the priorities check on every iteration:

``````task['priority']) if task['priority'] not in priorities
``````

I’ve implemented the same logic with using `set()` for priorities, which should theoretically run faster.

The way I actually wrote this was this:

``````priorities = sorted(list(set([task['priority'] for task in task_list])))  # [1, 2, 5, 20]
priority_map = {priority:index for index, priority in enumerate(priorities)}  # {1: 0, 2: 1, 5: 2, 20: 3}