alisovenko
BAN USERYour post order successor works incorrectly for the following example:
7
| \
2 10
\
12
if we are at node 2
- alisovenko October 25, 2014Your code output for example input:
[b]
[a, c, d]
[e]
[f]
[g, h]
Could you provide the solution? What complexity will it have?
I see a lot of pluses, though it does not seem to be the linear solution. Check my O(n) solution with graphs and DFS below
Union-find seems to be bad variant as it has the api "are two points connected" and "connect two points". So this would lead to O(n^2) algorigthm, where N is the number of pairs.
For ASCI string we can use a simple graph that can be checked for connectivity using DFS. And although the implementation is a bit massive, it's very simple:
1. create graph as adjacency list
2. dfs through it, all dfs cycle discovers the connected elements
This is effectively O(n) implementation
public static void clusterize(char[][] pairs) {
// build graph
List<Character>[] graph = buildGraph(pairs);
char[] marked = new char[255];
for (int i = 0; i < graph.length; i++) {
if (marked[i] == 0 && graph[i] != null) {
// we have not come to this letter yet
dfsAndPrint(i, graph, marked);
System.out.println();
}
}
}
private static void dfsAndPrint(int i, List<Character>[] graph, char[] marked) {
if (marked[i] > 0) {
return;
}
System.out.printf("%s, ", (char)i);
marked[i] = 1;
if (graph[i] != null) {
for (Character c : graph[i]) {
dfsAndPrint(c, graph, marked);
}
}
}
private static List<Character>[] buildGraph(char[][] pairs) {
List<Character>[] graph = new ArrayList[255];
for (final char[] pair : pairs) {
addToGraph(graph, pair[0], pair[1]);
addToGraph(graph, pair[1], pair[0]);
}
return graph;
}
public static void addToGraph(List<Character>[] graph, char v1, char v2) {
List<Character> characters = graph[v1];
if (characters == null) {
characters = new ArrayList<>();
graph[v1] = characters;
}
characters.add(v2);
}
public static void main(String[] args) {
char[][] input = {
{'a', 'b'},
{'c', 'd'},
{'e', 'f'},
{'g', 'h'},
{'a', 'd'},
{'f', 'g'}
};
clusterize(input);
}
bankertapan, are you the author? Very good solution, I just could not find how to inject the "find all integers that sum to X" problem solution here, but everything is pretty simple :). Good O(n^2) solution with O(1) extra space
- alisovenko October 13, 2014Are you sure memcpy() takes O(1) time? I always thought it takes O(n) time, in this case you algorithm is O(n^2).
- alisovenko October 13, 2014It's possible. Just try my solution below. We need to carefully deal with buffer elements and swap when in proper time.
- alisovenko October 13, 2014There are two ways this can be solved:
1 - use 4-depth loops to iterate through all combinations of pairs. This is O(1) of size but O(n^4) of time
2 - use hashtable of lists of pairs to cache all sums as they are met and use 2-depth loops to find out all pairs of numbers. Then for each sum print out all pairs permutations.
This uses O(n^2) of size but O(n^2) of time. Actually this reduces to 2n^2 in case all numbers are equal but this it's O(n) complexity is not changed though
this is not clear at all, it will be great, if you code this.
- alisovenko October 10, 2014Can you give the full source? This does not give correct numbers for 1, 3, 2 and k=2
- alisovenko October 09, 2014sorry, conversion is correct, I thought each decimal will be converted to direct ASCII symbol 1.
check inputs 8799 and 7899 they must provide the same result for k=2
Greedy solution doesn't work here, see above. Also int conversion is not correct
- alisovenko October 08, 2014agree, there is no way to solve this greedely.
Below I provided the recursive solution (not the first one to provide it, though) with deep explanation of steps.
I know that this answer is not fully correct (as Moi found the case, when this doesn't work), but as I spent a lot of time and would like to safe it for anyone, who comes here to find the solution, but cannot underestand it. So I added lots of comments and will explain it here.
To my mind if this algorithm is provided on the interview - they would accept it anyway, though it's not always correct :))
So, the main idea is to recurse the list and support the following invariant:
- maximum equal elements in the current sublist are moved to the head
- the swapped elements are moved to their position in descending order
So at each iteration we find the next LEN maximum elements and substitute them with LEN elements at the head of current sublist. Though elements at the head must be sorted so that to support the invariant.
Hope, this helps anybody, as I spend half a day on this and initially wrote incorrect greedy algorithm, suppose, that there are many such people.
public static void kSwap(List<Integer> input, int k) {
if (k == 0 || input.size() <= k) {
return;
}
// Finding the maximum digit in the list
int m = getMaxDigit(input, k);
// This contains all indexes in the array, that == m
List<Integer> maxPositions = new ArrayList<>();
// This contains all values from 0 to maxPosition.size()
List<Integer> forSwapping = new ArrayList<>();
int leftCursor = 0;
// We iterate two cursors - one from the end that gathers indeces of all values == m
// and the other from the head - just increment. Loop stops when cursors meet
for (int i = input.size() - 1; i > 0 && i > leftCursor; i--) {
if (input.get(i) == m) {
forSwapping.add(input.get(leftCursor));
maxPositions.add(i);
leftCursor++;
}
}
int len = maxPositions.size();
// The most important part - we sort the 'head' in ascending order
// to move in place of maximum elements in correct order
Collections.sort(forSwapping);
// Now just swap max item elements with #len first ones
for (int i = 0; i < len; i++) {
input.set(i, m);
input.set(maxPositions.get(i), forSwapping.get(i));
}
// Recurse for sublist (#len first elements are already inplace)
kSwap(input.subList(len, input.size()), k - len);
}
private static int getMaxDigit(List<Integer> input, int k) {
return input.stream().max(Comparator.<Integer>naturalOrder()).get();
}
public static void main(String[] args) {
List<Integer> l = new ArrayList<>(Arrays.asList(1, 3, 2));
int k = 1;
kSwap(l, k);
System.out.println(l);
l = new ArrayList<>(Arrays.asList(1, 3, 2));
k = 2;
kSwap(l, k);
System.out.println(l);
l = new ArrayList<>(Arrays.asList(7, 8, 9, 9));
k = 2;
kSwap(l, k);
System.out.println(l);
l = new ArrayList<>(Arrays.asList(8, 7, 9, 9));
k = 2;
kSwap(l, k);
System.out.println(l);
l = new ArrayList<>(Arrays.asList(8, 7, 6, 9, 5, 9));
k = 3;
kSwap(l, k);
System.out.println(l); // This is not correct :((
}
It seems, that you have much more than k swaps here...
- alisovenko October 06, 2014this is not effectively O(n), this is effectively O(nk)
- alisovenko October 05, 2014This is just a simple K iterations of selection sort with one exclusions:
- when looking for maximum element from all leftmost ones we take the position of the "latest" one - e.g. for "26316" - if we are at "2" digit now we swap it with latest "6" - not with first met.
Here is the code (it's rather big because I need to convert from int to list of ints and back)
public static int find(int input, int k) {
List<Integer> digits = new ArrayList<>();
int n = input;
while (n > 0) {
digits.add(n % 10);
n /= 10;
}
Collections.reverse(digits);
int numberOfSwaps = 0, idx = 0;
while (numberOfSwaps != k) {
int pos = findLastBiggest(digits, idx);
if (pos != idx) {
// We managed to find the next number that is bigger than current
swap(digits, idx, pos);
numberOfSwaps++;
}
idx++;
}
return arrayToInt(digits);
}
private static int findLastBiggest(List<Integer> digits, int from) {
int max = 0, maxPos = 0;
for (int i = from; i < digits.size(); i++) {
// Note, that latest max overrides the previous one even if they are equal
if (digits.get(i) >= max) {
max = digits.get(i);
maxPos = i;
}
}
// In case that we already on maximum - return the current pos
if (max == digits.get(from)) {
return from;
}
return maxPos;
}
private static void swap(List<Integer> digits, int from, int to) {
int t =digits.get(from);
digits.set(from, digits.get(to));
digits.set(to, t);
}
private static int arrayToInt(List<Integer> digits) {
int result = 0;
for (int i : digits) {
result = result * 10 + i;
}
return result;
}
public static void main(String[] args) {
assert (find(34155, 2) == 55143);
assert (find(12520, 2) == 52210);
}
Code looks a bit tough for understanding and massive, but the sense is simple: we keep counters for sum (current and maximum) and indices of range (current and maximum), As maximum sum exceeds current one - we remember new indices as maxumum ones. The special case is tail - after iteration we must check the last element.
public static int[] findLargestSubarray(int[] array) {
int curSum = 0, curStart = -1;
int maxSum = 0, maxStart = -1, maxEnd = -1;
for (int i = 0; i < array.length; i++) {
if (array[i] > 0) {
if (curStart < 0) {
// We only came to next sequence of positive numbers, lets' store the start idx (inclusive)
curStart = i;
}
curSum += array[i];
if (curSum > maxSum) {
// update max indices
maxSum = curSum;
maxStart = curStart;
}
} else {
if (curStart >= 0 && maxStart == curStart) {
// we just left the maximum sequence, let's remember ending index (exclusive)
maxEnd = i;
}
// reset fields
curSum = 0;
curStart = -1;
}
}
// Special case for last element (don't forget about tail!)
if (array[array.length - 1] > 0 && curStart >= 0 && maxStart == curStart) {
maxEnd = array.length;
}
if (maxStart < 0) {
return new int[]{};
}
return Arrays.copyOfRange(array, maxStart, maxEnd);
}
public static void main(String[] args) {
int[] largestSubarray = findLargestSubarray(new int[]{2, 5, 1, -1, -2, 8, 9});
assert Arrays.equals(largestSubarray, new int[]{8, 9}) : Arrays.toString(largestSubarray);
int[] largestSubarray1 = findLargestSubarray(new int[]{-1, -3, -6, -2, -9});
assert Arrays.equals(largestSubarray1, new int[]{}) : Arrays.toString(largestSubarray);
int[] largestSubarray2 = findLargestSubarray(new int[]{-9, 3, 2, 3, -4, 4, 3});
assert Arrays.equals(largestSubarray2, new int[]{3, 2, 3}) : Arrays.toString(largestSubarray);
}
I use preorder traversal here and on each level check whether the new sum for node is in ranges for the matching sum for max/min numbers. To do this I precompute all the possible combinations of numbers of min/max range (123 -> 1, 12, 123) and pass this list to recursive method together with level indication. If any non-leaf node is outside the range, I pass through the "marked" attribute to mark all descendants as though.
Also some big optimization: if some number at some level is exclusively inside ranges (not equal to any border), than we may skip further recursion as it will also be in ranges.
public static void checkAndMark(Node node, int curValue, List<Integer> from, List<Integer> to, int level, boolean markAll) {
if (markAll
|| from.size() <= level || curValue < from.get(level)
|| to.size() <= level || curValue > to.get(level)) {
node.mark();
markAll = true;
}
// Special case: if our number is exclusively inside the range - we don't need to recurse any more
if (node.value > from.get(level) && node.value < to.get(level)) {
return;
}
if (node.left != null) {
checkAndMark(node.left, curValue * 10 + node.left.value, from, to, level + 1, markAll);
}
if (node.right != null) {
checkAndMark(node.right, curValue * 10 + node.right.value, from, to, level + 1, markAll);
}
}
public static void main(String[] args) {
Node root = new Node(null, 1);
/// initialize tree here
int min = 124;
int max = 145;
checkAndMark(root, root.value, split(min), split(max), 0, false);
}
private static List<Integer> split(int min) {
int i = min;
List<Integer> list = new ArrayList<>();
while (i > 0) {
list.add(i);
i /= 10;
}
Collections.reverse(list);
return list;
}
Why isn't 6 included to answer? 126 and 136 fall into range perfectly
- alisovenko October 03, 2014The correct solution is to use stack and get its size at the end of path, but it's important to avoid infinite recursion. So we need to mark branches, we have already processed: if we've already gone to left subtree, we need to mark its root as visitited:
public static int height(Node root) {
LinkedList<Node> stack = new LinkedList<>();
stack.add(root);
Set<Node> marked = new HashSet<>();
int maxHeight = 0;
while (!stack.isEmpty()) {
Node last = stack.getLast();
if (last.left != null && !marked.contains(last.left)) {
stack.addLast(last.left);
marked.add(last.left);
}
else if (last.right != null && !marked.contains(last.right)) {
stack.addLast(last.right);
marked.add(last.right);
}
else {
maxHeight = Math.max(maxHeight, stack.size());
stack.removeLast();
}
}
return maxHeight;
}
public static void main(String[] args) {
Node root = new Node(null, 8);
root.add(4);
root.add(2);
root.add(6);
root.add(7);
root.add(15);
root.add(17);
root.add(19);
root.add(11);
System.out.println(height(root));
}
For multi-children variant we do the same but just iterate through children looking for unmarked nodes:
while (!stack.isEmpty()) {
Node last = stack.getLast();
Node child;
if ((child = findNextNotMarked(last.children, marked)) != null) {
stack.addLast(child);
marked.add(child);
}
else {
maxHeight = Math.max(maxHeight, stack.size());
stack.removeLast();
}
}
first code doesn't work, it just goes into infinite recursion, you need to mark nodes visited
- alisovenko September 27, 2014Elegant and fast way - to regard 9 as '1' bit and 0 - as '0' bit. In this case we just iteravely increase binary number and check that translated version (from binary '10..' to '90..') is divisable by the provided number
public class Smallest0And9DivisibleNumber {
public static int find(int divisible) {
int bin = 1;
while (true) {
int res = translate(bin);
if (res % divisible == 0) {
return res;
}
bin += 1;
}
}
private static int translate(int bin) {
int result = 0;
for (int i = Integer.toBinaryString(bin).length(); i > 0; i--) {
result *= result != 0 ? 10 : 0;
int mask = 1 << (i - 1);
result += (bin & mask) == mask ? 9 : 0;
}
return result;
}
public static void main(String[] args) {
assert find(10) == 90;
assert find(99) == 99;
assert find(33) == 99;
assert find(3) == 9;
assert find(333) == 999;
assert find(300) == 900;
assert find(303) == 909;
assert find(3033) == 9099;
assert find(3303) == 9909;
}
}
Sure, the best way is to use additional structure (array, queue, etc), but there is way to do this with O(1) additional space and O(n) runtime. The trick is to keep 4 pointers: positive, swap positive, negative, swap negative and one cursor. Cursor moves through the array, at each iteration the following invariant is provided: positive and negative pointers point to next positive and negative numbers in the array. "Swap" pointers are used in cases, when we need to swap the next integer (e.g. expected +, but have -, so we swap - to next + and appoint swap negative variable to just moved position). At each iteration swap variable keeps the position of next positive or negative number, that must be placed at next matching cursor position.
This all is difficult to understand, just run the code, see tracing output and you will understand.
If anyone creates data sets, that break the program - will be glad to see.
public class InterleavePosAndNegIntegers {
static int dp, sp, dn, sn;
static int cursor = 0;
static int[] data;
public static void interleave() {
boolean expectedPositive, tail = false;
int N = data.length;
// initialization
dp = -1; sp = -1; dn = -1; sn = -1;
cursor = 0;
expectedPositive = data[0] > 0;
propagatePositive(false);
propagateNegative(false);
while (cursor < N) {
printStats("main" + cursor);
boolean nextPositive = data[cursor] > 0;
// These are good situations: numbers are placed ok - just skipping
if ((tail || expectedPositive) && nextPositive) {
propagatePositive(true);
}
else if ((tail || !expectedPositive) && !nextPositive) {
propagateNegative(true);
}
// Bad situation1:
else if (expectedPositive && !nextPositive) {
swapNegativeWithPositive();
}
else if (!expectedPositive && nextPositive) {
swapPositiveWithNegative();
}
// if positive or negative numbers ended - just propagate the tail
if (dp < 0 || dn < 0) {
tail = true;
}
expectedPositive = !expectedPositive;
cursor++;
}
}
private static void swapNegativeWithPositive() {
assert dn == cursor;
// two swaps: current negative with swapped negative, and then current negative with future positive
if (sn > dn) {
swap(data, cursor, sn);
printStats("neg->pos.0");
}
swap(data, cursor, dp);
// point swap negative pointer to just moved negative number
sn = dp;
printStats("neg->pos.1");
// propagate
propagatePositive(false);
propagateNegative(false);
printStats("neg->pos.2");
}
private static void swapPositiveWithNegative() {
assert dp == cursor;
// two swaps: current positive with swapped positive, and then current positive with future negative
if (sp > dp) {
swap(data, cursor, sp);
printStats("pos->neg.0");
}
swap(data, cursor, dn);
// point swap negative pointer to just moved negative number
sp = dn;
printStats("pos->neg.1");
// propagate
propagateNegative(false);
propagatePositive(false);
printStats("pos->neg.2");
}
private static void propagatePositive(boolean swap) {
// assert dp == cursor;
if (sp > dp && swap) {
swap(data, dp, sp);
}
for (int i = dp + 1; i < data.length; i++) {
if (data[i] > 0) {
dp = i;
return;
}
}
// there is no more positive
dp = -1;
}
private static void propagateNegative(boolean swap) {
// assert dn == cursor;
if (sn > dn && swap) {
swap(data, dn, sn);
}
for (int i = dn + 1; i < data.length; i++) {
if (data[i] < 0) {
dn = i;
return;
}
}
// there is no more negative
dn = -1;
}
private static void printStats(String str) {
System.out.printf("[%s] dn: %d, sn: %d, dp: %d, sp: %d, array: %s\n", str, dn, sn, dp, sp,
Arrays.toString(data));
}
private static void swap(int[] ints, int i, int j) {
int t = ints[i];
ints[i] = ints[j];
ints[j] = t;
}
public static void main(String[] args) {
check(new int[]{-1, -8, -5, -6, 7, 9, -3, 1, 6}, new int[]{-1, 7, -8, 9, -5, 1, -6, 6, -3});
// with tail
check(new int[]{2, 3, -5, 6, 7}, new int[]{2, -5, 3, 6, 7});
// unchanged
check(new int[]{-1, 2, -3, 4, -5, 6, -7, 8}, new int[]{-1, 2, -3, 4, -5, 6, -7, 8});
check(new int[]{1, 5, -2, 3, 7, -3, 6, 6, -2}, new int[]{1, -2, 5, -3, 3, -2, 7, 6, 6});
}
private static void check(int[] input, int[] expected) {
data = input;
interleave();
assert Arrays.equals(data, expected): String.format("Expected: %s\n Result : %s\n", Arrays.toString(expected), Arrays.toString(data));
System.out.println(" OK: " + Arrays.toString(data));
}
}
This is a recursive task.
We recurse to N levels, where N is the number of lists of strings. On each level we iterate through all strings in current level list, store its index in int[] array and recurse further. Next level will fill it's own index with its next word. When we came to the next after last level - we have the indexes array filled with indexes of words in matching lists - we just iterate through them and print matching words.
When recursion goes back, the matching index in indexes array is overwritten with next word.
This has O(1) size complexity and O(M^N) time complexity where M is the largest number of words in lists and N is the number of lists.
O(1) size complexity is a big win as almost all solutions, that I see here, use strings concatenations, that would produce lots of garbage
- alisovenko October 26, 2014