a sorted array with all elements appear twice except one, find that element (the best solution should be O(logn))

Question

Ambu Sreedharan · Accepted Answer

int start = 0;
        int end = size - 1;
        int mid = 0;
        while(1){
                mid = start + ((end - start)/2);
                if((mid==start)&&(mid==end)){
                        return arr[mid];
                }
                if (!(mid%2)){
                        if(arr[mid] == arr[mid+1])
                        {
                                start = mid + 2;
                        }
                        else if (arr[mid] == arr[mid - 1]){
                                end = mid - 1;
                        }
                        else{
                                return arr[mid];
                        }
                }
                else{
                        if(arr[mid] == arr[mid-1])
                        {
                                start = mid + 1;
                        }
                        else if (arr[mid] == arr[mid + 1]){
                                end = mid - 1;
                        }
                        else{
                                return arr[mid];
                        }

                }
        }

vs · Answer

Here's a recursive solution:

// Given: sorted array, where all numbers repeat twice except for one. Find that number.
const int INF = -999999999;
int findSingle(int arr[], int size, int start, int end)
{
	if (start > end)
		return INF;

	bool found = false;
	int mid = (start + end)/2;
	// check left and right neighbor
	// if either one is equal to the mid element, then it is one of the duplicates
	if ((mid-1 >= 0 && arr[mid-1] == arr[mid]) ||
		(mid+1 < size && arr[mid+1] == arr[mid]))
		found = true;
	
	// dupe not found, this must be the single element
	if (!found)
		return arr[mid];

	// check left sub-array
	int val = findSingle(arr, size, start, mid-1);
	if (val != INF)
		return val;

	// check right sub-array
	val = findSingle(arr, size, mid+1, end);
	if (val != INF)
		return val;
}

Microsoft

Pergunta de entrevista da empresa Microsoft

Respostas da entrevista

Empresas seguidas

Buscas de vagas