EMC Interview Question Java Developers
Country: India
Interview Type: In-Person
public static String reorderByPattern(String src, String pattern){
int [] dp = new int [26];
char [] chs = src.toCharArray();
for (int i = 0 ;i<chs.length ;++i){
dp[chs[i]-'a']++;
}
int j = 0;
for (int i = 0; i<pattern.length() ;++i){
int count = dp [pattern.charAt(i)-'a'];
if (count !=0){
for (int k = 0 ;k<count ;++k){
chs [j++] = pattern.charAt(i);
}
}
}
return new String(chs,0,j);
}}
This Java method will consider the characters that are repeated and then print them in sequential order. It does not consider the 'sorting' part, as it relies on HashTable and 'sorting' is not requirement per the question!
private void matchAlphaNumerals()
{
String input = "abdecadcszx";
//String input = "abcdefgh";
//String input = "aaaaaaaaaaa";
Hashtable<String, Integer> ht = new Hashtable<String, Integer>();
for(int i=0, len=input.length(); i<len; i++)
{
char ch = input.charAt(i);
if(ht.get(ch + "") != null)
{
Integer count = ht.get(ch + "");
ht.put(ch + "", new Integer(count.intValue() + 1));
}
else
ht.put(ch + "", new Integer(1));
}
Set<String> chars = ht.keySet();
StringBuffer sequencedOutput = new StringBuffer();
Iterator<String> it = chars.iterator();
while(it.hasNext())
{
String currentChar = it.next();
for(int i=0, count=ht.get(currentChar).intValue(); i<count; i++)
sequencedOutput.append(currentChar);
}
System.out.println(sequencedOutput);
}
Here is a solution with o(n) time complexity. Please correct me if I am making any mistake in complexity calculation.
public static void main(String[] args) {
String s="abdecadcbdaeaec";
class StringHolder
{
private String s="";
public StringHolder(char c) {
this.s=this.s+c;
}
public String getS() {
return s;
}
public void setS(String s) {
this.s = s;
}
public void addAnother()
{
this.s=this.s+s.charAt(0);
}
}
Map<Character, StringHolder> alphaMap=new LinkedHashMap<>();
for(char c:s.toCharArray())
{
if(!alphaMap.containsKey(c))
{
alphaMap.put(c, new StringHolder(c));
}
else
{
alphaMap.get(c).addAnother();
}
}
String result="";
for(char c:alphaMap.keySet())
{
result=result+alphaMap.get(c).getS();
}
System.out.print(result);
}
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class StringPattern {
public static void main(String[] args) {
String s ="abasjnabmzcmskciowecmsncjfgewtcjn";
TreeMap<Character, Integer> hmap = new TreeMap<>();
for(Character c : s.toCharArray()){
Integer freq=hmap.get(c);
if(freq==null){
freq=1;
}
hmap.put(c,freq+1);
}
StringBuffer sb = new StringBuffer();
for(Map.Entry<Character, Integer> m : hmap.entrySet()){
Character c1= m.getKey();
for(int i=0 ,count=hmap.get(c1).intValue();i<count;i++){
sb.append(m.getKey());
}
}
System.out.println(sb);
}
}
public class ShowPattern {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String input = in.nextLine();
TreeMap<Character, Integer> inputMap = new TreeMap<Character, Integer>();
Integer value;
for (int i = 0; i < input.length(); i++) {
value = inputMap.get(input.charAt(i));
if (value == null) {
value = 1;
}
inputMap.put(input.charAt(i), value + 1);
}
StringBuilder sb = new StringBuilder();
for (Map.Entry<Character, Integer> entry : inputMap.entrySet()) {
value = entry.getValue();
Character key = entry.getKey();
for (int i = 1; i < value; i++) {
sb.append(key);
}
}
System.out.println(sb);
}
}
String s="abde0cad2cbd9aeaec";
char[] test = s.toCharArray();
ArrayList al = new ArrayList<>();
for( char c: test){
al.add(c);
}
System.out.println("source string: "+al);
Collections.sort(al);
System.out.println("sorted string:"+al);
Output:
source string: [a, b, d, e, 0, c, a, d, 2, c, b, d, 9, a, e, a, e, c]
sorted string: [0, 2, 9, a, a, a, a, b, b, c, c, c, d, d, d, e, e, e]
Merge sort:
public static String arrangeLetters(String input){
char[] str = input.toCharArray();
sort(str);
return new String(str);
}
private static void sort(char[] a){
char[] aux = new char[a.length];
sort(a,aux,0,a.length-1);
}
private static void sort(char[] a,char[] aux, int lo,int hi){
if(lo>=hi) return;
int mid = lo + (hi-lo)/2;
sort(a,aux,lo,mid);
sort(a,aux,mid+1,hi);
merge(a,aux,lo,mid,hi);
}
private static void merge(char[] a, char[] aux, int lo, int mid, int hi) {
for(int i=lo;i<=hi;i++){
aux[i] = a[i];
}
int i=lo,j=mid+1;
for(int x=lo;x<=hi;x++){
if(j>hi) a[x] = aux[i++];
else if(i>mid) a[x] = aux[j++];
else if(aux[i]<aux[j]) a[x] = aux[i++];
else{
if(aux[i]=='\u0000') a[x] = aux[j++];
else if(aux[j]=='\u0000') a[x] = aux[i++];
else a[x] = aux[j++];
}
}
}
package BucketValues;
import java.util.TreeMap;
public class SortedKeys {
TreeMap<Character, Integer> m = new TreeMap<Character, Integer>();
public void BSort(String x) {
char[] chars = x.toCharArray();
Integer count = 0;
for(Character c: chars) {
count = m.get(c);
if(m.get(c) != null){
m.put(c, ++count);
}else{
m.put(c, 1);
}
}
}
public String getSorted(String x) {
BSort(x);
StringBuilder s = new StringBuilder();
Integer count =0;
for(Character c: m.keySet()){
count = m.get(c);
System.out.println(c + ""+count);
for(int i=0; i< count; i++) {
s.append(c);
}
s.append("--");
}
return s.toString();
}
public static void main(String[] args) {
SortedKeys s= new SortedKeys();
System.out.println(s.getSorted("aaaabbaa"));
}
}
import java.util.Map;
import java.util.TreeMap;
public class Sequence {
public static void main(String[] args) {
String str = "abfddaaccffb";
char[] charMap = str.toCharArray();
Map<String,Integer> map = new TreeMap<String, Integer>();
Map<String,StringBuffer> newMap = new TreeMap<String, StringBuffer>();
for(int i =0; i < charMap.length; i++){
if(map.containsKey(Character.toString(charMap[i]))){
Integer val = map.get(Character.toString(charMap[i]));
map.put(Character.toString(charMap[i]), new Integer(val +1));
}else{
map.put(Character.toString(charMap[i]), 1);
}
}
for(Map.Entry<String, Integer> entry : map.entrySet()){
StringBuffer strBuff = new StringBuffer();
for(int j = 0; j < entry.getValue()-1;j++){
strBuff = strBuff.append(new StringBuffer(entry.getKey())) ;
}
newMap.put(entry.getKey(), strBuff);
// System.out.print(entry.getKey()+entry.getValue());
}
for(Map.Entry<String, StringBuffer> entry : newMap.entrySet()){
System.out.print(entry.getKey()+entry.getValue());
}
}
}
public String sortString(String str){
int[] counts = new int[26];
for(int i=0;i<str.length();i++){
char c = str.charAt(i);
counts[c-'a']++;
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<counts.length;i++){
for(int j=0;j<counts[i];j++){
sb.append((char)('a'+i));
}
}
return new String(sb);
}
public String sortString(String str){
int[] counts = new int[26];
for(int i=0;i<str.length();i++){
char c = str.charAt(i);
counts[c-'a']++;
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<counts.length;i++){
for(int j=0;j<counts[i];j++){
sb.append((char)('a'+i));
}
}
return new String(sb);
}
This piece of code will arrange all ASCII characters together in increasing order. I think this is what the question is about.
- Coder December 28, 2013int arr[255]; char *str = "aadkfskfjsknvnskdfababal234jklfabfblafadfkj"; int i=0,j; for(i=0;i<255;i++) arr[i]=0; i=0; while(*str != '\0'){ arr[*str]++; str++; } for(i=0;i<255;i++){ for(j=0;j<arr[i];j++){ printf("%c",i); } }