Hackerrank The Full Couting Sort problem solution

Hackerrank The Full Couting Sort problem solution – In this Hackerrank The Full Counting Sort problem, use the counting sort to order a list of strings associated with integers. If two strings are associated with the same integer, they must be printed in their original order, i.e. your sorting algorithm should be stable. There is one other twist: strings in the first half of the array are to be replaced with the character - (dash, ascii 45 decimal).

Insertion Sort and the simple version of Quicksort are stable, but the faster in-place version of Quicksort is not since it scrambles around elements while sorting.

Design your counting sort to be stable.

Function Description

Complete the countSort function in the editor below. It should construct and print the sorted strings.

countSort has the following parameter(s):

• string arr[n][2]: each arr[i] is comprised of two strings, x and s

Returns
– Print the finished array with each element separated by a single space.

Hackerrank The Full Couting Sort problem solution in Python.

import collections

def tc(n, arr):
    d = collections.defaultdict(list)
    for i in range(n):
        k,v = arr[i].split()
        if i < n//2:
            d[int(k)].append("-")
        else:
            d[int(k)].append(v)
    od = collections.OrderedDict(sorted(d.items()))
    print(" ".join([" ".join(l) for l in od.values()]))

n = int(input())
arr = []
for _ in range(n):
    arr.append(input())
tc(n,arr)

The Full Couting Sort problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int entries = scanner.nextInt();
        StringBuilder[] freqs = new StringBuilder[100];
        for (int i = 0; i < entries; i++) {
            int idx = scanner.nextInt();
            if (i < entries / 2) {
                freqs[idx] = freqs[idx] == null ? new StringBuilder("-")
                                                : freqs[idx].append(" -");
                scanner.next();
            } else {
                freqs[idx] = freqs[idx] == null ? new StringBuilder(scanner.next()) 
                                                : freqs[idx].append(" ").append(scanner.next());
            }
        }
        for (int i = 0; i < freqs.length; i++) {
            if (freqs[i] != null) {
                System.out.print(freqs[i].toString());
                System.out.print(" ");
            }
        }
        System.out.println();
    }
    
    
}

Problem solution in C++ programming.

#include <cstdio>
#include <iostream>
#include <vector>
#define MAX 1000001

using namespace std;

int num;
vector<int> cnt[101];
string name[MAX];
int val[MAX];
int order[MAX];

int main(){
    cin >> num;
    int stop = num/2;
    int temp1;
    string temp2;
    for(int x = 0;x<num;x++){
        cin >> temp1 >> temp2;
        val[x] = temp1;
        name[x] = temp2;
        cnt[temp1].push_back(x);
    }
    for(int x = 0;x<100;x++){
        for(vector<int>::iterator it = cnt[x].begin();it!=cnt[x].end();++it){
            if((*it)<stop) cout << "- ";
            else cout << name[*it] << " ";
        }
    }

    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>

#define MAXN 1000000
#define MAXNUM 100
#define MAXSTR 10

int main() {
    
    long i, j, n, num[MAXN];
    static char str[MAXN/2][MAXSTR];
    scanf("%ld", &n);
    
    for ( i = 0; i < n/2; i++ ) {
        scanf("%ld", &num[i]);
        scanf("%*s");
    }
    
    for ( i = n/2; i < n; i++ ) {
        scanf("%ld", &num[i]);
        scanf("%s", str[i-n/2]);
    }
    
    for ( i = 0; i < MAXNUM; i++ ) {
        for ( j = 0; j < n/2; j++ ) {
            if ( num[j] == i ) {
                printf("- ");
            }
        }
        for ( j = n/2; j < n; j++ ) {
            if ( num[j] == i ) {
                printf("%s ", str[j-n/2]);
            }
        }
    }
    
    return 0;
}

Problem solution in JavaScript programming.

function processData(input) {
    //Enter your code here
    var ar = input.split('n');
    var n = parseInt(ar.shift(), 10);
    var sorted = {}
    for(var i = 0; i < n; i++) {
        var space = ar[i].indexOf(' ');
        var pos = parseInt(ar[i].substr(0, space), 10);
        var chars = i < n/2 ? '-' : ar[i].substr(space + 1);
        sorted[pos] = (sorted[pos] || []);
        sorted[pos].push(chars);
    }
    var out = []
    for(key in sorted)
        out.push(sorted[key].join(' '));
    console.log(out.join(' '));
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});