Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
5
of 5 vote

Step 1:Divide the array in 2 parts such that the first part contains even number of elements.
Step 2: Now compare the last element of first part to the first element of second part.
Step 3: If they match then the non-repeating element is in the first part of the array.
Step 4: Now make this is as your main array & go to step 1.

- Stupid Developer October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

what if the array is 0,0,1,1,4,4,4,4,5 your algo wont work

- anonymous October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Question says that all the numbers just occur twice and only number occurs once. So the input which you are stating is invalid :)

- Anonymous October 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

n is odd.
first look at the element A[n/2+1].
if A[n/2 +1] == A[n/2]
search the left part (from 0 to n/2-1) //the number of the left part is odd, so it's where the target is.
else if A[n/2+1] == A[n/2+2]
search the right part (from n/2+3, n-1)// the number of the right part is odd, so it's where the target is
else
return A[n/2];

- doubao October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Problem solving process:
- You see "sorted array"
- You see lg(n)

Above suggest you try some modified binary search.

Then on paper you work with examples (check middle elements) and decide two things:
1) For this specific problem, which half would I choose and how would I choose it
2) What is the ending condition

- S O U N D W A V E October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{
public class OccurringOnce {

public static void main(String[] args) {

// int[] arr = { 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7 };

// int[] arr = { 0, 0 ,1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7 };

// int[] arr = { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7 };

// int[] arr = { 0, 0, 1, 1, 2, 2 };

int[] arr = { 1, 1, 3 };

System.out.println(findNumber(arr, 0, arr.length - 1));

}

private static int findNumber(int[] arr, int start, int end) {

int mid = (start + end) / 2;

// handling case when length of array is even number
if (arr.length % 2 == 0) {

return -1;

}

int num = -1;// return -1 if there is no occurrence of such element

if (mid - 1 >= start && arr[mid] == arr[mid - 1]) {
/*
* search element in right half of the array
*/
num = findNumber(arr, mid + 1, end);
} else if (mid + 1 <= end && arr[mid] == arr[mid + 1]) {
/*
* search element in left half of the array
*/
num = findNumber(arr, start, mid - 1);

} else {
/*
* return middle of the array
*/
num = arr[mid];

}

return num;
}
}
}

- Manish October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class BinaryOddAI
    {
        public static void Do()
        {
            int[] array = { 0, 0, 1, 2, 2 };
            Console.WriteLine(GetOdd(array, 0, array.Length - 1));
            int[] array2 = { 0, 0, 1, 1, 3, 2, 2 };
            Console.WriteLine(GetOdd(array2, 0, array2.Length - 1));
            int[] array3 = { 1, 1, 3 };
            Console.WriteLine(GetOdd(array3, 0, array3.Length - 1));
        }

        private static int GetOdd(int[] array, int start, int end)
        {
            if (array == null || array.Length % 2 == 0)
            {
                return -1;
            }

            if (array.Length == 1)
            {
                return array[0];
            }

            if (start == end)
            {
                return array[start];
            }

            int mid = (start + end) / 2;
            if (array[mid] != array[mid - 1] && array[mid] != array[mid + 1])
            {
                return array[mid];
            }
            if (array[mid] == array[mid + 1])
            {
                return GetOdd(array, start, mid - 1);
            }
            else
            {
                return GetOdd(array, mid + 1, end);
            }
        }
    }

- allanchanly October 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int FindSingle(A, i, j)
{
	if (i == j) return -1;
	int middle = (i + j) / 2;
	if (A[m] != A[m - 1] && A[m] != A[m + 1]) return m;
	return max(FindSingle(A, i, m - 1), FindSingle(A, m + 1, j));
}

- Andrew October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, m = middle. Also, need to handle case where m is zero.

- Andrew October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

XOR on all numbers ... The result will be the number that appears only once.

- Anonymous October 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I would assume this would be O(n) since you need to visit every number.

- RC October 20, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More