Iuri Sitinschi
BAN USER
Software engineer with 4 years of professional software development experience with Java working on multi-tiered applications. Solid foundation in computer science fundamentals from data structures and algorithms to design patterns and multi-threading. I am highly interested in scalability, performance, reliability, architecture and design.
It could be done using MRU cache.
- Iuri Sitinschi November 25, 2015more than one player :D
- Iuri Sitinschi November 20, 2015I believe that condition should be the "smallest" substring. Otherwise the largest substring would be s1 itself (if it contains all characters from s2).
- Iuri Sitinschi November 20, 2015public class MyQueue<T> {
private Stack<T> inputStack = new Stack<T>();
private Stack<T> outputStack = new Stack<T>();
public void enqueue(T data) {
inputStack.push(data);
}
public T dequeue() {
if (outputStack.isEmpty()) {
if (inputStack.isEmpty()) {
return null;
}
while (!inputStack.isEmpty()) {
outputStack.push(inputStack.pop());
}
}
return outputStack.pop();
}
// peek() and count() are trivial
}
How will you change your solution if we introduce another type of reading?
- Iuri Sitinschi November 18, 2015KMP algorithm is for searching for occurrences of word "b" in "a", but not longest common subsequence.
- Iuri Sitinschi November 17, 2015public String findLCS(String a, String b) {
if (a == null || b == null ||
a.length() == 0 || b.length() == 0) {
return "";
}
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < b.length(); ++i) {
map.put(b.charAt(i), i);
}
String lcs = null;
int count = 0;
for (int i = 0; i < a.length(); ++i) {
if (map.containsKey(a.charAt(i))) {
if (count != 0 && map.get(a.charAt(i - 1)) + 1 == map.get(a.charAt(i))) {
++count;
} else {
count = 1;
}
if (lcs == null || lcs.length() < count) {
lcs = a.substring(i - count + 1, i + 1);
}
} else {
count = 0;
}
}
return lcs;
}
O(N) time, O(N) space
- Iuri Sitinschi November 17, 2015We can calculate sum of arithmetic progression (from 0 to N) and subtract actual sum of input array. Difference is the missing number.
int expectedSum = N * (0 + N) / 2;
int actualSum = sum(array); // trivial
return expectedSum - actualSum;
It is better to call it subsets, because actually combination it is when we choose k something out of n ("C" in combinatorics).
- Iuri Sitinschi October 22, 2015Hi Anton. Combination is when order is not important. So, 'AB' and 'BA' is the same combination.
- Iuri Sitinschi October 22, 2015What if input string has length more than 32?
- Iuri Sitinschi October 22, 2015What if input string has length more than 32?
- Iuri Sitinschi October 22, 2015Is this example valid? "(<str)>"
- Iuri Sitinschi October 05, 2015My O(N^2) solution:
public class LongestPalindrome {
public String find(String s) {
if (s == null || s.length() < 2) {
return s;
}
int maxLength = 0;
int start = 0;
for (int center = 0; center < s.length() - 1; ++center) {
int length = Math.max(findPalindromeLength(s, center), findPalindromeLength(s, center, center + 1));
if (length > maxLength) {
maxLength = length;
start = center - maxLength / 2;
if (maxLength % 2 == 0) {
start += 1;
}
}
}
return s.substring(start, start + maxLength);
}
private int findPalindromeLength(String s, int center) {
int length = 1;
return length + findPalindromeLength(s, center - 1, center + 1);
}
private int findPalindromeLength(String s, int i1, int i2) {
int length = 0;
while (i1 >= 0 && i2 < s.length() && s.charAt(i1) == s.charAt(i2)) {
length += 2;
--i1;
++i2;
}
return length;
}
}
I want to mention that there exists more sophisticated O(N) solution called "Manacher".
- Iuri Sitinschi October 01, 2015Pre-order, in-order, post-order traversal?
- Iuri Sitinschi September 25, 2015public class Node {
...
public boolean isBST() {
boolean valid = true;
if (left != null) {
if (left.data <= data) {
valid = left.isBST();
} else {
return false;
}
}
if (!valid) {
return false;
}
if (right != null) {
if (right.data > data) {
valid = right.isBST();
} else {
return false;
}
}
return valid;
}
}
O(N) time, O(1) space
- Iuri Sitinschi September 24, 2015import java.util.Map;
import java.util.HashMap;
public class UniqueWords {
public int count(String s) {
Map<String, Integer> words = new HashMap<>();
int lastSpace = -1;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == ' ') {
count(s, lastSpace + 1, i, words);
lastSpace = i;
}
}
count(s, lastSpace + 1, s.length(), words);
int count = 0;
for (String word : words.keySet()) {
if (words.get(word) == 1) {
++count;
}
}
return count;
}
private void count(String s, int start, int end, Map<String, Integer> words) {
String word = s.substring(start, end);
Integer count = words.get(word);
if (count == null) {
count = 0;
}
words.put(word, count + 1);
}
}
O(N) time, O(N) space
- Iuri Sitinschi September 24, 2015import java.util.List;
import java.util.ArrayList;
class Permutations {
private static List<String> permutations(String s) {
List<String> permutations = new ArrayList<String>();
if (s == null) {
return null;
} else if (s.length() == 0) {
permutations.add("");
return permutations;
}
List<String> remainder = permutations(s.substring(1));
for (String permutation : remainder) {
for (int i = 0; i <= permutation.length(); ++i) {
permutations.add(insertCharAt(permutation, s.charAt(0), i));
}
}
return permutations;
}
private static String insertCharAt(String s, char c, int i) {
return new StringBuilder(s).insert(i, c).toString();
}
}
O(N!) time and space. The problem cannot be solved in linear time because we have N! solutions (as Technoapurva said).
- Iuri Sitinschi September 24, 2015O(N + M) time, O(N + M) space
import java.util.ArrayList;
import java.util.List;
public class ListUtils {
public List<Integer> union(List<Integer> list1, List<Integer> list2) {
if (list1 == null || list2 == null) {
throw new IllegalArgumentException();
}
return merge(list1, list2);
}
private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
List<Integer> mergedList = new ArrayList<>();
int i1 = 0;
int i2 = 0;
while (i1 + i2 != list1.size() + list2.size()) {
if (i1 == list1.size()) {
mergedList.add(list2.get(i2++));
} else if (i2 == list2.size()) {
mergedList.add(list1.get(i1++));
} else if (list1.get(i1) < list2.get(i2)) {
mergedList.add(list1.get(i1++));
} else {
mergedList.add(list2.get(i2++));
}
}
return mergedList;
}
public List<Integer> intersection(List<Integer> list1, List<Integer> list2) {
if (list1 == null || list2 == null) {
throw new IllegalArgumentException();
}
return intersect(list1, list2);
}
private List<Integer> intersect(List<Integer> list1, List<Integer> list2) {
List<Integer> mergedList = new ArrayList<>();
int i1 = 0;
int i2 = 0;
while (i1 + i2 != list1.size() + list2.size()) {
if (i1 == list1.size() || i2 == list2.size()) {
break;
} else if (list1.get(i1) == list2.get(i2)) {
mergedList.add(list1.get(i1));
++i1;
++i2;
} else if (list1.get(i1) < list2.get(i2)) {
++i1;
} else {
++i2;
}
}
return mergedList;
}
}
I really like Malinbupt's approach. Here it is in Java:
public class Log {
private static final int MAX = 123124;
private int start;
private int end;
private int usage;
public Log(int start, int end, int usage) {
this.start = start;
this.end = end;
this.usage = usage;
}
public static int findPeak(Log... logs) {
int [] usageArray = new int[MAX + 2];
for (int i = 0; i < logs.length; ++i) {
usageArray[logs[i].start] += logs[i].usage;
usageArray[logs[i].end + 1] -= logs[i].usage;
}
int maxSoFar = usageArray[0];
int time = 0;
for (int i = 1; i <= MAX; ++i) {
usageArray[i] += usageArray[i - 1];
if (usageArray[i] > maxSoFar) {
maxSoFar = usageArray[i];
time = i;
}
}
return time;
}
}
O(N) time, O(N) space
- Iuri Sitinschi September 23, 2015Below solution uses Shunting-yard algorithm to convert common expression to Reverse Polish Notation (a.k.a Postfix Notation) and then calculates it. It has O(N) time and O(N) complexities and calculates expressions like:
"2 + (3*5 - 3) / 3"
"1 - 2*((3 - 5) / (-2)) + 2"
"1.5 - 2*((10 - 5) / (-2)) + 2.3"
import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class AdvanceCalculator {
public double calc(String expression) {
String exp = prepareExpression(expression);
Queue<String> queue = convertToRPN(exp);
return calc(queue);
}
// remove unnecessary symbols and deal with unary minuses
private String prepareExpression(String expression) {
String exp = expression.trim().replaceAll(" ","");
// deal with unary '-'
exp = exp.replaceAll("\\(-", "(0-");
if (exp.charAt(0) == '-') {
exp = "0-" + exp;
}
return exp;
}
// convert expression to postfix notation using Shunting-yard algorithm
private Queue<String> convertToRPN(String exp) {
Stack<String> stack = new Stack<>();
Queue<String> queue = new LinkedList<>();
StringTokenizer st = new StringTokenizer(exp, "+-*/()", true);
while (st.hasMoreTokens()) {
String e = st.nextToken();
if (isOperator(e)) {
switch(e) {
case "+":
case "-":
case "*":
case "/": while (!stack.isEmpty() &&
!stack.peek().equals("(") &&
getOperatorPriority(e) <= getOperatorPriority(stack.peek())) {
queue.add(stack.pop());
}
stack.push(e);break;
case ")": while(!stack.peek().equals("(")) {
queue.add(stack.pop());
}
stack.pop(); break;
case "(": stack.push(e);break;
}
} else {
queue.add(e);
}
}
while (!stack.isEmpty()) {
queue.add(stack.pop());
}
return queue;
}
// calculate postfix notation (a.k.a Reverse Polish Notation)
private double calc(Queue<String> queue) {
Stack<Double> calc = new Stack<>();
while (!queue.isEmpty()) {
String e = queue.poll();
if (isOperator(e)) {
double v2 = calc.pop();
double v1 = calc.pop();
switch(e) {
case "+": calc.push(v1 + v2);break;
case "-": calc.push(v1 - v2);break;
case "*": calc.push(v1 * v2);break;
case "/": calc.push(v1 / v2);break;
}
} else {
double value = Double.valueOf(e);
calc.push(value);
}
}
return calc.pop();
}
private boolean isOperator(String s) {
switch(s) {
case "+": return true;
case "-": return true;
case "*": return true;
case "/": return true;
case "(": return true;
case ")": return true;
default: return false;
}
}
private int getOperatorPriority(String s) {
switch(s) {
case "+": return 1;
case "-": return 1;
case "*": return 2;
case "/": return 2;
default: return 0;
}
}
}
import java.util.Map;
import java.util.HashMap;
public class Node<T> {
private T data;
private Node<T> left;
private Node<T> right;
public void printFirstLastOnEachLevel() {
Map<Integer, Node<T>> firstNodes = new HashMap<>();
Map<Integer, Node<T>> lastNodes = new HashMap<>();
int maxLeft = populate(this.left, firstNodes, lastNodes, 1);
int maxRight = populate(this.right, firstNodes, lastNodes, 1);
System.out.println(data);
int max = Math.max(maxLeft, maxRight);
for (int depth = 1; depth <= max; ++depth) {
Node<T> first = firstNodes.get(depth);
Node<T> last = lastNodes.get(depth);
if (first != null) {
System.out.print(" " + first.data);
}
if (last != null) {
System.out.print(" " + last.data);
}
}
}
private int populate(Node<T> node, Map<Integer, Node<T>> firstNodes, Map<Integer, Node<T>> lastNodes, int depth) {
if (node == null) {
return depth - 1;
} else {
if (firstNodes.get(depth) == null) {
firstNodes.put(depth, node);
} else {
lastNodes.put(depth, node);
}
int maxLeft = populate(node.left, firstNodes, lastNodes, depth + 1);
int maxRight = populate(node.right, firstNodes, lastNodes, depth + 1);
return Math.max(maxLeft, maxRight);
}
}
}
O(N) time, O(logN) space
- Iuri Sitinschi September 22, 2015import java.util.Arrays;
import java.lang.reflect.Array;
import java.lang.Comparable;
public class OrderStatistic<T extends Comparable<T>> {
public T findKthLargest(T [] array, int k) {
validateInputParameters(array, k);
return findKthLargest(array, 0, array.length, k);
}
private void validateInputParameters(T [] array, int k) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array is null or empty");
}
if (k < 0 || k >= array.length) {
throw new IllegalArgumentException("Wrong k = " + k);
}
}
private T findKthLargest(T [] array, int l, int r, int k) {
T medianOfMedians = findMedianOfMedians(array, l, r);
int pos = partition(array, l, r, medianOfMedians);
if (array.length - k - 1 == pos) {
return array[array.length - k - 1];
} else if (array.length - k - 1 > pos) {
return findKthLargest(array, pos + 1, r, k);
} else {
return findKthLargest(array, l, pos, k) ;
}
}
private T findMedianOfMedians(T [] array, int l, int r) {
int n = r - l;
int mediansSize = n / 5;
if (n % 5 != 0) {
++mediansSize;
}
T [] medians = (T []) Array.newInstance(array[0].getClass(), mediansSize);
int i = l;
int index = 0;
while (i + 5 <= r) {
medians[index++] = findMedian(array, i, i + 5);
i += 5;
}
if (i != r) {
medians[index] = findMedian(array, i, r);
}
if (medians.length == 1) {
return medians[0];
} else {
return findKthLargest(medians, 0, medians.length, medians.length / 2);
}
}
private T findMedian(T [] array, int l, int r) {
Arrays.sort(array, l, r);
return array[l + (r - l) / 2];
}
private int partition(T [] array, int l, int r, T pivot) {
int index = l;
for (int i = l; i < r; ++i) {
if (array[i].compareTo(pivot) < 0) {
T t = array[i];
array[i] = array[index];
array[index] = t;
++index;
}
}
return index;
}
}
This problem is called "kth order statistics". Above solution has O(N) time and O(N) space complexities.
- Iuri Sitinschi September 22, 2015A* algorithm
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.Queue;
import java.util.PriorityQueue;
public class AStar {
private Queue<Point> queue;
private Map<Integer, Point> points;
private Set<Point> visited;
private int [][] adjacencyMatrix;
private Point end;
class Point implements Comparable<Point> {
int x;
int y;
int min; // min distance
int hash; // approximate distance to end point
Point predeccessor;
Point(int x, int y) {
this.x = x;
this.y = y;
min = Integer.MAX_VALUE;
if (end != null) {
hash = (int) Math.sqrt(Math.pow(x - end.x, 2) + Math.pow(y - end.y, 2));
}
}
@Override
public int compareTo(Point p) {
return Integer.valueOf(min + hash).compareTo(p.min + p.hash);
}
@Override
public boolean equals(Object o) {
if (o == null || o.getClass() != Point.class) {
return false;
}
Point p = (Point) o;
if (x == p.x && y == p.y) {
return true;
}
return false;
}
@Override
public int hashCode() {
return 13*x + 23*y;
}
}
public int findShortestPath(int [][] adjacencyMatrix, int x1, int y1, int x2, int y2) {
if (adjacencyMatrix == null) {
throw new IllegalArgumentException("Matrix is null");
}
queue = new PriorityQueue<>();
points = new HashMap<>();
visited = new HashSet<>();
this.adjacencyMatrix = adjacencyMatrix;
end = new Point(x2, y2);
Point start = new Point(x1, y1);
start.min = 0;
queue.add(start);
points.put(x1*adjacencyMatrix.length + y1, start);
Point cur = null;
while (!(cur = queue.poll()).equals(end)) {
if (!visited.contains(cur)) {
visit(cur, cur.x - 1, cur.y);
visit(cur, cur.x, cur.y - 1);
visit(cur, cur.x, cur.y + 1);
visit(cur, cur.x + 1, cur.y);
visited.add(cur);
}
}
cur = points.get(x2*adjacencyMatrix.length + y2); // end point
int shortestDistance = cur.min;
System.out.println("Shortest path: ");
while (cur != null) {
System.out.print(" (" + cur.x + ", " + cur.y + ")");
cur = cur.predeccessor;
}
return shortestDistance;
}
private void visit(Point cur, int i, int j) {
if (i >= 0 && i < adjacencyMatrix.length && j >= 0 && j < adjacencyMatrix[0].length && adjacencyMatrix[i][j] != 0) {
Point p = points.get(i*adjacencyMatrix.length + j);
boolean fUpdate = false;
if (p == null) {
p = new Point(i, j);
fUpdate = true;
} else if (cur.min + adjacencyMatrix[i][j] < p.min) {
fUpdate = true;
queue.remove(p);
}
if (fUpdate) {
p.min = cur.min + adjacencyMatrix[i][j];
p.predeccessor = cur;
points.put(i*adjacencyMatrix.length + j, p);
queue.add(p);
}
}
}
}
public class DuplicatesRemover<T> {
public int remove(List<T> list) {
if (list == null || list.size() < 2) {
return list.size(); // nothing to do
}
Map<T, Boolean> map = new HashMap<>();
for (T t : list) {
if (map.get(t) == null) {
map.put(t, true);
}
}
list.clear();
list.addAll(map.keySet());
return list.size();
}
}
O(N) time, O(N) space
- Iuri Sitinschi September 18, 2015Java code:
public class PrimeNumber {
public void print(int a, int n) {
while (n != 0) {
if (isPrime(++a)) {
--n;
}
}
System.out.println(a);
}
private boolean isPrime(int a) {
if (a == 2) {
return true;
} else if(a < 2 || a % 2 == 0) {
return false;
}
for (int i = 3; i*i <= a; i += 2) {
if (a % i == 0) {
return false;
}
}
return true;
}
}
Quadratic time, constant space complexity. If we have maximum limit for output prime number, we could use Sieve of Eratosthenes to calculate all prime numbers beforehand. Thus, complexity would be O(n log log n) time and O(N) space.
- Iuri Sitinschi September 17, 2015import java.util.Map;
import java.util.Set;
import java.util.Queue;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.lang.Comparable;
public class Dijkstra {
class Point implements Comparable<Point>{
int x;
int y;
int min;
Point predeccessor;
Point(int x, int y) {
this.x = x;
this.y = y;
min = Integer.MAX_VALUE;
predeccessor = null;
}
@Override
public int compareTo(Point p) {
if (min < p.min) {
return -1;
} else if (min > p.min) {
return 1;
} else {
return 0;
}
}
@Override
public boolean equals(Object o) {
if (o != null && o.getClass() == Point.class) {
Point point = (Point) o;
if (this.x == point.x && this.y == point.y) {
return true;
}
}
return false;
}
@Override
public int hashCode() {
return 13*x +23*y;
}
}
public void printShortestPath(int [][] array, int x1, int y1, int x2, int y2) {
Queue<Point> heap = new PriorityQueue<>();
Point source = new Point(x1, y1);
source.min = 0;
Point dest = new Point(x2, y2);
heap.add(source);
Map<Integer, Point> map = new HashMap<>();
map.put(x1*array.length + y1, source);
heap.add(source);
Set<Point> visited = new HashSet<>();
Point cur = null;
while (!(cur = heap.poll()).equals(dest)) {
if (!visited.contains(cur)) {
visit(cur, array, cur.x - 1, cur.y, map, heap);
visit(cur, array, cur.x, cur.y - 1, map, heap);
visit(cur, array, cur.x, cur.y + 1, map, heap);
visit(cur, array, cur.x + 1, cur.y, map, heap);
visited.add(cur);
}
if (heap.isEmpty()) {
System.out.println("Point are not connected!");
return;
}
}
cur = map.get(x2*array.length + y2);
while (cur != null) {
System.out.println("(" + cur.x + ", " + cur.y + ")");
cur = cur.predeccessor;
}
}
private void visit(Point cur, int [][] array, int i, int j, Map<Integer, Point> map, Queue<Point> heap) {
if (i >= 0 && i < array.length && j >= 0 && j < array[0].length && array[i][j] != 0) {
Point p = map.get(i*array.length + j);
boolean fUpdated = false;
if (p == null) {
p = new Point(i, j);
p.min = cur.min + array[i][j];
fUpdated = true;
} else if (p.min > cur.min + array[i][j]) {
p.min = cur.min + array[i][j];
heap.remove(p);
fUpdated = true;
}
if (fUpdated) {
p.predeccessor = cur;
map.put(i*array.length + j, p);
heap.add(p);
}
}
}
public static void main(String [] args) {
int [][] array = new int [][] {
{0,0,0,1,0,1},
{0,0,0,1,0,1},
{1,1,1,1,0,1},
{0,0,1,1,0,1},
{0,1,1,1,0,1},
{1,1,0,1,0,1},
{1,1,0,1,0,1}
};
Dijkstra dijkstra = new Dijkstra();
dijkstra.printShortestPath(array, 6, 0, 0, 3);
}
}
O(NxM) space. Quadratic time complexity because of heap.remove(p) (is liniar). If implement own version of min-heap with ability to update priority, algorithm becomes linearithmic.
- Iuri Sitinschi September 16, 2015Can be O(1) space if we can modify input array
- Iuri Sitinschi September 16, 2015public class ConsecutiveSegments {
public void print(int [] array) {
if (array == null || array.length == 0) {
System.out.println("Nothing to print!");
} else if (array.length == 1) {
System.out.println(array[0]);
} else {
boolean consecutive = false;
for (int i = 1; i < array.length; ++i) {
if (array[i] != array[i - 1] + 1) {
if (consecutive) {
System.out.print("-");
}
System.out.print(array[i - 1] + ", ");
consecutive = false;
} else if (!consecutive) {
consecutive = true;
System.out.print(array[i - 1]);
}
}
if (consecutive) {
System.out.print("-");
}
System.out.print(array[array.length - 1]);
}
}
}
O(N) time, O(1) space
- Iuri Sitinschi September 16, 2015public class Islands {
private static final int SEA = 0;
private static final int LAND = 1;
public int countIslands(int [][] map) {
if (map == null || map.length == 0 || map[0].length == 0) {
return 0;
}
boolean [][] visited = new boolean[map.length][map[0].length];
int counter = 0;
for (int i = 0; i < map.length; ++i) {
for (int j = 0; j < map[0].length; ++j) {
if (map[i][j] == LAND && !visited[i][j]) {
++counter;
markVisited(map, visited, i, j);
}
}
}
return counter;
}
private void markVisited(int [][] map, boolean [][] visited, int i, int j) {
if (i >= 0 && i < map.length && j >= 0 && j < map[0].length) {
if (map[i][j] == LAND && !visited[i][j]) {
visited[i][j] = true;
markVisited(map, visited, i - 1, j);
markVisited(map, visited, i, j - 1);
markVisited(map, visited, i, j + 1);
markVisited(map, visited, i + 1, j);
}
}
}
}
// O(n*m) time, O(n*m) space
Hi, you misunderstood that algorithm is iterative. So, no recursion
- Iuri Sitinschi September 15, 2015import java.util.List;
import java.util.ArrayList;
import java.util.Stack;
import java.util.Arrays;
public class Node {
private int val;
private List<Node> children;
public Node(int val) {
this.val = val;
}
public void printWithIterativePostOrderTraversal() {
Stack<Integer> print = new Stack<>();
Stack<Node> traverse = new Stack<>();
traverse.push(this);
while (!traverse.isEmpty()) {
Node n = traverse.pop();
print.push(n.val);
if (n.children != null) {
for (Node child : n.children) {
traverse.push(child);
}
}
}
while(!print.isEmpty()) {
System.out.print(" " + print.pop());
}
}
public void setChildren(Node... children) {
this.children = Arrays.asList(children);
}
}
I believe you should use another stack instead of queue
- Iuri Sitinschi September 15, 2015
You don't need max heap here. Hash table is enough for this task. Just store current MSP in a variable and update it if necessary.
- Iuri Sitinschi November 25, 2015