Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
/*
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
*/
@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;
}
#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;
}
#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;
}
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;
}
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;
}
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;
}
#! /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}"
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]
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])
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])
#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;
}
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;
}
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;
}
}
/*
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]);
}
}
}
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);
}
}
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]]);
}
}
@Chrisz
That's brilliant!!!
I never thought of intervals.....
Anyway, I improved your algorithm a little bit, and I've got O(n):
- tryhard November 15, 2016