3
\$\begingroup\$

Given a dictionary where the values are iterables, print the dictionary sorted by the length of its values.

def sort_dict_by_value_len(lst):
    while lst:
        min_key = min([(len(v), k) for (k, v) in lst.items()])
        print(min_key[1], lst.pop(min_key[1]))

sort_dict_by_value_len({1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine', 10: 'ten'})
1 one
2 two
6 six
10 ten
4 four
5 five
9 nine
3 three
7 seven
8 eight

I feel like I'm doing too much computations, and worst of all, I'm emptying the input list. Is there any better way to achieve this, with or without using sort or sorted, and optionally keeping the dictionary intact?

\$\endgroup\$
7
\$\begingroup\$
  • Calling a dictionary a list is very confusing
  • Rather than using min, you could use sorted.

    This'll change the time complexity of your code from \$O(n^2)\$ to \$O(n \log n)\$, as Python uses the Timsort. And since sorted is written in C, it'll be super fast too.

    Sorted also has the keyword argument key, which lets you sort by another value, rather than the value you get.

    This also keeps the original dictionary intact.

  • You can use dict and enumerate to build your input list. And to build a list to pass to enumerate you could use str.split.

And so I'd change your code to:

def sort_dict_by_value_len(dict_):
    return sorted(dict_.items(), key=lambda kv: (len(kv[1]), kv[0]))

def sort_dict_by_value_len_without_key(dict_):
    return [(k, dict_[k]) for _, k in sorted((len(v), k) for (k, v) in dict_.items())]

dict_ = dict(enumerate('one two three four five six seven eight nine ten'.split(), start=1))
for key, value in sort_dict_by_value_len(dict_):
    print(key, value)

If you only want \$O(1)\$ memory usage, then you could use an insertion sort. But keeps the \$O(n^2)\$ time complexity. I also cheated a bit.

  • I used a generator comprehension, rather than a list comprehension to ensure \$O(1)\$ space. Alternately, you could invert the algorithm, and pop from one array to another.
  • I used bisect.insort to remove most of the logic.
def sort_dict_by_value_len(dict_):
    output = []
    while dict_:
        key, value = dict_.popitem()
        bisect.insort(output, ((len(value), key), (key, value)))
    return (i[1] for i in output)
\$\endgroup\$
  • \$\begingroup\$ Thanks for the prompt response, but I have a few questions: 1. Would this have better performance than what I've posted in the question? 2. sorted copies the whole iterable, so wouldn't an in-place sort be better memory-wise if the input dictionary is large? 3. How do I implement this without sort and sorted like I've done in the question but better? \$\endgroup\$ – Gao Nov 9 '17 at 15:17
  • 2
    \$\begingroup\$ @Gao 1. Your question has \$O(n^2)\$ time complexity, sorted uses the Timsort, so it's \$O(n\log n)\$. And C is faster than Python. 2. Unless you're using a SortedDictionary or exploiting CPython, then there is no way to do this in place, and writing that would not be worth the effort IMO. 3. I wouldn't recommend this, sorted and sort are written in C, so are much faster, never mind them using a good algorithm. \$\endgroup\$ – Peilonrayz Nov 9 '17 at 15:22
  • \$\begingroup\$ Nice explanation. I asked 3. because that's what the interviewer was expecting to see, and also because I am not familiar with using sort with none-default key and wasn't allowed to search on the internet during the interview, I had to do it that way. \$\endgroup\$ – Gao Nov 9 '17 at 15:29
  • \$\begingroup\$ @Gao If you only know the default parameter, you could still use sorted rather than min, and stick with your way. return [(k, dict_[k]) for _, k in sorted((len(v), k) for (k, v) in dict_.items())], which is a bit more to read. Otherwise, if you didn't know of that, I'd implement any sort you know on the array [(len(v), k) for (k, v) in dict_.items()]. \$\endgroup\$ – Peilonrayz Nov 9 '17 at 15:35
  • \$\begingroup\$ Wow, you really breathe in Python! Why didn't I think of that? I must have looked bad to take a while to solve this. The two for would make my head spin a bit when under pressure. \$\endgroup\$ – Gao Nov 9 '17 at 15:56
2
\$\begingroup\$

For me, the magic of Python is evident in this one-liner (magic line in comments):

dictionary_sorted = ({1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine', 10: 'ten'})
dictionary_mixed = ({5: 'five', 3: 'three', 7: 'seven', 1: 'one', 10: 'ten', 4: 'four', 9: 'nine', 6: 'six', 2: 'two', 8: 'eight'})

dictionary = dictionary_mixed

# Begin magic line
sortedKeyList = sorted(dictionary.keys(), key=lambda s: len(dictionary.get(s)))
# End magic line

for index in xrange(len(sortedKeyList)):
    print("{}: {}".format(sortedKeyList[index], dictionary[sortedKeyList[index]]))

A few takeaways (for those reading):

  1. You cannot sort a dictionary because they have no concept of order
  2. Lists CAN be sorted because order is in their nature
  3. The sorted() function returns an iterable (list), which by default is a list sorted by increasing value (unless you include optional reverse=True argument). Here, we are asking that value to be the length of the dict's value for each key. We sort the keys to get the values back later for printing.
  4. Again, the dictionary data structure by nature has no concept of order as in Python's dict and the interviewer specifically requested the output to be printed, not returned, for this reason.
  5. If you still want to satisfy your itch, you can implement a high-performance sort algorithm (i.e. merge sort) using Python's collections.OrderedDict() and then simply print in-order. Yet, again, you'd be sorting more than you need because you really just need the keys.

In any case, an interviewer should love this Pythonic one-liner approach :)

EDIT: If you want to sort the results by key in case multiple value lengths are equal, you could use a while loop. The full code would be:

dictionary_sorted = ({1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five', 6: 'six', 7: 'seven', 8: 'eight', 9: 'nine', 10: 'ten'})
dictionary_mixed = ({5: 'five', 3: 'three', 7: 'seven', 1: 'one', 10: 'ten', 4: 'four', 9: 'nine', 6: 'six', 2: 'two', 8: 'eight'})

dictionary = dictionary_mixed

# Begin magic line
sortedKeyList = sorted(dictionary.keys(), key=lambda s: len(dictionary.get(s)))
# End magic line

# BEGIN sort by keys if values are equal
beg_eq_vals_index = 0
end_eq_vals_index = 0
cur_val = -1

while end_eq_vals_index < len(sortedKeyList):
    if len(dictionary[sortedKeyList[end_eq_vals_index]]) > cur_val > -1:
        # Replace slice of key list with sorted key list slice
        sortedKeyList[beg_eq_vals_index:end_eq_vals_index] = sorted(sortedKeyList[beg_eq_vals_index:end_eq_vals_index])

        # Update beginning index to end index in order to start a new section
        beg_eq_vals_index = end_eq_vals_index

        # Update current value used to determine sub-sections with equal values
        cur_val = len(dictionary[sortedKeyList[beg_eq_vals_index]])
    else:
        if cur_val == -1:
            cur_val = len(dictionary[sortedKeyList[end_eq_vals_index]])

    # Move end of current section ahead one spot
    end_eq_vals_index += 1
# END sort by keys if values are equal

for index in xrange(len(sortedKeyList)):
    print("{}: {}".format(sortedKeyList[index], dictionary[sortedKeyList[index]]))

You could test this by adding the reverse=True optional argument to the "magic line" sorted call, which results in a sorted call that looks like:

# Begin magic line
sortedKeyList = sorted(dictionary.keys(), key=lambda s: len(dictionary.get(s)), reverse=True)
# End magic line

Which has an output of:

3: three
7: seven
8: eight
4: four
5: five
9: nine
1: one
2: two
6: six
10: ten

So, you can see that even when we reverse the list, the sub-sections are correctly sorted in ascending key order. Still, this is not the best performance approach so keep that in mind.

\$\endgroup\$
  • \$\begingroup\$ This isn't the same as the original, yours doesn't guarantee that (10, 'ten') comes after (1, 'one'). \$\endgroup\$ – Peilonrayz Nov 9 '17 at 18:53
  • \$\begingroup\$ It prints the exact same list the OP provided. Besides, the question makes no mention of an additional search criterion being the value of the keys. It merely mentions sorting by one criterion, the length of the dict's iterable value. \$\endgroup\$ – Thunderkatz Nov 9 '17 at 18:56
  • \$\begingroup\$ Change dictionary to dict(reversed(list(enumerate('one two three four five six seven eight nine ten'.split(), start=1)))) and it no longer prints the same. Sure their text didn't specify a second order, but their code does. \$\endgroup\$ – Peilonrayz Nov 9 '17 at 19:00
  • \$\begingroup\$ In an interview, it's very important to answer the exact question asked and not introduce new constraints for yourself. \$\endgroup\$ – Thunderkatz Nov 9 '17 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.