Amazon Interview Question
Software Engineer / Developers@Sathya: good solution. I suggest you creating an account so that if you want to make any changes later you could, because I saw some of your solutions that you corrected later. also, use
before the code and
after the code. this keeps it formatted.like below:
//Code here
//format stays as specified inside these braces
There has to be a check for capital letters
the above code would fail for capital letters
also cases like
ABCD bcda would not be considered
better to S1[i]-'A' and then check if its greater than equal to 32,
if it is then subract 32
@Sathya, What about whitespace? you havent considered that.
I think the following code should work
int i =0 , j =0;
while( i < s1.length || j < s2.length) {
if(s1[i] != ' ' && i < s1.length)
a[s1[i++] - 'a']--;
if(s2[j] != ' ' && j < s2.length)
a[s2[j++] - 'a']++;
}
for i=0 to 25{
if a[i]!=0
return false
}
return true
This is working for all cases ( upper case , lower case and spaces)
boolean isAnagram(String s1, String s2) {
if(s1.length()!=s2.length()){
return false;
}
char c1[] = s1.toCharArray();
char c2[] = s2.toCharArray();
int i =0 , j =0;
int a[] = new int[26];
while( i < c1.length || j < c2.length) {
int x = c1[i]-'A';
int y = c2[j]-'A';
if(x > 31){
x =x - 32;
}
if( y > 31){
y = y-32;
}
if(i < c1.length && c1[i] != ' ' ){
a[x]--;
}
if(j < c2.length && c2[j] != ' ' ){
a[y]++;
}
i++;
j++;
}
for (i=0; i<25;i++){
if (a[i]!=0)
return false;
}
return true;
}
Can someone please explain this in plain english. I tried to compile the above program for a single string in Java
It gives me 0
0
0
public class charcheck {
public static void main(String args[]){
char[] ch={'s','u','r'};
int c;
int[] abc;
abc= new int[26];
for(int i=0;i<3;i++)
{
System.out.println(abc[ch[i]-'a']--);
}
}
}
C++
int main(){
string s1,s2; int a=0;
cout<<"Enter first string: ";cin>>s1;
cout<<"Next: ";cin>>s2;
if (s1.length()!=s2.length()){
cout<<"Strings are of different length";
}
else{
for (int i=0; i<s1.length();i++){
a+= (int)s1[i]-(int)s2[i];
}
if ((a==0)||(a%32==0))
{cout<<"anagram";}
else{
cout<<"not anagram";
}
}
}
search s1 in s2+s2, if its there then they are anagrams
s1 = hello
s2 = llohe
s2+s2 = llohellohe (it has hello)
Ch.v.suresh:
Followed program generated permutations of string ... compare with other string whether its anagram are not.
#include <stdio.h>
#include <string.h>
#define NULL 0
#define MAX_SIZE 5050
static temp_out_pos = 0;
void permutations(char str[],char inital[],char *out[MAX_SIZE],int len,int *out_pos);
int main()
{
char str[MAX_SIZE];
char *out[MAX_SIZE];
int len = 0;
int i =0,out_pos = 0;
while(1)
{
printf("\nEnter input: ");
out_pos = 0; temp_out_pos = 0;
gets(str);
if(strcmp(str,"0")==0)
break;
for(i=0;i<MAX_SIZE;i++)
{
out[i] = (char*) malloc(MAX_SIZE);
memset(out[i],0x0,MAX_SIZE);
}
len = strlen(str);
permutations(str,NULL,out,len,&out_pos);
for(i=0;i<MAX_SIZE;i++)
{
if(out[i][0] != '\0')
puts(out[i]);
else
break;
}
printf("\nTotal permutation = %d\n",temp_out_pos);
for(i=0;i<MAX_SIZE;i++)
free(out[i]);
}
return 0;
}
void permutations(char str[],char inital[],char *out[MAX_SIZE],int len,int *out_pos)
{
int i=0;
char res[10][10];
char ch;
int from =0;
for(i=0;i<strlen(str);i++)
{
ch = str[0];
str[0] = str[i];
str[i] = ch;
strcpy(res[i],str);
}
for(i=0;i<strlen(str);i++)
{
char temp_inital[2];
char temp_str[10];
char temp_out[10];
int k=0;
temp_inital[0] = res[i][0];temp_inital[1] = '\0';
strcpy(temp_str,res[i]);
from = temp_out_pos;
if(len > 1)
permutations(temp_str+1,temp_
inital,out,len-1,out_pos);
if(len == 1)
{
*out_pos = temp_out_pos;
temp_out_pos++;
}
for(k=from;k<=*out_pos;k++)
{
strcpy(temp_out,temp_inital);
strcat(temp_out,out[k]);
strcpy(out[k],temp_out);
}
}
}
Use a HashMap to store chars in string A. (increment count for duplicates).Then compare each char in string B with HashMap (decrement count each time a match is found.) If all chars are found . then return true else false
//I THINK THIS ONE WILL WORK FINE FOR ALL ABOVE CASES, PLZ LET ME KNOW IF THERE'S //SOME DEMERITS
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
int i,j,len1,len2;
char s1[10],s2[10];
clrscr();
printf("\n\n\t\tENTER THE FIRST STRING : ");
scanf("%s",s1);
printf("\n\n\t\tENTER THE SECOND STRING : ");
scanf("%s",s2);
len1 = strlen(s1);
len2 = strlen(s2);
if(len1 != len2)
{
printf("\n\n\t\tNOT AN ANAGRAM !!!");
getch();
return 0;
}
for(i = 0;s1[i] != '\0';i++)
{
for(j = 0;s2[j] != '\0';j++)
if(s1[i] == s2[j])
{
s2[j] = ' ';
break;
}
if(j >= len2)
{
printf("\n\n\t\tNOT AN ANAGRAM !!!");
getch();
return 0;
}
}
printf("\n\n\t\tFOUND TO BE AN ANAGRAM !!!");
getch();
return 0;
}
Make an account at CC and whenever u post code use 3 open curly braces before code and 3 closed curly braces after the code to keep it formatted
Code works perfectly for lower case letters...But when it encounters a Capital ltter it does NOT work..
I guess while comparing the the two strings S1 and S2 we need to make it to lower case first
tolower (s1[i])==tolower (s2[i])
i dont Know Bout C but it definetly works for C++
BTW its a nice Simple Code..
#include <stdio.h>
#include <stdlib.h>
int main()
{
char s1[]={ "utHurajm"};
char s2[]={ "uumtaHrj"};
int n1,n2;
n1=n2=0;
int i=0;
while(s1[i++])
{
n1+=s1[i];
}
i=0;
while(s2[i++])
{
n2+=s1[i];
}
if(n1==n2)
printf("anagarams\n");
else
printf("not anagrams\n");
return 0;
}
This is much more efficient and less comparisons than any of the above solutions
Hi sameer,
u can optimize the code..
bool anagram3(char *a , char *b)
{
int n1 = 0 , n2 = 0;
while(*a && *b)
{
n1 += *a++;
n2 += *b++;
}
if(n1 == n2)
return 1;
else
return 0;
}
An easy implementation in perl:
sub check_anagrams
{
my $str1 = shift;
my $str2 = shift;
if (length($str) != length($input))
{
print "not anagrams";
return;
}
my @original = split(//, $str);
foreach(@original)
{
$input =~ s/$_//;
}
if (length($input) == 0)
{
print "anagrams\n";
}
else
{
print "not anagrams\n";
}
}
Handling whitespace, upper, and lower case characters.
#include <iostream>
#include <string.h>
// 122 is 'z'
#define MAX_NUM_IDXS 122
using namespace std;
bool isanagram(const char*, const char*);
int main() {
const char* s1 = "abCdef";
const char* s2 = "FeCdba";
if(isanagram(s1,s2) == 1)
cout << "TRUE\n";
else
cout << "FALSE\n";
return 0;
}
bool isanagram(const char* s1, const char* s2) {
if(s1 == NULL && s2 == NULL)
return true;
if(s1 == NULL || s2 == NULL || strlen(s1) != strlen(s2))
return false;
int arr[MAX_NUM_IDXS] = {0};
for(unsigned int i = 0; i < strlen(s1); ++i) {
arr[(int)s1[i]]++;
arr[(int)s2[i]]--;
}
for(int i = 0; i < MAX_NUM_IDXS; ++i) {
if(arr[i] == 1) return false;
}
return true;
}
Here is an Objective-C variant
int main(int argc, char *argv[]) {
@autoreleasepool {
NSString *input = @"abcdefabxa0001";
NSString *target = @"1cabdefabxa000";
if (input.length != target.length) {
NSLog(@"length is different, strings don't match");
return 0;
}
NSInteger val = 0;
NSMutableDictionary *histogram = [NSMutableDictionary new];
for (int i = 0; i < input.length ; i++) {
NSString *curChar = [input substringWithRange: NSMakeRange(i,1)];
val = 0;
if ([histogram valueForKey:curChar] != nil) {
val = [[histogram valueForKey:curChar] integerValue];
NSLog(@" char: %@ val: %ld", curChar, (long)val);
[histogram setObject:[NSNumber numberWithInteger:++val] forKey:curChar];
} else {
[histogram setObject:[NSNumber numberWithInteger:val] forKey:curChar];
}
}
NSLog(@"dict: %@", histogram);
for (int i = 0; i < target.length; i++) {
NSString *curChar = [target substringWithRange: NSMakeRange(i,1)];
val = 0;
if ([histogram valueForKey:curChar] == nil) {
NSLog(@"new char: %@", curChar);
return 0;
} else {
val = [[histogram valueForKey:curChar] integerValue];
if (val == 0) { [histogram removeObjectForKey:curChar];}
if (val > 0) {
val--;
[histogram setObject:[NSNumber numberWithInteger:val] forKey:curChar];
}
}
}
NSLog(@"dict: %@, count: %lu", histogram, (unsigned long)[histogram count]);
if ([histogram count] == 0) {
NSLog(@"input: %@ is an anagram for target: %@", input, target);
} else {
NSLog(@"input: %@ doesn't match target: %@ , difference: %@", input, target, histogram);
}
}
return 0;
}
If(s1.length!=s2.length)
- Sathya February 14, 2011return false
int a[26]
for i=0 to s1.len-1{
a[s1[0]-'a']--;
a[s2[0]-'a']++;
}
for i=0 to 25{
if a[i]!=0
return false
}
return true