Adobe Interview Question
Software EngineersCountry: India
Interview Type: In-Person
Use a hashmap:
-the key is a character; the value is a boolean.
-iterate through the second string and insert each character into the map, assigning it a value of false. If the character is already in the map, ignore it.
-iterate through the first string and check to see if all of its characters exist in the map. If a character exists in the map change the value to 'true'. If it doesn't, keep it false.
-iterate through the map and print all the characters with a value of 'false'
your output missing 'n' as well.
however easy way to do this is put the first string in a hash-table (char by char) and then loop over the chars of the second string to determine whether they are in the hashtable or not O(1) for every char so that makes the total of about O(n+m) i believe. where n is string1 length and m is string2 length.
#include <stdio.h>
#include <string.h>
int found(char c,char *x)
{
int i =0;
for(i=0;i<strlen(x);i++){
if(c == x[i]){
return 1;
}
}
return -1;
}
void print_char(char *x,char *y)
{
int i = 0;
for(i=0;i<strlen(y);i++){
if(found(y[i],x) != 1){
printf("%c",y[i]);
}
}
printf("\n");
}
int main()
{
char x[50] , y[50];
scanf("%s",x);
scanf("%s",y);
print_char(x,y);
return 0;
}
#include <stdio.h>
#include <string.h>
int found(char c,char *x)
{
int i =0;
for(i=0;i<strlen(x);i++){
if(c == x[i]){
return 1;
}
}
return -1;
}
void print_char(char *x,char *y)
{
int i = 0;
for(i=0;i<strlen(y);i++){
if(found(y[i],x) != 1){
printf("%c",y[i]);
}
}
printf("\n");
}
int main()
{
char x[50] , y[50];
scanf("%s",x);
scanf("%s",y);
print_char(x,y);
return 0;
}
In this question, we must first convert second string into a set of characters so that we only check for a characters presence in first string only once. Below is code which does so,
import collections
def printNotInFirstStr(str1, str2):
# remove duplicate characters from str2
x = collections.OrderedDict.fromkeys(list(str2))
for i in x:
if i[0] not in str1:
print(i[0])
>>> x = "apple"
>>> y = "aeroplane"
>>>
>>> printNotInFirstStr(x, y)
r
o
n
Similar logic can be coded in C, with some more code for creating a kind of set or map.
- revanth October 26, 2015