Sorting a list of strings by custom key

Question

I recently had a live coding interview, and was asked to solve a relatively simple problem:

Given a list of two-character strings in an arbitrary order, write a function that returns a list of the same strings, sorted first by strings containing both alpha and numeric characters in ascending order, followed by numerical-only strings in ascending order.

I was able to solve this fairly quickly with the below:

polelist = ['13', '2', '20', '3', '30', '1a', '1b', '1', '3c', '2a', 'a1', '2b', '10', 'aa']

def sortpoles(poles):
    alphapoles = []
    numpoles = []

    for item in poles:
        if item.isnumeric():
            numpoles.append(item)
        else:
            alphapoles.append(item)

    numpoles = [int(x) for x in numpoles]
    numpoles.sort()
    numpoles = [str(x) for x in numpoles]

    alphapoles.sort()

    alphapoles.extend(numpoles)

    return alphapoles

This returns: ['1a', '1b', '2a', '2b', '3c', 'a1', 'aa', '1', '2', '3', '10', '13', '20', '30'] which is the correct answer.

With the remaining time, they asked me if I could find a more efficient way to do this. I know that both sort() and sorted() can accept a "key" argument with a function for custom sort criteria, but I wasn't able to figure out the logic to accomplish this. I've been trying to solve this for my own edification for the last couple hours but I'm stumped. Is this even the right approach for improving the efficiency of my solution? Is there a better way I'm not thinking of?

Since your code doesn't really have a problem and you're not asking about a specific problem (other than how to apply sort's key) here, this is more of a code review question than an SO question. I'd recommend asking the same question here: codereview.stackexchange.com — Grismar
– Grismar, Commented Mar 12, 2021 at 1:29
Thanks for the suggestion, I wasn't aware of the difference. I think I'll do that. — LK3K
– LK3K, Commented Mar 12, 2021 at 1:33
When someone asks "better" in an interview, it may be a good idea to ask clarification what that means, .e.g, memory, speed, code lines, readability, maintainability, etc. This also shows engagement and not jumping straight into a task with unclear specifications. For example, writing an one-liner which requires a comment to be understood may not be preferable over a 3-line self-documented method. Or it could be they wanted to see you defending your approach if it is indeed optimal. Not to imply there weren't improvements to be made to your method. — Reti43
– Reti43, Commented Mar 12, 2021 at 10:40

GIOVANNI QUINONES VALDEZ · Accepted Answer · 2021-03-12 01:31:33Z

3

Not the cleanest solution, but does the job.

>>> polelist.sort(key = lambda x : (x.isnumeric(), len(x)))
['1a', '1b', '2a', '2b', '3c', 'a1', 'aa', '1', '2', '3', '10', '13', '20', '30']

The logic is to sort first by bool (is numeric or not), and the by the length of the string as larger numbers --> larger length and numbers of the same length are intrinsically sorted.

answered Mar 12, 2021 at 1:31

GIOVANNI QUINONES VALDEZ

2773 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Grismar · Accepted Answer · 2021-03-12 01:35:53Z

This is a clean solution:

polelist = ['13', '2', '20', '3', '30', '1a', '1b', '1', '3c', '2a', 'a1', '2b', '10', 'aa']

result = sorted(polelist, key=lambda x: (x.isnumeric(), int(x) if x.isnumeric() else x))
print(result)

It's similar to what I just noticed @GIOVANNIQUINONESVALDEZ posted, but since your description didn't mention negative numbers being excluded, I wouldn't want to rely on length.

Output:

['1a', '1b', '2a', '2b', '3c', 'a1', 'aa', '1', '2', '3', '10', '13', '20', '30']

This is more efficient not because of its brevity (although it's also shorter and , in my opinion, more readable), but because it avoids needlessly copying the lists and later recombining them.

Also, sorted ensures each key is only computed once, when needed, so there's no losses there.

Bing Wang · Accepted Answer · 2021-03-12 01:29:52Z

1

Your code is already NlogN and there is technically no more efficient way, but coding can be shorten

print(list(sorted(polelist,key=lambda x:(x.isnumeric(),int(x) if x.isnumeric() else x))))

answered Mar 12, 2021 at 1:29

Bing Wang

1,7181 gold badge10 silver badges7 bronze badges

2 Comments

Reti43 Over a year ago

list() is unnecessary as sorted already returns a list.

LK3K Over a year ago

Interesting. I wonder if by "make it more efficient", the interviewer just wanted to see if I could refactor into something shorter. Thanks!

Collectives™ on Stack Overflow

Sorting a list of strings by custom key

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related