Palantir Technology Interview Question
Software Engineer / DevelopersCountry: United States
Can be done using hash map or can count the characters
//Assumption only small letters are given
#include <iostream>
using namespace std;
class sort_linear {
public :
sort_linear(char *source,char *dest);
void hash_map_create();
void sort_dest();
void print();
private:
char hash_array[26];
char *source_str;
char *dest_str;
};
sort_linear::sort_linear(char *source,char *dest)
{
source_str = source;
dest_str = dest;
for(int i=0;i<26;i++)
{
hash_array[i] = 0;
}
}
void sort_linear::hash_map_create(void)
{
char *temp = source_str;
while(*temp != '\0')
{
hash_array[*temp - 97] = hash_array[*temp - 97] + 1;
temp++;
}
}
void sort_linear::sort_dest(void)
{
char *temp = dest_str;
char *start = source_str;
int key;
int value,i;
while(*temp != '\0')
{
key = *temp - 97;
value = hash_array[key];
for(i=0;i<value;i++)
{
*start = (char)(key + 97);
start++;
}
hash_array[key] = 0;
temp++;
}
for(i=0;i<26;i++)
{
if(hash_array[i] != 0)
{
for(int j =0;j<hash_array[i];j++)
{
*start = (char)(i+97);
start++;
}
}
}
*start = '\0';
}
void sort_linear::print()
{
char *temp = source_str;
while(*temp != '\0')
{
cout<<*temp;
temp++;
}
return;
}
int main()
{
char source[] = "darek";
char dest[] = "rek";
sort_linear obj(source,dest);
obj.hash_map_create();
obj.sort_dest();
obj.print();
return 0;
}
It is assumed that all letters from the first word are in the second one.
public class Main {
public static void main(String[] args) {
String firstWord = "ThisWord";
String secondWord = "drowSiht";
Map<Character, Integer> orderMap = buildOrderMap(firstWord);
Set<CharWrapper> sortedWord = buildSortedWord(secondWord, orderMap);
System.out.println(sortedWord);
}
private static Map<Character, Integer> buildOrderMap(String word) {
Map<Character, Integer> resultMap = new HashMap<Character, Integer>();
int order = 0;
for (char c : word.toLowerCase().toCharArray()) {
resultMap.put(c, order++);
}
return resultMap;
}
private static Set<CharWrapper> buildSortedWord(String word, Map<Character, Integer> orderMap) {
Set<CharWrapper> result = new TreeSet<CharWrapper>();
for (char c : word.toLowerCase().toCharArray()) {
result.add(new CharWrapper(c, orderMap.get(c)));
}
return result;
}
private static class CharWrapper implements Comparable<CharWrapper> {
private char letter;
private int orderNum;
public CharWrapper(char letter, int orderNum) {
this.letter = letter;
this.orderNum = orderNum;
}
public char getLetter() {
return letter;
}
public int getOrderNum() {
return orderNum;
}
@Override
public int compareTo(CharWrapper charWrapper) {
return this.getOrderNum() - charWrapper.getOrderNum();
}
@Override
public String toString() {
return getLetter() + "";
}
}
}
I think I have a simple solution:
public String sortByString(String input, String sortBy) {
if (input == null)
return "";//Maybe throw exception here?
if (sortBy == null)
return "";//Maybe throw exception
HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
String stringToReturn = "";
for (int i = 0; i < input.length(); i++) {
if (hashMap.get(input[i]))//already in so increment the value
hashMap.put(input[i], hashMap.get(input[i]) + 1);
else
hashMap.put(input[i], 1);
}
for (int i = 0; i < sortBy.length(); i++) {
if (hashSet.get(sortBy[i]))
for (int j = 0; j < hashSet.get(sortBy[i]); j++)
stringToReturn += sortBy[i];
}
return stringToReturn;
}
For the first word, build the count array by scanning left to right and incrementing values.
Now start with the first char of the word according to which we need to order. For every char print it as many times as its corresponding value in count array.
#include<stdio.h>
#include<stdlib.h>
int main()
{
//order str2 according to ordering in str1
char* str1="badc",*str2="abcddb";
int i=0;
int* count=(int*)calloc(26,sizeof(int));
while(str2[i]!='\0')
{
count[str2[i]-97]++;
i++;
}
i=0;
while(str1[i]!='\0')
{
int j=count[str1[i]-97];
while(j>0)
{
printf("%c",str1[i]); j--;
}
i++;
}
return 0;
}
1. Build a linked hash map with the order definition with key as the letter, 0 as the value
- Jie July 22, 20132. scan the word, increase the value for every letter
3. re-scan the hash, output every letter with the frequency of value
A little improvement (if the letters scope can be determined), use an array as the linked hash map implementation.