Ehsan
BAN USERI have a background in electrical engineering and telecommunications and very interested in computer science and programming puzzles.
Here is the DP solution. It involves O(N) iterations. In each iteration I make O(1) operations. This is true if we assume the string is a linked list so that we can delete, replace, and insert in O(1). However, I am not implementing like this and the way I am doing it right now, each iteration also takes O(N). So overall O(N^2).
To know which position I am doing these operations, I use the state variable "pos". When at some stage "pos = n" it means that the first "n" characters of generated string are "matched".
Python:
str1 = "xx**xxxxx*"
str2 = "xx*x*"
strings = []
prevdec = []
costs = []
pos = []
max_itr = 2 * (len(str1) + len(str2))
action_txt = ['pass', 'insert(x)', 'insert(*)', 'replace', 'delete']
K = -1
N = -1
best_cost_overall = 1000
BIG_CONSTANT = 10
def costOf(d):
return 0 if d == 0 else 1
def other(c):
return ('x' if c == '*' else '*')
def drawState(ds, length):
for row in range(0, len(ds[0])):
r = str(row) + ':'
for ns in range(0, len(ds)):
x = str(ds[ns][row])
if len(x) < length:
rr = [' ' for m in range(0, length - len(x))]
rr = ''.join(rr)
r = r + rr + x
print r
def nextString(s, action, pos):
global str2
if action == 1:
return (s[0:pos] + 'x' + s[pos:], pos)
if action == 2:
return (s[0:pos] + '*' + s[pos:], pos)
# For delete and replace assert len(s) > 0
if pos < len(s):
if action == 3:
s = s[0:pos] + other(s[0]) + s[pos + 1:]
elif action == 4:
s = s[0:pos] + s[pos + 1:]
ml = min(len(s), len(str2))
if pos >= ml:
return (s, pos)
while True:
if s[pos] == str2[pos]:
pos += 1
else:
break
if pos >= ml:
break
return (s, pos)
def diffCost(s1, s2, p):
ext_cost = max(len(s2), len(s1))
ext_cost -= p
return ext_cost
for k in range(0, max_itr):
next_str = ['' for n in range(0, 5)]
next_pos = [0 for n in range(0, 5)]
prev_dec = [0 for n in range(0, 5)]
cost = [0 for n in range(0, 5)]
if k == 0:
for n in range(0, 5):
next_str[n], next_pos[n] = nextString(str1, n, 0)
prev_dec[n] = 0
cost[n] = costOf(n)
else:
for n in range(0, 5):
best_str = ''
best_dec = 0
best_pos = 0
best_cost = 100000
for m in range(0, 5):
s, p = nextString(strings[k - 1][m], n, pos[k - 1][m])
cop = costOf(n) + diffCost(s, str2, p) * BIG_CONSTANT
if cop < best_cost:
best_cost = cop
best_pos = p
best_dec = m
best_str = s
next_str[n] = best_str
next_pos[n] = best_pos
cost[n] = costOf(n) + costs[k - 1][best_dec]
prev_dec[n] = best_dec
costs.append(cost)
strings.append(next_str)
prevdec.append(prev_dec)
pos.append(next_pos)
for n in range(0, 5):
if diffCost(strings[k][n], str2, pos[k][n]) == 0:
if costs[k][n] < best_cost_overall:
best_cost_overall = costs[k][n]
K, N = k, n
def getOps(K, N):
global action_txt, prevdec, pos
action = ''
n = N
for k in range(K, -1, -1):
action = action_txt[n] + "@[" + str(pos[k][n]) + "]" + action
n = prevdec[k][n]
action = action_txt[n] + "@[" + str(pos[k][n]) + "]" + action
return action
print "COST OF CHANGE = ", best_cost_overall
print getOps(K, N)
#print drawState(strings, 20) ==> to view the dynamic programming table
It is a stack question. The correct question is when you have multiple operators and some have precedence, so you will need to include paranthesis. For this one, assuming only the "*" operator, a simple code will do it:
A) Go through the sequence and push operands in one stack, and operators in another
B) Pop an operator, pick a new operand and if we already have one from before, then attach them as the new operand. If we don't have an operand from before, just pop another one from operand stack
Python code running in O(N = number of operands + number of operators)
s = "x*X*Y*y*Career*Cup*Facebook"
operand_stack = []
operator_stack = []
operators = "*"
t = ''
for c in s:
if c in operators:
operand_stack.append(t)
operator_stack.append(c)
t = ''
else:
t = t + c
operand_stack.append(t)
txt = ''
v1 = ''
vinmem = False
while len(operand_stack) > 0:
op = operator_stack.pop(len(operator_stack) - 1)
# take two variables
if vinmem == False:
v1 = operand_stack.pop(len(operand_stack) - 1)
vinmem = True
v2 = operand_stack.pop(len(operand_stack) - 1)
term = '(' + v1 + v2 + op + ')'
v1 = term
print v1
nopar = v1.replace('(', '')
nopar = nopar.replace(')', '')
print nopar
Result:
((((((FacebookCup*)Career*)y*)Y*)X*)x*)
FacebookCup*Career*y*Y*X*x*
As Sam nicely suggested, previous code was wrong so I replaced it with this one. This one runs in O(WH) = O(N^2) for N = max(W, H).
The idea is we find something like cumulative sum over all columns. So when at row "i", w[j] is the sum of all the previous consecutive "1"s.
From "w" we can find the rectangles up to current row in O(N) time. For example, if w = [1 1 2 2 2 1], the largest rectangle has an area of 6.
Here is the python code:
m = open('sample.txt', 'r').read().rstrip().split('\n')
def getMaxRectOnRow(w):
stack = []
pos, max_area, rect = 0, 0, 0
while pos < len(w):
next_value = w[pos]
if len(stack) == 0:
stack.append([next_value, 1])
else:
stacktop = stack.pop(len(stack) - 1)
if stacktop[0] < next_value:
stack.append(stacktop)
stack.append([next_value, 1])
elif stacktop[0] == next_value:
stacktop[1] += 1
stack.append(stacktop)
else:
buffer = [0, 0]
lnew, lold = 0, 0
while stacktop[0] > next_value:
buffer[0], buffer[1] = stacktop[0], stacktop[1] + buffer[1]
lnew += stacktop[1]
area = buffer[0] * buffer[1]
(max_area, rect) = (area, [pos - lnew, pos - 1]) if max_area < area else (max_area, rect)
if len(stack) > 0:
stacktop = stack.pop(len(stack) - 1)
else:
break
buffer[1] += 1
buffer[0] = next_value
if stacktop[0] == next_value:
stacktop[1] += buffer[1]
stack.append(stacktop)
elif stacktop[0] < next_value:
stack.append(stacktop)
stack.append(buffer)
else:
stack.append(buffer)
pos += 1
# empty stack
lnew = 0
buffer = [0, 0]
while len(stack) > 0:
stacktop = stack.pop(len(stack) - 1)
buffer[0], buffer[1] = stacktop[0], stacktop[1] + buffer[1]
area = buffer[0] * buffer[1]
lnew += stacktop[1]
(max_area, rect) = (area, [pos - lnew, pos - 1]) if max_area < area else (max_area, rect)
return max_area, rect
w = [0 for n in range(0, len(m[0]))]
max_area = 0
rect = 0
for n in range(0, len(m)):
for j in range(0, len(m[0])):
w[j] = w[j] + 1 if m[n][j] == '1' else 0
area, r = getMaxRectOnRow(w)
r = [n] + r
(max_area, rect) = (area, r) if area > max_area else (max_area, rect)
print w
print "Found area of ", max_area
print "Rect located at row " , rect[0], " from column ", rect[1], " to column ", rect[2]
A non-recursive solution in Python:
It (theoretically) takes O(1) space since no stack is used. I am using a set "sets" to store all subsets rather than printing them.
def getSet(ss):
s = ""
for k in range(0, len(ss) - 1):
s = s + str(ss[k]) + " "
return s + str(ss[len(ss) - 1])
def subsets(N, K):
sub_set = [0 for k in range(0, K + 1)]
pos = 1
sets = []
sub_set[0] = 0
while pos != 0:
if sub_set[pos] >= N + 1:
sub_set[pos] = 0
pos = pos - 1
else:
if sub_set[pos] == 0:
sub_set[pos] = sub_set[pos - 1] + 1
else:
sub_set[pos] += 1
if pos == K:
if (sub_set[K] < N + 1) and (sub_set[K] != 0):
sets.append(getSet(sub_set[1:]))
else:
pos += 1
return sets
A non-recursive solution in Python:
It (theoretically) takes O(1) space since no stack is used. I am using a set "sets" to store all subsets rather than printing them.
def getSet(ss):
s = ""
for k in range(0, len(ss) - 1):
s = s + str(ss[k]) + " "
return s + str(ss[len(ss) - 1])
def subsets(N, K):
sub_set = [0 for k in range(0, K + 1)]
pos = 1
sets = []
sub_set[0] = 0
while pos != 0:
if sub_set[pos] >= N + 1:
sub_set[pos] = 0
pos = pos - 1
else:
if sub_set[pos] == 0:
sub_set[pos] = sub_set[pos - 1] + 1
else:
sub_set[pos] += 1
if pos == K:
if (sub_set[K] < N + 1) and (sub_set[K] != 0):
sets.append(getSet(sub_set[1:]))
else:
pos += 1
return sets
One missing point is that the anagram has to be a word. So we should have a dictionary handy. Looking up a word of length "n" in the dictionary takes O(n).
I assumed all words are in dictionary.
Python:
# A dictionary with max entropy containing all
# combinations of characters
def isInDict(word):
return True
def anaStrStr(word, text):
nw = len(word)
sword = ''.join(sorted(word))
for n in range(0, len(text) - nw):
if sword == ''.join(sorted(text[n: n + nw])):
return isInDict(text[n : n + nw])
Example:
# Test
text = "This is a complicated sentence,"
print anaStrStr("act", text)
print anaStrStr("tac", text)
print anaStrStr("xoxo", text)
print anaStrStr("tense", text) #
Result:
True
True
None
True
You can use Partition, which uses "n - 1" comparisons and at most "n - 1" swaps using a customized comparator which assumes "0" is the largest number. Comparator code follows:
public class CustomComparator implements Comparetor<Integer> {
public int compareTo(Integer a, Integer b) {
if ((a == 0 && b == 0) || (a * b != 0))
return 0;
if (a != 0 && b == 0) {
return -1;
}
if (a ==0) {
return 1;
}
}
}
Reads from arguments:
public class Convert {
public static void main(String[] argv) {
String num = argv[0];
// split string is not a parsing function.
// you could write a for loop instead if you like
String[] num_pow = num.split("E");
if (num_pow.length == 1) {
num_pow = num.split("e");
}
double f = 0.0;
int p = 0;
char[] dec = num_pow[0].toCharArray();
while(dec[p++] != '.');
p--;
double c = Math.pow(10.0, p - 1);
for (int k = 0; k < dec.length; k++) {
if (dec[k] != '.') {
f = f + c * floatOf(dec[k]);
c = c / 10.0;
}
}
// Decode the exp. term
char[] exp_char = null;
boolean neg = false;
if (num_pow[1].charAt(0) == '-') {
exp_char = num_pow[1].substring(1).toCharArray();
neg = !neg;
}
else if (num_pow[1].charAt(0) == '+') {
exp_char = num_pow[1].substring(1).toCharArray();
}
else {
exp_char = num_pow[1].toCharArray();
}
double e = 0.0;
c = Math.pow(10, exp_char.length - 1);
p = 0;
while(p < exp_char.length) {
e += c * floatOf(exp_char[p]);
c /= 10;
p++;
}
if (neg) {
e = -e;
}
f *= Math.pow(10.0, e);
System.out.println(f);
}
public static double floatOf(char dig) {
switch(dig) {
case '0':
return 0.0;
case '1':
return 1.0;
case '2':
return 2.0;
case '3':
return 3.0;
case '4':
return 4.0;
case '5':
return 5.0;
case '6':
return 6.0;
case '7':
return 7.0;
case '8':
return 8.0;
case '9':
return 9.0;
}
return -1;
}
}
You have to clarify if the integer is 32 bit or 64 bit. For 64 bit case, it is actually easier to generate an integer randomly. Since you have 4 billion = 2^32 integer, if you generate a random 64 bit integer, the chance that it is unique is (2^64 - 2^32) / 2^64 = 1.0 (with good precision)
So the question should be, having 4 billion 32 bit integers, how do you know if one of them is repeated?
This is what came to my mind.
Let's assume you have 4 MB = 2^20 integer words. Define an array of length 2^20 of integers. Each value (unsigned) can hold up to 2^32
Round A)
Now read the stream of numbers (4 billion):
For number X Let Y = X % 2^20. and array[Y] = array[Y] + 1
After reading all, go through the array and find a "Y"with array[Y] < 2^12
Round B)
We know something about the missing number. The 20 LSB are same as Y.
Clear memory except for "Y" and make another array of length 2^12.
Read all X again. For each X, if X%2^20 == Y, increase the memory location at array[Z].
Round C)
For through array Z and find the location where "array[Z] = 0". Report Z * 2^20 + Y as the missing number.
You can use BFS to serialize the tree. Then, you simply need to insert the values in order to get the same exact tree. The order is:
"Root R L RR RL LR LL RRR RRL RLR RLL LRR LRL..."
I implemented a simple BST with "insert" only.
from Queue import *
class bst_node(object):
def __init__(self, p, l, r, v):
self.parent = p
self.right = r
self.left = l
self.value = v
class bst(object):
def __init__(self):
self.root = 0
def insert(self, value):
if self.root == 0:
self.root = bst_node(0, 0, 0, value)
else:
x = self.root
while True:
if x.value < value:
if x.right == 0:
x.right = bst_node(x, 0, 0, value)
break
else:
x = x.right
else:
if x.left == 0:
x.left = bst_node(x, 0, 0, value)
break
else:
x = x.left
def serialize(b):
q = Queue(maxsize = 0)
q.put(b.root)
s = ""
while not q.empty():
node = q.get()
if node.right != 0:
q.put(node.right)
if node.left != 0:
q.put(node.left)
# print this
if q.empty():
s = s + str(node.value)
else:
s = s + str(node.value) + " "
return s
def deserialize(string_bst):
values = string_bst.split(" ")
b = bst()
for k in range(0, len(values)):
value = int(values[k])
b.insert(value)
return b
numbers =[-5, 3, -2, 5, 10, 12, 11]
first_bst = bst()
for n in range(0, len(numbers)):
first_bst.insert(numbers[n])
str_first = serialize(first_bst)
print "First BST Serialized to:", str_first
second_bst = deserialize(str_first)
str_second = serialize(second_bst)
print "Second BST serialized to:", str_second
Here is a DP approach in python. I did not make it efficient but it is working fine I suppose.
DP works as long as the total sum of elements in the array is not too large.
I am also assuming all elements are positive.
idea: Assume you pick elements 1, 2, ..., k and would like to find a subset summing to "exactly" C. We have
SUM[k][C] = either SUM[k - 1][C] && (not picking ak) OR SUM[k - 1][C - ak] && (picking ak)
Eventually you have SUM[N - 1][x] for 0 <= x <= Cmax (sum of all elements) to be either true or false. If it is true, a subset summing to that value exists.
The rest is easy. You just need to break it into some c and Cmax - c and make c and Cmax - c as close as possible. Assuming c < Cmax - c, you just need to check Cmax / 2 and decrease "c" until for some value, SUM[N - 1][c] = TRUE
main_set = {1, 2, 4, 11, 44, 20}
main_set = list(main_set)
Cmax = sum(main_set)
N = len(main_set)
# init a list
dp_table = []
decision = []
for n in range(0, N):
x = []
y = []
for k in range(0, Cmax + 1):
x.append(k == 0)
y.append([])
dp_table.append(x)
decision.append(y)
for i in range(0, N):
for c in range(0, Cmax + 1):
ai = main_set[i]
if c > 0:
dp_table[i][c] = False
if i > 0:
if dp_table[i - 1][c]:
dp_table[i][c] = True
decision[i][c].append(-ai)
if c - ai > -1:
if dp_table[i - 1][c - ai]:
dp_table[i][c] = True
decision[i][c].append(ai)
c = Cmax / 2
while not dp_table[N - 1][c]:
c = c - 1
if c < 0:
print "WHAT?!"
exit(-1)
print "The smaller or equal subset will sum up to ", c
print "And the larger or equal subset will sum up to ", Cmax - c
d = []
nc = c
for k in range(N - 1, -1, -1):
if len(decision[k][nc]) > 0:
dec = decision[k][nc][0]
if dec > 0:
nc = nc - dec
d.append(dec)
print "One of the sets is : ", d , " summing up to ", sum(d)
If by "mid-point", you mean a point exactly in the middle, then all you need to check is whether (x1 + x2) % 2 == 0 and (y1 + y2) % 2 == 0. For "N" dimensions, it will be O(N) to determine whether or not this happens.
If mid-point is "some" point on the line segment connecting the two given points. It will be quite harder to determine. If X = [x1, x2, ..., xN] and y = [y1, y2, ..., yN], then you can do this in O(D N) where D = min(abs(xi - yi)). I don't know if faster is possible:
Here is the code for the second case:
def midPoint(point_a, point_b):
d = 10000000;
N = len(point_a)
index = -1
for n in range(0, len(point_a)):
diff = point_a[n] - point_b[n]
if diff < 0:
diff = -diff
if diff < d:
d = diff
index = n
DX = point_b[index] - point_a[index]
for inc in range(1, d):
didnt_work = False
for i in range(0, N):
if i == index:
continue
dy = point_b[i] - point_b[i]
dx = inc
if ((dy * dx) % DX):
didnt_work = True
break
if not didnt_work:
point_c = point_a
for n in range(0, N):
point_c[n] = (point_b[n] - point_a[n]) * inc / DX + point_c[n]
print point_c
if __name__ == '__main__':
line = raw_input("Point A (blank space separated. RET after last.): ")
x = line.split(" ")
line = raw_input("Point B (blank space separated.RET after last.): ")
y = line.split(" ")
if len(x) != len(y):
print "Points have different dimensions. Exit -1"
exit(-1)
point_a = []
point_b = []
for n in range(0, len(x)):
point_a.append(int(x[n]))
point_b.append(int(y[n]))
midPoint(point_a, point_b)
Test:
Point A (blank space separated. RET after last.): 4 9 13 2 -5 12
Point B (blank space separated.RET after last.): 9 19 28 22 20 2
[5, 11, 16, 6, 0, 10]
[6, 14, 20, 12, 8, 6]
[7, 17, 24, 18, 15, 3]
[8, 18, 27, 21, 19, 2]
Sweep for all digits. It takes much less than it looks like since not all digits divide N.
Test case for 27: answer 139
N = 27;
if N == 0:
print 100
exit()
for n in range(1, 10):
if N % n != 0:
continue
M = N / n
for m in range(1, 10):
if M % m != 0:
continue
L = M / m
if L < 10:
n = n * 100 + m * 10 + L
print n
exit()
For an NxN board, I found a solution O(N^2) time. The worst case space is also O(N^2) when all the cell values are "O". But for random input it will be much less (the space is due to stack for recursion).
The only logical clue I found is that if there is an "O" on the border, then any it along with all the connected "O"'s won't turn into "X".
In my code I treat "0" as X and "1" as "O". Also, "fillup()" is the function to call and it will use "spread(i, j)" to mark the "O"'s that won't convert into "X".
Code in C:
int* mat;
void init() {
mat = (int*) malloc(sizeof(int) * WIDTH * HEIGHT);
};
void spread(int i, int j) {
if (CELL(mat, i, j) == 1) {
CELL(mat, i, j) = 2;
}
else
return;
if (i < HEIGHT - 1)
spread(i + 1, j);
if (i > 1)
spread(i - 1, j);
if (j > 1)
spread(i, j - 1);
if (j < WIDTH - 1)
spread(i, j + 1);
}
void fillup() {
int i = 0;
// side columns
for (i = 0; i < HEIGHT; i++) {
if (CELL(mat, i, 0)) {
spread(i, 0);
};
if (CELL(mat, i, WIDTH - 1)) {
spread(i, WIDTH - 1);
};
}
// top-bottom rows
for (i = 0; i < WIDTH; i++) {
if (CELL(mat, 0, i)) {
spread(0, i);
};
if (CELL(mat, HEIGHT - 1, i)) {
spread(HEIGHT - 1, i);
};
};
for (i = 0; i < HEIGHT; i++) {
int j;
for (j = 0; j < WIDTH; j++) {
CELL(mat, i, j) = 1 ? CELL(mat, i, j) > 1 : 0;
};
};
};
TEST (first input then output):
X X X X X X X X X X
X X X X X O O X X X
X X X X X O O X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X O O O X
X X X X X X X O X X
X O O O X X X X X X
X O X X X X X X X X
Finished the paint...
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X X X X X X X X X X
X O O O X X X X X X
X O X X X X X X X X
It is actually "x = !x" interpret it as " x = (!x)". In C++, the logical date type "bool" is simply "int". In C, you don't have "bool" and should use "int"
That being said, and "int" type is TRUE if it is not zero. e.g.,
int x = -1;
if (x) {
printf("TRUE");
};
prints TRUE unless you set x = 0.
In this code, x = 10, so x is "TRUE" and !x is FALSE which is zero.
A set can be used to prevent printing duplicates. In any case, this is an EXPTIME problem and adding a set makes it EXPSPACE.
temp = ''
printed_sets = set()
def subsetList(s):
global temp
if len(s) == 0:
if temp not in printed_sets:
print temp
printed_sets.add(temp)
return
temp_ = temp
temp = temp + s[0]
subsetList(s[1:])
temp = temp_
subsetList(s[1:])
I used a dict to keep track of printed subsets.
This one takes EXPSPACE in the length of input, also EXPTIME.
temp = ''
printed_sets = set()
def subsetList(s):
global temp
if len(s) == 0:
if temp not in printed_sets:
print temp
printed_sets.add(temp)
return
temp_ = temp
temp = temp + s[0]
subsetList(s[1:])
temp = temp_
subsetList(s[1:])
I used a set to keep track of already printed subsets.
I did not see any constraints on space so here is a solution in EXPSPACE/EXPTIME
temp = ''
printed_sets = set()
def subsetList(s):
global temp
if len(s) == 0:
if temp not in printed_sets:
print temp
printed_sets.add(temp)
return
temp_ = temp
temp = temp + s[0]
subsetList(s[1:])
temp = temp_
subsetList(s[1:])
I found an O(n log(n)) solution.
I first find the number of occurrences of each object.
Then, break each number into batches of "M" repetitions, i.e., one Run.
Example:
sequence: 1, 1, 1, 1, 4, 4, 1
M = 2
Runs: (1, 1), (1, 1), (1) for type = 1
(4, 4) for type = 4
An object "Type" is defined as a set of Runs of same type. Type1 > Type2 if Type1 has more runs. This way, I can sort all Types descending. This is of course O(nlog(n)).
Lets assume "1" is the type with largest number of runs. Now if the total number of "other" runs is equal or greater than the number of runs of "1", we can proceed to making a proper output ("MakeSequence()" routine). Otherwise, I will break the runs into smaller runs until that happens. If not, then there is no solution. This step is linear in the number of Runs() < number of elements.
To make the sequence we do this:
a) Take out head of line in queue and remove one run add to sequence. If the Type is empty now, throw it away. If not, keep it somewhere but don't put in queue.
b) Take out another type. Add to sequence. If non-empty, keep it somewhere.
c) Now if there is a type outside, put it back into queue.
e) go back to a) until queue is empty.
Example (above):
Type1 = [(11), (11), (1)]
Type2= [(4,4)]
since Type1.nRuns() == 3 > Type2.nRuns() + 1, we will break Type2.
Type2=[(4),(4)].
Now we go to make sequence:
seq = "";
a)-> seq = "11", Type1 = [(1,1),(1)];
b)->seq="4",Type2=[(4)],
c) Type1 goes back into queue.
a)-> seq="11411"
b)->seq="114114";
c)->Type1 goes back in
a)->seq="1141141"
done!
here is the code:
public class SequenceSeparation {
public static int M = 2;
public static class Run {
String value;
int length;
public int getLength() {
return length;
}
public Run(String value) {
this.value = value;
this.length = 1;
}
public void add() {
length++;
}
public LinkedList<Run> breakRun(int n) {
LinkedList<Run> runs = new LinkedList<>();
while (n != 0 && length != 1) {
Run r = new Run(value);
runs.add(r);
n--;
length--;
}
runs.add(this);
return runs;
}
@Override
public String toString() {
String s = "";
for (int i = 0; i < length; i++)
s = s + value;
return s;
}
}
public static class Type implements Comparable<Type> {
String value;
int buffer = 0;
Run current_run = null;
LinkedList<Run> runs;
public Type(String value) {
this.value = value;
runs = new LinkedList<>();
current_run = new Run(value);
runs.add(current_run);
buffer = 1;
}
public Run nextRun() {
if (runs.isEmpty())
return null;
else
return runs.pollFirst();
}
public void add() {
if (buffer == 0) {
current_run = new Run(value);
runs.add(current_run);
buffer = 1;
}
else {
current_run.add();
}
if (current_run.length == M)
buffer = 0;
}
public String getValue() {
return value;
}
public Integer nRuns() {
return runs.size();
}
@Override
public int compareTo(Type o) {
return -nRuns().compareTo(o.nRuns());
}
public int increaseRuns(int n) {
Run first_run = null;
while (true) {
Run r = runs.getFirst();
if (first_run == null)
first_run = r;
else
if (first_run == r)
return n;
int c = runs.size();
while (r.getLength() == 1) {
runs.removeFirst();
runs.addLast(r);
r = runs.getFirst();
c--;
if (c == 0)
return n;
}
LinkedList<Run> new_runs = r.breakRun(n + 1);
runs.removeFirst();
int ii = new_runs.size();
for (int i = 0; i < ii; i++) {
Run rr = new_runs.pollFirst();
runs.addLast(rr);
}
n -= (ii - 1);
if (n == 0)
return 0;
}
}
}
public SequenceSeparation(String sequence, int M) {
SequenceSeparation.M = M;
String[] types = sequence.split(",");
HashMap<String, Type> repetitions = new HashMap<>();
// Round 1: count
Type max_type = null;
int ng = 0;
for (String t : types) {
if (repetitions.containsKey(t))
repetitions.get(t).add();
else
repetitions.put(t, new Type(t));
if (repetitions.get(t).nRuns() > ng) {
ng = repetitions.get(t).nRuns();
max_type = repetitions.get(t);
}
}
int n_total_other = 0;
for (String t : repetitions.keySet()) {
if (t.compareTo(max_type.getValue()) != 0)
n_total_other += repetitions.get(t).nRuns();
}
if (n_total_other + 1 < max_type.nRuns()) {
int diff = max_type.nRuns() - n_total_other - 1;
for (String t : repetitions.keySet()) {
if (t.compareTo(max_type.getValue()) != 0) {
Type type = repetitions.get(t);
diff = type.increaseRuns(diff);
}
}
if (diff > 0) {
System.out.println("Could not resolve.");
return;
}
}
MakeSequence(repetitions);
}
private void MakeSequence(HashMap<String, Type> repetitions) {
// A sorted-queue : MaxHeap (note the comparedTo defition for Type)
PriorityQueue<Type> queue = new PriorityQueue<>(repetitions.values());
Type type1 = null, type2 = null;
String seq = "";
while (queue.isEmpty() == false) {
type2 = type1;
Type next = queue.poll();
seq += next.nextRun().toString();
if (next.nRuns() > 0)
type1 = next;
else
type1 = null;
if (type2 != null)
queue.add(type2);
}
System.out.println("Solution:");
System.out.print(seq);
}
}
If it is null-terminated, then finding a cycle means we can't reach all cells. Otherwise, the cycle must be of length "nxn". Also, we must make sure the traversal takes "nxn", i.e., the graph is connected or technically every vertex is reachable from (0, 0).
I guess we can also do this in O(n^2) time with O(1) extra space. It is similar to finding a cycle in a sequence (Floyd's cycle finding algorithm = hare-tortoise).
If there is a cycle then is has to be of length "nxn".
If there are no cycles, then the tortoise has to have walked "nxn" cells.
Time complexity : O((n1 + n2)^2) worst case, but for random input will be O(nlog(n)).
First off, I should say that I believe O(nlog(n)) for worst does not seem to be likely to exist. The Quicksort algorithm, which is in-place sorting, needs O(1) swapping between elements which we cannot do here. Nonetheless, It is just a guess.
I show the algorithm with an example. The attach the java code.
Lets assume Q1: [1 4 3 2] and Q2: [8 6 5 7] are the two queues where the
left most is head of line. I just show the steps
1- (dequeue Q2 into Q1)
Q1:[1 4 3 2 8 6 7 5] Q: [] (nQ2inQ1 = 4, nQ1inQ1 = 4)
2- Dequeue the first the head of line in Q1 into Q2.
Q1:[4 3 2 8 6 7 5] Q2:[1] (nQ1inQ1 = 3)
3- Dequeue all the elements from Q1. If it is larger than the last element
entering Q2, enqueue into Q2, otherwise, enqueue into Q1.
Q1:[3 2 8 6 7 5] Q2:[1 4] nQ1inQ1 = 3, nQ2inQ1 = 4, nQ1inQ2 = 2,
last_entered_Q2 = 4
Q1:[2 8 6 7 5 3] Q2:[1 4] nQ1inQ1 = 3, nQ2inQ1 = 4, nQ1inQ2 = 2,
last_entered_Q2 = 4
Q1:[8 6 7 5 3 2] Q2:[1 4].
4- Dequeue Q2 into Q1.
Q1:[8 6 7 5 3 2 1 4] Q2:[] nQ2inQ1 = 4, nQ1inQ1 = 4.
5- Repeat the process again for elements of Q2. You eventually get:
Q1[3 2 1 4 6 7 5 8] Q2:[]
6- Again doing it for elements of Q1. We get at the end
Q1[6 7 5 8 2 1 3 4] Q2:[]
7- Again (for Q2)
Q1[2 1 3 4 5 6 7 8] Q:[] (note that Q2 is sorted now)
8- Again (for Q1)
Q1:[5 6 7 8 1 2 3 4] Q:[]
9- In this round, we realize that Q2 is sorted. (no inversions)
10- In the next step, we find that Q1 is also sorted.
public class TwoQueueSorting {
public static void Sort(Queue<Integer> source, Queue<Integer> destination) {
// The following are state variables, not containers
int len_src = source.size();
int len_dest = destination.size();
int last_to_move_to_destination;
int n_queues_sorted = 0;
boolean working_on_source = true;
while (n_queues_sorted < 2) {
// Move everything to source
while (!destination.isEmpty())
source.add(destination.poll());
// Read from source.
last_to_move_to_destination = source.poll();
destination.add(last_to_move_to_destination);
boolean sorted = true;
int n_out = len_src - 1;
if (!working_on_source)
n_out = len_dest - 1;
for (int i = 0; i < n_out; i++) {
int new_out = source.poll();
if (new_out > last_to_move_to_destination) {
last_to_move_to_destination = new_out;
destination.add(new_out);
} else {
sorted = false;
source.add(new_out); // Not in order and has to return.
}
}
// Change the order for the next round, if it happens
working_on_source = !working_on_source;
if (sorted)
n_queues_sorted++;
}
}
}
Sample:
public class CareerCup {
public static void main(String[] args) {
int[] src = {10, 3, 5, 2, 8, 4};
int[] dst = {9, 3, 4, 1, 2, 12, 33, 98, 20};
ArrayDeque<Integer> source = new ArrayDeque<Integer>();
ArrayDeque<Integer> destination = new ArrayDeque<Integer>();
for (int i = 0; i < src.length; i++)
source.add(src[i]);
for (int i = 0; i < dst.length; i++)
destination.add(dst[i]);
TwoQueueSorting.Sort(source, destination);
System.out.print("Source:\n");
while(!source.isEmpty())
System.out.print(source.poll().toString() + " ");
System.out.print("\n");
System.out.print("destination:\n");
while(!destination.isEmpty())
System.out.print(destination.poll().toString() + " ");
System.out.print("\n");
}
}
run:
Source:
2 3 4 5 8 10
destination:
1 2 3 4 9 12 20 33 98
I guess the question is finding "k" closest pair of nodes. That is, we consider n choose 2 cases and sort them based on distance and then return the "k" smallest. Otherwise, depending on the definition of "k closest points", the problem can be much harder.
For the former case, the algorithm above is better than listing all pairs since it is O(knlogn). If k = n, the complexity will be O(n2 logn) which is that of sorting all pairs.
The algorithm is correct. When you compare across the "y" axis for seven consecutive points, it makes sure that any point with distance smaller than that of sub-problems is detected.
For a proof of correctness, I suggest you refer to the Algorithms course in Stanford by "Tim Roughgarden". He solved it as an example for divide and conquer (I took it on coursera).
As mentioned by Ayush, if there are no space constraints, a "map/hashtable" can do the job in O(n) where "n" is the length of the list (in fact the number of distinct numbers on the list). I added a simple java function for that.
public static void Solve(Iterator<Integer> numbers, int K) {
HashMap<Integer, Integer> table = new HashMap<>();
while (numbers.hasNext()) {
Integer new_number = numbers.next();
table.put(new_number, K - new_number);
int target = K - new_number;
if (table.containsKey(target)) {
System.out.print("Found the pair (" + new_number.toString() +
", " + Integer.toString(target) + ")\n");
}
}
}
Example:
public static void main(String[] args) {
// TODO code application logic here
List<Integer> l = new LinkedList<>();
for (int i = 1; i < 21; i++)
l.add(i);
SumKonLL.Solve(l.iterator(), 13);
}
Output:
Found the pair (7, 6)
Found the pair (8, 5)
Found the pair (9, 4)
Found the pair (10, 3)
Found the pair (11, 2)
Found the pair (12, 1)
For small "k" this can be done in O(k N log(N)) using divide and conquer.
Start by sorting the list of points with respect to "x" and "y". Let's form two sorted arrays this way, namely Ax and Ay.
1- Take Ax and divide it into lower and upper halves (roughly N / 2 length). That is, divide the array around its median (say Mx).
2- Run the algorithm for the first half and then second half, independently (divide and conquer: this is a recursive call).
3- Lets assume by solving it over the two subarrays, "delta" is the minimum length found.
NOW We want to see if the two closest points are in different subarrays.
4- Now choose all points where "|x - Mx| < delta".
5- Go through all such points, (at most N). For a given point (x, y), look for the next "7" points on the array sorted with respect to "y". This will take O(N) time. At the end, if you find a pair with distance less than "delta", return it as solution, otherwise, return "delta".
I saw this algorithms in some course notes from Algorithm I in Stanford.
Your problem is a mixture of "Bin Packing" (assign different objects with volumes to different bins with finite capacity) and "Agent Matching" (assignment based on preference) and hence,
NP-complete. So in general, any solution might be as good as others, i.e., worst time exponential.
What I suggest, is a backtracking algorithm (aka Branch and Bound). This is just to have a first crack at the problem. The idea behind branch and bound is very simple:
A- Browse all (worst case) possibilities (through recursion, for instance)
B- Before each assignment check if we bound
Bounding: Cleverly deducing whether or not we need to delve in deeper. For example, you have already found a solution to serve 3 customers. Now you are checking customer 3/4 and you have assigned only one yet. Obviously, the best you can do is to assign only one more customer which brings you to "2" and this is a worst solution than what you already have. So just don't bother!
The code is in Java.
Main Algorithm:
// Assign customer with ID = c_id
public void RunAssignment(int c_id) {
// Here goes nothing... (worst time exponential)
// Trying to assign customer id = c_id
/// HERE IS THE BOUNDING PART (a very simplistic one indeed)
int customers_left = customers.length - c_id; // How many more customers left to assign
if (curr_customers_in + customers_left < max_customers_assigned) // There is no way to find a better assignment since we already have a better solution
return;
// Check all rooms that this customer likes
for (int room_index : customers[c_id].preferred_rooms) {
// Can we check this customer in? (Here you resolve the clashes)
if (rooms[room_index].CheckIn(customers[c_id])) {
// YES!
// Count one more
curr_customers_in++;
// Is it a better or equally good as our best one so far?
if (curr_customers_in >= max_customers_assigned) {
// YES!
max_customers_assigned = curr_customers_in;
// Print it!
AnnounceSolution();
}
// Do we have anybody left?
if (c_id < customers.length - 1) {
// Assign next!
RunAssignment(c_id + 1);
// To brows other options, check this customer out.
rooms[room_index].CheckOut(customers[c_id]);
// Count one out
curr_customers_in--;
// Try to assign next (this time, our current customer is not assigned anymore!)
RunAssignment(c_id + 1);
}
else {
// No? Just check out to try next room (not necessary at this point, but just to make sure we have all possible solutions)
curr_customers_in--;
rooms[room_index].CheckOut(customers[c_id]);
}
}
}
}
I am using two types of Objects: Customer and Room
First Room:
public class Room {
public static int MaxHour = 300;
public ArrayList<Customer> customers;
int ID;
boolean[] hours;
// Sets the room ID
public Room(int ID) {
customers = new ArrayList<Customer>();
hours = new boolean[Room.MaxHour];
this.ID = ID;
}
/**
*
* @param c Customer (object)
* @return True if "c" can be checked in. If so, the corresponding hours of occupancy are marked off. Otherwise, just say false.
*/
public boolean CheckIn(Customer c) {
for (int i = c.hour_in; i < c.hour_out; i++)
if (hours[i])
return false;
for (int i = c.hour_in; i < c.hour_out; i ++)
hours[i] = true;
customers.add(c);
return true;
}
/**
* Release the hours assigned to a customer.
* @param c Check out this customer.
*/
public void CheckOut(Customer c) {
for (int i = c.hour_in; i < c.hour_out; i++)
hours[i] = false;
customers.remove(c);
}
// For printing solution
@Override
public String toString() {
String msg= "Room " + Integer.toString(ID) + " serves ";
if (customers.isEmpty())
msg = msg + " no one!";
else
for (Customer c : customers)
msg = msg + "[" + c.toString() + "]";
return msg;
}
}
And now the Customer class (nothing to it)
public class Customer {
// Set the corresponding info.
public Customer(int ID, int hours_in, int hours_out, int[] rooms) {
this.ID = ID;
this.hour_in = hours_in - 1;
this.hour_out = hours_out - 1;
this.preferred_rooms = rooms;
}
int ID, hour_in, hour_out;
public int[] preferred_rooms;
@Override
public String toString() {
return "Customer " + Integer.toString(ID);
}
}
If all vertices are supposed to be of degree "1", then you must have exactly "n_vertices / 2" edges. That is the first thing to check.
Then, prepare an array of boolean for the vertices checked. Read through all edges and for each edge, mark off two vertices. If a vertex has already been marked off, return false.
Otherwise, return true.
Main Algorithm:
#pragma once
#include "Problem.h"
#include <list>
#include <iostream>
using namespace std;
class Edge
{
public:
int vertex_1, vertex_2;
Edge(int v1, int v2) : vertex_1(v1), vertex_2(v2)
{
}
Edge() : vertex_1(0), vertex_2(0)
{
}
};
class PerfectMatch :
public Problem
{
public:
static const int FALSE_INCORRECT_EDGE_NUMBER = -1;
static const int FALSE_NOT_PERFECTLY_MATCHED = -2;
static const int TRUE_PERFECT_MATCH = 0;
static const int FALSE_INCORRECT_VERTEX_NUMBER = -3;
static const int FALSE_UNMATCHED_VERTICES = -4;
PerfectMatch() : vertices(0), edges(0)
{
}
~PerfectMatch()
{
}
/** Solving the problem */
void SetGraph(list<int>* vertices_, list<Edge>* edges_)
{
vertices = vertices_;
edges = edges_;
}
int Solve()
{
int n_vertices = vertices->size();
int n_edges = edges->size();
// If it is a perfect match, then we should have two vertices per edge
if ((n_edges << 1) != n_vertices)
return FALSE_INCORRECT_EDGE_NUMBER;
if (n_vertices % 2 == 1)
return FALSE_INCORRECT_VERTEX_NUMBER;
bool* encountered = new bool[n_vertices];
for (int i = 0; i < n_vertices; i++) encountered[i] = false;
int counted_vetices = 0;
for (const auto& e : *edges)
{
if (encountered[e.vertex_1] || encountered[e.vertex_2])
return FALSE_NOT_PERFECTLY_MATCHED;
encountered[e.vertex_1] = true;
encountered[e.vertex_2] = true;
counted_vetices += 2;
}
delete[] encountered;
if (counted_vetices != n_vertices)
return FALSE_UNMATCHED_VERTICES;
return TRUE_PERFECT_MATCH;
}
void Result()
{
int result = Solve();
switch (result)
{
case TRUE_PERFECT_MATCH:
cout << "Perfect Match!" << endl;
break;
default:
cout << "Not a Perfect Match!" << endl;
}
}
list<int>* vertices;
list<Edge>* edges;
};
Code to test three graphs:
#include "PerfectMatch.h"
#include <set>
#include <list>
using namespace std;
int main(int argc, _TCHAR* argv[])
{
list<int> vertices{ { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } };
list<Edge> edges{ { Edge(0, 1), Edge(2, 3), Edge(4, 5), Edge(6, 7), Edge(8, 9) } };
list<Edge> bad_edges{ { Edge(0, 1), Edge(2, 3), Edge(2, 1), Edge(6, 7), Edge(8, 9) } };
list<Edge> insuff_edges{ { Edge(0, 1), Edge(2, 3) } };
PerfectMatch pf;
pf.SetGraph(&vertices, &edges);
pf.Result();
pf.SetGraph(&vertices, &bad_edges);
pf.Result();
pf.SetGraph(&vertices, &insuff_edges);
pf.Result();
fgetc(stdin);
}
Output:
Perfect Match!
Not a Perfect Match!
Not a Perfect Match!
Best O(1) (if you can do infinite precision calculation of doubles by solving the recursive formula and finding the solution as a function of (n) and the eigen functions of the recursion)
Worst O(2^(O(1) n)) (exponential).
If you do a naive recursive approach, such as this:
int fib(n) {
if (n == 0)
return 1;
if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}
By increasing the recursion depth by 1, the value of "n" is reduced by a constant (1 or 2). Also each recursion leads to "2" other recursions, so in general, you are doing O(2^n).
- Ehsan December 24, 2013This complexity is O(K^2 log(K)). You are not using some of the information about A and B. We know that A and B are sorted, which implies that you only need the first "K" elements. But that is not all that is implied.
If the first "K" elements of A and B are not sorted, then the list of numbers A[i] + B[j] could form (K^2)! different types of orderings. Then, your algorithm might have been optimal since the complexity is that of sorting.
For this problem we know that A and B are sorted. An O(K log(K)) algorithm actually exists). I guess even an O(K) algorithm might exist but as Anonymous said, if it does, it looks very hard to be found.
** Nevermind, I only saw the second algorithm which you already mentioned is O(N*N)
Also for the first algorithm, in the main loop you are increasing either "i" or "j" by 1 in each iteration. Then each time you also call "nextIdx" which has a for loop running for (N - i) or (N - j) iterations. So the complexity seems to be O(K N).
The way I implemented this takes O(K log(K)) time if I use a heap, or O(K^2) if I use a naive sorted array.
Here is the key idea: Obviously, the first pair is A[0] and B[0]. Furthermore, the first pair where we take index "i" from array "A" is indeed (A[i], B[0]). So we can initialize a list of "K" pairs of (A[i], B[0]) for "i = 0, 1, ..., K- 1".
Assume this list is sorted (or Heap with Extract Min). Take first Pair out say, (A[0], B[0]). NOTE: If the next pair leading to K-minimum sum includes (A[0]) it must be (A[0], B[1]). So we simply put the pair (A[0], B[1]) inside. In general, when you extract the pair (A[i], B[j]), you must Insert (A[i], B[j + 1]) back in.
Insertion and Extraction takes O(K) time if you use a simple sorted array, and O(log(K)) if you use a Heap. Overall, it takes, O(K Log(K)) = O(K^2).
Here is what I used for class Pair:
class Pair {
ind ind_A, ind_B;
public Pair(int a, b) {
ind_A = a; ind_B = b
}
public boolean IsLessThan(Pair other) {
return (A[ind_A] + B[ind_B]) < (A[other.ind_A] + B[other.ind_B]);
}
Here is the code for the main for-loop
public void Solve(int K) {
pairs = new Heap(A.length);
for (int i = 0; i < A.length; i++)
pairs.Insert(new Pair(i, 0));
// Now begin
for (int k = 0; k < K; k++) {
Pair p = pairs.ExtractMin();
System.out.println(p);
p.ind_B++;
pairs.Insert(p);
}
}
Here is a sample test:
public static void main(String[] args) {
// TODO code application logic here
int[] a = {1, 5, 6, 7, 8, 20, 21, 22};
int[] b = {1, 4, 5, 10, 15, 16, 17, 18};
MinSumArray ms = new MinSumArray(a, b);
ms.Solve(6);
}
Output:
A[0] + B[0] = 1 + 1 = 2
A[0] + B[1] = 1 + 4 = 5
A[1] + B[0] = 5 + 1 = 6
A[0] + B[2] = 1 + 5 = 6
A[2] + B[0] = 6 + 1 = 7
A[3] + B[0] = 7 + 1 = 8
It is not relevant. The question mentions two pointers, "next" and "prev" which will point to the right/left children. There is no pointer to the parent. As a result, all we can say is if the "sub-data structure" rooting at the given pointer is a tree.
Also, in the code above I am checking all children and since a HashMap is used, it will say no as soon as a cycle is found.
Since it is pointer-based, there is a hint at recursive implementation.
For BinaryTree when starting at root, you need to make sure there is no cycle, e.g., when moving down the tree, you can keep a HashMap to make sure new nodes are not being revisited. Another thing which "I did not consider" but could be important is the consistency of values at different nodes, e.g., do we need to have one child value larger, and the other one smaller than current node?
private static boolean IsBT(GeneralLinkedList gll) {
if (gll == null)
return true;
if (met_this_node.containsKey(gll)) // cycke
return false;
met_this_node.put(gll, true);
return IsBT(gll.next) && (IsBT(gll.prev));
}
private static HashMap<GeneralLinkedList, Boolean> met_this_node;
For DoublyLinkedList;
Assuming that the list is null terminated, all we need to check is that at each node we get:
this.next.prev = this;
this.prev.next = this;
unless "next" or "prev" are null.
private static boolean IsDLL(GeneralLinkedList gll) {
if (gll == null)
return true;
if (met_this_node.containsKey(gll))
return true;
met_this_node.put(gll, true);
if (gll.next != null)
if (gll.next.prev != gll)
return false;
if (gll.prev != null)
if (gll.prev.next != gll)
return false;
return (IsDLL(gll.next) && IsDLL(gll.prev));
}
In case we are allowing for cycles, you should keep the value of one fixed node somewhere an instead of terminating at "null", terminate when you re-visit this node.
- Ehsan December 16, 2013Thanks for the reference to Cn and generators in python. I guess I see your point.
I believe one way to modify my implementation to work as a generator is to store the state after each call (e.g., sequence and the last value of "N" and "nClose" before finding a new sequence).
I checked the code with the given example. Now it gives the correct solution.
- Ehsan March 07, 2014