Timeline for Find the origin and the destination of a trip from a serie of tickets
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 24, 2013 at 3:28 | history | edited | Juho | CC BY-SA 3.0 |
edited body
|
| Jan 29, 2013 at 7:21 | comment | added | Yuval Filmus | If the path loops over itself, then A and B could appear more than once. | |
| Jan 29, 2013 at 5:30 | comment | added | Antoine Lassauzay | Anyhow, the interviewer who asked me this question said there was a better approach for the time for time when I proposed a similar solution, because it involved two loops : one to create the map, and one to find A and B in the map. I am not sure how to formally measure if your solution is superior to the solutions given by Pal GD or me. | |
| Jan 29, 2013 at 5:26 | comment | added | Antoine Lassauzay | If A!=B (which is what I reasoned with), A could be the city that appeared 0 time as destination, and B the one that appeared 0 time as a departure, right? | |
| Jan 28, 2013 at 14:33 | history | edited | Yuval Filmus | CC BY-SA 3.0 |
added 268 characters in body
|
| Jan 28, 2013 at 9:10 | comment | added | Jan Hudec | Actually for oriented graph, you need to compare number of times the city appears as source to number of times it appears as destination. | |
| Jan 28, 2013 at 9:09 | comment | added | Jan Hudec | @SaeedAmiri: Why is it not linear time or space (on average, when using hash tables)? Size of task is number of tickets, each ticked is only processed once, there can't be more sources/destinations than tickets, so the number of entries is also at most linear. | |
| Jan 28, 2013 at 8:59 | comment | added | user742 | It's not a linear time algorithm. (Specially in space). | |
| Jan 28, 2013 at 6:12 | history | answered | Yuval Filmus | CC BY-SA 3.0 |