Interview Exercise – Earliest Index of array, where the subarray contains all unique elements of the array

Time: 2 hours

Try to solve the following exercise in O(n) worst-case time complexity and O(n) worst-case space complexity – giving a more complex solution is also acceptable, but not so valuable.
Also, try not to rely on library functions, unless they don’t increase complexity.
Please test your solution – correctness is important.

You get a non-empty zero-indexed array parameter A that contains N integers. Return S, the earliest index of that array where the sub-array A[0..S] contains all unique elements of the array.
For example, the solution for the following 5−element array A:
A[0] = 3
A[1] = 3
A[2] = 2
A[3] = 0
A[4] = 2
is 3, because sub-array [ A[0], A[1], A[2], A[3] ] equal to [3, 3, 2, 0], contains all values that occur in array A.

Write a function
function solution($A);
that, given a zero-indexed non-empty array A consisting of N integers, returns this S index.
For example, if we call solution(A) with the above array, it should return 3.

You can assume that:
· N is an integer within the range [1..1,000,000];
· each element of array A is an integer within the range [0..N−1].

//whiteboard logic
15:20 – 16:03

//coding in up in C++
16:03 – 17:29

1st try, O(n^2)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

// main.cpp

// subarray

// Created by Ricky Tsao on 6/22/16.

#include <iostream>

using namespace std;

//utility

void initArray(int ** array, int length) {

for ( int z = 0; z < length; z++) {

*(*array+z) = -1;

}

void printArray(int array []) {

int * temp = array;

while (*temp != -1) {

cout << *temp << endl;

temp++;

}

int getArrayLen(int array []) {

int * temp = array;

int length = 0;

while (*(temp++) != -1) {

length++;

}

return length;

}

//make sure we get an array called unique

//1)

// given an original array

// we need a unique array

//O(n)

bool doesIntExistInUnique(int val, int unique [], int length ) {

for (int i = 0 ; i < length; i++ ) {

if(unique[i]==val)

return true; //val exists in unique

}

return false; //val does not exist in unique

}

// O(n^2)

int * generateUniqueArray( int originalArray [], int length) {

int uniqueCur = 0; //remind

int * heapArray = new int[length]; //create an array in the heap

//init to -1

initArray(&heapArray, length);

//O(n)

for (int i = 0; i < length; i++) {

int origNum = originalArray[i];

if(origNum == -1) break;

if(!doesIntExistInUnique(originalArray[i], heapArray, length)) {

//we add it to our heap array

heapArray[uniqueCur++] = originalArray[i];

}

return heapArray;

}

//O(n)

int earliestIndex(int original [], int unique [] ) {

int cur = 0;

int uniqueArrayLength = getArrayLen(unique);

for (int j = 0; j < getArrayLen(original); j++) {

int toCompare = original[j];

if(toCompare == unique[cur]){

cur++;

if(cur==uniqueArrayLength)

return j;

}

return -1;

}

int main(int argc, const char * argv[]) {

//create test array

//passed tests

//3,3,2,0,2, -1

//3,3,2,0,2,0,2, -1

//3,3,3,3,3,3,3, -1

//1,3,5,1,3,5,1,3,5,-1

//1,1,1,1,1,1,1,-1

int arr[10] = {1,1,1,1,1,1,1,-1}; //-1 terminating

//1) create a unique array

int * uniqueArray = generateUniqueArray(arr, 10);

printArray(uniqueArray); //check

//2) given the original array "arr", and unique array "unique",

//we can then figure out where the earliest index happen

int answer = earliestIndex(arr, uniqueArray);

return 0;

}

Further thoughts

We can first use a merge sort O ( n log n ) to sort the original array.
After sorting it,you do a O ( n ) run through to build your unique array.

Then, you can build your unique array with O ( n log n ).