Hackerrank The Full Counting Sort Solution
.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
In this challenge you need to print the string that accompanies each integer in a list sorted by the integers. If two strings are associated with the same integer, they must be printed in their original order so your sorting algorithm should be stable. There is one other twist. The first half of the strings encountered in the inputs are to be replaced with the character "".
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.
In this challenge, you will use counting sort to sort a list while keeping the order of the strings preserved.
For example, if your inputs are you could set up a helper array with three empty arrays as elements. The following shows the insertions:i string converted list0 [[],[],[]]1 a - [[-],[],[]]2 b - [[-],[-],[]]3 c [[-,c],[-],[]]4 d [[-,c],[-,d],[]]
The result is then printed: .
Function Description
Complete the countSort function in the editor below. It should construct and print out the sorted strings.
countSort has the following parameter(s):
- arr: a 2D array where each arr[i] is comprised of two strings: x and s.
Note: The first element of each , , must be cast as an integer to perform the sort.
Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
The first line contains , the number of integer/string pairs in the array .
Each of the next contains and , the integers (as strings) with their associated strings.
Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
is even
consists of characters in the range
Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
Print the strings in their correct order, space-separated on one line.
Sample Input.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
20
0 ab
6 cd
0 ef
6 gh
4 ij
0 ab
6 cd
0 ef
6 gh
0 ij
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the
Sample Output.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
- - - - - to be or not to be - that is the question - - - -
Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
Below is the list in the correct order. In the array at the bottom, strings from the first half of the original array were replaced with dashes.
0 ab
0 ef
0 ab
0 ef
0 ij
0 to
1 be
1 or
2 not
2 to
3 be
4 ij
4 that
4 is
4 the
5 question
6 cd
6 gh
6 cd
6 gh
sorted = [['-', '-', '-', '-', '-', 'to'], ['be', 'or'], ['not', 'to'], ['be'], ['-', 'that', 'is', 'the'], ['question'], ['-', '-', '-', '-'], [], [], [], []]
Solution in java8
Approach 1.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuilder[] sb=new StringBuilder[100];
int n = in.nextInt();
int max=0;
// String newArr[]=new String[100];
for (int i = 0; i < sb.length; i++) {
sb[i] = new StringBuilder("");
}
for(int a0 = 0; a0 < n; a0++){
int x = in.nextInt();
if(x>max)
max=x;
String s = in.next();
if(a0<n/2)
s="-";
sb[x].append(s + " ");
}
for(int i=0;i<max+1;i++)
{
System.out.print(sb[i].toString());
}
in.close();
}
}
Approach 2.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.stream.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int x[] = new int[n];
String s[] = new String[n];
String l = "";
for(int a0 = 0; a0 < n; a0++){
x[a0] = in.nextInt();
l = in.next();
s[a0] = (a0 < n/2) ? "-" : l;
}
in.close();
printSolution (x, s);
}
static void printSolution (int[] positions, String[] labels) {
int maxX = 100;
StringBuffer[] result = IntStream.range(0, 100).mapToObj(StringBuffer::new).toArray(StringBuffer[]::new);
for (int i=0; i<positions.length; i++) {
result[positions[i]].append (labels[i] + " ");
}
System.out.println(Stream.of(result).map(x -> x.toString()).collect(Collectors.joining()));
}
}
Approach 3.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) throws IOException {
final int maxValue = 100;
/* Create HashMap with empty "buckets" to put Strings into */
HashMap<Integer, ArrayList<String>> map = new HashMap<>(maxValue);
for (int i = 0; i < maxValue; i++) {
map.put(i, new ArrayList<String>());
}
/* Save input */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
String [] pair = br.readLine().split(" ");
int key = Integer.parseInt(pair[0]);
String value = (i < n/2) ? "-" : pair[1];
ArrayList<String> list = map.get(key);
list.add(value);
}
br.close();
/* Print output */
StringBuffer sb = new StringBuffer();
for (int i = 0; i < maxValue; i++) {
ArrayList<String> values = map.get(i);
for (String str : values) {
sb.append(str + " ");
}
}
System.out.println(sb);
}
}
Solution in python3
Approach 1.
#!/bin/python3
import sys
if __name__ == "__main__":
n = int(input().strip())
sort=[""]*100
for a0 in range(n):
x, s = input().strip().split(' ')
x, s = [int(x), str(s)]
if a0<n//2:
sort[x]+="- "
else:
sort[x]+=s+" "
print("".join(i for i in sort))Approach 2.
#!/bin/python3
import sys
if __name__ == "__main__":
n = int(input().strip())
helper =[[] for i in range(n)]
for a0 in range(n):
x, s = input().strip().split(' ')
x, s = [int(x), str(s)]
if a0 < n // 2:
helper[x].append('-')
else:
helper[x].append(s)
ret = ''
for arr in helper:
ret += ' '.join(arr) + ' '
print (ret)Approach 3.
#!/bin/python3
import sys
if __name__ == "__main__":
n = int(input().strip())
retList = []
for i in range(n):
retList.append([])
for i in range(n):
x, s = input().strip().split(' ')
x, s = [int(x), str(s)]
if i < n/2:
retList[x].append('-')
else:
retList[x].append(s)
prString = ''
for x in retList:
for i in x:
prString += i + " "
print(prString)Solution in cpp
Approach 1.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int N;
string s;
cin>>N;
vector<string> S(100);
for (int i=0;i<N;i++) {
int a;
cin>>a>>s;
if (i<(N/2)) s="-";
if (S[a].length()) S[a]=S[a]+" "+s; else S[a]=s;
}
string res;
for (int i=0;i<100;i++) res+=S[i]+" ";
printf("%s\n",res.c_str());
// cout<<res<<endl;
return 0;
}
Approach 2.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<string> counter[100];
int main() {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
int x; string s;
cin >> x >> s;
if (i < n / 2) {
counter[x].push_back("-");
} else {
counter[x].push_back(s);
}
}
for (int x = 0; x < 100; ++x) {
for (auto &s : counter[x]) {
cout << s << " ";
}
}
cout << endl;
return 0;
}
Approach 3.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin>>n;
vector<string> arr[100];
for(int i=0; i<n/2; i++){
int x;
string str;
cin>>x>>str;
arr[x].push_back("-");
}
for(int i=n/2; i<n; i++){
int x;
string str;
cin>>x>>str;
arr[x].push_back(str);
}
for(int i=0; i<100; i++){
//sort(arr[i].begin(),arr[i].end());
for(int j=0; j<arr[i].size(); j++)
cout<<arr[i][j]<<' ';
}
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}
