Timeline for Determine if string has all unique characters
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 12, 2015 at 9:52 | comment | added | janos |
Building a set from a string is nothing magical: for each character, insert into the set. For option 3, by using sorted which returns a new list, you have effectively chosen to use \$O(n)\$ space, and that's what the comment should say
|
|
| Jul 12, 2015 at 9:48 | comment | added | janos |
There's not a lot of details on that page... But I assume that the set is implemented as a hash set, and the worst case is when you have n elements that are not equal, but have the same hash code, in which case the hash set degenerates to a linked list. This scenario is not actually possible with characters or numbers, where distinct elements will never have the same hash code. So the complexity of the in operation is \$O(1)\$
|
|
| Jul 12, 2015 at 9:39 | comment | added | DJanssens |
Thanks @Janos! A few things: (1) Isn't worst-case complexity the main focus of an interview. According to wiki.python.org/moin/TimeComplexity, the statement char in char_seen: is O(n), resulting in a total of O(n^2), no? (2) I couldn't find anywhere the complexity of building a set from a string. Thats why option 2 is unknow. (3) For option 3, could you elaborate what part exactly makes my comment inadequate? I totally agree with the unit testing advice you gave, thanks again!
|
|
| Jul 12, 2015 at 9:28 | history | answered | janos | CC BY-SA 3.0 |