zaitcev.anton
BAN USERSimply use DFS to find shortest path on un-weighted graph represented by 2d array
public class ShortestPath {
private Collection<Point> path;
public ShortestPath(int[][] matrix, Point start, Point end) {
Map<Point, Point> previous = new HashMap<>();
Queue<Point> queue = new LinkedList<>();
queue.add(start);
previous.put(start, null);
while (!queue.isEmpty()) {
Point point = queue.poll();
if (point.equals(end)) {
path = calculatePath(previous, end);
break;
}
List<Point> adjacentPoints = getAdjacentPoints(matrix, point);
for(Point adjacent : adjacentPoints) {
if (!previous.containsKey(adjacent)) {
previous.put(adjacent, point);
queue.add(adjacent);
}
}
}
}
public Collection<Point> getPath() {
return path != null ? Collections.unmodifiableCollection(path) : Collections.emptyList();
}
private Collection<Point> calculatePath(Map<Point, Point> route, Point end) {
Deque<Point> deque = new ArrayDeque<>();
deque.addFirst(end);
Point previous = route.get(end);
while (previous != null) {
deque.addFirst(previous);
previous = route.get(previous);
}
return deque;
}
private List<Point> getAdjacentPoints(int[][] matrix, Point point) {
List<Point> points = new ArrayList<>();
// up
if (point.x - 1 >= 0 && matrix[point.x - 1][point.y] > 0) {
points.add(new Point(point.x - 1, point.y));
}
// right
if (point.y + 1 < matrix[point.x].length && matrix[point.x][point.y + 1] > 0) {
points.add(new Point(point.x, point.y + 1));
}
// down
if (point.x + 1 < matrix.length && matrix[point.x + 1][point.y] > 0) {
points.add(new Point(point.x + 1, point.y));
}
// left
if (point.y - 1 >=0 && matrix[point.x][point.y - 1] > 0) {
points.add(new Point(point.x, point.y - 1));
}
return points;
}
static class Point {
final int x;
final int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
public int hashCode() {
return 7 * x + 13 * y;
}
public boolean equals(Object other) {
if (other == null) return false;
if (other == this) return true;
if (other instanceof Point) {
Point o = (Point) other;
return this.x == o.x && this.y == o.y;
}
return false;
}
public String toString() {
return "[" + x + "," + y + "]";
}
}
}
// split to words, calculate positions of each word
// given two positions arrays (one per each word) find min |a[i] - b[j]|:
// - current min = a[0] - b[0]
// - iterate i [1 .. a.length-1] && j [1 .. b.length-1]
// - if (a[i] > b[j]) -> j++
// - else -> i++
// - decrease current min if needed
// - return current min indexes
public class MinimumDistance {
public int findMinimumDistance(String input, String firstWord, String secondWord) {
if (input == null || input.isEmpty()) {
return -1;
}
if (firstWord == null || firstWord.isEmpty()) {
return -1;
}
if (secondWord == null || secondWord.isEmpty()) {
return -1;
}
String[] words = input.split("\\s+");
Map<String, List<Integer>> dictionary = getPositions(words);
if (firstWord.equals(secondWord)) {
return findMinimumDistance(dictionary.get(firstWord));
} else {
return findMinimumDistance(dictionary.get(firstWord), dictionary.get(secondWord));
}
}
private Map<String, List<Integer>> getPositions(String[] words) {
Map<String, List<Integer>> dictionary = new HashMap<>();
for(int i = 0; i < words.length; i++) {
List<Integer> positions = dictionary.get(words[i]);
if (positions == null) {
positions = new ArrayList<>();
dictionary.put(words[i], positions);
}
positions.add(i);
}
return dictionary;
}
private int findMinimumDistance(List<Integer> firstPositions, List<Integer> secondPositions) {
if (firstPositions == null || firstPositions.isEmpty()) {
return -1;
}
if (secondPositions == null || secondPositions.isEmpty()) {
return -1;
}
int i = 0;
int j = 0;
int currentMin = Math.abs(firstPositions.get(i) - secondPositions.get(j));
while (currentMin != 0 && i < firstPositions.size() && j < secondPositions.size()) {
int firstNumber = firstPositions.get(i);
int secondNumber = secondPositions.get(j);
if (firstNumber > secondNumber) {
j++;
} else {
i++;
}
if (i < firstPositions.size() && j < secondPositions.size()) {
firstNumber = firstPositions.get(i);
secondNumber = secondPositions.get(j);
int min = Math.abs(firstNumber - secondNumber);
if (min < currentMin) {
currentMin = min;
}
}
}
return currentMin;
}
private int findMinimumDistance(List<Integer> positions) {
if (positions.size() >= 2) {
int i = 0;
int j = 1;
int currentMin = Math.abs(positions.get(i) - positions.get(j));
i++;
j++;
while (j < positions.size()) {
int min = Math.abs(positions.get(i) - positions.get(j));
if (min < currentMin) {
currentMin = min;
}
i++;
j++;
}
return currentMin - 1;
}
return 0;
}
}
java solution based on binary search
public class BinaryFirstLastIndex {
public int[] findFirstLastIndex(int[] input, int number) {
if (input == null) return new int[]{-1,-1};
int start = 0;
int end = input.length - 1;
while (start <= end) {
int middle = start + ((end - start) >> 1);
if (input[middle] > number) {
end = middle - 1;
} else if (input[middle] < number) {
start = middle + 1;
} else { // find first & last index
int first = findFirstIndex(input, middle, number);
int last = findLastIndex(input, middle, number);
return new int[]{first, last};
}
}
// not found
return new int[]{-1, -1};
}
private int findFirstIndex(int[] input, int index, int number) {
int i = index - 1;
for (; i >= 0; i--) {
if (input[i] != number) {
break;
}
}
return i + 1;
}
private int findLastIndex(int[] input, int index, int number) {
int i = index + 1;
for (; i < input.length; i++) {
if (input[i] != number) {
break;
}
}
return i - 1;
}
}
public class FibonacciNumbers {
public List<Integer> filterByIndex(LinkedList<Integer> numbers) {
if (numbers == null || numbers.isEmpty()) {
return Collections.emptyList();
}
List<Integer> fibonacciNumbers = new ArrayList<>();
Iterator<Integer> iterator = numbers.iterator();
// add first number & remove it
fibonacciNumbers.add(iterator.next());
iterator.remove();
int prevFibIndex = 1;
int nextFibIndex = 2;
int currentIndex = 2;
while (iterator.hasNext() && nextFibIndex > 0) {
Integer number = iterator.next();
if (currentIndex == nextFibIndex) {
// remove number from first list & add it to second list
iterator.remove();
fibonacciNumbers.add(number);
// calculate next fibonacci index number
int tmp = nextFibIndex;
nextFibIndex = prevFibIndex + nextFibIndex;
prevFibIndex = tmp;
}
currentIndex++;
}
return fibonacciNumbers;
}
public static void main(String[] args) {
LinkedList<Integer> input = new LinkedList<>(Arrays.asList(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15));
FibonacciNumbers test = new FibonacciNumbers();
List<Integer> output = test.filterByIndex(input);
System.out.println("Fibonacci: " + output);
System.out.println("Filtered: " + input);
}
}
0) sort a, b, c
1) i,j,k = 0 to length
2) calculate X = |a[i] - b[j]|, Y = |b[j] - c[k]|, Z = |c[k] - a[i]|
3) max = maximum(X, Y, Z)
4) minimize max
- if max == X
a[i] > b[j]:
j++
else:
i++
- if max == Y
b[j] > c[k]:
k++
else:
j++
- if max == Z
c[k] > a[i]:
i++
else:
k++
public class MinimumSum {
public int[] findMinimum(int[] a, int[] b, int[] c) {
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
int i = 0, j = 0, k = 0;
long x = Math.abs(a[i] - b[j]);
long y = Math.abs(b[j] - c[k]);
long z = Math.abs(c[k] - a[i]);
long minimum = x + y + z;
int minI = i;
int minJ = j;
int minK = k;
while (minimum != 0 && i < a.length && j < b.length && k < c.length) {
// find max of x, y, z
long max = Math.max(Math.max(x, y), z);
// minimize max
if (max == x) {
if (a[i] > b[j]) {
j++;
} else {
i++;
}
} else if (max == y) {
if (b[j] > c[k]) {
k++;
} else {
j++;
}
} else { // max == z
if (c[k] > a[i]) {
i++;
} else {
k++;
}
}
if (i < a.length && j < b.length && k < c.length) {
x = Math.abs(a[i] - b[j]);
y = Math.abs(b[j] - c[k]);
z = Math.abs(c[k] - a[i]);
long current = x + y + z;
if (current < minimum) {
minimum = current;
minI = i;
minJ = j;
minK = k;
}
} else {
break; // stop searching
}
}
return new int[]{a[minI], b[minJ], c[minK]};
}
I would suggest to run a simple DFS and calculate connectivity component for each vertex. It would allow to answer several questions like "pathExists(from, to)" on the same input without calculating the path each time for each new input.
public class ConnectivityComponents {
private final Map<Position, Integer> components = new HashMap<>();
public ConnectivityComponents(int[][] matrix) {
find(matrix);
}
private void find(int[][] matrix) {
int component = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 0) { // allowed
Position position = new Position(i, j);
if (!components.containsKey(position)) {
dfs(matrix, position, component++);
}
}
}
}
}
private void dfs(int[][] matrix, Position position, int component) {
components.put(position, component);
getAdjacentPositions(matrix, position).stream().filter(p -> !components.containsKey(p)).forEach(p -> {
dfs(matrix, p, component);
});
}
private List<Position> getAdjacentPositions(int[][] matrix, Position position) {
List<Position> positions = new ArrayList<>();
// up
if (position.x - 1 >= 0 && matrix[position.x - 1][position.y] == 0) {
positions.add(new Position(position.x - 1, position.y));
}
// down
if (position.x + 1 < matrix.length && matrix[position.x + 1][position.y] == 0) {
positions.add(new Position(position.x + 1, position.y));
}
// left
if (position.y - 1 >= 0 && matrix[position.x][position.y - 1] == 0) {
positions.add(new Position(position.x, position.y - 1));
}
// right
if (position.y + 1 < matrix[position.x].length && matrix[position.x][position.y + 1] == 0) {
positions.add(new Position(position.x, position.y + 1));
}
return positions;
}
public boolean hasPath(Position start, Position end) {
Integer startComponent = components.get(start);
Integer endComponent = components.get(end);
return startComponent != null && startComponent.equals(endComponent);
}
private static class Position {
final int x;
final int y;
Position(int x, int y) {
this.x = x;
this.y = y;
}
public boolean equals(Object o) {
if (o == null || o.getClass() != Position.class) {
return false;
}
Position p = (Position) o;
return x == p.x && y == p.y;
}
public int hashCode() {
return 13*x + 23*y;
}
}
public static void main(String[] args) {
int[][] input = new int[][]{{0,0,1,0,1},{0,1,0,0,0},{0,1,1,1,1},{0,1,1,0,0}};
ConnectivityComponents test = new ConnectivityComponents(input);
System.out.println(test.hasPath(new Position(3, 0), new Position(0, 3)));
}
}
we need ALL possible combinations, e.g. 'AB' and 'BA' are two different combinations
public class StringCombinations {
public List<String> getCombinations(char[] input) {
if (input == null) return Collections.emptyList();
return getCombinations(new String(input));
}
private List<String> getCombinations(String input) {
if (input.length() == 1) return Collections.singletonList(input);
List<String> permutations = new ArrayList<>();
String letter = String.valueOf(input.charAt(0));
String remainder = input.substring(1);
List<String> words = getCombinations(remainder);
for (String word : words) {
for (int i = 0; i <= word.length(); i ++) {
permutations.add(insertLetterAt(word, letter, i));
}
}
permutations.add(letter);
permutations.addAll(words);
return permutations;
}
private String insertLetterAt(String word, String letter, int index) {
String prefix = word.substring(0, index);
String postfix = word.substring(index);
return prefix + letter + postfix;
}
}
order statistics problem based on quick sort partitioning
public class OrderedStatistics {
private static class Item implements Comparable<Item> {
String itemId;
int quantitySold;
public Item(String itemId, int quantitySold) {
this.itemId = itemId;
this.quantitySold = quantitySold;
}
public int compareTo(Item other) {
return other.quantitySold - this.quantitySold;
}
}
public String find(List<Item> items, int index) {
if (index <= 0 || index > items.size()) {
throw new IllegalArgumentException("Unexpected index:" + index);
}
return find(new ArrayList<>(items), index - 1, 0, items.size() - 1);
}
private String find(List<Item> items, int index, int from, int to) {
if (from < to) {
int pivotIndex = partition(items, from, to);
if (pivotIndex == index) {
return items.get(index).itemId;
} else if (pivotIndex < index) {
return find(items, index, pivotIndex + 1, to);
} else { // pivotIndex > index
return find(items, index, from, pivotIndex - 1);
}
}
return items.get(from).itemId;
}
private int partition(List<Item> items, int from, int to) {
Item pivot = items.get(to);
int j = from - 1;
for (int i = from; i < to; i++) {
if (less(items.get(i), pivot)) {
j++;
swap(items, j , i);
}
}
j++;
swap(items, j, to);
return j;
}
private boolean less(Item i1, Item i2) {
return i1.compareTo(i2) < 0;
}
private void swap(List<Item> items, int i, int j) {
if (i != j) {
Item temp = items.get(i);
items.set(i, items.get(j));
items.set(j, temp);
}
}
}
1. max possible longest palindrome's length is max even number closest to input's length
2. iterate through all input's sub-strings of length == max possible length
3. if candidate sub-string is palindrome - return it
4. decrement max possible length by 2 (it can only be even) and repeat steps 2-3
public class LongestPalindrome {
public String findLongestPalindrome(String input) {
if (input == null || input.length() == 1) {
return input;
}
// get maximum possible palindrome's length - always even
int palindromeLength = (input.length() % 2 == 0) ? input.length() : input.length() - 1;
while (palindromeLength > 0) {
// iterate all substrings with length == palindromeLength
for (int i = 0, j = palindromeLength; j <= input.length(); i++, j++) {
String candidate = input.substring(i, j);
if (isPalindrome(candidate)) {
return candidate; // longest substring palindrome
}
}
palindromeLength = palindromeLength - 2;
}
return input.substring(0, 1); // no palindromes with length >=2 - return first char
}
private boolean isPalindrome(String input) {
if (input == null || input.length() == 1) {
return true; // base palindrome
}
if (input.length() % 2 == 1) {
return false; // odd strings can NOT be palindromes
}
for (int i = 0, j = input.length() - 1; i < j; i++, j--) {
if (input.charAt(i) != input.charAt(j)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
LongestPalindrome test = new LongestPalindrome();
String input = "abccbbcca";
System.out.println(String.format("Longest palindrome from '%s' is '%s'", input, test.findLongestPalindrome(input)));
}
}
public class ValidString {
private static final Map<Character, Character> brackets = new HashMap<>();
static {
brackets.put('(', ')');
brackets.put('[', ']');
brackets.put('<', '>');
}
public boolean isValid(String input) {
if (input == null || input.isEmpty()) {
return true;
}
char[] elements = input.toCharArray();
Stack<Character> stack = new Stack<>();
Set<Character> openBrackets = brackets.keySet();
Set<Character> closeBrackets = new HashSet<>(brackets.values());
for(char element : elements) {
if (openBrackets.contains(element)) {
stack.push(element);
} else if (closeBrackets.contains(element)) {
Character openElement;
if (stack.isEmpty() || (openElement = stack.pop()) == null) {
return false; // no valid open bracket
} else {
Character closeElement = brackets.get(openElement);
if (closeElement == null) {
return false; // unknown close bracket
} else if (!closeElement.equals(element)) {
return false; // unexpected close bracket
}
}
} else {
// do nothing
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
ValidString test = new ValidString();
System.out.println(test.isValid("<((([dada+-dad])))>"));
}
}
why do you need to call "containsKey" before "remove" ?
"remove" returns null if key is NOT found in map - in such case, you should return "false" and stop checking
I would also use HashSet instead HashMap
similar to lowest common ancestor but for list of node, e.g. employees
public Employee getLCM(Employee employee, String first, String second) {
if (employee == null || employee.reporters == null) {
return null;
}
for (Employee reporter : employee.reporters) {
if (reporter.name.equals(first) || reporter.name.equals(second)) {
return employee;
}
}
Employee firstEmployee = null;
Employee secondEmployee = null;
for (Employee reporter : employee.reporters) {
if (firstEmployee != null) {
secondEmployee = getLCM(reporter, first, second);
if (secondEmployee != null) {
return reporter;
}
} else {
firstEmployee = getLCM(reporter, first, second);
}
}
return firstEmployee;
}
via standard k-way merge
public List<Integer> merge(List<int[]> input) {
List<Integer> result = new ArrayList<>();
int[] indexes = new int[input.size()];
int minElement = Integer.MAX_VALUE;
int minIndex = -1;
while (true) {
for (int i = 0; i < input.size(); i++) {
int lastIndex = indexes[i];
int[] currentArray = input.get(i);
if (lastIndex < currentArray.length) {
if (currentArray[lastIndex] < minElement) {
minElement = currentArray[lastIndex];
minIndex = i;
}
}
}
if (minIndex >= 0) {
indexes[minIndex]++;
result.add(minElement);
minElement = Integer.MAX_VALUE;
minIndex = -1;
} else {
break;
}
}
return result;
}
iterate all columns and eliminate rows with '0', worst case O(n^2)
- zaitcev.anton November 23, 2015