rchg1988
BAN USERIn order to find the median you have to merge all n rows and get the mid element. So to merge the n rows of m elements you could use a heap, insert in the heap the first element of every row and then repeat this operation: Extract min insert next element of the extracted element row, note that you have to do this (n*m)/2 wich is the position of the median.
1 - Create the heap and insert first n elements - O(n logn)
2- until extract element at (n*m)/ 2 do: extract min insert next element - O(nmlogn)
So the time complexity is O(nmlogn)
* The case n*m is even so the median will be the average of two numbers in the middle is the same because requires O(1) time complexity the average operation.
Good solution. You are missing this case though, s = [1,2,4,4,2,3] this spiral is not intersected and your code will return that is a crossed path because of this check
if(i < s.length && i > 3 && s[i+1] >= (s[i-1]-s[i-3])){
return true;
}
I added one more check inside, so the entire check goes like this:
if (i < s.Length && i > 3 && s[i + 1] >= (s[i - 1] - s[i - 3])
{
if (s[i] >= (s[i - 2] - s[i - 4]) || s[i + 1] >= s[i - 1])
return True
}
This question is to general to give the most effective data structure, first we need to ask question like which scenario our data structure is going to be used, is going to be in constant change or is going to be used for search mostly, what about memory requirements (a LL or BST based DS could be more effective), features of the type of objects we are going to store in it.
But based only in the operations described in the question a simple HashMap solve the problem since the order in which the elements are inserted is not important to the rest of the operations, a DS with a re-sizable array solve the problem too since no time complexity was specified.
This is how I would've answered the question in a real interview.
class DirectionInfo:
def __init__(self):
self.map = {}
class Solution:
def __init__(self, matrix, n):
self.memory = {}
self.matrix = matrix
self.N = n
def LargestPlus(self):
if not self.matrix:
return -1
largest = 0
directions = [(-1, 0), (0, -1), (0, 1)]
for i in range(0, self.N):
for j in range(0, self.N):
if self.matrix[i][j] == 1:
minDir = self.largestOnesSequence((i,j), (1,0), 0)
for d in directions:
res = self.largestOnesSequence((i,j), d, 0)
if res < minDir:
minDir = res
if 4* minDir + 1 > largest:
largest = 4* minDir + 1
return largest
def largestOnesSequence(self, start, direction, distance):
if not self.legal(start):
return 0
if self.get_val(start) == 0:
return 0
if start not in self.memory:
print('Creating direction Info for: ' + str(start))
self.memory[start] = DirectionInfo()
memo = self.memory[start]
if direction not in memo.map:
print('Entro con: '+ str(start) + 'en direccion' + str(direction))
next_coord = Solution.apply_direction(start, direction)
calc = self.largestOnesSequence(next_coord, direction, distance + 1)
memo.map[direction] = calc + 1
if distance > 0:
odirection = Solution.get_opposite(direction)
if odirection not in memo.map:
memo.map[odirection] = distance
return memo.map[direction]
@staticmethod
def get_opposite(direction):
return -1 * direction[0], -1 * direction[1]
@staticmethod
def apply_direction(coord, direction):
return coord[0] + direction[0], coord[1] + direction[1]
def legal(self, coord):
return 0 <= coord[0] < self.N and 0 <= coord[1] < self.N and self.get_val(coord) == 1
def get_val(self, coord):
return self.matrix[coord[0]][coord[1]]
import heapq
class HeapNode:
def __init__(self, value, collIndex):
self.value = value
self.collIndex = collIndex
def __eq__(self, other):
return self.value == other.value
def __lt__(self, other):
return self.value < other.value
def __gt__(self, other):
return self.value > other.value
class MergeIterator:
def __init__(self, sources):
self.sources = sources
self.sourcesCount = len(sources)
self.minHeap = []
for i in range(0, self.sourcesCount):
current = self.sources[i]
if len(current) > 0:
node = HeapNode(current.pop(0), i)
heapq.heappush(self.minHeap, node)
def hasNext(self):
return len(self.minHeap) > 0
def next(self):
if not self.hasNext():
return None
min = heapq.heappop(self.minHeap)
collection = self.sources[min.collIndex]
if len(collection) > 0:
node = HeapNode(collection.pop(0), min.collIndex)
heapq.heappush(self.minHeap, node)
return min.value
class String:
def __init__(self, sentence):
nospaces = ' '.join(sentence.split())
self.words = nospaces.split(' ')
def palindromecheck(self):
if not self.words:
return True
indexInit = 0
indexEnd = len(self.words) - 1
while indexInit <= indexEnd:
if self.words[indexInit] != self.words[indexEnd]:
return False
indexInit += 1
indexEnd -= 1
return True
- rchg1988 September 07, 2015