0 like 0 dislike
1,366 views
| 1,366 views

0 like 0 dislike

Hackerrank OA 2 questions 120 min

1. Tag Identification Number
You're given a string containing a list of digits. You must make as many IDs of the format 8xxxxxxxxxx (an 8 followed by 10 digits) as possible. Return the number of IDs you can make. The IDs do not have to be unique, and you may rearrange the digits, but you may only use each digit once.
``````def numOfIds(pool):
s = len(pool)/11
c = 0
for i in range(0,len(pool)):
if pool[i] == '8':
c+=1
return min(c, int(s))
``````
1. Inversion is a strictly decreasing subsequence of length 3. More formally, given an array, p, an inversion in the array is any time some p[i] > p[j] > p[k] and i < j < k. Given an array of length n, find the number of inversions.
Example:
n = 5, arr = [5, 3, 4, 2, 1]
Array inversions are [5, 3, 2], [5,3,1], [5,4,2], [5,4,1], [5,2,1], [3,2,1], [4,2,1]
n = 4, arr = [4,2,2,1]
The only inversion is [4,2,1] and we do not count the duplicate inversion.

Solution in O(n)^2
NOTE: Only 10/12 test cases passed

``````def getInvCount(arr):
c = 0
for i in range(1,n-1):
r = 0
for j in range(i+1 ,n):
if (arr[i] > arr[j]):
r+=1
l = 0;
for j in range(i-1,-1,-1): #Tricky remember
if (arr[i] < arr[j]):
l+=1
c += int(l*r)

return c
``````

by Expert (111,350 points)
0 like 0 dislike

My accepted solution for first question

``````public static int numOfIds(String pool) {
if(pool.length() < 11) return 0;

Stack<Character> stack = new Stack<>();

for(char ch : pool.toCharArray()){
}

int nonEights = pool.length() / 11;

if(stack.isEmpty()) return 0;
else if(stack.size() > nonEights) return nonEights;

return stack.size();
}``````
by Expert (111,350 points)
0 like 0 dislike

The second solution can be done in `O(nlgn)` time using a merge sort technique. Below is the code

``````[#include](https://leetcode.com/problems/minimum-interval-to-include-each-query) <bits/stdc++.h>
using namespace std;

int inv;

vector<int>merge_cnt(vector<int>a, vector<int>b){
if(a.empty())return b;
if(b.empty())return a;
int n = (int)a.size();
int m = (int)b.size();
a.push_back(INT_MAX);
b.push_back(INT_MAX);
int i = 0, j = 0;
vector<int>fin;

while(i<n || j<m){
if(a[i]<=b[j]){
fin.push_back(a[i]);
++i;
}else{

inv += n-i;
fin.push_back(b[j]);
++j;
}
}
return fin;
}

vector<int> merge_sort(vector<int>a){
if(a.empty())return {};

int n = (int)a.size();
if(n == 1 )return a;

vector<int>left, right;
for(int i = 0; i<(n+1)/2; ++i){
left.push_back(a[i]);
}
for(int i = (n+1)/2; i<n; ++i){
right.push_back(a[i]);
}
left = merge_sort(left);
right = merge_sort(right);
// how to check if this is the first call?
auto ans = merge_cnt(left, right);
return ans;
}

int main() {
vector<int>a = {5, 6, 7, 1, 2, 3};
// a = { 1, 20, 6, 4, 5 };
a = merge_sort(a);
for(auto&it:a)cout<<it<<" ";
cout<<"\n";

cout<<"Inversion = "<<inv<<endl;
cout<<"\n";
return 0;
}``````
by Expert (111,350 points)