Nitin Agrawal
Contact -
  • Home
  • Interviews
    • Secret Receipe
    • InterviewFacts
    • Resume Thoughts
    • Daily Coding Problems
    • BigShyft
    • Companies
    • Interviews Theory
  • Programming Languages
    • Java Script >
      • Tutorials
      • Code Snippets
    • Reactive Programming >
      • Code Snippets
    • R
    • DataStructures >
      • LeetCode Problems >
        • Problem10
        • Problem300
      • AnagramsSet
    • Core Java >
      • Codility
      • Program Arguments OR VM arguments & Environment variables
      • Java Releases >
        • Java8 >
          • Performance
          • NasHorn
          • WordCount
          • Thoughts
        • Java9 >
          • ServiceLoaders
          • Lambdas
          • List Of Objects
          • Code Snippets
        • Java14 >
          • Teeing
          • Pattern
          • Semaphores
        • Java17 >
          • Switches
          • FunctionalStreams
          • Predicate
          • Consumer_Supplier
          • Collectors in Java
        • Java21 >
          • Un-named Class
          • Virtual Threads
          • Structured Concurrency
      • Threading >
        • ThreadsOrder
        • ProducerConsumer
        • Finalizer
        • RaceCondition
        • Executors
        • Future Or CompletableFuture
      • Important Points
      • Immutability
      • Dictionary
      • Sample Code Part 1 >
        • PatternLength
        • Serialization >
          • Kryo2
          • JAXB/XSD
          • XStream
        • MongoDB
        • Strings >
          • Reverse the String
          • Reverse the String in n/2 complexity
          • StringEditor
          • Reversing String
          • String Puzzle
          • Knuth Morris Pratt
          • Unique characters
          • Top N most occurring characters
          • Longest Common Subsequence
          • Longest Common Substring
        • New methods in Collections
        • MethodReferences
        • Complex Objects Comparator >
          • Performance
        • NIO >
          • NIO 2nd Sample
        • Date Converter
        • Minimum cost path
        • Find File
      • URL Validator
    • Julia
    • Python >
      • Decorators
      • String Formatting
      • Generators_Threads
      • JustLikeThat
    • Go >
      • Tutorial
      • CodeSnippet
      • Go Routine_Channel
      • Suggestions
    • Methodologies & Design Patterns >
      • Design Principles
      • Design Patterns >
        • TemplatePattern
        • Adapter Design Pattern
        • Proxy
        • Lazy Initialization
        • CombinatorPattern
        • Singleton >
          • Singletons
        • Strategy
  • Frameworks
    • Apache Velocity
    • React Library >
      • Tutorial
    • Spring >
      • Spring Boot >
        • CustomProperties
        • ExceptionHandling
        • Custom Beans
        • Issues
      • Quick View
    • Rest WebServices >
      • Interviews
      • Swagger
    • Cloudera BigData >
      • Ques_Ans
      • Hive
      • Apache Spark >
        • ApacheSpark Installation
        • SparkCode
        • Sample1
        • DataFrames
        • RDDs
        • SparkStreaming
        • SparkFiles
    • Integration >
      • Apache Camel
    • Testing Frameworks >
      • JUnit >
        • JUnit Runners
      • EasyMock
      • Mockito >
        • Page 2
      • TestNG
    • Blockchain >
      • Ethereum Smart Contract
      • Blockchain Java Example
    • Microservices >
      • Messaging Formats
      • Design Patterns
    • AWS >
      • Honeycode
    • Dockers >
      • GitBash
      • Issues
      • Kubernetes
  • Databases
    • MySql
    • Oracle >
      • Interview1
      • SQL Queries
    • Elastic Search
  • Random issues
    • TOAD issue
    • Architect's suggestions
  • Your Views
One interesting interview question -
You are given a list or array of words & you have to create sets of anagrams such that all anagram words are in one set. So you can have multiple different sets, all having anagram words.
e.g. Input : "DOG", "CAT","TAC","GOD","ACT"
       Output : ACT=[ACT, TAC, CAT],
                     DGO=[DOG, GOD]

Check a simpler version from Round1 asked in Expedia here.
Below is the code & later I have attached the code file also to download & use -
​import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.stream.IntStream;

/**
 * @author Nitin Agrawal
 * 
 */
public class AnagramSets {

private Map<String, Set<String>> anagramsSets = new HashMap<>();
private static int count = 0;

public static void main(String[] args) {

AnagramSets anagramSets = new AnagramSets();
String[] input = {"DOG", "CAT","TAC","GOD","ACT"};
// String[] input = anagramSets.generateStringArray(500000);
// One Way
long start = System.currentTimeMillis();
anagramSets.findSets(input);
anagramSets.anagramsSets.forEach((a,b) -> {
if(b.size() > 1)
count++;
});
System.out.println("Count : " + count);
System.out.println(System.currentTimeMillis()-start);

count = 0;
anagramSets.anagramsSets.clear();

// Another Way
start = System.currentTimeMillis();
List<Block> list = new ArrayList<>();
int len = input.length;
for(int i = 0; i < len; i++) {
list.add(new Block(input[i], i));
}

Collections.sort(list);
Block cur = list.get(0);
Set<String> anagrams = null;
for(int i = 1; i < len; i++) {
if((anagrams=anagramSets.anagramsSets.get(cur.sorted)) == null) {
anagrams = new HashSet<>();
anagramSets.anagramsSets.put(cur.sorted, anagrams);
}
if(list.get(i).equals(cur)) {
anagrams.add(input[list.get(i).index]);
} else {
anagrams.add(input[cur.index]);
anagramSets.anagramsSets.put(cur.sorted, anagrams);
anagrams = new HashSet<>();
anagrams.add(input[list.get(i).index]);
anagramSets.anagramsSets.put(list.get(i).sorted, anagrams);
cur = list.get(i);
}
}
anagramSets.anagramsSets.forEach((a,b) -> {
if(b.size() > 1)
count++;
});
System.out.println("Count : " + count);
System.out.println(System.currentTimeMillis()-start);
}

private void findSets(String[] words) {
Arrays.asList(words)
.parallelStream()
.forEach(this::addToSet);
}

private void addToSet(String word) {
char[] chars = null;
Arrays.sort((chars=word.toCharArray()));
String key = new String(chars);
Set<String> set = null;
if((set=anagramsSets.get(key)) == null) {
set = new HashSet<>();
set.add(word);
anagramsSets.put(key, set);
} else {
set.add(word);
}
}

private String[] generateStringArray(int size) {
String[] array = new String[size];
IntStream.range(0, size)
.forEach(a -> {
char ch1 = (char)new Random().ints(65, 75).findFirst().getAsInt();
char ch2 = (char)new Random().ints(75, 85).findAny().getAsInt();
char ch3 = (char)new Random().ints(70, 80).findAny().getAsInt();
char ch4 = (char)new Random().ints(80, 90).findAny().getAsInt();
String str = ""+ch1+ch2+ch3+ch4;
array[a] = str;
});
return array;
}

static class Block implements Comparable<Block> {
String sorted;
int index;
public Block(String word, int index) {
this.index = index;
char[] chars = word.toCharArray();
Arrays.sort(chars);
sorted = new String(chars);
}

@Override
public boolean equals(Object obj) {
if(obj instanceof Block)
return ((Block)obj).sorted.equals(sorted);
return false;
}

@Override
public int compareTo(Block o) {
return sorted.compareTo(o.sorted);
}

@Override
public String toString() {
return sorted;
}
}
}
anagramsets.java
File Size: 3 kb
File Type: java
Download File

Picture
Powered by Create your own unique website with customizable templates.