Stripe Interview Question
Software EngineersCountry: 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