akyker20
BAN USERSo your answer is pretty close, but your BFS does not guarantee shortest path (only a path). Instead of a simple BFS, use Dijkstra's algorithm with P as the source. Like you said, maintain the parents in a hashmap or array of some sort and then ascend through the parents starting with Q's parent to determine the shortest path.
- akyker20 March 16, 2015My solution is not linear...I know that. However, I do not need to create a graph and perform DFS. Simply sort pairs based on smallest value in pair.
(2,3), (5, 1) => (5, 1), (2, 3) because 1 is the smallest value in (5, 1) and is smaller than 2 (the smallest value in (2, 3)).
Now, simply iterate through pairs and determine if consecutive pairs are in the same group (if they contain one of the same numbers). The code is shown below:
public class Pair implements Comparable<Pair> {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
public boolean contains(int num) {
return this.x == num || this.y == num;
}
@Override
public int compareTo (Pair other) {
return new Integer(Math.min(x, y)).compareTo(Math.min(other.x, other.y));
}
}
//In some other class
public List<Set<Integer>> computeGroups(List<Pair> pairs) {
List<Set<Integer>> groups = new ArrayList<Set<Integer>>();
Collections.sort(pairs);
Pair pair = pairs.get(0);
Set<Integer> group = new HashSet<Integer>();
group.add(pair.x);
group.add(pair.y);
for(int i = 1; i < pairs.size(); i++) {
if(!pairs.get(i).contains(pair.x) && !pairs.get(i).contains(pair.y)) {
groups.add(group);
group = new HashSet<Integer>();
}
pair = pairs.get(i);
group.add(pairs.get(i).x);
group.add(pairs.get(i).y);
}
groups.add(group);
return groups;
}
Toss coin 3 times (6 can be represented by 3 bits). If coin is heads set bit to 1, if coin is tails set bit to 0. If you get three heads in a row or three tails in a row [111 (7) or 000 (0)], start over. Otherwise convert the 3 bits into an integer (it will be between 1 and 6) and return that.
- akyker20 January 16, 2015Thats good for looking at a sum composed of 3 numbers, but what are you going to do when (as expected) the interviewer turns around and says change your solution to find a sum of zero composed of n numbers. My recursive function below is definitely slower than yours, but it could be easily modified to check for a sum of zero for n numbers.
- akyker20 January 16, 2015Here is, in my opinion, a fairly elegant solution. Obviously, its slower than some messy iterative function. The advantage of this function however is that it could be easily modified to check for a sum of zero composed with n numbers (instead of 3).
import java.util.Arrays;
public class Algorithm {
public boolean threeNumbersAddUpToZero(int[] input) {
return recursiveHelper(0, 0, input);
}
private boolean recursiveHelper(int sum, int numNumbers, int[] input) {
if(numNumbers == 3) return sum == 0;
if(input.length == 0) return false;
int[] subarray = Arrays.copyOfRange(input, 1, input.length);
return recursiveHelper(sum+input[0], numNumbers+1, subarray) ||
recursiveHelper(sum, numNumbers, subarray);
}
}
Clearly we cannot swap first character for last character, etc. Way too much I/O consumption (reading from disk is wayyy slow).
What we can do is read in a block B_f of characters from the front of the file and a block of the same size B_e from the end of the file.
Then, reverse B_f and reverse B_e. Now, swap the blocks. Now continue this process with block reversing and swapping like we would have done with character swaps until you reach the center of the file.
abcd
B_f = ab, B_e = cd
Rev(B_f) = ba, Rev(B_e) = dc
Swap(B_f, B_e) => dcba
Thoughts???
import java.util.Map;
import java.util.TreeMap;
public class StringCounter {
private Map<String, Character> myMap;
public StringCounter() {
myMap = new TreeMap<String, Character>();
//Builds the map: 0 -> A, ..., 25->Z
for(int i = 0; i < 26; i++) {
myMap.put(i+"", (char) (i+65));
}
}
//slow recursive strategy.
public int countStrings(String input) {
if(input.isEmpty()) return 1;
int num = countStrings(input.substring(1));
if(input.length() >=2 && myMap.containsKey(input.substring(0, 2)))
num += countStrings(input.substring(2));
return num;
}
//DP Soln - O(n) space, O(n) time
public int countStringsDP(String input) {
int[] numStrings = new int[input.length()];
numStrings[0] = 1;
numStrings[1] = myMap.containsKey(input.substring(0,2)) ? 2 : 1;
for(int i = 2; i < input.length(); i++) {
numStrings[i] = numStrings[i-1];
if(myMap.containsKey(input.substring(i-1, i+1)))
numStrings[i] += numStrings[i-2];
}
return numStrings[input.length()-1];
}
//DP Soln - O(n) time, constant space
public int countStringsDP2(String input) {
int val1 = 1;
int val2 = myMap.containsKey(input.substring(0,2)) ? 2 : 1;
for(int i = 2; i < input.length(); i++) {
int temp = val2;
if(myMap.containsKey(input.substring(i-1, i+1)))
temp += val1;
val1 = val2;
val2 = temp;
}
return val2;
}
}
I can't seem to think of a solution without a sort which would mean the best is nlogn. An alternate solution is to sort and then add the first element to the new array and then for every sequential pair of elements afterwards add the larger element of the pair first and then the smaller element. For instance, if the sort yields [1 2 3 4 5 ...], then add 1 followed by 3 then 2 and 5 then 4 and so on with the result being [1 3 2 5 4 7 6 ...]. Essentially, you are swapping the 2nd and 3rd elements, the 4th and 5th elements, etc. Still same runtime as your solution above, but the advantage of mine is that it could be performed in place (which I understand is not the question).
- akyker20 March 17, 2015