Question

Goldman Sachs | OA | Hackerrank | Set - 33

Answer 1

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

 

Answer 2

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()){
            if(ch == '8') stack.add(ch);
        }

        int nonEights = pool.length() / 11;

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

Answer 3

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;
}