igor.s.sokolov
BAN USERIf we are allowed to assume that the numbers are not bigger than K (for example 1000 or something like that) then we can use union-find data structure instead of hash maps. UF allows us to union and find intersection in amortized O(1). As a result what we need is to check union in two nested loops for first elements in each LinkedList. UF requires O(K) memory. Time complexity is bound above by double loop to go through all elements in lists once -> O(N * M).
import java.util.*;
/**
* Created by Igor_Sokolov on 6/16/2015.
*/
public class CareerCup_5991240778645504 {
private static final int K = 1000;
private static class UF {
int[] parent;
int[] rank;
public UF(int size) {
this.parent = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
this.rank = new int[size];
Arrays.fill(rank, 1);
}
public void union(int i, int j) {
int pi = find(i);
int pj = find(j);
if (rank[pi] == rank[pj]) {
parent[pi] = pj;
rank[pj]++;
} else if (rank[pi] > rank[pj]) {
parent[pj] = pi;
} else {
parent[pi] = pj;
}
}
public int find(int j) {
int p = j;
while (parent[p] != p) {
p = parent[p];
}
while (parent[j] != p) {
int x = parent[j];
parent[j] = p;
j = x;
}
return p;
}
}
public static void main(String[] args) {
LinkedList<Integer>[] lists = prepareData();
List<List<Integer>> result = findIntersections(lists);
printResult(result);
}
private static void printResult(List<List<Integer>> result) {
for (List<Integer> list: result) {
StringBuilder sb = new StringBuilder();
for (int i: list) {
sb.append(i).append(' ');
}
System.out.println(sb);
}
}
private static LinkedList<Integer>[] prepareData() {
LinkedList<Integer>[] lists = new LinkedList[5];
for (int i = 0; i < lists.length; i++) {
lists[i] = new LinkedList<>();
}
lists[0].addAll(Arrays.asList(1, 2, 3, 4, 5));
lists[1].addAll(Arrays.asList(6, 7, 8, 4, 5));
lists[2].addAll(Arrays.asList(8, 9, 10, 11, 12));
lists[3].addAll(Arrays.asList(13, 14, 15, 12));
lists[4].addAll(Arrays.asList(16, 17, 18 ));
return lists;
}
private static List<List<Integer>> findIntersections(LinkedList<Integer>[] input) {
UF uf = new UF(K);
final int N = input.length;
for (int i = 0; i < N; i++) {
int head = input[i].getFirst();
for (int v : input[i]) {
uf.union(head, v);
}
}
boolean[] visited = new boolean[N];
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < N; i++) {
if (!visited[i]) {
visited[i] = true;
int x = input[i].getFirst();
List<Integer> list = new ArrayList<>();
list.add(x);
for (int j = i + 1; j < N; j++) {
int y = input[j].getFirst();
if (uf.find(x) == uf.find(y)) {
visited[j] = true;
list.add(y);
}
}
result.add(list);
}
}
return result;
}
}
"mid = (lo + hi) / 2;" here is a classical issue with overflow. Actually such bug was in implementation of sort algorithm in java. If we have lo and hi close to integer max value it may lead to overflow.
- igor.s.sokolov June 16, 2015I don't know how to replay for an comment, so I am answering here:
>> Nicely done Why are you sorting the array using prepareData? The array is already sorted?
prepareData is just a generator. It prepare random input data in format as you descibed in the task. The solution is in the method binarySearch().
>> This fails for [0, 0, 0]. Returns 2.
an odd, I ran my code with your example and I see the answer:
[0, 0, 0]
3
You can check it via copy-paste the code below:
import java.util.Arrays;
import java.util.Random;
/**
* Created by Igor_Sokolov on 6/16/2015.
*/
public class CareerCup_5766344614084608 {
public static void main(String[] args) {
int[] a = {0, 0, 0};
System.out.println(Arrays.toString(a));
int pos = binarySearch(a);
System.out.print(pos);
}
private static int binarySearch(int[] a) {
int l = 0;
int r = a.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] < 1) {
l = m + 1;
} else {
r = m - 1;
}
}
return l;
}
}
This is a task for binary search. Time complexity is O(LogN).
import java.util.Arrays;
import java.util.Random;
/**
* Created by Igor_Sokolov on 6/16/2015.
*/
public class CareerCup_5766344614084608 {
public static void main(String[] args) {
int[] a = prepareData(10);
System.out.println(Arrays.toString(a));
int pos = binarySearch(a);
System.out.print(pos);
}
private static int binarySearch(int[] a) {
int l = 0;
int r = a.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (a[m] < 1) {
l = m + 1;
} else {
r = m - 1;
}
}
return l;
}
private static int[] prepareData(int N) {
final Random rand = new Random();
int[] a = new int[N];
for (int i = 0; i < N; i++) {
a[i] = rand.nextBoolean() ? 1 : 0;
}
Arrays.sort(a);
return a;
}
}
If you know Java good and it is allowed to be lazy, we can reuse LinkedHashMap to achieve the desired behavior.
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Function;
/**
* Created by sis on 6/4/15.
*/
public class CareerCup_5735022524891136 {
public static void main(String[] args) {
LRU<Integer, Integer> cache = new LRU<>(2, s -> {
System.out.println(s);
return s;
});
// new value
cache.apply(1);
// use cache
cache.apply(1);
// new value
cache.apply(2);
// new value, 1 is pushed from cache
cache.apply(3);
// use cache
cache.apply(2);
// new value because we removed 1 previously
cache.apply(1);
}
/**
* LRU implementation as a pattern 'Proxy'.
* @param <K> key type
* @param <V> value type
*/
public static final class LRU<K, V> implements Function<K, V> {
private final LinkedHashMap<K, V> map;
private final Function<K, V> realSubject;
public LRU(final int size, Function<K, V> realSubject) {
this.realSubject = realSubject;
this.map = new LinkedHashMap(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return this.size() == size + 1;
}
};
}
@Override
public V apply(K k) {
V v = map.get(k);
if (v == null) {
v = realSubject.apply(k);
map.put(k, v);
}
return v;
}
}
}
Maybe I understood the task not fully correct, but as for me the goal was to build a search of secret combination of n digits such way that we use minimum of key presses. My solution uses a bitset to keep which sequence of numbers we already visited and which not. Actually we just go through all int values from 0 to 10^n and check whether we have already visit the current number or not. If we add a new n-digits to the sequence we concatenate it with previous n digits and visit all sub-strings.
import java.util.BitSet;
/**
* Created by sis on 5/31/15.
*/
public class CareerCup_5126565916573696 {
public static void main(String[] args) {
new Problem(5).naive();
}
static class Problem {
private int length;
private final BitSet visited;
private String previousString;
private int totalKeys;
private int duplications;
private int maxValue;
Problem(int length) {
this.length = length;
this.maxValue = (int) Math.pow(10.0, length);
this.visited = new BitSet(maxValue);
}
private void innerCheck(String currentString) {
if (previousString != null) {
String concat = previousString + currentString;
for (int i = 1; i < concat.length() - length; i++) {
checkAndVisit(concat.substring(i, i + length));
}
}
checkAndVisit(currentString);
previousString = currentString;
}
private void checkAndVisit(String str) {
int value = Integer.valueOf(str);
if (visited.get(value)) {
// uncomment this line to see duplicated values
// System.out.printf("!!!! duplication: %05d %n", value);
duplications++;
} else {
visited.set(value, true);
}
}
public void naive() {
final String fmt = "%0" + length + "d";
for (int i = 0; i < maxValue; i++) {
if (!visited.get(i)) {
String str = String.format(fmt, i);
innerCheck(str);
totalKeys += length;
}
}
System.out.printf("Total duplications: %d%n", duplications);
System.out.printf("Total keys: %d%n", totalKeys);
}
}
}
Here was a good idea to use HashSet, however the time complexity is presented for that solution not sharp, actually it should be O(N + M) where N is number of elements in array and M is offset which we have to go from min value in the array to the next omitted value if we sorted it. In some cases M could be significant bigger than N.
The following solution works guaranteed O(N). We just use one more HashSet to store potential answer to our question:
import java.util.HashSet;
/**
* Created by sis on 5/27/15.
*/
public class CareerCup_5758677862580224 {
public static void main(String[] args) {
int[] a = {-1, 4, 5, -23, 24};
int m = getNotPresentedMin(a);
System.out.println(m);
}
private static int getNotPresentedMin(int[] a) {
if (a.length == 0) {
throw new IllegalArgumentException();
}
HashSet<Integer> real = new HashSet<>();
HashSet<Integer> potential = new HashSet<>();
for (int i = 0; i < a.length; i++) {
real.add(a[i]);
potential.add(a[i] + 1);
}
int min = Integer.MAX_VALUE;
for (int i: potential) {
if (!real.contains(i)) {
min = Math.min(min, i);
}
}
return min;
}
}
One more option is to use Union-Find data structure that allows us to perform union and find operations in amortized O(1) (more precisely the time complexity is counted as inverse Ackermann function). So we can go through all nodes of grids and union them if m[x][y] == 1 and the are adjacent. One additional pass we need to go through union-find data structure and place point from one union to map and return it. The total time complexity and memory is O (M * N).
import java.util.*;
import java.util.stream.Collectors;
/**
* Created by sis on 5/26/15.
*/
public class CareerCup_5671254340141056 {
private static class Point {
int x, y;
public Point(int y, int x) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "(" + (x + 1) + "," + (y + 1) +')';
}
}
public static void main(String[] args) {
int[][] m = {
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0}
};
List<List<Point>> res = ufApproach(m);
for (int i = 0; i < res.size(); i++) {
System.out.printf("#%d {", i);
res.get(i).forEach(System.out::print);
System.out.println("}");
}
}
private static class UF {
int[] parent;
int[] rank;
public UF(int size) {
this.parent = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
this.rank = new int[size];
Arrays.fill(rank, 1);
}
public void union(int i, int j) {
int pi = find(i);
int pj = find(j);
if (rank[pi] == rank[pj]) {
parent[pi] = pj;
rank[pj]++;
} else if (rank[pi] > rank[pj]) {
parent[pj] = pi;
} else {
parent[pi] = pj;
}
}
public int find(int j) {
int p = j;
while (parent[p] != p) {
p = parent[p];
}
while (parent[j] != p) {
int x = parent[j];
parent[j] = p;
j = x;
}
return p;
}
}
private static List<List<Point>> ufApproach(int[][] m) {
if (m.length == 0 || m[0].length == 0) {
throw new IllegalArgumentException();
}
int H = m.length;
int W = m[0].length;
int[][] offsets = {{-1, 0}, {-1, -1}, {0, -1}, {1, -1}};
UF uf = new UF(W * H);
for (int ys = 0; ys < H; ys++) {
for (int xs = 0; xs < W; xs++) {
if (m[ys][xs] == 1) {
int value1 = ys * W + xs;
for (int i = 0; i < offsets.length; i++) {
int x = xs + offsets[i][0];
int y = ys + offsets[i][1];
if (x >= 0 && x < W && y >= 0 && m[y][x] == 1) {
int value2 = y * W + x;
uf.union(value1, value2);
}
}
}
}
}
HashMap<Integer, List<Point>> subres = new HashMap<>();
for (int i = 0; i < uf.parent.length; i++) {
int p = uf.find(i);
if (p != i || uf.rank[i] > 1) {
List<Point> points = subres.get(p);
if (points == null) {
points = new ArrayList<>();
}
points.add(new Point(i / W, i % W));
subres.put(p, points);
}
}
return subres.values().stream().collect(Collectors.toList());
}
}
I didn't find ability to answer to a particular comment, so answering just below.
>> Can try the same in the recursion?
Yes, but in this case you will get DFS (deep). From asymptotic perspective this is equal O(N * M), but because DFS is to aggressive and tries to go deeper and deeper in recursion and ultimately we could have one recursive call for each point in stack if we have full '1' field. BFS is slightly modest and stores only border (perimeter) points.
This is a classical BFS task in a grid graph.
import java.util.*;
/**
* Created by sis on 5/26/15.
*/
public class CareerCup_5671254340141056 {
private static class Point {
int x, y;
public Point(int y, int x) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "(" + (x + 1) + "," + (y + 1) +')';
}
}
public static void main(String[] args) {
int[][] m = {
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 1, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0}
};
List<List<Point>> res = getAdjacentNodes(m);
for (int i = 0; i < res.size(); i++) {
System.out.printf("#%d {", i);
res.get(i).forEach(System.out::print);
System.out.println("}");
}
}
private static List<List<Point>> getAdjacentNodes(int[][] m) {
if (m.length == 0 || m[0].length == 0) {
throw new IllegalArgumentException();
}
List<List<Point>> res = new ArrayList<>();
int H = m.length;
int W = m[0].length;
boolean[][] visit = new boolean[H][W];
int[][] offsets = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
Queue<Point> q = new LinkedList<>();
for (int ys = 0; ys < H; ys++) {
for (int xs = 0; xs < W; xs++) {
if (!visit[ys][xs] && m[ys][xs] == 1) {
visit[ys][xs] = true;
q.add(new Point(ys,xs));
List<Point> subres = new ArrayList<>();
while (!q.isEmpty()) {
Point p = q.remove();
subres.add(p);
for (int i = 0; i < offsets.length; i++) {
int y = p.y + offsets[i][0];
int x = p.x + offsets[i][1];
if (x >= 0 && x < W && y >= 0 && y < H && !visit[y][x] && m[y][x] == 1) {
visit[y][x] = true;
q.add(new Point(x, y));
}
}
}
res.add(subres);
}
}
}
return res;
}
}
time O(N * M) and memory O(N * M).
- igor.s.sokolov May 27, 2015Similar recursive approach with a little shorter check of null vs not null:
/**
* Created by Igor_Sokolov on 5/18/2015.
*/
public class CareerCup_5092252147777536 {
private static class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return String.valueOf(value);
}
Node setLeft(Node left) {
this.left = left;
return this;
}
Node setRight(Node right) {
this.right = right;
return this;
}
}
private static Node prepareData() {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(2);
Node node4 = new Node(3);
Node node5 = new Node(4);
Node node6 = new Node(3);
Node node7 = new Node(4);
node1.setLeft(node2).setRight(node3);
node2.setLeft(node4).setRight(node5);
node3.setLeft(node7).setRight(node6);
return node1;
}
public static void main(String[] args) {
Node root = prepareData();
System.out.println(checkFoldable(root));
}
private static boolean checkFoldable(Node root) {
if (root == null) {
return true;
}
return checkFoldable(root.left, root.right);
}
private static boolean checkFoldable(Node root1, Node root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 != null ^ root2 != null || root1.value != root2.value) {
return false;
}
return checkFoldable(root1.left, root2.right) && checkFoldable(root1.right, root2.left);
}
}
Similar to what the folk here posted, but maybe slightly more structured and human-readable, but of course longer:
import java.util.Deque;
import java.util.LinkedList;
/**
* Created by Igor_Sokolov on 5/18/2015.
*/
public class CareerCup_5177676899811328 {
private static class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return String.valueOf(value);
}
}
private static Node prepareData() {
Node one = new Node(1);
Node two = new Node(2);
Node three = new Node(3);
Node four = new Node(4);
Node five = new Node(5);
Node six = new Node(6);
Node seven = new Node(7);
Node eight = new Node(8);
Node nine = new Node(9);
one.left = two;
one.right = three;
two.left = four;
two.right = five;
three.left = six;
three.right = seven;
four.left = eight;
four.right = nine;
return one;
}
public static void main(String[] args) {
Node root = prepareData();
printZigzag(root);
}
private static class Entry {
Node node;
int level;
public Entry(Node node) {
this.node = node;
this.level = 0;
}
public Entry(Node node, int level) {
this.node = node;
this.level = level;
}
public Entry subLeft() {
return (this.node.left != null) ? new Entry(this.node.left, this.level + 1): null;
}
public Entry subRight() {
return (this.node.right != null) ? new Entry(this.node.right, this.level + 1) : null;
}
}
private static void printZigzag(Node root) {
Deque<Entry>[] lists = new Deque[] {new LinkedList<>(), new LinkedList<>()};
add(lists, new Entry(root));
int level = 0;
while (!isEmpty(lists)) {
Entry e = enqueue(lists, level);
if (level != e.level) {
System.out.println();
}
System.out.print(e.node + " ");
Entry subLeft = e.subLeft();
if (subLeft != null) {
add(lists, subLeft);
}
Entry subRight = e.subRight();
if (subRight != null) {
add(lists, subRight);
}
level = e.level;
}
}
private static Entry enqueue(Deque<Entry>[] lists, int level) {
int idx = level % 2;
if (lists[idx].isEmpty()) {
return lists[(level + 1) % 2].removeFirst();
} else {
return lists[idx].removeFirst();
}
}
private static boolean isEmpty(Deque<Entry>[] lists) {
return lists[0].isEmpty() && lists[1].isEmpty();
}
private static void add(Deque<Entry>[] lists, Entry entry) {
if (entry.level % 2 == 0) {
lists[0].addFirst(entry);
} else {
lists[1].addLast(entry);
}
}
}
Your time complexity is not accurate. Each loop you have to go through candles and decrease value by one, so in worst case you have to perform O(k) operation in the loop. As as result your time complexity is O(k n log(n)) and because k is bound above by n, O(n^2 log(n)).
- igor.s.sokolov March 16, 2015We use greedy approach: each turn we try to decrease candles with max values by one. If there is not enough candles or we exhaust the length of a next candle, we done. Instead to use max_heap for supporting turn-number max values we can use count sort.
Thus the time complexity is O(N * K), where N is number of turns and K is number of candles. Because number of turns is bounded above of number of candles we can replace N with K, so we have O(K^2). Memory complexity is O(K).
/**
* Created by Igor_Sokolov on 3/12/2015.
*/
public class CarrerCup_5196482787409920 {
public static int candleTurns(int[] candles) {
if (candles.length == 0) {
return 0;
}
countSort(candles);
int turn = 0;
while (true) {
for (int i = 0; i < turn + 1; i++) {
if (--candles[i] < 0) {
return turn;
}
}
turn++;
if (turn >= candles.length) {
return turn;
}
countSort(candles);
}
}
private static void countSort(int[] candles) {
int[] counts = new int[candles.length];
int last = 0;
for (int i = 0; i < candles.length; i++) {
int candle = candles[i];
if (candle >= counts.length) {
swap(candles, last++, i);
} else {
counts[candle]++;
}
}
for (int i = counts.length - 1; i >= 0; i--) {
int count = counts[i];
if (count != 0) {
for (int j = 0; j < count; j++) {
candles[last++] = i;
}
}
}
}
private static void swap(int[] candles, int i, int j) {
int t = candles[i];
candles[i] = candles[j];
candles[j] = t;
}
public static void main(String[] args) {
int[] test1 = {};
System.out.println(candleTurns(test1)); // 0
int[] test2 = {1};
System.out.println(candleTurns(test2)); // 1
int[] test3 = {10};
System.out.println(candleTurns(test3)); // 1
int[] test4 = {2, 2, 2};
System.out.println(candleTurns(test4)); // 3
int[] test5 = {1, 2, 2};
System.out.println(candleTurns(test5)); // 2
int[] test6 = {1, 2, 3};
System.out.println(candleTurns(test6)); // 3
int[] test7 = {1, 2, 3, 4};
System.out.println(candleTurns(test7)); // 4
int[] test8 = {1, 2, 3, 3};
System.out.println(candleTurns(test8)); // 3
int[] test9 = {3, 3, 3, 3};
System.out.println(candleTurns(test9)); // 4
}
}
Not sure that your time complexity is correct. As for me your solution takes in worst case O(N * K) where N - number of days and K number of candles, because you have while loop which always has N iteration and internal for loop which should go on the last step through all candles in worst case (when all candles are equal and have numbers equal to number of days).
- igor.s.sokolov March 13, 2015It is not clear from the description of the task that all integers in the array are positive, so there is possible case when we have for example array {-1, 10, 1, 9, 2, 3, 8, 12, 100, 12} and the answer is {[1, 10], [-1, 12], [9, 2], [3, 8]}. If we solve more generally this task we can't use the simple array approach, we have to use hashtable data structure. Here is my solution which takes into account possibility of negative integers in the array.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
/**
* Created by Igor_Sokolov on 3/12/2015.
*/
public class CarrerCup_5727163577794560 {
public static void main(String[] args) {
int[][] tests = {{2, 5, 3, 7, 9}, {-1, 10, 1, 9, 2, 3, 8, 12, 100, 12}, {}, {-1}};
int sum = 11;
for (int i = 0; i < tests.length; i++) {
System.out.println("test #" + (i + 1));
final List<int[]> pairs = findPairs(tests[i], sum);
for (int[] pair: pairs) {
System.out.printf("[%d, %d]%n", pair[0], pair[1]);
}
}
}
private static List<int[]> findPairs(int[] a, int sum) {
final List<int[]> result = new ArrayList<>();
final HashSet<Integer> set = new HashSet<>(a.length);
for (int i = 0; i < a.length; i++) {
set.add(a[i]);
}
final HashSet<Integer> used = new HashSet<>(a.length);
for (int i = 0; i < a.length; i++) {
final int first = a[i];
if (used.contains(first)) {
continue;
}
final int second = sum - first;
if (set.contains(second)) {
result.add(new int[] {first, second});
used.add(first);
used.add(second);
}
}
return result;
}
}
Here is my solution based only on simple arrays. I consider also one additional interesting case, when our path is not relevance and it is absolute, for example, /etc/../.././../usr/" -> "/usr"or "C:/..Windows/./systems32/../../temp/." - > "C:/temp"
import java.io.File;
import java.io.IOException;
/**
* Created by Igor_Sokolov on 3/12/2015.
*/
public class CarrerCup_5634050834300928 {
public static void main(String[] args) throws IOException {
String tests[] = {"e/../../a/d/./../b/c", "/etc/../.././../usr/", "C:/../Windows/./systems32/../../temp/."};
for (int i = 0; i < tests.length; i++) {
String path = getCanonicalPath(tests[i]);
System.out.println(path);
}
}
private static String getCanonicalPath(String line) {
if (line.isEmpty()) {
throw new RuntimeException("invalid path");
}
String root = extractRoot(line);
if (root != null) {
line = line.substring(root.length());
}
String[] terms = line.split("/");
int j = 0;
String[] result = new String[terms.length];
int stepUp = 0;
int i = terms.length - 1;
while (i >= 0) {
final String term = terms[i--];
if (term == null || term.isEmpty()) {
throw new RuntimeException("invalid path");
}
if (term.equals(".")) {
continue;
}
if (term.equals("..")) {
stepUp++;
continue;
}
if (stepUp != 0) {
stepUp--;
} else {
result[j++] = term;
}
}
StringBuilder sb = new StringBuilder();
if (root != null) {
sb.append(root);
}
for (int k = j - 1; k >= 0; k--) {
if (k != j - 1) {
sb.append('/');
}
sb.append(result[k]);
}
return sb.toString();
}
private static String extractRoot(String line) {
int pos = line.indexOf('/');
// we assume this is unix path, for example "/etc/hosts"
if (pos == 0) {
return "/";
}
// maybe this is windows path, for example "C:/widows/system32"
String root = line.substring(0, pos + 1);
if (root.contains(":")) {
return root;
}
return null;
}
}
Let's start with definition what is "push notification". We can define it as "A push notification is a message delivered by a centralized server to an endpoint device." In our case the endpoint device is an android device. Then we need to figure out how a device will receive a message. One of the simple approaches could be to open socket to listen messages from server when the device is up. It may be performed by system or a special system application. So the device tries to reach server by general DNS name like push.android.com. Initial requests to open connection goes through load balancer and is delegated to one of servers behind balancer. That will help us to extend number of servers to support more clients without affects to architecture. There are connection timeout handlers, we can assign to this handlers initialization of connection. Thus if a server is down all its client will get event that connection is closed and it leads to new establishing of connection again though the load balancer. It is worth also to support redundancy for load balancer level.
- igor.s.sokolov June 22, 2015Now it is time to discuss what is 'a message'. Nowaday this is usual thing to base the message format on XML or JSON. Cons of this approach in comparing with binary format is increasing of data transfer size, but because it is not anticipated to have long message this should be OK.
The last question is a conception of guarantee delivery. By default we include guarantee delivery in scope that means if a server gets down or a device is not available then we don't send notification although a client of your push notification solution sends notification. This is not so good. To resolve this case we should introduce persistence layer to keep messages and delivery statuses. When a client of our push notification solution initiates sending a message we create a row in DB. Then the server which is responsible to send message for the specified device pick up the row and tries to send it to device and is waiting for acknowledgement. When acknowledgement is getting back to the server it updates row to reflect successful delivery.