Microsoft Interview Question
InternsCountry: United States
Interview Type: In-Person
This is a good solution but the problem is the following testcase:
2,2,2,2,2,2,2,2,2,2,2,2,2,2,3
So if you are searching for 3 it will traverse the whole array anyway. I don't know of a better solution, but for the above test case it is O(n).
O(n) is a lower bound for the worst-case. Consider that in the example
2,2,2,2,2,2,2,2,2,2,2,2,2,2,3 the value of 3 could have been anywhere and the input would still have been legal. Any location you inspect that has a 2 reveals no information about the location of the 3. As long as you haven't found the 3 yet and there's some entry you haven't inspected, the 3 could be there. Any correct algorithm will therefore have to read all of the input in the worst case.
The best we can hope for is a heuristic that requires fewer than N array reads on some (but not all) inputs, which is exactly what this answer provides.
What do you mean by "find a given number of x in the array"?
let say the array is: 4,4,5,6,7,6,5,5,4,3,2,3
and I want to find search for "6" then I should return "4" because the first "6" is in the 4rd place from the beginning? or "2" beacuse there are 2 occurrences of 6 in the array?
int CountOfX(vector<int> a, int x)
{
int occurences = 0;
int i = abs(a[0] - x); // min index to look for values
int end = a.size() - abs(a[a.size() - 1] - x); // max index to look for values
while (i < end )
{
if (a[i] == x)
{
occurences++;
i++;
}
else
{
i += abs(a[i] - x); // this is the minimum index our value can now be at
}
end = end - abs(a[end - 1] - x); // based on our current max, this is the maximum distance
}
return occurences;
}
//Naive O(n)
int find(int value, int[] a) {
int n = a.Length;
for (int i=0; i<n; i++) {
if (value==a[i])
return i;
}
return -1;
}
//binary search ... ish
int find(value, a) {
int n = a.Length;
Queue q = new Queue();
q.Enqueue({ 0,n/2,n }); // START,MID,END of a subrange to search
while (q.Count > 0) {
int[] sub = q.Pop();
int start=sub[0], mid=sub[1], end=sub[2];
if (a[mid]==value) {
return mid;
}
int gap = mid - start;
int range = Math.Abs(a[mid]-value);
if (gap>=range) {
q.append( (mid-start)/2+start, start, mid);
}
gap = end-mid;
if (gap>=range) {
q.append( (mid-start)/2+mid, mid, end);
}
}
return -1;
}
//index 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18
int[] a = {7,8,9,8,8,7,6,5,4,5,5,4,3,3,2,2,4,5,6}
int i = find(2, a);
System.Console.WriteLine(i); //output 14
the binary search u implemented is not O(log n).. yes, it splits the array in half but you will search both sides so it is still O(n)
int count()
{
int a[10] = {4,5,5,2,4,5,5,3,7,1};
int i,j,temp,min=0,max=9, search= 5,count =0;
for(i =0;i<9;i++)
{
for(j=0;j<9-i;j++)
{
if(a[j] > a[j+1])
{
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
while(1)
{
i = (min + max)/2;
if( a[i] < search)
{
min = i;
}
else if(a[i] >search)
{
max = i;
}
else
{
break;
}
}
for(i = min ;i<max;i++)
{
if(a[i] == search)
{
count++;
}
}
printf("%d count %d\n",search,count);
}
Here is my algorithm:
1. check the difference between the number and the first element of the array
2. If the absolute value of the difference is zero, return true;
3. if the difference isn't zero, check the number whose index is equal to the difference.
4. Repeat step 1 to 3 until the index you find in step 3 is greater than the array size.
Here is a C++ implementation:
int find(vector<int> &A, int start, int v) {
if(start >= A.size()) return false;
if(A[start] == v) return true;
int offset = abs(v - A[start]);
return find(A, start + offset, v);
}
int foundInPlusMinus1VectorINT(int ai_number, std::vector<int> ai_vector, int ai_l, int ai_r)
{
int med = (ai_l + ai_r) / 2;
int delta = std::abs(ai_number - ai_vector[med]);
if (delta == 0)
return med;
int ret;
if (delta <= med - ai_l + 1)
// Look in r side ...
if ((ret = foundInPlusMinus1VectorINT(ai_number, ai_vector, med + 1, ai_r)) >= 0)
return ret;
if (delta <= ai_r - med + 1)
// Look in r side ...
if ((ret = foundInPlusMinus1VectorINT(ai_number, ai_vector, ai_l, med - 1)) >= 0)
return ret;
// NOT FOUND
return -1;
}
int foundInPlusMinus1Vector(int ai_number, std::vector<int> ai_vector)
{
return foundInPlusMinus1VectorINT(ai_number, ai_vector, 0, ai_vector.size() - 1);
}
import java.util.*;
public class GivenNumberX {
public static void main(String[] args){
int i= 0;
int count=0;
int difference = 0;
int input[] = {5,6,7,6,5,5,4,4,3,2,1,2,3};
System.out.println("Enter the value of x");
Scanner input1= new Scanner(System.in);
int x = input1.nextInt();
while(i< input.length && input[i]!=x){
difference = Math.abs(x - input[i]);
i = i +difference;
}
if(i > input.length){
System.out.println("Element not found");
}else
System.out.println("First position for "+ x + " is " + i);
for(i=0;i<input.length;i++){
if(input[i]==x){
count++;
}
}
if(count==0){
System.out.println("Element not found");
}else
System.out.println("The number of times " + x + " appears in the array is " + count);
}
}
/// <summary>
/// Find if the element is present in the array.
/// Property of array is that each neighbor element is not more than 1 difference
/// </summary>
/// <param name="a">Array to be searched</param>
/// <param name="x">Element to be searched</param>
/// <returns>Returns the index of the element</returns>
public static int FindElement(int[] a, int x)
{
if (a == null || a.Length == 0)
{
throw new ArgumentNullException("a");
}
for (int i = 0; i < a.Length; )
{
int jump = 1;
if (x == a[i])
{
return i;
}
jump = Math.Abs(x - a[i]);
i += jump;
}
return -1;
}
Follow this approach:
find last-first element.
case 1.If the difference is more than one it was an increase way.
case 2:If the difference is less than one it was a decreasing array.
case 3:If the difference is 0 it means that array increase and then decreased with flip exactly in between.In all cases you can do a binary search.
n=no of elements
- Anonymous November 24, 2014x element to found
i=0;
while(i<n && a[i]!=x)
{
diff=abs(x-a[i]);
i+=diff;
}
if(i>=n)
print "element no found";
else
print i;