diogo.neves
BAN USERI think this problem depends a lot on the range of the expected values and how large do we expect K to be.
We do know K <= N, where N is the length of the input array, otherwise it wouldn't make sense.
I've designed the class interface thinking that this could also be solved with a running stream of values.
My assumptions are that K is much smaller than N (very small!).
I've got a running time of O(N * K) and extra space of O(K). I could also improve the solution using a Heap of max size K but again, assuming K is very small, that would be extra complexity for little added value.
Here's my Python solution:
You can either call the static method to solve it in batch or keep pushing and querying the values (provided K is a constant).
class KthLargest(object):
def __init__(self, k):
self._largest = [None] * (k + 1)
def get_kth(self):
return self._largest[0]
def push(self, value):
if self._largest[0] and self._largest[0] > value:
return
i = 0
while i < len(self._largest) - 1 and self._largest[i + 1] < value:
self._largest[i] = self._largest[i + 1]
i += 1
self._largest[i] = value
@staticmethod
def kth_largest(iterable, k):
largest = KthLargest(k)
for value in iterable:
largest.push(value)
return largest.get_kth()
I also iterate over each guard (as I find them using a generator).
For each guard I do a BFS and update any distances in place.
It won't update distances if it is a wall or there's a shorter distance at that location already (near another guard).
A little optimisation that, depending on the configuration of the board, might save some time on average is:
Don't explore neighbours of locations that already have a shorter distance to another guard. Because of the BFS expansion, it means it isn't possible to find another location with a shorter distance afterwards. (p.s. that's an advantage over doing DFS here).
Here's my Python solution:
class GuardDistance(object):
def __init__(self, matrix):
self._matrix = matrix
self._size = len(matrix)
def matrix(self):
return self._matrix
def calculate_distances(self):
for gx, gy in self._find_guards():
visited = set()
frontier = self._neighbours(gx, gy, 0, visited)
while frontier:
(x, y), distance = frontier.pop(0)
visited.add((x, y))
if self._update(x, y, distance):
frontier += self._neighbours(x, y, distance, visited)
def _find_guards(self):
return ((x, y) for x in xrange(self._size)
for y in xrange(self._size)
if self._matrix[x][y] == 'G')
def _neighbours(self, x, y, distance, visited):
neighbours = []
for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
nx, ny = x + dx, y + dy
if self._valid_location(nx, ny) and (nx, ny) not in visited:
neighbours.append(((nx, ny), distance + 1))
return neighbours
def _valid_location(self, x, y):
return 0 <= x < self._size and 0 <= y < self._size
def _update(self, x, y, distance):
value = self._matrix[x][y]
if str(value) not in 'GW' and (value == 'O' or value >= distance):
self._matrix[x][y] = distance
return True
else:
return False
# ere's some code to run this
solution = GuardDistance([['O','O','O','G'],
['O','W','W','W'],
['O','W','G','W'],
['O','O','O','O']])
solution.calculate_distances()
print solution.matrix()
I also used divide and conquer and dynamic programming here.
I've implemented it recursively just because I love it's simplicity and the solution should run in O(N) space and time so, unless we're dealing with a long string, it should work fine.
I have separated the dynamic programming solution from the divide and conquer approach in 2 functions (one being a cache decorator).
# Yes, this is Python
def cache(func):
cache = {}
def wrapper(value):
if value in cache:
print 'cache hit: %s (%d)' % (value, len(cache))
return cache[value]
else:
count = func(value)
cache[value] = count
print 'cache miss: %s (%d)' % (value, len(cache))
return count
wrapper.__name__ = func.__name__
return wrapper
@cache
def count_encodings(value):
if len(value) < 2:
return 1
z = 26
count = count_encodings(value[1:])
# if the first 2 digits can encode a letter
if int(value[:2]) <= z:
count += count_encodings(value[2:])
return count
Repsheenaamajors, System Administrator at Achieve Internet
Teach art classes to a diverse array of students of varying ages and abilities. Strong desire to incorporate a multidimensional ...
Since it can only move a maximum of X units size times, wouldn't it be always possible to build a wall? Maybe there's a constraint on the size of the wall?
- diogo.neves June 26, 2016