Amazon Interview Question
Country: United States
public static void main(String[] args) {
String s1 = "fghab";
String s2 = "abfmgfghnaixcv";
String remainder = "";
String result="";
int i=0;
Hashtable<Character,Integer> h = new Hashtable<Character,Integer>();
for(i=0;i<s1.length();i++) {
h.put(s1.charAt(i), 0 );
}
for(i=0;i<s2.length();i++) {
if(h.containsKey(s2.charAt(i))) {
int count = h.get(s2.charAt(i));
h.put(s2.charAt(i), count+1);
}
else {
remainder+=s2.charAt(i);
}
}
for(i=0;i<s1.length();i++) {
int count = h.get(s1.charAt(i));
for(int j=0;j<count;j++) {
result+=s1.charAt(i);
}
}
result+=remainder;
System.out.println(result);
}
#include<stdio.h>
int main()
{
char *string s1="fghab";
char * string s2="abfmgfghnaixcv"
int count[26];
int i;
for(i=0;i<strlen(s2);i++)
count[s2[i]-'a']++;
int j=0;
int temp;
for(i=0;i<strlen(s1);i++){
temp=count[s1[i]-'a'];
if(temp)
while(temp){
s2[j++]=s1[i];
temp--;
}
}
s2[j]='\0';
0
of 0 vote
#include<stdio.h>
int main()
{
char *string s1="fghab";
char * string s2="abfmgfghnaixcv"
int count[26];
int i;
for(i=0;i<strlen(s2);i++)
count[s2[i]-'a']++;
int j=0;
int temp;
for(i=0;i<strlen(s1);i++){
temp=count[s1[i]-'a'];
if(temp)
while(temp){
s2[j++]=s1[i];
temp--;
}
count[s[i]-'a']=0;
}
for(i=0;i<strlen(s2);i++){
temp=count[s2[i]-'a'];
if(temp)
while(temp){
s2[j++]=s2[i];
temp--;
}
count[s2[i]-'a']=0;
}
s2[j]='\0';
main()
{
char sam[]={"fghab"};
char obj[]={"abfmgfghnaixcv"};
char t, c;
int strlens = strlen(sam);
int strleno = strlen(obj);
int i,j, k=0;
for(i=0; i<strlens; i++)
{
t = sam[i];
for(j=k; j<strleno; j++)
{
if(obj[j] == t)
{
//exchange obj[j] and obj[k]
obj[j] = obj[k];
obj[k] = t;
k++;
}
}
}
printf("%s\n\r", obj);
}
1) create a lookup table for string of smaller size indicating the order of the character in the string, for other characters just add the order as int_max
in this case lookup table will be
arr[26]
in order = 0;
for each char x in s1
arr[121-(int)x] = order++;
2) perform a merge sort on the second array using the lookup table
Does the solution need to be made generic? If so, how are the lengths of input strings bound?
- Ben October 29, 2012If the pre-sorted string is always small in distinct letters relative to the string being sorted, insert is acceptable as other sorting algorithms suffer when most of the string is already 'sorted'.
Insert sort is also preferable for small strings in general. That is why it is one way to better performance of quicksort after a threshold of sub-string/array has been reached.
Observing letters not included in the sorting string do not change position related to one another, one solution is to use a new Character data object implementing comparable interface where f = 0, g = 1, h = 2, a = 3, b = 4, else = 99. Then use merge sort which is a 'stable' sort, preserving positions of 'equal' items relative to one another.