mikewhity
BAN USER- 1of 1 vote
AnswersGiven infinite supply of coins of denominations 25, 10, 5 and 1, find the distinct number of ways to use the coins to sum up to the given value
- mikewhity in United States
Find the best algorithm with the best time complexity| Report Duplicate | Flag | PURGE
Akamai Software Developer - 0of 0 votes
AnswersYou have a binary tree where each node knows the number of nodes in its sub-tree (including itself).
- mikewhity in United States
Given a node n and an int k,
write a function to return the kth
node in an in order traversal.
Can you do this non recursively| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersSuppose I am given a set of input strings input[5](five of them) and their corresponding replacement strings replace[5]. Then I am given an input text, how can I replace the strings in the text matching any of the inputs with their corresponding replacements.
- mikewhity in United States
Also I have to make sure that if suppose, I find a match input[0] and I replace it by replace[0], then because of that it could be possible that I have a new match for input[2] lets say because of the new characters added by replace[0]. I don't want to make replacements with replace[2].
Also I cannot use regex of java.| Report Duplicate | Flag | PURGE
Amazon Software Development Manager Replacing multiple string occurences from a text - 0of 0 votes
AnswersSuppose I am given a set of input strings input[5](five of them) and their corresponding replacement strings replace[5]. Then I am given an input text, how can I replace the strings in the text matching any of the inputs with their corresponding replacements.
- mikewhity in United States
Also I have to make sure that if suppose, I find a match input[0] and I replace it by replace[0], then because of that it could be possible that I have a new match for input[2] lets say because of the new characters added by replace[0]. I don't want to make replacements with replace[2].| Report Duplicate | Flag | PURGE
Software Engineer / Developer Replacing multiple string occurences from a text - 0of 0 votes
AnswersSuppose I have five strings input[5] and their corresponding replacements replace[5]. I am given an input text and I want to find the occurence of any of the input strings and replace them with the corresponding replace strings. I cannot use regex. How can I do it. Also I have to make sure that lets say after replace input[0] with replace[0], if a new string arises due to replace[0] that matches with lest say input[2], then I cannot replace it with replace[2].
- mikewhity in United States| Report Duplicate | Flag | PURGE
Software Engineer / Developer Replacing multiple string occurences from a text
public class PermutationWays {
public static int count = 0;
public static void countSequences(int[] values, StringBuilder sb, int totalCount) {
if(sb.length() == totalCount) {
count++;
return;
}
if(values[0] > 0) {
if(sb.length() == 0 || sb.charAt(sb.length()-1) != '1') {
sb.append('1');
values[0]--;
countSequences(values, sb, totalCount);
sb.setLength(sb.length()-1);
values[0]++;
}
}
if(values[1] > 0) {
if(sb.length() == 0 || sb.charAt(sb.length()-1) != '2') {
sb.append('2');
values[1]--;
countSequences(values, sb, totalCount);
sb.setLength(sb.length()-1);
values[1]++;
}
}
if(values[2] > 0) {
if(sb.length() == 0 || sb.charAt(sb.length()-1) != '3') {
sb.append('3');
values[2]--;
countSequences(values, sb, totalCount);
sb.setLength(sb.length()-1);
values[2]++;
}
}
if(values[3] > 0) {
if(sb.length() == 0 || sb.charAt(sb.length()-1) != '4') {
sb.append('4');
values[3]--;
countSequences(values, sb, totalCount);
sb.setLength(sb.length()-1);
}
values[3]++;
}
}
public static void main(String args[]) {
int[] count = {2,2,2,2};
PermutationWays.countSequences(count, new StringBuilder(), 8);
System.out.println(PermutationWays.count);
}
}
import java.util.HashSet;
public class Main {
public boolean getRepeatedSequence(String input) {
char[] inputArray = input.toCharArray();
HashSet<String> subsetMatcher = new HashSet<String>();
StringBuilder buffer = new StringBuilder();
return recursiveSubSequence(inputArray, subsetMatcher, 0, buffer);
}
public boolean recursiveSubSequence(char [] inputArray, HashSet<String> subsetMatcher, int start, StringBuilder buffer) {
if(buffer.length() >= 2) {
if(subsetMatcher.contains(buffer.toString())) {
return true;
} else {
subsetMatcher.add(buffer.toString());
}
}
boolean result = false;
for(int i=start; i<inputArray.length; i++) {
buffer.append(inputArray[i]);
result = recursiveSubSequence(inputArray, subsetMatcher, i+1, buffer);
if(result == true) {
return true;
}
buffer.setLength(buffer.length()-1);
}
return false;
}
public static void main(String args[]) {
Main m = new Main();
System.out.println(m.getRepeatedSequence("abba"));
}
}
My solution is just take all the subsets and see if they are unique. Obviously the code doesn't work for "abba" as mentioned by the author of the post. I am not sure why abba is not valid. It has ab at two places {1,2} and {1,3} with b following a. So it's valid I guess.
However, if it is invalid, then I can store the indices that joined together to form the subset and then when comparing if there is repetition, I will check if the indices(first) in the two cases are same or not. For instance in the example string "abba", the first ab will have indices {1,2}, the second ab will have indices {1,3}. Since the first indices are same. I will regard them as different.
Has anyone better solution than this? Please let me know
You can use quick sort for that. Pick a random pivot and arrange your numbers. Based upon the index of the pivot element you will know where the required number lies(in which partition). Then you can again use quick sort on the other partition and so on. This will have time complexity O(logn)
The above is assuming you have enough memory then you can use external sort and get the 90th percentile.
- mikewhity September 01, 2016