Sort an array of strings so that anagrams are next to each other

 Posted on March 28, 2014  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Write a method to sort an array of strings so that all the anagrams are next to each other. Example INPUT : "xyz", "ca", "ab", "ac", "ba", "zyx" OUTPUT: "ab", "ba", "ac", "ca", "xyz", "zyx" Lets see the solutions now. Solution Method 1 - Using bubble sort Check if two pairs of strings are anagrams or not, if yes, swap. Java code private static boolean areAnagrams(String s1, String s2) { if (s1. [Read More]
kodeknight  sorting  anagrams  compare  CrackingTheCodingInterview  sorting-and-searching 

Given a dictionary of word - Group all words into set of anagrams of each other

 Posted on August 10, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Given a set of words in a dictionary, write a program to group all words which are anagrams of each other in to sets. input: “bat”, “tar”, “xyz” , “tab”, “tar” output:[[“bat”, tab”], [“tar”, rat”],”xyz” ] Anagrams Two words are anagrams if one of them has exactly same characters as that of the another word. Example : Anagram & Nagaram are anagrams (case-insensitive). Approach The simpler logic would be to : [Read More]
kodeknight  Microsoft  String  Amazon  anagrams 

Find anagrams in the array of Strings

 Posted on December 31, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Question: You are given an array of strings and you are asked to display all the anagrams within the array. For those who don’t know, two words are anagrams if they contain the same characters. We have already discussed how to check if 2 strings are anagrams here. Answer: The brute force solution would be to take each string and compare it to every other string in the array one character at a time ( O(n^4) solution, assuming there are n strings with maximum n characters each). [Read More]
kodeknight  String  anagrams  array 

Anagram Checker–To check if 2 strings are anagrams

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

An anagram is a type of word, the result of rearra… Unknown - Jul 1, 2014An anagram is a type of word, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once. For example: orchestra can be rearranged into carthorse or cat can be rearranged into act. We can find out the anagram strings using below algorithm: [Read More]
kodeknight  String  java-code  anagrams  hashes  CrackingTheCodingInterview 

Anagram Checker–To check if 2 strings are anagrams

 Posted on September 11, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem  Wap to find out if 2 strings are anagrams or not. Anagrams Two words are anagrams if one of them has exactly same characters as that of the another word. Example : Anagram & Nagaram are anagrams (case-insensitive).Similarily, abcd and abdc are anagrams, but abcd and abdce is not. Solution A simple way to check if two strings are anagrams is to find out if the numeric sum of the characters in the strings is equal. [Read More]
kodeknight  String  java-code  anagrams  hashes  CrackingTheCodingInterview 

Anagram Trees : Part 2

 Posted on February 17, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

One nice thing about working at Google is that you are surrounded by very smart people. I told one of my coworkers about the anagram tree idea, and he immediately pointed out that reordering the alphabet so that the least frequently used letters come first would reduce the branching factor early in the tree, which has the effect of reducing the overall size of the tree substantially. While this seems obvious in retrospect, it’s kind of unintuitive - usually we try to _increase_ the branching factor of n-ary trees to make them shallower and require fewer operations, rather than trying to reduce it. [Read More]
tree  kodeknight  String  anagrams 

Anagram Trees

 Posted on February 17, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

When it comes to finding anagrams of words, a frequent approach is to use an anagram dictionary - simply put, sort the letters in your word to provide a unique key that all anagrams of a word have in common. Another approach is to generate a letter-frequency histogram for each letter in your word. (Both these approaches are more or less equivalent, in fact.) These approaches make the problem of finding exact single-word anagrams for strings very efficient - O(1) if you use a hashtable. [Read More]
Algorithms  kodeknight  anagrams 

Anagram program implentation

 Posted on January 6, 2010  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

#include using namespace std; #include "anaword.h" static const int ALPH\_SIZE = 26; Anaword::Anaword(const string & word) : myWord(word), myCounts(ALPH\_SIZE,0) // postcondition: constructed { normalize(); } Anaword::Anaword() : myWord(""), myCounts(ALPH\_SIZE,0) { } void Anaword::normalize() // postcondition: myCounts represents the letter signture of myWord { } string Anaword::toString() const // postcondition: return "bagel" or "gable", regular form of string { return myWord; } ostream & operator << (ostream & out, const Anaword & a) // postcondition: a printed t stream out, out returned { out << a. [Read More]
kodeknight  programming  anagrams