Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Find the Duplicate Number (easy)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

Solution doesn't work on [3, 1, 3], which is one of the test cases.

Show 2 replies
A

Anonymous

· 2 years ago

class Solution:
  def findNumber(self, nums):
    
    def swap(i, j):
      nums[i], nums[j] = nums[j], nums[i]

    for i in range(len(nums)):
      while nums[i] != i + 1 and nums[i] != nums[nums[i] - 1]:
        swap(i, nums[i] - 1)

    return nums[-1]
A

Anonymous

· 3 years ago

The question (Find the Duplicate Number) should clarify that constant O(1) extra space is allowed given the Python3 solution instantiates a variable (and thus uses extra space).

A

Anonymous

· 3 years ago

What is the idea behind it?

current = arr[arr[slow]]
A

Anonymous

· 3 years ago

The fourth test (first hidden) is [5, 5, 5, 5, 5] but the problem states the array contains numbers 1 through N with N+1 numbers in the array.

Show 1 reply
A

Anonymous

· 3 years ago

Problem reads:

We are given an unsorted array containing n+1 numbers taken from the range 1 to n. The array has only one duplicate but it can be repeated multiple times. Find that duplicate number without using any extra space. You are, however, allowed to modify the input array.

However, we are supplied 5,5,5,5,5 as a test case. Given that the array is supposed to contain n+1 numbers taken from the range 1 to n If the number 5 is anywhere in the range 1 to n, then the minimum array length must be 6

A

Anonymous

· 5 years ago

Can't you just return slow value for the similar problem? Since we found that there is a cycle when they meet, then surely the duplicate is the value at the slow position, and thus no use for the find_start method? I just returned the slow value without using find_start and it still passes all the cases mentioned above.

Show 2 replies
A

Anonymous

· 5 years ago

The hyperlink to the "Start of LinkedList Cycle" actually takes you to the topic on a different website at educative.io instead of this course on designgurus.org.

Show 1 reply

Reading Progress

0%

Vote for new content