albin.severinson
BAN USER
Comments (3)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
@LinkSausage What do you think about bounding the font sizes you need to consider and then doing binary search?
In other, words find a font that will for sure fit and one that will for sure not fit. Then do binary search on the remaining fonts. You could maybe even improve the speed by using the average font size somehow.
Comment hidden because of low score. Click to expand.
0
of 0 vote
You might want to take a different approach if you're dealing with sparse matrices. This runs in O(n log n), where n is the number of nonzero entries. This assumes zigzag means going bottomleft to top right for each diagonal. If you want to alternate direction you need to sort each diagonal separately, I think.
# Matrix element
class Element(object):
def __init__(self, row, col, val):
self.row = row
self.col = col
self.val = val
return
# Coordinate list matrix class
class Matrix(object):
def __init__(self):
self.rows = 0
self.cols = 0
self.elements = list()
return
def add(self, e):
assert type(e) is Element
self.elements.append(e)
if e.row > self.rows:
self.rows = e.row
if e.col > self.cols:
self.cols = e.col
return
class ZZIter(object):
def __init__(self, matrix):
assert type(matrix) is Matrix
elements = sorted(matrix.elements, key=lambda x: x.row)
elements = sorted(elements, key=lambda x: x.row + x.col)
self.elements = elements
self.index = 0
return
def __iter__(self):
return self
def __next__(self):
if self.index == len(self.elements):
raise StopIteration
e = self.elements[self.index]
self.index += 1
return e

albin.severinson
January 05, 2017 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Open Chat in New Window
Open Chat in New Window
Don't think we have a python solution yet. This is a bit clunky, but it does the job. Forgetting to take negative numbers into account is probably a common mistake.
 albin.severinson January 05, 2017