In this HackerRank Reverse shuffle merge interview preparation kit problem, You need to complete the reverseShuffleMerge function.
Problem solution in Python programming.
#!/bin/python3 import math import os import random import re import sys from collections import Counter # Complete the reverseShuffleMerge function below. def reverseShuffleMerge(s): s = list(reversed(s)) remaining_dict,required_dict,added_dict = {},{},{} for c in s: if c not in remaining_dict: remaining_dict[c]=1 else: remaining_dict[c]+=1 for key,value in remaining_dict.items(): required_dict[key] = value // 2 added_dict[key] = 0 char_list=[] index = 0 min_index = 0 min_char = '|' while index < len(s): char = s[index] if required_dict[char]>added_dict[char]: if char < min_char: min_char = char min_index = index if remaining_dict[char]-1<required_dict[char]-added_dict[char]: while index>min_index: index-=1 char = s[index] remaining_dict[char]+=1 added_dict[char]+=1 char_list.append(char) min_char = '|' remaining_dict[char]-=1 index+=1 return "".join(char_list) if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') s = input() result = reverseShuffleMerge(s) fptr.write(result + 'n') fptr.close()
Problem solution in Java Programming.
import java.io.*; import java.util.*; public class Solution { static public class CharData { int total; int skipped; int taken; boolean hasToTake(){ return 2*skipped == total; } boolean hasToSkip(){ return 2*taken == total; } void putBack(){ taken--; skipped++; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = new StringBuilder(in.nextLine()).reverse().toString(); CharData cd[] = new CharData['z' - 'a' + 1]; for(int i=0;i<cd.length;i++){ cd[i]=new CharData(); } for (int i = 0; i < s.length(); i++) { cd[s.charAt(i)-'a'].total++; } char [] r = new char[s.length()/2]; int ri=0; for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); CharData di = cd[ch-'a']; if(di.hasToSkip()){ di.skipped++; }else { while(ri>0 && r[ri-1]>ch && !cd[r[ri-1]-'a'].hasToTake()){ cd[r[--ri]-'a'].putBack(); } r[ri++]=ch; di.taken++; } } System.out.println(new String(r)); in.close(); } }
Problem solution in C++ programming.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <cstring> using namespace std; char in[10005]; int L[128]; int need[128]; char ans[10005]; int ansPos; using namespace std; int main() { scanf("%s", in); for(int i=0; in[i]; ++i){ ++L[in[i]]; } int len=strlen(in); for(int j=0; j < 128; ++j) need[j]=L[j]/2; int pos=len-1; while(ansPos < len/2){ bool init=0; char best; int ind, i; for(i=pos; i >= 0; --i){ if((!init || in[i] < best) && need[in[i]]){ init=1; best=in[i]; ind=i; } L[in[i]]--; if(L[in[i]] < need[in[i]]) break; } for(; i < ind; ++i){ ++L[in[i]]; } --need[best]; ans[ansPos++]=best; pos=ind-1; } printf("%s", ans); return 0; }
Problem solution in C programming.
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> void reverse(char* s,char *rev,int len){ int i=len-1,j=0; while(i>=0){ rev[j++] = s[i]; i--; } rev[j] = ' '; } int find_occ(char *s, char match, int beg, int end){ int i; for(i=beg;i<=end;i++){ if(s[i]==match){ return i; } } return -1; } int next_min(int arr[], int n, int count){ int i; for(i=0;i<n;i++){ if(arr[i]>0 && count==0){ return i; } else if(arr[i]>0){ count--; } } return -1; } int subseq(char *s, int freq[], int beg, int end){ int i; for(i=beg;i<=end;i++){ freq[s[i]-97]--; } for(i=0;i<26;i++){ if(freq[i]>0){ return 0; } } return 1; } int main() { char s[10001],rev[10001],a[10001]; scanf("%s",s); int i,len = strlen(s), freq[26]; reverse(s,rev,len); for(i=0;i<len;i++){ freq[s[i]-97]++; } for(i=0;i<26;i++){ freq[i] /=2; } int beg = 0,counter =0,next=0; while(counter<len/2){ char candidate_char = next_min(freq,26,next)+97; int pos = find_occ(rev,candidate_char,beg,len-1); // copy freq_arr int freq_copy[26]; for(i=0;i<26;i++){ freq_copy[i] = freq[i]; } freq_copy[candidate_char-97]--; int satisfy = subseq(rev,freq_copy,pos+1,len-1); if(satisfy){ a[counter++] = candidate_char; freq[candidate_char-97]--; next = 0; beg = pos+1; // printf("str is"); // int k; // for(k=0;k<counter;k++) // {printf("%c",a[k]); // } // printf("n"); } else{ next++; } } a[counter] = ' '; printf("%s",a); return 0; }
Problem solution in JavaScript programming.
function getPos(a, v, c) { var p={}, i, max=-1; for ( var k in c ) { for ( i=0; i<a.length; ++i ) { if ( a[i]==k && v[i]==c[k] ) { if ( max<(p[k]=i) ) max=i; break; } } } return {max:max, pos:p}; } function smallest(a, i, end, c) { var min = 'z', pos=-1; for (;i<end;++i) { if ( c[a[i]]==null ) continue; if ( min>=a[i]) min=a[pos=i]; } return {elm:min, pos:pos}; } function processData(input) { var a = input.split(''), i, j, n=a.length, cD={}, c={}, v=[], p, r=[]; for ( i=0; i<n; ++i ) { if ( cD[a[i]]==null ) v.push(cD[a[i]] = 1); else v.push(++cD[a[i]]); } for ( var k in cD ) { c[k] = cD[k]/2; } //console.log(input); var end = a.length; p = getPos(a, v, c); //console.log( 'v',v, 'c',c, 'p',p, 'r',r); for ( i=p.max; i>=0; ) { var s = smallest(a, i, end, c); //console.log( 'i',i, 'end',end, 's',s); r.unshift(s.elm); if ( c[s.elm]<=1 ) delete c[s.elm]; else --c[s.elm]; end = s.pos; p = getPos(a, v, c); i = p.max; //console.log( 'v',v, 'i',i, 'c',c, 'p',p, 'r',r); if ( p.max == -1 ) break; } console.log(r.reverse().join('')); } process.stdin.resume(); process.stdin.setEncoding("ascii"); _input = ""; process.stdin.on("data", function (input) { _input += input; }); process.stdin.on("end", function () { processData(_input); });