Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

@Chrisz
That's brilliant!!!
I never thought of intervals.....

Anyway, I improved your algorithm a little bit, and I've got O(n):

public class _6018738030641152 {
    public static void main(String[] args) {
        int[] a = {4, 3, 6, 8, 0, 3, 2, 3};
        //         6  7  0  1  2  3  4  5 = 6
        //         7  0  1  2  3  4  5  6 = 5
        //         4  5  6  7  0  1  2  3 = 6
//        a = new int[]{0, 1, 2, 3};
//        a = new int[]{1, 0, 0};

        System.out.println(amazingNumber(a));
//        System.out.println(bruteForce(a));
    }

    private static int bruteForce(int[] a) {
        int res = 0;
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            int count = 0;
            for (int j = 0; j < a.length; j++) {
                int p = j + i;
                if (j - a[p % a.length] >= 0) count++;
            }
            if (count > max) {
                max = count;
                res = i;
            }
        }
        return res;
    }

    public static int amazingNumber(int[] a) {
        int len = a.length;
        LinkedList<Interval> intervals = new LinkedList<>();

        // find all the intervals that if the array starts at any index in the interval, there will
        // be at least 1 element is amazing number
        for (int i = 0; i < len; i++) {
            if (a[i] >= len) continue;
            int start = (i+1) % len;
            int end = (len + (i - a[i])) % len;
            System.out.println(i + ": " + start + " - " + end);
            intervals.add(new Interval(start, end));
        }

        // now our problem has just become: "find the year that has the maximum number of people
        // alive"
        int[] count = new int[len];
        for (Interval i : intervals) {
            count[i.start]++;
            if (i.end+1 < count.length) count[i.end+1]--;
        }
        int max = 0;
        int counter = 0;
        int idx = 0;
        for (int i = 0; i < count.length; i++) {
            counter += count[i];
            if (counter > max) {
                max = counter;
                idx = i;
            }
        }

        return idx;
    }

    static class Interval {
        int start;
        int end;
        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}

- tryhard November 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

One small correction: Since it is a circular array, the for loop for intervals should be modified to

for (Interval i : intervals) {
            count[i.start]++;
	    int nextToEndIndx = (i.end+1)%len;
            count[nextToEndIndx]--;
        }

- Zero2 June 30, 2018 | Flag
Comment hidden because of low score. Click to expand.
5
of 7 vote

/*
1) obvious solution, try all sub-sequences which are n*(n-1) leading to O(n²) runtime with O(1) space
2) there is a better approach:
- for each element we can know for which interval of start index it will count as an amazing number
- so, we get n intervals and need to know what is the best start. start can be between 0 and n
- if we go through 0..n for each interval, when we have a list with all start and all ends, we can
  find the desired lowest start index if interval starts and ends are sorted
  
2) in detail, assuming the following array:

index: 0, 1, 2, 3, 4, 5, 6, 
value: 4, 2, 8, 2, 4, 5, 3, 
n = 7

value 4 at index 0: can be used if start index is between 1 and 3
    becaue there must be at least 4 elements before a[0] to satisfy
	a[0] >= index.	 
	that is 0 + 1 .. n + 0 - a[0]
value 2 at index 1: can be used if start index is between 2 and 6
    that is 1 + 1 .. n + 1 - a[1]
value 8 at index 2 can never be used because 8>n
	that is 2 + 1 .. n + 2 - a[2] => 3 .. 1 (which is not an interval)
value 2 at index 3 can be used if start index is between 4 and 8 (*), 
	that is 3 + 1 .. n + 3 - a[3]
value 4 at index 4 can be used if start index is between 5..7
    that is 4 + 1 .. n + 4 - a[4]
value 5 at index 5 can be used if start index is between 6..7
	that is 5 + 1 .. n + 5 - a[5]
value 3 at in dex 6 can be used if start index is between 7..10
	that is 6 + 1 .. n + 6 - a[6]

result: at index 6 (4 values are amazing)
        at index 7 (4 values are amazing)
		note index 7 = 0, 0 < 6, therefore the result is 0

(*) if index > 6 means basically just index - n, or more generic index mod n
    due to circular buffer characteristics of the problem
	create two intervals, one from start to n-1 and one from 0 to end mod n

sorting the two vectors with start and end index will allow to calculate the 
index at which the most intervals overlap which is essentially the index of 
interest.

Finding the index works as follows:
let k be the number of intervals covered by the current index
int k = 0;
int maxk = 0;
int maxki = 0;
int s = 0;
int e = 0;
for(int i = 0; i < n; i++)
{
	while(s < start.size() && start[s] == i)  { s++; k++; }
	if(k > maxk) // new found { ... } 
	while(e < end.size() && end[e] == i) { e++; k--; }  
}

runtime complexity:
creating the start and end vectors: O(n)
sorting start and end vectors O(n * log(n))
finding max index: O(n)
total runtime: O(n * log(n))

space complexity: O(n)
*/

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

// the smarter version in O(n * lg(n))
int getIndexForMaxAmazingNo(const vector<int>& a)
{
	int n = a.size();
	vector<int> start;
	vector<int> end;

	// find start index interval that makes this element an amazing no
	for(int i = 0; i < n; i++) 
	{
		int s = i + 1;
		int e = n + i - a[i];
		if(e >= s)
		{
			start.push_back(s);
			if(e < n) 
			{
				end.push_back(e);
			}
			else 
			{
				end.push_back(n - 1);
				start.push_back(0);
				end.push_back(e % n);				
			}
		}
	}

	// sort interval start and interval end
	sort(start.begin(), start.end());
	sort(end.begin(), end.end());

	// by counting the number of intervals for start index i
	int k = 0;
	int maxk = 0;
	int maxki = 0;
	int s = 0;
	int e = 0;
	for(int i = 0; i < n; i++)
	{
		// why this inner loop makes not O(n^2): start has max 2*n elements, 
		// so e.g. if first element is n and second is n, all the others are 0 
		// (compensated runtime of this inner loop thus is constant)		
		while(s < start.size() && start[s] == i)  { s++; k++; } 
		if(k > maxk)
		{
			maxki = i % n;
			maxk = k;
		}
		while(e < end.size() && end[e] == i) { e++; k--; }  
	}

	return maxki;
}

// the brute force version in O(n²)
int getIndexForMaxAmazingNoBf(const vector<int>& a)
{
	int n = a.size();
	int maxk = 0;
	int maxki = 0;		
	for(int i = 0; i < n; i++)
	{
		int k = 0;		
		for(int j = 0; j < n; j++)
		{
			if(a[(i + j) % n] <= j) k++;
		}		
		if(k > maxk)
		{
			maxki = i;
			maxk = k;
		}
	}
	return maxki;	
}

// some primitive validation by comparing bruteforce with optimized
void test(const vector<int>& a)
{
	cout << "test array:\n ";
	for(auto e : a) cout << e << " ";
	int bfr = getIndexForMaxAmazingNoBf(a);
	int r = getIndexForMaxAmazingNo(a);
	cout << "\nbrute force result: " << bfr << " optimized result: " << r << (bfr == r ? " MATCH" : " !!DO NOT MATCH!!") << endl;
}

int main()
{
	test({4, 2, 8, 2, 4, 5, 3});
	test({1, 2, 3, 4, 5, 6, 7});
	test({9, 8, 7, 6, 5, 4, 3, 2, 1});
	test({0, 0, 0, 0, 0, 0, 0, 0, 0});
	test({});
	test({1});
	test({1, 2});
	test({1, 2, 3, 4, 5, 1, 2, 9, 10, 11, 1, 2, 3, 4, 5, 6});
}

/* output
test array:
 4 2 8 2 4 5 3 
brute force result: 0 optimized result: 0 MATCH
test array:
 1 2 3 4 5 6 7 
brute force result: 6 optimized result: 6 MATCH
test array:
 9 8 7 6 5 4 3 2 1 
brute force result: 0 optimized result: 0 MATCH
test array:
 0 0 0 0 0 0 0 0 0 
brute force result: 0 optimized result: 0 MATCH
test array:
 
brute force result: 0 optimized result: 0 MATCH
test array:
 1 
brute force result: 0 optimized result: 0 MATCH
test array:
 1 2 
brute force result: 1 optimized result: 1 MATCH
test array:
 1 2 3 4 5 1 2 9 10 11 1 2 3 4 5 6 
brute force result: 9 optimized result: 9 MATCH
*/

- Chris November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 vote

@tryhard, thanks, oh yea, the interval can be solved much better and I noticed you treated the intervals end > start as well different (I checked, it's correct, but by far not intuitive, and be aware that the count is wrong, but the maximized index is correct).
full credits on tryhard, the shortest and fastest solution is as follows

// the best solution in O(n)
int getIndexForMaxAmazingNo(const vector<int>& a)
{
	int n = a.size();
	vector<int> change(n, 0);

	// find for every element the interval that makes it an amazing number
	for(int i = 0; i < n; i++) 
	{
		if(a[i] >= n) continue;  // it will never participate
		int s = (i + 1) % n; 
		int e = (n + i - a[i]) % n; 
		change[s] ++;
		if(e + 1 < n) change[e + 1] --;
	}

	// find index with max (note: the maxk will not contain
	// the count of amazing numbers, if we want that, we have
	// to consider intervals whose start%n > end%n differntly
	// by considering them as two intevals, from start%n - n-1
	// and from 0 to end%n.
	int k = 0;
	int maxk = 0;
	int maxki = 0;
	for(int i = 0; i < n; i++)
	{
		k += change[i];
		if(k > maxk)
		{
			maxki = i;
			maxk = k;
		}
	}
	return maxki;
}

- Chris November 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int tot[n];
memset(tot,0,sizeof(tot));
for(int i=0;i<n;i++)
if((i-arr[i]+n)%n>=0)
tot[(i-arr[i]+n)%n]++;
int k=0;
int val=tot[0];
for(int i=0;i<n;i++)
cout<<tot[i]<<" ";
cout<<endl;
}

- abcd November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int tot[n];
memset(tot,0,sizeof(tot));
for(int i=0;i<n;i++)
if((i-arr[i]+n)%n>=0)
tot[(i-arr[i]+n)%n]++;
int k=0;
int val=tot[0];
for(int i=0;i<n;i++)
cout<<tot[i]<<" ";
cout<<endl;
}

- pratyush2013 November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. for each element in the array substract the value from the index. (For magic numbers these values will be positive or 0, for non happy numbers this value will be negative).

2. Find the largest positive subarray (including the circular case) leveraging kadane's algorithm.

- Guy November 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int FindAmazingNumberIndex(int[] a)
{
	int maxLength = 0;
	int maxIndex = -1;
	
	int i=0, j =0;
	while (i < a.Length)
	{
		// j >= i;
		//int index = j - i;   // length - 1
		//if (j < i)
		//    index = a.Length - (i - j);
		
		int index = (j >= i) ? j - i : a.Length - (i - j); 
		if (a[j] <= index)
		{
			j = (j + 1) % a.Length;
			if (j == i)
				return i;
			
			int length = index + 1;
			if (length > maxLength)
			{
				maxLength = length;
				maxIndex = i;
			}
		}
		else
		{
			if (i == j)
				j++;
			i++;
		}
	}
	
	return maxIndex;
}

- hnatsu November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an Objective-C solution in O(n), since is a circular array we need to find the max difference between index and value so the result should be the difference plus current index of the max difference.

Consider follow cases:
2, 3, 0, 1
0, 0, 0, 4, 0
1, 0, 0
-1, 2, 0

- (int)getMaxAmazingNumber:(NSArray *)array {
    
    int maxDiff = 0;
    int tempDiff = 0;
    int index = 0;
    
    for(int i = 0; i < [array count]; i++){
        
        if([array[i] intValue] > i){
            
            tempDiff = abs(i - [array[i] intValue]);
        }
        
        if(maxDiff < tempDiff){
            
            maxDiff = tempDiff;
            index = i;
        }
    }
    
    return maxDiff + index;
}

- oscarsanchez1937 November 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For 1, 5, 2, 4, 3 it outputs 5. 5 is not a valid index.

- azeemmohd October 19, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If I'm not wrong, here is another O(n) solution without intervals, but by just calculating moves on which item will get/lose "amazing" property.

int maxIdeal(vector<int> list){
    long n = list.size();
    vector<int> itemsToLostIdeal(n);
    vector<int> itemsToGetIdeal(n);
    int initialIdeal = 0;
    
    for(int i =0; i < n; i++){
        if(list[i] <= 0 || list[i] >= n ){
            continue;
        }
        if(list[i] <= i){
            initialIdeal++;
            itemsToLostIdeal[i - list[i]+1] ++;
        }else{
            itemsToLostIdeal[n - list[i] + i +1] ++;
        }
        if(i + 1 < n){
            itemsToGetIdeal[i+1] ++;
        }
    }
    int maxMoreIdeal = 0;
    int maxMoreIdealIndex = 0;
    int moreIdeal = 0;
    for(int i =1; i < n; i++){
        moreIdeal += itemsToGetIdeal[i]-itemsToLostIdeal[i];
        if(moreIdeal > maxMoreIdeal){
            maxMoreIdeal = moreIdeal;
            maxMoreIdealIndex = i;
        }
    }
    return maxMoreIdealIndex;
    
}

- Krizai November 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int seqcnt(int a[], int sze, int s, int pos)
{
 if(a[pos]>((pos+sze-s)%sze)) return 0;
 if(((pos+sze+1)%sze==s) return 1;
 return seqcnt(a,sze,s,(pos+1)%sze);
}
int gotN(int a[], int sze)
{
 int i;
 for(i=0;i<sze;i++)
  if(seqcnt(a,sze,i,i) return i;
 return -1;
}

}

- Jeff Ding December 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#! /usr/bin/env ruby

# input = [3, 4, 5, 1, 2]
input = [0, 1, 2, 3]

def count_amazing_num(arr)
  arr.reduce(0) { |mem, v| v >= 0 ? mem + 1 : mem }
end

max_amazing_num = nil
max_amazing_pos = nil
diff = input.each_with_index.map { |val, i| i - val }

(0...input.size-1).each do |pos|
  count = count_amazing_num(diff)
  if max_amazing_num.nil? || count > max_amazing_num
    max_amazing_num = count
    max_amazing_pos = pos
  end

  # shift the diff array
  shift_out = diff[0]
  (0...input.size-1).each do |i|
    diff[i] = diff[i+1] - 1
  end

  diff[-1] = shift_out + (input.size-1)
end

puts "max amazing num: #{max_amazing_num}\nmax amazing pos: #{max_amazing_pos}"

- jimmychu0807 January 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi tryhard,

1. I understood the start calculation.
2. how are you calculating end ?
3. only based on start and end index how can you tell, entire sequence is correct ?

Could you please explain it ?

- Raj January 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Could some one please explain me @Chriz or @tryhard solutions.

1. I understood interval part
2. How can incrementing and documenting start and end indexes can give the start index
m not able to understand this part

- Raj February 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Swift Version:::::

func getAmazingNumbers(_ array: [Int], startingPoint: Int) -> [Int]? {
    var a = array
    var i = 0
    while i < startingPoint {
        let val = a.removeFirst()
        a.append(val)
        i += 1
    }
    
    for (i,v) in a.enumerated() {
        if v > i {
            a.remove(at: i)
        }
    }
    
    return a
}

let n = getAmazingNumbers([0,1,2,3], startingPoint: 0) // n = [0,1,2,3]
let n1 = getAmazingNumbers([1,0,0], startingPoint: 1) // n1 = [0,0,1]

- Rupak February 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findamazingnmber(arr):
	min_index = 1000000
	amazing_numbers = []
	max_val = -1
	for i in range(len(arr)):
		if arr[i] <= i and max_val < i-arr[i]:
			min_index = i
			max_val = i - arr[i]
	for i in range(0,min_index):
		if arr[i] <= i+min_index:
			amazing_numbers.append(arr[i])
	for i in range(min_index,len(arr)):
		if arr[i] <= i:
			amazing_numbers.append(arr[i])
	print "strting index is " + str(min_index)
	print amazing_numbers

findamazingnmber([34,5,23,6,4,2,6,1,8,4])

- Pradeep April 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findamazingnmber(arr):
	min_index = 1000000
	amazing_numbers = []
	max_val = -1
	for i in range(len(arr)):
		if arr[i] <= i and max_val < i-arr[i]:
			min_index = i
			max_val = i - arr[i]
	for i in range(0,min_index):
		if arr[i] <= i+min_index:
			amazing_numbers.append(arr[i])
	for i in range(min_index,len(arr)):
		if arr[i] <= i:
			amazing_numbers.append(arr[i])
	print "strting index is " + str(min_index)
	print amazing_numbers

findamazingnmber([34,5,23,6,4,2,6,1,8,4])

- Pradeep April 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
int tot[n];
memset(tot,0,sizeof(tot));
for(int i=0;i<n;i++)
if((i-arr[i]+n)%n>=0)
tot[(i-arr[i]+n)%n]++;
int k=0;
int val=tot[0];
for(int i=0;i<n;i++)
cout<<tot[i]<<" ";
cout<<endl;
}

- abcd November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

anyone can solve this less than O(N^2)?
@OP: could you?

This is my brute force O(N^2):

private static int bruteForce(int[] a) {
        int res = 0;
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            int count = 0;
            for (int j = 0; j < a.length; j++) {
                int p = j + i;
                if (j - a[p % a.length] >= 0) count++;
            }
            if (count > max) {
                max = count;
                res = i;
            }
        }
        return res;
    }

- tryhard November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.io.*;
import java.util.*;

class Solution {
public static void main(String[] args) {
int[] a = {0,1,2,3};
int sln = numMoves(a);
int answer = 0;
assert sln == answer : "EXPECTED: " + answer + " ACTUAL: " + sln;

int[] b = {1,0,0};
sln = numMoves(b);
answer = 1;
assert sln == answer : "EXPECTED: " + answer + " ACTUAL: " + sln;

int[] c = {1,2,0};
sln = numMoves(c);
answer = 2;
assert sln == answer : "EXPECTED: " + answer + " ACTUAL: " + sln;

int[] d = {3,0,0};
sln = numMoves(d);
answer = -1;
assert sln == answer : "EXPECTED: " + answer + " ACTUAL: " + sln;

int[] e = {0,0,0,4,0};
sln = numMoves(e);
answer = 4;
assert sln == answer : "EXPECTED: " + answer + " ACTUAL: " + sln;

int[] f = {1};
sln = numMoves(f);
answer = -1;
assert sln == answer : "EXPECTED: " + answer + " ACTUAL: " + sln;
}

public static int numMoves(int[] array) {
int startIndex = 0;
int currIndex = 0;

for(int i = 0; i < array.length; i++) {
int value = array[i];

if(value > currIndex) {
startIndex = i + 1;
currIndex = -1;
}
if(value >= array.length) {
startIndex = -1;
break;
}

currIndex++;
}

return startIndex;
}
}

- Anonymous November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*
Assumption: all element is integer and >= 0
From the question, we can understand the output queue must be:
1. Begin from 0 (because all index are begin with 0)
2. The Max value must be smaller than the array size.

So here we can calculate the begin position directly:
1. Find the Max value (MV) and its index (MI) of the array
2. Find the candidate position canStart = MV - MI
3. Find the 0 which index < canStart
*/

import java.io.*;
import java.util.*;

class Solution {
public static void main(String[] args) {
	int[] questionQueue = {0, 0, 0, 2, 2, 0};
	int startPosition = GetSolutionIndex(questionQueue);
	int [] answerQueue = OutputAnswer(questionQueue, startPosition);
	}
	
	public class int GetSolutionIndex(int[] Q){
		private int maxIndex = 0;
		private int maxValue = -999;
		private int canStart = 0;
		for (int i=0; i< Q.length; i++){
			if (Q[i] > maxValue){
				maxValue = Q[i];
				maxIndex = i;
			}
		}
		canStart = maxValue - maxIndex; //(must <= 0)
		
		/*
		The start point should <= canStart
		*/
		int startIndex = 0;
		for (int i = (maxIndex + canStart); i != maxIndex ; i--){
			if (Q[i] == 0){
				startIndex = i;
			}
			if (i == 0){
				i == Q.length - 1;
			}				
		}
		return startIndex;
	}
	public class int OutputAnswer(int[] Q, int index){
		for (int i = 0; i < Q.length; i++){
			int currentPosition = index + i;
		if (currentPosition >= Q.length)
			currentPosition -= Q.length
		System.output.print(Q[currentPosition]);
		}
	}
}

- Albert Chen November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here is a Java solution with O(n);
Assumption:
1. all numbers are integer and larger than 0;
2. the array must contain a index which can result in magic number.
Solution:
1. Find the MAX number (and its position) inside the array
2. Find the difference between the MAX number and its position to decide the candidates
3. Find the best 0 of from candidates positions

package MagicNumber;

class getMagicNumberIndex{
	public int GetMax(int[] intQueue){
		int index = 0;
		int maxNumber = -999;
		for (int i : intQueue){
			if (intQueue[i] > maxNumber){
				maxNumber = intQueue[i];
				index = i;
			}
		}
		return index;
	}
	
	public int GetfirstZero(int[] intQueue, int start, int end){
		int firstZero = 0;
		for (int i = start; i < end; i++){
			if (intQueue[i] == 0){
				firstZero = i;
				break;
			}
		}
		return firstZero;
	}
}


public class MagicNumber {

	public static void main(String[] args) {
		int[] questionList = {0,0,0,0,2,3,1,0,0}; //define any number list here
		int startPosition = 0;
		int maxIdx =0;
		
		getMagicNumberIndex magic = new getMagicNumberIndex();
		
		maxIdx = magic.GetMax(questionList);
		int shiftposition = questionList[maxIdx] - maxIdx;
		if (shiftposition < 0){
			startPosition = magic.GetfirstZero(questionList, 0, maxIdx + shiftposition);
		}
		else{
			startPosition = magic.GetfirstZero(questionList, maxIdx, questionList.length - shiftposition);
		}
		
		System.out.println("The index of magic number is: " + startPosition);
	}
}

- Albert November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(n) solution for Objective-C coders.
The key principle is simple. When the number of matches from index (i) equals k, the number of matches for (i+1) must be at least k-1. By doing this, we can guarantee O(n).

#import <Foundation/Foundation.h>
#import <stdio.h>


@interface AmazingNumber:NSObject

@property (nonatomic, strong) NSArray *numbers;
  
- (NSNumber *)getMaxAmazingNumber:(NSArray *)numbers;
  
@end

@implementation AmazingNumber
  
- (NSNumber *)getMaxAmazingNumber:(NSArray *)numbers {

  int maxMatches = -1;
  int maxIndex = -1;
  int p = 0;
  int matches = 0;
  int previousMatch = 0;
  for(int i = 0; i < [numbers count]; i++) {
    matches = MAX(0, previousMatch-1);    // as increasing the index by 1, the first match of the previous index disapp
    while([numbers[p] intValue] >= (i+matches) && matches < [numbers count]) {
      p = (p+1)%[numbers count];
      matches += 1;
    }
    if(matches > maxMatches) {
      maxMatches = matches;
      maxIndex = i;
    }
  }
  return @(maxIndex);
}

@end

int main (int argc, const char * argv[])
{
  @autoreleasepool {
    AmazingNumber *am = [[AmazingNumber alloc] init];
    NSLog(@"%@", [am getMaxAmazingNumber:@[@0, @1, @2, @3]]);
    NSLog(@"%@", [am getMaxAmazingNumber:@[@4, @2, @1, @3]]);
  }
}

- Jake November 18, 2016 | Flag Reply


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