buntybittoo
BAN USERApproach:
For a given string, the possible palindromes are a concatenation of the string and a subset of the string's reverse substrings.
For example, if the given string is: "CATA".
The reverse of this string is: "ATAC".
And the set of substrings of the reverse is: {"ATAC", "TAC", "AC", "C"}
Now all possible palindromes with "CATA" can be obtained from a subset of this set.
All possible palindromes with "CATA" are:
"CATA" + "ATAC"
"CATA" + "TAC"
"CATA" + "C"
How this algorithm works:
- Goes through the input list and puts each string in a HashSet for quick lookup
- For each inputString:
-- Find out the reverse of the string
---- For each substring of the reverse:
-------- if it exists in the set:
------------ if concatenating it with the string creates a palindrome
---------------- add the pair to the result
public static boolean isPalindrome(String inputString) {
if (inputString.length() == 0 || inputString.length() == 1) {
return true;
}
boolean currentSame = inputString.charAt(0) == inputString.charAt(inputString.length() - 1);
String remaining = inputString.substring(1, inputString.length() - 1);
return (same && isPalindrome(remaining));
}
public static class Pair<F, S> {
F first;
S second;
public Pair(F first, S second) {
this.first = first;
this.second = second;
}
}
public static List<Pair<String, String>> getPalindromes(List<String> inputList) {
Set<String> inputSet = new HashSet<>();
inputSet.addAll(inputList);
for (String current : inputList) {
StringBuilder sb = new StringBuilder(current);
String reverse = sb.reverse().toString();
for (int i = 0; i < reverse.length(); i++) {
String currentReverse = reverse.substring(i);
if (stringSet.contains(currentReverse)) {
if (isPalindrome(current + currentReverse)) {
returnList.add(new Pair(current, currentReverse));
}
}
}
}
return returnList;
}
{
Pair<Float, Float> getRange(Float[] array) {
if (array == null || array.length == 0) {
return null;
}
if (array.length == 1) {
return new Pair(array[0], array[0] + 1.0);
}
Arrays.sort(array, Collections.reverseOrder());
int i = 0;
int maxCount = 0;
Pair<Float, Float> maxRange = null;
while (i < array.length) {
int count = 0;
Pair<Float, Float> range = new Pair(array[i], array[i] - 1.0);
for (int j = i; j < array.length; j++) {
if (array[j] <= range.first && array[j] >= range.second) {
count++;
} else {
break;
}
}
if (count > maxCount) {
maxCount = count;
maxRange = range;
}
i++;
}
return maxRange;
}
}
- buntybittoo June 13, 2015Algorithm isn't clear after the first step.
What kind of sliding window? Do you mean a window of width 1? Where does the dequeue come into play?
Remove the number from that back of what? Sum of what is >= 1?
What are you even trying to do?
Of course the worst case is O(n). The worst case will always be O(n). What is your point? Do you have a better solution?
- buntybittoo June 13, 2015String subtractStream(String s_a, Stream s_b) {
StringBuilder sb = new StringBuilder();
boolean carry = false;
while (s_a.hasNext()) {
int a = s_a.nextInt();
int b = 0;
if (s_b.hasNext()) {
b = s_b.nextInt();
}
if (carry) {
a--;
}
int result = (a - b);
if (result < 0) {
result += 10;
carry = true;
} else {
carry = false;
}
sb.append(result);
}
return sb.reverse().toString();
}
RepKinsleyJames, Network Engineer at Accenture
I graduated from College with a master’s degree in arthrogryposis. After graduation I am working as a manager in ...
Repkristyrsharp0, AT&T Customer service email at ABC TECH SUPPORT
I love exploring facts about hvac maintenance services brampton. Operated a service repair and maintenance, answered client questions about the ...
Repalinehchavez, SHOT 1500 NIGHT 5000 Call girls in Munirka Metro 9711794795 at Apple
Hi, I am Aline From New York USA. I am working as a Real estate rental agent in an Energy ...
Repceciliajbaker24, Area Sales Manager at ABC TECH SUPPORT
I work as an Aide at the Alhambra Maker-space, consulting ASU students who come into the space with their projects ...
Repkarinkwalton, Backend Developer at Broadsoft
I am working as a Support clerk in an MVP Sports company. I love traveling and exploring facts about technology ...
WTF is this crap? You've posted like 20 questions which are completely open ended. You could not possibly have been asked all these questions. I could just make up 100s of these: design Google Inbox, design Google Maps, design Spotify, design Windows, design Linux.
- buntybittoo July 14, 2015What are you trying to achieve here?