Interview Question
Data EngineersCountry: United States
void FindGap(const std::vector<int>& data)
{
assert(!data.empty());
auto min = data.front();
auto max = data.back();
auto curIt = data.cbegin();
bool first = true;
for(auto i = min; i < max; i++)
if(i != *curIt)
{
if(!first)
std::cout << ',';
std::cout << i;
first = false;
}
else
curIt++;
}
A correct solution for this during interview would depend on some clarifications:
* Is the input already sorted?
* If input is not sorted, do we want to optimize for time or space?
* what is exactly considered a gap? the sequence should start with 1 or with the minimum value already present?
* What about duplicates?
public class FindGap {
public static void main(String[] args) {
int a [] = {1, 2, 5, 6, 10};
printGap(a);
}
public static void printGap(int a[]) {
int max = maxElementOfArray(a);
int j = 0;
for (int i = 0; i < max; i++) {
if (a[j]==i) {
j++;
} else if(i > 0) {
System.out.print(i +", ");
}
}
}
public static int maxElementOfArray(int a[]) {
int max = Integer.MIN_VALUE;
for (int i : a) {
if (i > max) {
max = i;
}
}
return max;
}
}
int a[]={1,2,5,6,10,11,12,18,21,22,23,100};
- Anonymous October 04, 2017int i=0;
int j=1;
while(j<=a[a.length-1]){
if(a[i]==j){
j++;
}else{
while(j<=a[i]){
if(a[i]==j){
j++;
break;
}
System.out.println(j);
j++;
}
}
i++;
}