nandkarthik
BAN USERConstraints:
1. Web-service should return the result with in sub-second (< 1 second)
2. Using the permutation mechanism can slow down the processing
3. The data structure used to store the dictionary should be explained as well
Algorithm:
1. Pre-processing: Store the dictionary as multimap <Key, words>. Construct the key by sorting the letters of the word. (Use quick sort for sorting the letters)
2. Web-Service: The web-service takes the word as input and sort the letters using quick sort O(nlogn) and query the multimap O(1) for all the anagrams.
The logic you mentioned is for Longest Palindrome Sub-Sequence
- nandkarthik February 07, 2014Hi All, I wrote this O(n) program in Java. I didn't find any solution that is less than this.
public class SortedArrayPairSum {
public static void main(String [] args) {
List<Integer> sortedArray = Lists.newArrayList(1, 5, 10, 12, 30, 60);
int sumExpected = 42;
int frontPointer = 0;
int backPointer = sortedArray.size() - 1;
while (frontPointer < backPointer) {
int actualSum = sortedArray.get(frontPointer) + sortedArray.get(backPointer);
if(actualSum < sumExpected) {
frontPointer++;
}
else if(actualSum > sumExpected) {
backPointer--;
}
else {
System.out.println("Pair=(" + sortedArray.get(frontPointer)+","+ sortedArray.get(backPointer) + ") Sum=" + actualSum);
break;
}
}
}
}
Use Set<Long>allFactorsBuffer instead of List<Long>allFactorsBuffer for unique factorials.
- nandkarthik April 01, 20121. Find all the prime factors
2. Find the all multiplication combinations for all factors using recursion
public class AllFactors {
public static void main(String [] args) {
int number = 15;
List<Long> primeFactors = getUniquePrimes(number);
List<Long> allFactors = new AllFactors().getAllFactors(primeFactors);
System.out.println(allFactors);
}
List<Long> allFactorsBuffer = Lists.newArrayList();
public List<Long> getAllFactors(List<Long> primeFactors) {
recursiveGrouping(primeFactors, 0, 1);
return Lists.newArrayList(allFactorsBuffer);
}
private void recursiveGrouping(List<Long> primeFactors, int position, long startValue) {
if(position == primeFactors.size()) {
allFactorsBuffer.add(startValue);
}
else {
recursiveGrouping(primeFactors, position + 1, startValue * primeFactors.get(position));
recursiveGrouping(primeFactors, position + 1, startValue);
}
}
public static List<Long> getUniquePrimes(long number) {
List<Long> uniquePrimes = new ArrayList<Long>();
long primeDivisor = 0;
long numberCopy = number;
do {
primeDivisor = getLeastPrimeDivisor(numberCopy, new ArrayList<Long>());
if(primeDivisor != -1) {
numberCopy = numberCopy/primeDivisor;
}
if(primeDivisor != -1) {
uniquePrimes.add(primeDivisor);
}
if(primeDivisor == -1) {
uniquePrimes.add(numberCopy);
}
} while(primeDivisor != -1);
return uniquePrimes;
}
private static long getLeastPrimeDivisor(long number, List<Long> primeNumbers) {
long halfNumber = number/2;
for(long i = 2; i<= halfNumber; i++) {
if(isPrime(i, primeNumbers)) {
if(number%i == 0) {
return i;
}
else {
primeNumbers.add(i);
}
}
}
return -1;
}
private static boolean isPrime(long number, List<Long> primeNumbers) {
long halfNumber = number/2;
for(long prime: primeNumbers) {
if(prime >= halfNumber) break;
if(number%prime == 0) {
return false;
}
}
return true;
}
}
Can anyone explain how XOR works. I think it doesn't. Here is my implementation O(n) time complexity and 0(3) space complexity. This program is not very clear because I was handling edge cases as well like if the odd man is in the middle, front, back and doesn't exists. This program is not thread-safe as it is saving data.
public class FirstDifferentRepeatedFormatStupid {
private int totalCount = 0;
private HashMap<Integer, Integer> counter = Maps.newLinkedHashMap();
public static void main(String [] args) {
List<Integer> integers1 = Lists.newArrayList(1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4);
List<Integer> integers2 = Lists.newArrayList(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4);
List<Integer> integers3 = Lists.newArrayList(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4);
List<Integer> integers4 = Lists.newArrayList(1, 2, 2, 2, 3, 3, 3, 4, 4, 4);
Integer outLier1 = new FirstDifferentRepeatedFormatStupid().findOutLier(integers1);
Integer outLier2 = new FirstDifferentRepeatedFormatStupid().findOutLier(integers2);
Integer outLier3 = new FirstDifferentRepeatedFormatStupid().findOutLier(integers3);
Integer outLier4 = new FirstDifferentRepeatedFormatStupid().findOutLier(integers4);
System.out.println(integers1 + "=" + outLier1);
System.out.println(integers2 + "=" + outLier2);
System.out.println(integers3 + "=" + outLier3);
System.out.println(integers4 + "=" + outLier4);
}
public Integer findOutLier(List<Integer> integers) {
int firstPointer = 0;
int secondPointer = 1;
int size = integers.size();
int count;
while (firstPointer < size) {
count = secondPointer - firstPointer;
if(secondPointer > integers.size() - 1) {
Integer isDifferent = isDifferentNumber(count, integers.get(firstPointer), true);
if(isDifferent != null) {
return isDifferent;
}
else {
return null;
}
}
else if(integers.get(firstPointer).equals(integers.get(secondPointer))) {
secondPointer ++;
}
else {
Integer isDifferent = isDifferentNumber(count, integers.get(firstPointer), false);
if(isDifferent != null) {
return isDifferent;
}
secondPointer = secondPointer + 1;
firstPointer = secondPointer - 1;
}
}
return null;
}
private Integer isDifferentNumber(int count, int number, boolean isEnd) {
totalCount++;
if(counter.containsKey(count)) {
List<Integer> uniqueCounts = Lists.newArrayList(counter.keySet());
if(counter.size() == 2) {
if(totalCount >= 3 && uniqueCounts.get(0) == count) {
return counter.get(uniqueCounts.get(1));
}
else if(totalCount >= 3 && uniqueCounts.get(1) == count) {
return counter.get(uniqueCounts.get(0));
}
}
}
else {
counter.put(count, number);
}
if(isEnd && counter.size() == 2) {
return number;
}
return null;
}
}
Agreed.
- nandkarthik April 01, 2012This is in Java
public class StringPalindromeOrNot {
public static void main(String [] args) {
String palindrome = "MALAYALAM";
String notPalindrome = "MALADYLAM";
boolean palindromeTrue = isPalindrome(palindrome);
boolean palindromeFalse = isPalindrome(notPalindrome);
System.out.println(palindrome + " = " + palindromeTrue);
System.out.println(notPalindrome + " = " + palindromeFalse);
}
private static boolean isPalindrome(String word) {
if(word == null || word.length() == 0) {
throw new IllegalArgumentException("InvalidWord");
}
int front = 0;
int back = word.length() - 1;
while (front < back) {
if(word.charAt(front) != word.charAt(back)) {
return false;
}
else {
front++;
back--;
}
}
return true;
}
}
If we use the HashTable in Java. It is synchronized and It doesn't maintain the order in which we enter. So, use a LinkedHashMap instead.
public class FirstRepetitiveElementInList {
public static void main(String [] args) {
String text = "youtube facebook google amazon youtube google facebook";
List<String> wordList = Lists.newArrayList(text.split(" "));
HashMap<String, Integer> stringCounter = Maps.newLinkedHashMap();
for(String word: wordList) {
if(stringCounter.containsKey(word)) {
stringCounter.put(word, stringCounter.get(word) + 1);
}
else {
stringCounter.put(word, 1);
}
}
String nonRepetitiveString = getFirstNonRepetitiveElement(stringCounter);
if(nonRepetitiveString == null) {
System.out.println("Not exists");
}
else {
System.out.println(nonRepetitiveString);
}
}
private static String getFirstNonRepetitiveElement(HashMap<String, Integer> stringCounter) {
for(String key: stringCounter.keySet()) {
if(stringCounter.get(key).equals(1)) {
return key;
}
}
return null;
}
}
Infinite loop
- nandkarthik March 30, 2012
This is a in-place replacement except the matrix is traversed twice. Time complexity is O(m x n) + O(m x n). We might need some space for storing the rows and columns that have Zeroes.
- nandkarthik February 14, 20141. Find all the positions (X,Y) where the value is ZERO
2. Keep all X positions to rows set and Y positions to column set
3. If for any position in the matrix (X,Y) existing in the row set or column set respectively set as Zero or else keep it the same