Dave
BAN USERLet the length of the ith segment be denoted by len(i).
In order for segment i to intersect the path p composed of segments {1, 2, ... i-1} three conditions must be met:
- i >= 4
- len(i-1) <= len(i-3)
- len(i-2) <= (len(i) + len(i-4))
For each segment i, the value len(i) is simply x_i.
We only need to track the last 4 segment lengths and compare them as per the 3 conditions above:
# -*- coding: utf-8 -*-
import unittest
def collision(lst):
for i in range(3, len(lst)):
len_4 = lst[i - 4] if i > 3 else 0
if lst[i - 1] <= lst[i - 3] and lst[i - 2] <= (lst[i] + len_4):
return True
return False
class CollisionTest(unittest.TestCase):
def test_collision(self):
self.assertTrue(collision([2, 1, 1, 2]))
self.assertFalse(collision([1, 2, 3, 4]))
self.assertTrue(collision([1, 1, 2, 2, 1.5, 1.5]))
if __name__ == "__main__":
unittest.main()
Now we understand the question. Time linear in the size of the matrix.
By using swaps instead this could be done in place to save the O(n) space and in linear time (3 swaps for 2x2, 7 swaps for 3x3, 14 swaps for a 4x4, 22 swaps for 5x5 ) but in an interview I'd focus on getting a working solution then making it perform better.
import sys
def rotate(m):
nn = n**2
o = [0] * nn
for x in range(nn):
i = x // n
j = x % n
if i <= j and i < (n - j - 1):
o[x + 1] = m[x]
elif j > i >= (n - j - 1):
o[x + n] = m[x]
elif i >= j and i > (n - j - 1):
o[x - 1] = m[x]
elif j < i <= (n - j - 1):
o[x - n] = m[x]
else:
o[x] = m[x]
return o
if __name__ == "__main__":
matrix = []
n = int(sys.stdin.readline())
for l in range(n):
matrix.extend((int(e) for e in (sys.stdin.readline().split())))
matrix = rotate(matrix)
for r in range(n):
print(matrix[r*n:(r + 1)*n])
This simple version is O(n**2) time and space. It can also be done in-place in O(n) time.
import sys
def rotate(m):
nn = n**2
o = [0] * nn
for i in range(nn):
j = (n * i) % nn + (nn - 1 - i) // n
o[j] = m[i]
return o
if __name__ == "__main__":
matrix = []
n = int(sys.stdin.readline())
for l in range(n):
matrix.extend((int(e) for e in (sys.stdin.readline().split())))
rotate(matrix)
Are there any complexity constraints?
Transpose the matrix and reverse the rows, or just read the columns out backwards. Have I misunderstood what you mean by "rotate"?
When you say "length" are you referring to the entire length of the matrix when represented as an array or simply the dimension "m" of an m x m matrix?
You want the median, which can be found in linear time by applying "divide and conquer" using Hoare's partition from quicksort and the median-of-medians pivot selection. Alternatively, if you can negotiate O(n) "expected" time then use randomised pivot selection. Here is the latter using simple randomised pivot selection. A better pivot can be found on average by using the median of several (such as 3) random selections but as long as you explained your reasoning the simpler solution would be a better choice to implement in an interview.
# -*- coding: utf-8 -*-
import random
import unittest
import sys
def os_select(values, stat, p, r):
def partition():
k = random.randint(p, r)
values[r], values[k] = values[k], values[r]
pivot = values[r]
i, j = p - 1, r
while i < j:
i += 1
while values[i] < pivot:
i += 1
j -= 1
while values[j] > pivot:
j -= 1
if i < j:
values[i], values[j] = values[j], values[i]
values[r], values[i] = values[i], values[r]
return i
if p == r:
return values[p]
q = partition()
if stat == q:
return values[q]
elif stat < q:
return os_select(values, stat, p, q - 1)
return os_select(values, stat - q, q + 1, r)
def min_delta_sum(values):
stat = len(values) // 2
median = os_select(values, stat, 0, len(values) - 1)
return median, sum((abs(x - median) for x in values))
def brute_force(seq):
best = None
delta_sum = sys.maxint
for candidate in seq:
sigma = sum((abs(x - candidate) for x in seq))
if sigma < delta_sum:
delta_sum = sigma
best = candidate
return best, delta_sum
class MedianTest(unittest.TestCase):
def test_min_delta(self):
seq = [1, 2, 3, -4, 5]
self.assertEqual(min_delta_sum(seq), brute_force(seq))
if __name__ == "__main__":
unittest.main()
You want the median. You can find the median in linear time without sorting, and without the range constraint. Divide and conquer recursively (or iteratively) using Hoare's partition from quicksort and the median-of-medians pivot selection. O(n). Alternatively, if you can negotiate O(n) "expected" time then use randomised pivot selection.
- Dave September 02, 2015NB: The supplied sample isn't a BST, but it isn't important to the problem. Simple tree traversal - I use a preorder but it isn't important.
O(n) time and O(n) space (O(log n) space if your tree is unbalanced by at most a constant factor).
from data_structures import Queue
class Node(object):
def __init__(self, key):
super(Node, self).__init__()
self.key = key
self.left = None
self.right = None
def __str__(self):
return str(self.key)
def sum_levels(root):
def visit(node, i):
if node:
try:
sums[i] += node.key
except IndexError:
sums.append(node.key)
i += 1
visit(node.left, i)
visit(node.right, i)
i -= 1
sums = []
visit(root, 0)
return sums
if __name__ == "__main__":
nodes = [1, 2, 3, 4, 5, 1, 2]
q = Queue()
r = Node(nodes[0])
q.enqueue(r)
for k in range(1, len(nodes), 2):
n = q.dequeue()
n.left = Node(nodes[k])
q.enqueue(n.left)
n.right = Node(nodes[k + 1])
q.enqueue(n.right)
print(sum_levels(r))
You need to define your desired operational time and space complexity requirements as there are many data structures (all set data structures) that provide these three fundamental of operations. I expect you were either expected to describe the pros and cons of a few and/or probe the interviewer to refine the requirements before jumping into an answer.
- Dave September 01, 2015Assume it can. Using a two-heap, recursive-partition or order statistic tree will work in either case because they track, as their primary concern, the numbers of elements above and below some partition value. The values themselves are the secondary consideration.
- Dave September 01, 2015@don - A self-balancing BST will absolutely work if you augment each node in the tree with a "size" attribute which holds the number of nodes in the subtree. Inserting new elements only affects the "size" attributes of nodes "local" to the insertion path. Thus updating the "size" attribute does not change the asymptotic time complexity of the insert operation (this holds also for delete). Each insertion is O(log n). Finding ANY order statistic at any time is O(log n).
- Dave September 01, 2015You could also use an Order Statistic Tree, which is an augmented self-balancing binary tree, such as a RedBlack Tree. Implementation of this in an interview could be a bit much as you can see below - I haven't even bothered implementing "delete":
RED = "red"
BLACK = "black"
NIL = None
class Node(object):
def __init__(self, key, value=None):
super(Node, self).__init__()
self.key = key
self.value = value
self.parent = NIL
self.left = NIL
self.right = NIL
self.colour = BLACK
self.size = 0
def __str__(self):
return "NIL" if self == NIL else str(self.key)
# noinspection PyRedeclaration
NIL = Node(None)
class OSTree(object):
def __init__(self):
super(OSTree, self).__init__()
self.root = NIL
def os_select(self, i):
node = self.root
while node != NIL:
rank = node.left.size + 1
if i == rank:
return node
if i < rank:
node = node.left
else:
i -= rank
node = node.right
return node
@staticmethod
def os_rank(node):
rank = node.left.size + 1
while node != NIL:
if node == node.parent.right:
rank += node.parent.left.size + 1
node = node.parent
return rank
def search(self, key):
node = self.root
while node != NIL and node.key != key:
if key < node.key:
node = node.left
else:
node = node.right
return node
def insert(self, key, value=None):
node = Node(key, value)
node.size = 1
x = self.root
while x != NIL:
node.parent = x
x.size += 1
if node.key < x.key:
x = x.left
else:
x = x.right
if node.parent == NIL:
self.root = node
else:
if node.key < node.parent.key:
node.parent.left = node
else:
node.parent.right = node
node.colour = RED
self._insert_fix(node)
def _rotate_left(self, x):
y = x.right
y.parent = x.parent
if y.parent == NIL:
self.root = y
elif y.parent.left == x:
y.parent.left = y
else:
y.parent.right = y
x.right = y.left
if x.right != NIL:
x.right.parent = x
y.left = x
x.parent = y
y.size = x.size
x.size = x.left.size + x.right.size + 1
def _rotate_right(self, x):
y = x.left
y.parent = x.parent
if y.parent == NIL:
self.root = y
elif y.parent.left == x:
y.parent.left = y
else:
y.parent.right = y
x.left = y.right
if x.left != NIL:
x.left.parent = x
y.right = x
x.parent = y
y.size = x.size
x.size = x.left.size + x.right.size + 1
def _insert_fix(self, node):
while node.parent.colour == RED:
if node.parent == node.parent.parent.left:
uncle = node.parent.parent.right
if uncle.colour == RED:
uncle.colour = BLACK
node.parent.colour = BLACK
node.parent.parent.colour = RED
node = node.parent.parent
else:
if node == node.parent.right:
self._rotate_left(node.parent)
node = node.left
node.parent.colour = BLACK
node.parent.parent.colour = RED
self._rotate_right(node.parent.parent)
else:
uncle = node.parent.parent.left
if uncle.colour == RED:
uncle.colour = BLACK
node.parent.colour = BLACK
node.parent.parent.colour = RED
node = node.parent.parent
else:
if node == node.parent.left:
self._rotate_right(node.parent)
node = node.right
node.parent.colour = BLACK
node.parent.parent.colour = RED
self._rotate_left(node.parent.parent)
self.root.colour = BLACK
def delete(self, node):
pass
You have a couple of choices. One is O(n) but will only tell you the median of an accumulated set of numbers. The other uses a minheap and maxheap - this will be O(1) to find the median once you are asked for it but requires O(log n) each time a new number is added to the set.
For the first approach you use the partition subroutine from quicksort to recursively partition the set - ideally roughly in two halves per recursion. To achieve an even split, select a pivot value using a linear time median finding function, such as "median of medians" (if you only need O(n) "expected" runtime then you can use a randomised pivot selection which is simpler to implement in an interview). At each level of recursion you have, in O(1) time, the order statistic of the pivot value. You compare this to the desired order statistic and either return the pivot value as a match, or enter the next level of recursion into the partition containing your desired element. This method can be used to find ANY order statistic, and as a byproduct also yields the set of values above and below that statistic - eg the 10 largest numbers in the set. The algorithm is O(n) because you have at most O(log n) recursions and at each level you have to scan half as many elements as the previous level.
A Python example implementation of approach two follows - we define the "median" of an even number of elements to be the greater of the two medial values:
def find_median(line):
seq = (int(i) for i in line.strip().split(' '))
left_heap = Heap(MAX)
right_heap = Heap(MIN)
left_heap.push(-(2 ** 63))
right_heap.push(2 ** 63 - 1)
for num in seq:
if right_heap.size > left_heap.size:
if num < right_heap.peek():
left_heap.push(num)
else:
left_heap.push(right_heap.replace(num))
else:
if num > left_heap.peek():
right_heap.push(num)
else:
right_heap.push(left_heap.replace(num))
return right_heap.peek()
def incarray(seq):
num = 0
for digit in seq:
num = num * 10 + digit
num += 1
result = []
while num:
result.append(num % 10)
num //= 10
result.reverse()
return result
or using O(1) auxiliary space, iterating only once
def incarray2(seq):
i = len(seq) - 1
c = 1
while i >= 0 and c:
d = seq[i] + 1
seq[i] = d % 10
c = d // 10
i -= 1
if c:
seq.insert(0, 1)
return seq
Repjesusitahyer, Data Engineer at ASAPInfosystemsPvtLtd
Hello Everyone, I am Jesusita and I am passionate about writing the stories about powerful mantra to get what you ...
Repcarmelalewis9, Area Sales Manager at AMD
I am fond of reading stories then reading articles which are all about a story of a beautiful nature and ...
Close but I think it should be:
I don't think there is any escaping the need to track at least one value outside the input list because a collision can occur with only 4 steps, but for > 4 steps your collision condition becomes steps[i - 3] >= steps[i - 1] and steps[i - 2] <= (steps[i] + steps[i - 4]).
- Dave September 05, 2015For example test [1, 1, 2, 2, 1.5, 1.5]