## Stripe Interview Question

Software Engineers**Country:**United States

This question is asking the first missing positive integer from the list of n integers. (Total n-1 integers given and return value should be an integer missing (m) from this list. So, it is implied that 1<=m<=n.

```
#include<iostream>
#include<vector>
using namespace std;
int missingInt(vector<int> v) {
int cnt=0, tmp=v[0],n=v.size(),i=0;
while(cnt<=n) {
if(v[i] != i+1 && v[i]<=n) {
tmp = v[v[i]-1];
v[v[i]-1] = v[i];
v[i]=tmp;
}
else i++;
cnt++;
}
int j=0;
for( j=0;j<n;++j)
if(v[j]!=j+1) return j+1;
return j+1;
}
int main() {
vector<int> v = {4,1,5,3}; // Don't sort it. Otherwise it will be n log(n).
int ret = missingInt(v);
cout<<ret;
return 0;
}
```

We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value. In the following code, findMissingPositive() function does this part. Note that in findMissingPositive, we have subtracted 1 from the values as indexes start from 0 in C.

```
/* Find the smallest positive missing number
in an array that contains all positive integers */
int findMissingPositive(int arr[], int size)
{
int i;
// Mark arr[i] as visited by making arr[arr[i] - 1] negative.
// Note that 1 is subtracted because index start
// from 0 and positive numbers start from 1
for(i = 0; i < size; i++)
{
if(abs(arr[i]) - 1 < size && arr[ abs(arr[i]) - 1] > 0)
arr[ abs(arr[i]) - 1] = -arr[ abs(arr[i]) - 1];
}
// Return the first index value at which is positive
for(i = 0; i < size; i++)
if (arr[i] > 0)
// 1 is added because indexes start from 0
return i+1;
return size+1;
}
```

import java.util.HashMap;

import java.util.Map;

import java.util.PriorityQueue;

class ServerTrackerDetail {

int currMax = 0;

PriorityQueue<String> priorityQueue = new PriorityQueue<>();

}

public class ServerTracker {

Map<String, ServerTrackerDetail> prefixMap = new HashMap<>();

public ServerTracker() {

}

public String allocate(String prefix) {

if(!prefixMap.containsKey(prefix)) {

prefixMap.put(prefix, new ServerTrackerDetail());

}

ServerTrackerDetail detail = prefixMap.get(prefix);

if(detail.priorityQueue.size() > 0) {

return detail.priorityQueue.poll();

} else {

return prefix + ++detail.currMax;

}

}

public void deallocate(String server) {

String prefix = "";

for(int i = server.length()-1; i > 0 ; i--) {

if(!Character.isDigit(server.charAt(i))) {

prefix = server.substring(0, i+1);

break;

}

}

ServerTrackerDetail detail = prefixMap.get(prefix);

detail.priorityQueue.add(server);

}

public static void main(String[] args) {

ServerTracker serverTracker = new ServerTracker();

System.out.println(serverTracker.allocate("apibox"));

System.out.println(serverTracker.allocate("apibox"));

serverTracker.deallocate("apibox1");

System.out.println(serverTracker.allocate("apibox"));

System.out.println(serverTracker.allocate("apibox"));

System.out.println(serverTracker.allocate("sitebox"));

System.out.println(serverTracker.allocate("sitebox"));

System.out.println(serverTracker.allocate("sitebox"));

serverTracker.deallocate("sitebox2");

System.out.println(serverTracker.allocate("sitebox"));

}

}

- Diego August 01, 2019