Posts tagged ‘Interview Question’

## Question

Write an algorithm that finds the duplicate in an array using Big O of N, not Big O of N^2.

## Information

The array is an integer array and has a MAX_VALUE items (lets just use 1000 as an example). All integers are between 0 and MAX_VALUE (pretend the input is limited to values between 0 and MAX_VALUE). There is only one duplicate and you are not sure where it is. What is the most efficient way to find it.

```    int[] i = new int[1000];
```

There is one duplicate and it is the worst case duplicate.  You can simulate a worst case duplicate as follows:

```    for (int i = 0; i < 999; i++)
{
array[i] = i+1;
}
array[999] = 999;
```

So the duplicates are the second to last and the last.

This is one possible answer that assumes the values are between 0 and MAX_VALUE.

```    /// <summary>
/// Efficient because it has a Big O of n.
/// </summary>
public int FindDuplcate(int[] inArray)
{
bool[] tmpArray = new bool[1000];
for (int i = 0; i < inArray.Length; i++)
{
if (tmpArray[inArray[i]] == true)
return i;
tmpArray[inArray[i]] = true;
}
return -1;
}
```

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace FindDuplicateInArray
{
class Program
{
const int MAX_VALUE = 1000;

static void Main(string[] args)
{
// Worst case
int[] array = new int[MAX_VALUE];
for (int i = 0; i < MAX_VALUE - 1; i++)
{
array[i] = i + 1;
}
array[MAX_VALUE - 1] = MAX_VALUE - 1;

// Incorrect answer: Big O of N^2
//int dup = dupFinder1.FindDuplcate(array);

// Incorrect answer: Big O of N^2
//int dup = dupFinder2.FindDuplcate(array);

// Possible correct answer: Big O of N but with a limitation
//int dup = dupFinder3.FindDuplcate(array);

// Possbile correct answer: Big O of N
int dup = dupFinder3.FindDuplcate(array);

Console.WriteLine(dup);
}

{
int FindDuplcate(int[] inArray);
}

/// <summary>
/// Incorrect Answer: This is simple N*N alogithm. Big 0 = N^2
/// </summary>
{

public int FindDuplcate(int[] inArray)
{
for (int i = 0; i < inArray.Length; i++)
{
for (int j = 0; j < inArray.Length; j++)
{
if (i != j && inArray[i] == inArray[j])
return j;
}
}
return -1;
}

#endregion
}

/// <summary>
/// Incorrect Answer: This is N(N-1)/2 which is N*N/2-n/2 so remove the constants N^2-N.
/// When there is N^2-N you can keep the N that grows fastest: Big O = N2
/// But the original alrogithm is less N^2 than just N^2.
/// </summary>
{

public int FindDuplcate(int[] inArray)
{
for (int i = 0; i < inArray.Length; i++)
{
for (int j = i + 1; j < inArray.Length; j++)
{
if (inArray[i] == inArray[j])
return j;
}
}
return -1;
}

#endregion
}

/// <summary>
/// Possible Answer: Efficient because it has a Big O of n.
/// Limitation: If an item in the array is greater than the MAX_VALUE,
///             an ArrayIndexOutOfBoundsException occurs.
/// </summary>
{

public int FindDuplcate(int[] inArray)
{
bool[] tmpArray = new bool[1000];
for (int i = 0; i < inArray.Length; i++)
{
if (tmpArray[inArray[i]] == true)
return i;
tmpArray[inArray[i]] = true;
}
return -1;
}

#endregion
}

/// <summary>
/// Possible Answer: Efficient because it has a Big O of n.
/// </summary>
{
public int FindDuplcate(int[] inArray)
{
Dictionary<int, bool> table = new Dictionary<int, bool>();
for (int i = 0; i < inArray.Length; i++)
{
if (table.Keys.Contains(inArray[i]))
return i;