Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: Written Test
A byte, 8 bits, can assume values from 0 to 255. Therefore having 256 unique possible values. Not "0-256" as mentioned
import java.util.*;
class Anagrams {
static boolean isAnagram(String a, String b) {
char c[] = a.toLowerCase().toCharArray();
char d[] = b.toLowerCase().toCharArray();
Arrays.sort(c);
Arrays.sort(d);
if(Arrays.equals(c,d)){
return true;
}
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter first String: ");
String a = scan.next();
System.out.println("Enter seconf jumbled String");
String b = scan.next();
scan.close();
boolean ret = isAnagram(a, b);
System.out.println( (ret) ? "Anagrams" : "Not Anagrams" );
}
}
For checking that two strings are an anagram of each other, we can use an unordered set in c++ and insert all the characters of the first string and then iterate over the second string and keep checking that the characters in second string must be present in the set if not then both strings are not anagrams of each other else they are.
Implementation:
#include<bits/stdc++.h>
using namespace std;
bool findanagram(string s1, string s2){
unordered_set<char> s;
int n1 = s1.length();
int n2 = s2.length();
transform(s1.begin(), s1.end(), s1.begin(), ::tolower);
transform(s2.begin(), s2.end(), s2.begin(), ::tolower);
for(int i = 0; i < n1; i++)
s.insert(s1[i]);
for(int j = 0; j < n2; j++){
if(s.find(s2[j]) == s.end())
return false;
}
return true;
}
int main()
{
string str1 = "LISTEN";
string str2 = "silent";
cout<<findanagram(str1, str2)<<endl;
return 0;
}
public boolean isAnagram(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
char[] map = new char[256];
for (char c : s.toCharArray()) {
map[c]++;
}
for (char c : t.toCharArray()) {
map[c]--;
if (map[c] < 0) {
return false;
}
}
return true;
}
public static boolean isAnagram(String str1,String str2){
if(str1.length()==0||str2.length()==0||str1.length()!=str2.length()){
return false;
}
byte[] map = new byte[256];
for(char c:str1.toCharArray()){
map[c]++;
}
for(char c:str2.toCharArray()){
map[c]--;
if(map[c]<0){
return false;
}
}
return true;
}
// Solution in Javascript
function anagramCheck(str,strg) {
var arr =[];
var arr2 = [];
a = str.toLowerCase();
b = strg.toLowerCase();
arr = a.split('').sort();
arr2 = b.split('').sort();
if (arr.length === arr2.length) {
for (i=0;i<arr.length; i++) {
if (arr[i] !==arr2[i]) {
return false;
}
}
return true;
} else {
return false;
}
}
#include<vector>
#include<algorithm>
#include<string>
#include<set>
using namespace std;
typedef vector <int> VI;
int main()
{
//code
int t;
cin >> t;
while (t--)
{
string s,st;
int f = 0;
cin >> s;
cin >> st;
VI v1(26, 0);
VI v2(26, 0);
for (int i = 0; i < s.length(); i++)
{
v1[s[i] - 'a']++;
v2[st[i] - 'a']++;
}
for (int i = 0; i < 26; i++)
{
if (v1[i] != v2[i])
{
f = 1;
break;
}
}
if (f == 1)
cout << "NO\n";
else
cout << "YES\n";
}
return 0;
}
public static boolean isAnagram(String str1,String str2){
if(str1.length()==0||str2.length()==0||str1.length()!=str2.length()){
return false;
}
byte[] map = new byte[256];
for(char c:str1.toCharArray()){
map[c]++;
}
for(char c:str2.toCharArray()){
map[c]--;
if(map[c]<0){
return false;
}
}
return true;
}
public static boolean isAnagram(String str1,String str2){
if(str1.length()==0||str2.length()==0||str1.length()!=str2.length()){
return false;
}
byte[] map = new byte[256];
for(char c:str1.toCharArray()){
map[c]++;
}
for(char c:str2.toCharArray()){
map[c]--;
if(map[c]<0){
return false;
}
}
return true;
}
public static boolean isAnagram(String anagramStr, String verifyStr) {
boolean anagram = false;
String reverse = "";
char []strChar = verifyStr.toCharArray();
char revChar;
int j = strChar.length-1;
for(int i = 0; i<= strChar.length-1; i++) {
revChar = strChar[j];
j--;
reverse += revChar;
}
System.out.println("Reverse String :"+reverse);
if(anagramStr.equalsIgnoreCase(reverse)) {
anagram = true;
}
return anagram;
}
Always remember that whenever a string question is thrown at you, just remember this "A string is noting but an array of character that ranges from 0-256 chars(assuming all the char are alphabets)"
- Gaurav May 11, 2019Now to the question,
you can sort the first and sort the second using library function,
and compare each char by char
Time Complexity -> O(n*logn)
## If len(str2) != len(s1) -> return false, strings of uneven lengths can never be anagrams