Google Interview Question
Software Engineer / DevelopersHere is the c++ code.
#include <iostream>
using namespace std;
void swap(int *array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
int find(int *array, int n)
{
int i = 0;
int j = n - 1;
while (i <= j)
{
if (array[i] <= 0)
{
++i;
}
else
{
while (i <= j)
{
if (array[j] > 0)
{
--j;
}
else
{
swap(array, i, j);
++i;
--j;
break;
}
}
}
}
int positive = i;
while (i < n)
{
if (array[i] > n - positive)
{
++i;
}
if (array[i] == array[array[i] + positive - 1])
{
++i;
}
swap(array, i, array[i] + positive - 1);
}
for (int i = positive; i < n; ++i)
{
if (array[i] != i - positive + 1)
{
return i - positive + 1;
}
}
return n - positive + 1;
}
int main()
{
int n;
int array[1000];
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> array[i];
}
int result = find(array, n);
cout << result << endl;
return 0;
}
The idea is great but, putting all positives to the front and then traversing at the beginning of the array and also the swapping won't cost a lot ?
similar to Anon's idea, but no need to treat negative numbers differently.
High level idea is as follows. If there are n numbers, then the max positive number not present in the array is n+1. this happens when numbers 1 through n are all present. We could do something like a count sort. for each number x in [1,n], we would like to move it to position x-1, then scan the array again and see which number is missing. for numbers greater than n and less than 1, we just leave then at their original position.
Here is my code:
int minPositive(int a[], int n) {
for (int i = 0; i < n; ++i) {
int t1 = a[i]; // move t1 to a[t1-1]
while (t1 > 0 && t1 <= n) {
if (t1 == a[t1-1])
break;
int t2 = a[t1-1];
a[t1-1] = t1;
t1 = t2;
}
}
int i;
for (i = 0; i < n; ++i)
if (i != a[i]-1)
break;
return i+1;
}
i use several test cases to run db's code, find no mistake for now, thx db's code, really help a lot!
I think the above anonymous guy is the true idiot.
The above case will be swaped to [1, 2, 19999999, 1000000000000],
and since 19999999 != 3, we know the answer is 3.
1. Create an array of size N ( indexing 1 to N ) with all entries as zero.
2. Scan the input and ignore the input if it is
a) less than 1
b) greater than N
3. Otherwise, set array[input] = 1
4. In the end, return the first index with a zero value. If all entries are 1, return N+1.
Note: We don't have to find the maximum of elements as some people have suggested. If it is greater than N, it will create a hole in the range 1 to N, which we are trying to find out. The worst case will be the input will be a permutation of elements 1 to N.
people just post their solution without even thinking a little
.numbers are not between 1 to N.
public static int lowest (int[] arr){
int vals[] = new int[arr.length];
for( int i = 0; i < arr.length; i++ ) vals[i] = 0;
for( int i = 0; i < arr.length; i++ )
if (arr[i] > 0 && arr[i] < arr.length) vals[arr[i]] = 1;
int len = 0;
for(int i = 1; i < vals.length; i++)
if (vals[i] == 1) len++; else break;
return len+1;
}
An index bug fixes. O(n) solution
public static int lowest (int[] arr){
int vals[] = new int[arr.length+1];
for( int i = 0; i < arr.length+1; i++ ) vals[i] = 0;
for( int i = 0; i < arr.length; i++ )
if (arr[i] > 0 && arr[i] <= arr.length) vals[arr[i]] = 1;
int len = 0;
for(int i = 1; i < vals.length; i++)
if (vals[i] == 1) len++; else break;
return len+1;
}
How the memory can be O(n) here?. assume the input as {1,-10,4,6,370}. I assume your memory is O(370) i.e O(MAX)
He is checking if the val is > array length
arr[i] <= arr.length
This is to make sure that there are gaps from 1 - array.length.
the naive solution is
sort the array
scan from the first positive integer, and find any integer is missing.
What is the better solution for this ?
No need to sort. Consider only positive number for comparison when finding minimum. O(N).
min=INFINITY;
FOR I=1 to N
if(ARRAY[i]>0)
if(min>ARRAY[I])
min=ARRAY[I]
min = 0
after the loop is completed check min = 0 then there is no positive integers in array else min will have the lowest positive integer.
We need to find out the minimum element NOT present in the array.
Your soln. gives the minimum element present in the array
assume numbers are unique.
find FIRST_MIN and SECOND_MIN in array, such that both of them > 0 and FIRST_MIN < SECOND_MIN
if ( FIRST_MIN != 1) result = 1;
else if SECOND_MIN = FIRST_MIN + 1, result = SECOND_MIN + 1
else result = FIRST_MIN + 1
@ Tulley:Ur sol wont work take this array for eg)6,7,10,1,3,2,5,4 ans should be 8 but urs return the minimum in the array
@neebanv:yes sorting seems to be a better way.If space is no constraint declare a bit vector of length=largest number in the array and set those positions present in array to 1.Traverse the bit vector the first 0 u hit is the ans
Time-O(MAX),space-O(MAX)
Time: O(N)
Space: O(N) in worst case
public int lowestMissedPositive(int[] arr){
Set<Integer> positiveValues = new HashSet<Integer>();
int min = Integer.MAX_VALUE;
int max = 0;
for( int i = 0; i < arr.length; i++ ){
if( arr[i] > 0 ){
positiveValues.add( arr[i] );
if( arr[i] < min ){
min = arr[i];
}
else if( arr[i] > max ){
max = arr[i];
}
}
}
if( min > 1 ){
return 1;
}
for( int i = min; i < max+1; i++ ){
if( ! positiveValues.contains(i) ){
return i;
}
}
return max+1;
}
There should be more elegant solution in O(N) time and O(1) space.
Are u sure it's O(N)? I think set insert takes more than O(1) time in worst case (if hash table). For balanced tree, it can't be < O (log n).
anonymous is right. it's indeed O(n logn).
look at : cplusplus.com/reference/stl/set/insert/
1) set in stl implemented as a balanced BS tree(avl, rb, etc.), so O(n lgN).
2) Insertion takes O(1) worst-case time and deletion takes O(1)
worst-case time when the lists are doubly linked. HashSet in java use HashMap class. Here from documentation: "This implementation provides constant-time performance for the basic operations get and put), assuming the hash function
disperses the elements properly among the buckets."
essentially the question translates to whether 1 is present in the array. In an unsorted array, we can check that in o(n).
<pre lang="" line="1" title="CodeMonkey77728" class="run-this"> public int findLowestHM(int[] a){
int lowestNotPresentPos = -1;
int maxPositive = 0;
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
for(int i = 0;i < a.length;++i){
if(a[i] > maxPositive){
maxPositive = a[i];
}
if(a[i] > 0){
hashMap.put(i, a[i]);
}
}
for(int i = 1;i < maxPositive;++i){
if(!hashMap.containsValue(i)){
return i;
}
}
return lowestNotPresentPos;
}
</pre>
I'd prefer a sorting based O (nlogn) solution over O(MAX) solution, because MAX can be as large as 2^31-1 (for 4 byte int).
If we dont have space constraint then we can solve it in O(n) time complexity:
1) find MIN and MAX positive integer.
2) create one array with size MAX. Suppose A[MAX] and initialize it with 0.
3) Traverse the original array and put all positive integer in A in following way:
if number is x then A[x-1]=x .
4) Now traverse A and the first encountered zero value of array will the result.
Suppose A[6] is zero then result will be 7.
5) If A does not have any zero value then result will be MAX +1 .
Note: It will take more space but time complexity will O(n).
If any mistake is there please let me know.
<pre lang="" line="1" title="CodeMonkey10943" class="run-this">// Here is an O(N) time, O(N) space solution that does not depend on the value range of integers in the array
class MissingPositive {
private int[] a;
private Island lowest;
private Map<Integer, Island> map;
private Island inland = new Island(0, 0);
public static void main(String[] args) {
System.out.println(new MissingPositive(new int[]{}).find());
System.out.println(new MissingPositive(new int[]{4,2,3}).find());
System.out.println(new MissingPositive(new int[]{6,7,10,1,3,2,5,4}).find());
}
public MissingPositive(int[] a) {
this.a = a;
}
public int find() {
lowest = null;
map = new HashMap<Integer, Island>();
for (int i = 0; i < a.length; i++) {
int n = a[i];
if (n > 0 && map.get(n) == null) {
// No island containing this number exists
// Check if an island exists immediately on the left
Island left = null;
if (n > 1) {
left = map.get(n - 1);
if (left != null) {
if (left.min != left.max) {
// Mark the previous boundary number as inland
map.put(left.max, inland);
}
// Expand island to the right
left.max = n;
map.put(n, left);
}
}
// Check if an island exists immediately on the right
Island right = map.get(n + 1);
if (right != null) {
if (right.min != right.max) {
// Mark the previous boundary number as inland
map.put(right.min, inland);
}
// Expand the island to the left
right.min = n;
map.put(n, right);
storeIfLowest(right);
}
if (left != null && right != null) {
// Join the islands: the left one will be the main now.
left.max = right.max;
right.min = left.min;
// Mark the common boundary number as inland
map.put(n, inland);
map.put(left.min, left);
map.put(left.max, left);
} else if (left == null && right == null) {
// Create a new island
Island isle = new Island(n, n);
map.put(n, isle);
storeIfLowest(isle);
}
}
}
if (lowest == null) {
// No islands
return 1;
}
// The non-existing number is either before the lowest island or immediately after
return lowest.min > 1 ? lowest.min - 1 : lowest.max + 1;
}
private void storeIfLowest(Island isle) {
if (lowest == null) {
lowest = isle;
} else if (isle.min < lowest.min) {
lowest = isle;
}
}
private static class Island {
public int min;
public int max;
public Island(int min, int max) {
this.min = min;
this.max = max;
}
}
}
</pre><pre title="CodeMonkey10943" input="yes">
</pre>
Unable to come up with your own solution? Looking for a "royal path to geometry"? Then learn how to read the code; or at least, how to be polite.
@Anon - Then why don't you go ahead and chew on this code, while we do something more useful like understanding the solution:
#include<curses.h>
#include<stdlib.h>
#include<string.h>
#define A int
#define F float
#define O sizeof
#define V ((A *)(X+N))
#define U(a,b) for(a = 0; a < b; a++)
#define L(a) (X[K] * H[a*4]+ X[K+1] * H[a*4+1]+ X[K+2] * H[a*4+2])
#define _(e,f,a,b,c) if(M==e) { T[a*4+c] = T[b*4+c] = T[c*4+a] = T[c*4+b] = !(T[c*5] = 1); T[a*4+b] = -(T[b*4+a] = f .1045284632); T[b*5] = T[a*5] = .9945418726; U(M,3) U(E,4) U(K,3) R[M*4+E] += H[K*4+E] * T[M*4+K]; memcpy(H,R,12*O(F)); }
char Q[3792];
A K, M=0, E, B;
long Z;
F H[] = { 1,0,0,0,0,1,0,0,0,0,1,0 } , T[12], R[12], C, D, I, J, S, * X, G=4;
FILE * W;
A main(A N,char ** Y) {
char P[] = "AlWuzEre 72 -1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 -1 1 1 1 -1 1 -1 -1 -1 1 -1 -1 1 1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 1 1 -1 -1 -1 -1 -1 1 -1 1 1 -1 -1 -1 1 1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 ";
strcpy(Q,P);
if(!(W = fopen(Y[N<2?0:1],"r"))) {
printf("Can't read\n"); exit(-1); }
fseek(W,0,SEEK_END);
Z = ftell(W);
fseek(W,0,SEEK_SET);
strcpy(Q+9, "%d");
while(fscanf(W,Q,&N) != 1) {
fseek(W,1,SEEK_CUR);
if(ftell(W) >= Z) {
printf("Bad input\n"); exit(-1); } }
X = (F *)malloc(N * (O(A)>O(F)?O(A):O(F)) * 2);
if(!X) { printf("No memory\n"); exit(-1); }
U(K,N) fscanf(W,"%f",X+K);
fclose(W);
initscr();
halfdelay(30);
noecho();
CH:
memset(R,0,12*O(F));
_('h', ,1,2,0)
_('j', ,2,0,1)
_('k', ,1,0,2)
_('y',-,1,2,0)
_('u',-,2,0,1)
_('i',-,1,0,2)
G += M=='a'?-.1:M=='z'?.1:0;
if(M=='q') { printf("%.9s\n",P); exit(0); }
memset(Q,0,3792);
erase();
U(K,N) {
C = 40 / (L(2)+G);
V[K] = (A)(L(0) * C) + 40;
V[K+1] = (A)(L(1) * C) + 24;
K+=2; }
U(B,N) {
C = V[B++];
D = V[B++];
E = V[++B] - C;
M = V[++B] - D;
B++;
S = (F)abs((abs(E)>abs(M))?E:M);
I=E/S;
J=M/S++;
U(K,S)
{
E = (A)(C+0.5);
M = (A)(D+0.5);
if(E>=0 && M>=0 && E<79 && M<48)
{
Q[E + M * 79] = 1;
mvaddch((M&1?M-1:M)/2,E,Q[E+(M+(M&1?-1:1))*79]?':':(M&1?'.':'`'));
}
C+=I;
D+=J;
}
}
move(0,0);
refresh();
M = getch();
halfdelay(M==ERR?1:30);
M = M==ERR?'u':M;
goto CH;
}
<pre lang="" line="1" title="CodeMonkey66871" class="run-this"># In python:
class Island:
def __init__(self, minv, maxv):
self._min = minv
self._max = maxv
def find_missing_positive(array):
islandmap = {}
min_island = Island(0, 0)
for n in array:
if islandmap.has_key(n):
continue
left = None
island = Island(n, n)
if n > 1:
left = islandmap.get(n-1)
if left is not None:
island._min = left._min
right = islandmap.get(n+1)
if right is not None:
right._min = island._min
island._max = right._max
if left is not None:
left._max = island._max
if min_island._max == 0 or min_island._min >= island._min:
min_island._max = island._max
min_island._min = island._min
islandmap[n] = island
if min_island._min > 1:
return 1
return min_island._max + 1
</pre>
class Island:
def __init__(self, minv, maxv):
self._min = minv
self._max = maxv
def find_missing_positive(array):
islandmap = {}
min_island = Island(0, 0)
for n in array:
if islandmap.has_key(n):
continue
left = None
island = Island(n, n)
if n > 1:
left = islandmap.get(n-1)
if left is not None:
island._min = left._min
right = islandmap.get(n+1)
if right is not None:
island._max = right._max
if min_island._max == 0 or min_island._min >= island._min:
min_island._max = island._max
min_island._min = island._min
islandmap[n] = island
islandmap[island._min] = island
islandmap[island._max] = island
if min_island._min > 1:
return 1
return min_island._max + 1
Sorry, the previous code is wrong
who cares?
who has the time to decipher your code (which may well be incorrect.) It's always better to provide at least a rough idea of what you are trying to achieve before you throw your code at us.
@Xiaoyu
There is another problem with your solution.(Apart from space limitations)
while you check whether a no is positive or negative before inserting it into the hash map
however you enter the elements in the hash map using index i, and for a missing index i, you return i.
thus if you have a negative no in your array it wont be inserted into the hashmap and hence that index will be returned while checking for the missing smallest positive integer.
Sorry I misread the question:
This solution would work, the complexity is o(n)
private static int findLowestPostiveValue(int[] a) {
int min= a[0];
for(int i=1;i<a.length;i++)
{
if((a[i]<min)&&(a[i]>=0))
{
min=a[i];
}
}
int resultmin=min-1;
if(resultmin>=0)
return resultmin;
else
return min;
}
Maintain an n-bit vector(initialized to 0). Scan through the array, whenever you find a positive element(a[i]) and a[i] <= n, set the a[i]'th bit of bit vector to 1. After complete scan on array, let's say that bit vector contains 1st zero at xth position, then x is your answer!!
sort the array e.g (quick sort) -- O(log n)
Binary search the array for where +ive #s start. -- O(log n)
if(1st +ive # is not 1) return 1;
else scan till missing +ive # -- worst case O(n)
If space is no constraint then the solution suggested by some of us here, that to create a new array with size equal to max integer in the list is good.
If space is constraint then here is another method that can be used:
1) sort the array, TC O(nlgn)
2) traverse the array from start till first positive number is encountered, take care of if 0 is also an element of array.
3) lets assume the index of first positive number is i and length of array is n
use another variable, j and initialize it to 1.
the code will now look like
for(j=1;i<n;++j,++i) //traverse loop till we reach end of array, increment i & j at each step.
{
if(arr[i]/j != 1 && arr[i]%j != 0)
first_missing_positive_num = j;
}
We can also use if condition like (this strike me a moment later :) )
if(a[i] != j)
first_missing_positive_num = j;
O(n), constant storage.
void foo(int[] ai) {
int missing_min = 1;
for(int i = 0; i < ai.length; i++) {
if(ai[i] == missing_min) {
missing_min++;
}
}
If this problem has only one number missing and there is no repetition of numbers. Then XOR all the positive number is one iteration and store the max number too. Then Again XOR the resultant from 1^2^3^...^max
ans = resultant^1^2^3^...^max.
In that ideal case, if the array is size n, you can also just subtract (n+1)*(n+2)/2 from the total of the elements.
Example:
{1,3,5,7,9,2,4,6,10}
Here n=9 and the number 8 is missing. The sum of numbers from 1-10 is 10*11/2 = 55 and the total in this array is 47 so the result is 8 as expected.
Use a min-heap. Go through array (ignoring negative integers) and add positive numbers to heap. If you find integers 1&2 then remove 1 from heap. If heap has already 3, remove 2 and so on. We would need custom heap which would return min() and secondMin(). After starting removing minimal numbers from heap we could also ignore such numbers during going through array.
At the end start removing min numbers from heap, is next number is greater than current more than 1 you found the solution.
Worst case performance will be O=(n*log(n)), but the average case will be much faster than sorting.
1. Remove all negatives. Let nPos be no of +ves.
2. For 0 to Npos-1
a) if array element is greater than nPos-1--> set it to -1.
b) if Array element is not equal to its index and index of array element is also not equal to its value -->swap them
c) if Array element is not equal to its index but index of array elem is equal to its value --> Set elem -1
3. Find the first elem that is not equal to index and return it as minimum missing.
Complexity n+n+n= O(n)
Code:
int find_first_missing(int arr[],int len)
{
int i=0;
int j=0;
/** Remove all negatives STEP 1 **/
for(j=0;j<len;j++)
{
if(arr[j] >= 0)
{
arr[i++]=arr[j];
}
}
arr[i]='\0';
/*****STEP 2 ******/
for(j=0;j<i;j++)
{
if(arr[j]>i)
{
arr[j]=-1;
}
else if(j != arr[j])
{
if(arr[arr[j]]!=arr[j])
{
int temp=arr[arr[j]];
arr[arr[j]]=arr[j];
if(temp<i)
{
arr[j]=temp;
}
else
{
arr[j]=-1;
}
}
else
{
arr[j]=-1;
}
}
}
/******* STEP 3 ***/
for(j=0;j<i;j++)
{
if(arr[j] !=j)
return j;
}
}
1. Remove all negatives. Let nPos be no of +ves.
2. For 0 to Npos-1
a) if array element is greater than nPos-1--> set it to -1.
b) if Array element is not equal to its index and index of array element is also not equal to its value -->swap them
c) if Array element is not equal to its index but index of array elem is equal to its value --> Set elem -1
3. Find the first elem that is not equal to index and return it as minimum missing.
Complexity n+n+n= O(n)
Code:
int find_first_missing(int arr[],int len)
{
int i=0;
int j=0;
/** Remove all negatives STEP 1 **/
for(j=0;j<len;j++)
{
if(arr[j] >= 0)
{
arr[i++]=arr[j];
}
}
arr[i]='\0';
/*****STEP 2 ******/
for(j=0;j<i;j++)
{
if(arr[j]>i)
{
arr[j]=-1;
}
else if(j != arr[j])
{
if(arr[arr[j]]!=arr[j])
{
int temp=arr[arr[j]];
arr[arr[j]]=arr[j];
if(temp<i)
{
arr[j]=temp;
}
else
{
arr[j]=-1;
}
}
else
{
arr[j]=-1;
}
}
}
/******* STEP 3 ***/
for(j=0;j<i;j++)
{
if(arr[j] !=j)
return j;
}
}
An O(n) solution with maximum 3 run:
1st run: find minimum number a[k]>0
if a[k]>1 return return
2nd run: set bool b[a[i]]=true if a[i]>0 and a[i]<a.Length
3nd run: return first i that b[i]==false
if every b[i] is false, return a.length
The logic is that in the 1st run, if we can find the min number in array more than 1 , that means 1 is not in the array.
Otherwise, the array must has a subset(no need to be a sub-sequence) containing consecutive number staring from 1. so the length of that subset can not be more than the length of original array. So we just need to use a bit array b[] to record the consecutive numbers starting from 1 in original array.
The left thing is easy though......
public class MinPositiveNotInArray {
static int minPositiveNotInArray(int a[]){
int n = a.length;
// need to keep track of the end points of ranges for the endpoints only
Map<Integer,Integer> rangeMinWithElement = new HashMap<Integer,Integer>();
Map<Integer,Integer> rangeMaxWithElement = new HashMap<Integer,Integer>();
for(int i = 0; i < n; i++){
if(a[i] > 0){
int min = a[i], max = a[i];
if(!rangeMinWithElement.containsKey(a[i])){
rangeMinWithElement.put(a[i], a[i]);
}
if(!rangeMaxWithElement.containsKey(a[i])){
rangeMaxWithElement.put(a[i], a[i]);
}
if(rangeMinWithElement.containsKey(a[i]-1)){
min = rangeMinWithElement.get(a[i]-1);
}
if(rangeMaxWithElement.containsKey(a[i]+1)){
max = rangeMaxWithElement.get(a[i]+1);
}
//System.out.println(a[i] + "\t" + min + "\t" + max);
rangeMaxWithElement.put(min, max);
rangeMinWithElement.put(max, min);
}
}
if(!rangeMinWithElement.containsKey(1)){
return 1;
} else {
int max = rangeMaxWithElement.get(1);
return max+1;
}
}
public static void main(String[] args){
int[] testcase1 = {-2 , 1 , 5 , 8 , -8 , -6 , 0 , 2};
int res1 = 3;
int[] testcase2 = {-2 , 1 , 5 , 8 , -8 , -6 , 0 , 2 , 3 , 4};
int res2 = 6;
System.out.println(Arrays.toString(testcase1));
System.out.println(minPositiveNotInArray(testcase1)+ "\t" + res1);
System.out.println(Arrays.toString(testcase2));
System.out.println(minPositiveNotInArray(testcase2)+ "\t" + res2);
}
}
an O(n) C++ code with O(1) space
void swap(int &a, int &b){
int tmp = a;
a = b;
b = tmp;
}
int lowest_pos(int a[], int n)
{
int i = 0;
while(true){
if(a[i] == i+1)
i++;
else if(a[i] <= n && a[i] > 0)
swap(a[i],a[a[i]-1]);
else i++;
if(i==n)
break;
}
for(int i = 0; i < n ; i++)
if(a[i] != i+1)
return i+1;
return n+1;
}
Step 1:
- Anon April 07, 2011Disregard all negatives (put all the positives in the front of the array)
Step 2:
Say the number of positive numbers is: N
we can divide the array into two parts: <=N and >N (the part <=N is first, the >N is second)
Step 3:
For every number x in the array <=N, swap it with the number at index x. Do not swap repeats.
Step 4:
Scan through the numbers and find the first number that does not match its index.