cnu1438
BAN USERIgnore my comment.
Please check my code and let me know if anything is wrong
package com.cnu.ds.programs;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class SetOfAnagrams {
public int count(List<String> list) {
List<Set<String>> sets = new LinkedList<>();
boolean isNotPresent = false;
for (String string : list) {
for (Set<String> set : sets) {
String anagram = set.iterator().next();
if (anagrams(string, anagram)) {
set.add(string);
isNotPresent = true;
break;
}
}
System.out.println(isNotPresent+" "+sets+" "+string);
if (!isNotPresent) {
Set<String> set = new HashSet<>();
set.add(string);
sets.add(set);
}
isNotPresent = false;
}
System.out.println(sets);
return sets.size();
}
public boolean anagrams(String s1, String s2) {
if (s1 != null && s2 != null) {
if (s1.length() == s2.length()) {
int[] noOfAlphabetsInS1 = new int[26];
for (int i = 0; i < s1.length(); i++) {
noOfAlphabetsInS1[s1.charAt(i) - 97]++;
noOfAlphabetsInS1[s2.charAt(i) - 97]--;
}
for (int i = 0; i < noOfAlphabetsInS1.length; i++) {
if (noOfAlphabetsInS1[i] != 0) {
return false;
}
}
return true;
}
}
return false;
}
public static void main(String[] args) {
// String a = "bed";
// String b = "bee";
// System.out.println(String.format("%s and %s are %s anagrams", a, b,
// anagrams(a, b) ? "" : "not"));
String[] strings = { "abc", "cab", "dac", "bed", "few", "deb","acd" };
String[] strs={"xyz","abc"};
SetOfAnagrams anagrams = new SetOfAnagrams();
System.out.println("Total Number of sets of Anagrams: "
+ anagrams.count(Arrays.asList(strs)));
}
}
Sorry dude, even I missed two strings.
My Code:
Please let me know if any thing wrong in this
package com.cnu.ds.programs;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class SetOfAnagrams {
public int count(List<String> list) {
List<Set<String>> sets = new LinkedList<>();
boolean isNotPresent = false;
for (String string : list) {
for (Set<String> set : sets) {
String anagram = set.iterator().next();
if (anagrams(string, anagram)) {
set.add(string);
isNotPresent = true;
break;
}
}
System.out.println(isNotPresent+" "+sets+" "+string);
if (!isNotPresent) {
Set<String> set = new HashSet<>();
set.add(string);
sets.add(set);
}
isNotPresent = false;
}
System.out.println(sets);
return sets.size();
}
public boolean anagrams(String s1, String s2) {
if (s1 != null && s2 != null) {
if (s1.length() == s2.length()) {
int[] noOfAlphabetsInS1 = new int[26];
for (int i = 0; i < s1.length(); i++) {
noOfAlphabetsInS1[s1.charAt(i) - 97]++;
noOfAlphabetsInS1[s2.charAt(i) - 97]--;
}
for (int i = 0; i < noOfAlphabetsInS1.length; i++) {
if (noOfAlphabetsInS1[i] != 0) {
return false;
}
}
return true;
}
}
return false;
}
public static void main(String[] args) {
// String a = "bed";
// String b = "bee";
// System.out.println(String.format("%s and %s are %s anagrams", a, b,
// anagrams(a, b) ? "" : "not"));
String[] strings = { "abc", "cab", "dac", "bed", "few", "deb","acd" };
String[] strs={"xyz","abc"};
SetOfAnagrams anagrams = new SetOfAnagrams();
System.out.println("Total Number of sets of Anagrams: "
+ anagrams.count(Arrays.asList(strs)));
}
}
Dude,
Anagram means both the strings should have same set of alphabets and same number of types each alphabet should appear.
in above example
abc,bca -- have same alphabets a,b,c and appear same number of times in each string
dac,acd -- alphabets a,c,d and appear same number of times in each string
deb,beed are belong to two different sets because in 1st string b -1 e -1 d-1 but in 2nd string b -1 e-2 d-1
few --
So total 5 sets
package com.cnu.ds.sorting;
@SuppressWarnings("rawtypes")
abstract public class Sort {
int count;
protected boolean isSorted(Comparable[] a) {
for (int i = 0; i < a.length - 1; i++) {
// a[i].equals(a[i + 1]) is to allow duplicate elements
if (less(a[i], a[i + 1]) || a[i].equals(a[i + 1])) {
continue;
}
return false;
}
return true;
}
@SuppressWarnings("unchecked")
protected boolean less(Comparable i, Comparable j) {
return i.compareTo(j) < 0;
}
protected void excahnge(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public abstract void sort(Comparable<?>[] a);
}
package com.cnu.ds.sorting;
/**
* @author cnu8
* @see It is the improved version of {@link MergeSort}
*/
public class MergeSortVersion2 extends Sort {
private static Comparable<?>[] aux;
@Override
public void sort(Comparable<?>[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
protected void sort(Comparable<?>[] a, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
sort(a, low, mid);
sort(a, mid + 1, high);
merge(a, low, mid, high);
}
}
private void merge(Comparable<?>[] a, int low, int mid, int high) {
// !less(a[mid], a[mid + 1]) : No merge required if the last element of
// first array is
// less than or equal to the first element of second array. Because the
// complete array is already in sorted order
// !a[mid].equals(a[mid + 1]) -- check for equality of the above two
// elements
if (!less(a[mid], a[mid + 1]) || !a[mid].equals(a[mid + 1])) {
for (int i = low; i <= high; i++) {
aux[i] = a[i];
}
int i = low, j = mid + 1, k = low;
while (i <= mid && j <= high) {
if (less(aux[i], aux[j])) {
a[k] = aux[i];
i++;
} else {
a[k] = aux[j];
j++;
}
k++;
}
while (i <= mid) {
a[k] = aux[i];
i++;
k++;
}
while (j <= high) {
a[k] = aux[j];
j++;
k++;
}
}
// Testing the output of array : a after merging
// for (int k2 = low; k2 <= high; k2++) {
// System.out.print(a[k2]);
// }
// System.out.println();
}
public static void main(String[] args) {
char[] aa = "MERGEEXAMPLE".toCharArray();
System.out.println("Before Sort");
Comparable<?>[] a = new Comparable[aa.length];
for (int i = 0; i < a.length; i++) {
a[i] = aa[i];
}
for (Comparable<?> comparable : a) {
System.out.print(comparable);
}
System.out.println();
MergeSortVersion2 mergeSortVersion2 = new MergeSortVersion2();
mergeSortVersion2.sort(a);
if (mergeSortVersion2.isSorted(a)) {
System.out.println("After Sort:");
for (Comparable<?> comparable : a) {
System.out.print(comparable);
}
} else {
System.out.println("Array is not sorted");
}
}
}
package com.cnu.ds.programs;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.List;
import com.cnu.ds.sorting.MergeSortVersion2;
public class PersonSortClient {
public static void main(String[] args) {
MergeSortVersion2 mergeSort = new MergeSortVersion2();
Comparable<Person>[] persons = persons();
System.out.println("Before sort");
for (Comparable<Person> person : persons) {
System.out.println(person);
}
mergeSort.sort(persons);
System.out.println("After sort");
for (Comparable<Person> person : persons) {
System.out.println(person);
}
}
public static Comparable<Person>[] persons() {
List<Comparable<Person>> persons = new LinkedList<>();
BufferedReader bufferedReader =null;
try {
bufferedReader = new BufferedReader(new FileReader(
"persons"));
String personDetails = null;
while ((personDetails = bufferedReader.readLine()) != null) {
String details[] = personDetails.split(",");
Person person = new Person(details[0],
Integer.valueOf(details[1]));
persons.add(person);
}
Person[] personss = new Person[persons.size()];
return persons.toArray(personss);
} catch (IOException e) {
e.printStackTrace();
}finally {
if (bufferedReader!=null) {
try {
bufferedReader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return null;
}
}
package com.cnu.ds.hash;
public class DoubleHasingHashtable {
public void put(Long phonenumber) {
int hashValue = phonenumber.hashCode();
int probeSize = hashCode(phonenumber);
int index = hashValue % capacity;
if (loadfactor <= (((float) size) / capacity)) {
rehash(getPrime(capacity * 2));
System.out.println("new capacity : " + getPrime(capacity));
}
while (hashtable[index] != null) {
hashValue = hashValue + probeSize;
index = hashValue % capacity;
System.out.println(probeSize);
}
// finds empty place
hashtable[index] = phonenumber;
size++;
}
private int hashCode(Long key) {
return (int) (89L - key % 89L);
}
public boolean contains(Long key) {
int hashValue = key.hashCode();
int probeSize = hashCode(key);
int index = hashValue % capacity;
while (hashtable[index] != null) {
Long entry = hashtable[index];
if (entry.equals(key)) {
return true;
}
hashValue = hashValue + probeSize;
index = hashValue % capacity;
}
return false;
}
public DoubleHasingHashtable(float loadfactor, int capacity) {
this.capacity = capacity;
hashtable = new Long[capacity];
}
private void rehash(int newCapacity) {
Long newHashtable[] = new Long[newCapacity];
for (int i = 0; i < capacity; i++) {
Long entry = hashtable[i];
if (entry != null) {
int hashValue = entry.hashCode();
int index = hashValue % newCapacity;
while (newHashtable[index] != null) {
hashValue = hashValue + 1;
index = hashValue % newCapacity;
}
newHashtable[index] = entry;
}
}
hashtable = newHashtable;
capacity = newCapacity;
}
private int getPrime(int capacity) {
for (int i = capacity + 2; true; i += 2) {
if (isPrime(i)) {
return i;
}
}
}
private boolean isPrime(int num) {
int factors = 1;
for (int i = 2; i < num; i++) {
if (num % i == 0) {
factors++;
}
if (factors > 1) {
return false;
}
}
return true;
}
static class Entry<K, V> {
private K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
private Long hashtable[];
private int capacity = 11;
private float loadfactor = 0.75f;
private int size;
public DoubleHasingHashtable() {
this(0.75f, 11);
}
}
We can use Hashing mechanism here and to resolve collisions choose Open Addressing.
Input size : known before
Range of Values: Known before
All the phone numbers in range from 0 to 9999999999 will not be used. We can consider only 1 million of numbers can be used initially (if want in future we can increase the table size using grow-able array concept)
Initially we can start with a size of 181 array (181 is a prime number, prime number will distributes numbers as uniformly as possible)
We have to define a hash function which converts the following thing.
1. Convert the key (phone number) into the range of array size.
Choose double hashing technique
I will copy the code as reply to this comment
package com.cnu.ds.hash.test;
public class Microsoft {
public static String generateLowestNumber(String number, int n) {
if (number == null || number.length() < n) {
return null;
} else if (number.length() > n) {
int removed = 0;
for (int i = 0, j = 1; removed != n && j != number.length();) {
if (number.charAt(i) > number.charAt(j)) {
number = number.substring(0, i)
+ number.substring(j, number.length());
System.out.println(number);
i = 0;
j = 1;
removed++;
} else {
i++;
j++;
}
}
}
return null;
}
public static void main(String[] args) {
generateLowestNumber("2200010300", 4);
}
}
package com.company.epic;
public class Question3 {
static String next(String n) {
String nStringFormat = n + "";
char previousDigit = nStringFormat.charAt(0), currentDigit = ' ';
int noOfOccurences = 1;
String nextNumber = "";
for (int last = 1; last < nStringFormat.length(); last++) {
currentDigit = nStringFormat.charAt(last);
if (currentDigit != previousDigit) {
nextNumber = nextNumber + noOfOccurences + "" + previousDigit;
previousDigit = currentDigit;
noOfOccurences = 1;
} else {
noOfOccurences++;
}
}
nextNumber = nextNumber + noOfOccurences + previousDigit;
return nextNumber;
}
public static void main(String[] args) {
String nextNumber = "22111";
for (int i = 0; i < 10; i++) {
System.out.print(nextNumber + " ");
nextNumber = next(nextNumber);
}
}
}
Your approach will take constant amount of space complexity and linear time to find the largest
package com.cnu.ds;
public class LongestWord {
public static void main(String[] args) {
String list[] = { "back", "cab", "abba" };
String s = "a a b c k";
String letters[] = s.split(" ");
for (String letter : letters) {
a[letter.charAt(0)] += 1;
}
System.out.println();
for (String letter : letters) {
System.out.print(a[letter.charAt(0)] + " ");
}
System.out.println();
int max = 0;
String longestString = null;
for (int i = 0; i < list.length; i++) {
int temp[] = new int[256];
int j = 0;
for (; j < list[i].length(); j++) {
temp[list[i].charAt(j)] += 1;
}
if (isItConsiderable(temp)) {
if (max < list[i].length()) {
max = list[i].length();
longestString = list[i];
}
}
}
System.out.println("The longest string: "+longestString);
}
public static boolean isItConsiderable(int temp[]) {
for (int i = 0; i < temp.length; i++) {
if (temp[i] > a[i]) {
return false;
}
}
return true;
}
private static int a[] = new int[256];
}
Repsushiplarson, Animator at Achieve Internet
Hi, I am a creative Assistant Video Editor with experience in all aspects of video production. Working at a post-production ...
Reppamelajoung, Dev Lead at Absolute Softech Ltd
I have worked as a wedding photographer for the past two years, first as a photographer’s assistant and then ...
Repabbyhgabb, Associate at Abs india pvt. ltd.
Develop fresh content for emails, web banners, site wide communication, and subject lines.Write stories, blogs and related content about ...
- cnu1438 July 01, 2015