Follow up would be to do this in constant space where the complexity doesn’t exceed O(n*2). For that you can use the Floyd’s Turtoise and Hare algorithm.
Sorry, I just don't see how that algorithm helps us in this case. I've only used that to solve problems with cycles, and couldn't find any information as to how the Tortoise and Hare algorithm helps us solve this problem.
If you could post your source or a sample solution, I would appreciate it.
You’re right, i misread the question. I recently had this question during my FAANG phone interview, i eventually ended up using binary search. Then he went on about turtle and hare, bla bla. Luckily he deemed it not really important to know, but a other interviewer might not be that nice.
Full-Stack Software Engineer; using a background in Acting and Voice-Over to pursue a lifelong love of software and technology from an arts and humanities perspective.
Thanks for the suggestion! I'm trying to learn more about space/time complexity as I go along, so I really appreciate the nod for a direction to look in.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Follow up would be to do this in constant space where the complexity doesn’t exceed O(n*2). For that you can use the Floyd’s Turtoise and Hare algorithm.
Sorry, I just don't see how that algorithm helps us in this case. I've only used that to solve problems with cycles, and couldn't find any information as to how the Tortoise and Hare algorithm helps us solve this problem.
If you could post your source or a sample solution, I would appreciate it.
You’re right, i misread the question. I recently had this question during my FAANG phone interview, i eventually ended up using binary search. Then he went on about turtle and hare, bla bla. Luckily he deemed it not really important to know, but a other interviewer might not be that nice.
This was the question btw: leetcode.com/problems/find-the-dup...
Thanks for the suggestion! I'm trying to learn more about space/time complexity as I go along, so I really appreciate the nod for a direction to look in.