Timeline for Optimized Python Solution for Determining if an Array Contains All Possibilities
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27 at 14:59 | history | edited | greybeard | CC BY-SA 4.0 |
remove irritating repeated predicate name
|
| Feb 27 at 4:15 | comment | added | Benjamin Kuykendall |
@2012rcampion I agree that if you wanted to solve this for an immutable data type you would need a different algorithm. But that's not what the problem is asking: "You have been tasked with writing a method named is_all_possibilities ... that accepts an integer array". I suspect this question is poorly localized to Python since the array module is rather obscure. But both array and the more obvious choice of list are certainly mutable.
|
|
| Feb 27 at 1:52 | comment | added | 2012rcampion |
@BenjaminKuykendall The original also works if arr is immutable, e.g. a tuple or bytes. In fact it even works with range, which only uses constant space. So to guarantee that you can modify the input you'd have to start with arr = list(arr).
|
|
| Feb 26 at 23:58 | comment | added | Benjamin Kuykendall |
@2012rcampion the input arr is mutable as the OP presented it. I don't see any constraints on modifying the input in the question. Users might not like you permuting their input... but that's okay because it's a made up algorithms question and there aren't any real users!
|
|
| Feb 26 at 22:30 | comment | added | 2012rcampion | @BenjaminKuykendall Doesn't that still require O(n) space, since you have to make a modifiable copy of the array? | |
| Feb 26 at 10:46 | answer | added | Sudix | timeline score: 4 | |
| Feb 26 at 3:20 | comment | added | Benjamin Kuykendall |
There is a "trick" to solving this problem: iterate through the array, and on iteration i, try to swap the value at index i into position a[i]. If the array contains the elements 0...(n-1) this will just work. If it contains any duplicates or out-of-bounds elements, you can detect this when doing the swap. Honestly, problems like this are poorly suited for this site. The answer is less about writing good code and more about figuring out a neat trick.
|
|
| S Feb 25 at 20:56 | vote | accept | CommunityBot | ||
| Feb 25 at 20:55 | vote | accept | CommunityBot | ||
| S Feb 25 at 20:56 | |||||
| Feb 25 at 18:17 | answer | added | Reinderien | timeline score: 4 | |
| Feb 25 at 17:50 | history | became hot network question | |||
| Feb 25 at 17:08 | comment | added | Reinderien | Is it actually memory optimisation you're looking for? In the vast majority of problems like this, the problem typically wants run-time optimisation, which is not the same thing. | |
| Feb 25 at 17:05 | history | edited | Reinderien | CC BY-SA 4.0 |
Problem quote
|
| Feb 25 at 12:18 | answer | added | J_H | timeline score: 2 | |
| Feb 25 at 10:22 | answer | added | Harith | timeline score: 2 | |
| S Feb 25 at 9:50 | review | First questions | |||
| Feb 25 at 10:30 | |||||
| S Feb 25 at 9:50 | history | asked | user281371 | CC BY-SA 4.0 |