Google Interview Question Developer Program Engineers
not seems a nice solution. it has lot of limitation. What if 1st string is like "carcar"? You assume there is only 1 occurrence of each char of string 2 in string 1 ! It could be also possible string1 could be "ca" (no 'r').
"You assume there is only 1 occurrence of each char of string 2 in string 1"
-> Not at all. I am initializing all elements of hash array as zero and for each occurrence of an alphabet in string1 i am INCREMENTING corresponding index of hash by 1 (i am not marking it as 1 but incrementing by 1). in example string1, 'r' occurs twice so my corresponding hash index hash['r'-'a'] would be 2. after i delete one occurrence of 'r' from string2 (car) there would still remain one 'r' in hash array.
void reorderString (char* pStr1, char* pStr2)
{
int hash[256]={0};
int i;
for(i=0;i<strlen(pStr1);i++)
{
hash[pStr1[i]] += 1;
}
for(i=0;i<strlen(pStr2);i++)
{
if(hash[pStr2[i]]>0)
{
while(hash[pStr2[i]]>0)
{
putchar(pStr2[i]);
hash[pStr2[i]] -= 1;
}
}
else
{
putchar(pStr2[i]);
}
}
for(i=0;i<strlen(pStr1);i++)
{
while(hash[pStr1[i]]>0)
{
putchar(pStr1[i]);
hash[pStr1[i]] -= 1;
}
}
printf("\n");
}
int main()
{
char str1[100];
char str2[100];
gets(str1);
gets(str2);
reorderString(str1,str2);
return 0;
}
We don't need java to do that.
Just use a different comparison function.
Make an array of size 26
h[c - 97] = 1
h[a - 97] = 2
h[r - 97] = 3
h[everything else] = 0
Now sort first string using this array
Instead of str[i] < str[j], do h[str[i]] < h[str[j]]
<pre lang="" line="1" title="CodeMonkey47969" class="run-this">static char order[26];
int strcomp(const void* d1, const void* d2)
{
char *p1 = (char*)d1;
char *p2 = (char*)d2;
if (order[*p1%26] < order[*p2%26])
return -1;
else if (order[*p1%26] == order[*p2%26])
return 0;
else
return 1;
}
int newSortStr(char *bStr, char *oStr)
{
if (NULL == bStr || NULL == oStr)
return -1;
char *pstr = oStr;
int i = 0;
memset(order,26,26);
while (*pstr) order[*pstr++%26] = i++;
qsort(bStr,strlen(bStr),1,strcomp);
return 0;
}
</pre><pre title="CodeMonkey47969" input="yes">
</pre>
#include"queue"
#include <hash_map>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
using namespace stdext;
hash_map<char, int> m_dic;
bool mycomp(char x,char y)
{
return m_dic[x]<m_dic[y];
}
int main(){
freopen("in.txt", "r", stdin);
string mstr;
string mdic;
while(cin>>mstr)
{
cin>>mdic;
for(int i=0;i<26;i++)
{
m_dic['a'+i]=30;
}
for(int i=0;i<mdic.size();i++)
{
m_dic[mdic[i]]=i;
}
std::sort(mstr.begin(),mstr.end(),mycomp);
}
cout<<mstr<<endl;
return 0;
}
Logic in java but valid for every language:
1.Create a compare function that maps the characters on base to the index it appears. You can use a map to do this. For other characters you can offset then by the map size or put Integer.MAX_VALUE.
2.Use comparator with the sort method of your choice
Comparator code:
private static class StringBasedSort implements Comparator<Character> {
private Map<Character, Integer> baseMap = new HashMap<Character, Integer>();
public StringBasedSort(String base) {
for (int i=0; i<base.length();++i) {
if (!baseMap.containsKey(base.charAt(i))) {
baseMap.put(base.charAt(i), i);
}
}
}
@Override
public int compare(Character o1, Character o2) {
Integer val1 = baseMap.get(o1);
if (val1 == null)
val1 = (int)o1 + baseMap.size();
Integer val2 = baseMap.get(o2);
if (val2 == null)
val2 = (int)o2 + baseMap.size();
return val1.compareTo(val2);
}
}
Test code:
public static String sortStr1BasedStr2(String strToSort, String base) {
Comparator<Character> cmp = new StringBasedSort(base);
Character[] chrToSort = toCharacterArray(strToSort);
Arrays.sort(chrToSort, cmp);
return toString(chrToSort);
}
// utilitary functions
private static Character[] toCharacterArray(String str) {
char[] tmp = str.toCharArray();
Character[] array = new Character[tmp.length];
for (int i=0; i<tmp.length;++i) {
array[i] = tmp[i];
}
return array;
}
private static String toString(Character[] array) {
char[] tmp = new char[array.length];
for (int i=0; i<tmp.length;++i) {
tmp[i] = array[i];
}
return new String(tmp);
}
I may not be seeing everything here, please let me know if i am
I am thinking that an insertion sort type solution where each character in string 2 is used to find a match in string 1 and swap the match into the next most important position.
int j=0;
int next = 0;
while(next<n && j<m){ //where n is the length of string 1 and m is the length of string 2
for(int i=next; i<n; i++){
if(string1[i] == string2[j]){
if(i != next){
swap(string1, i, next);
}
next++;
}
j++
}
}
if i understood 'reordering' concept of this question..
assuming all letters are small.
1) hash[26] = {0};
2) hash 1st string as:
i = 0; while(string1[i]) hash[string1[i] - 'a']++, i++;3) for each letter in string2, print it and decrease from hash this way
i = 0; while(string2[i]) hash[string2[i] - 'a']--, i++;4) for remaining letters in hash table, print any permutation. for best complexity just print the hash array from beginning to end.
- someone June 29, 2011