Design uber backend  define use cases, scope on your own, come up with various components, give high and low level design....
sha256pki
@sha256pki
Posts made by sha256pki

Design Uber Backend

RE: Python, Simple with Explanation
@lee215 said in Python, Simple with Explanation:
cur += Counter()
Hey Lee, can you tell what is "cur += Counter()" about? why is this needed?

RE: Short Java O(n) time, O(1) space, one pass
both high and low increases on '(' both high and low decreases on ')' but high increases and low decreases on '*' < what is meaning of it? If low is greater than zero, consider '*' as ')' and decrease it and balance '(' Also consider it as '(' and increase high. (why?) At the end of this loop low will always be above zero, for whatever reason if low is above 0, it means '*' taken as ')' could not balance '('. My understanding  '*' can be both '(' or ')' high  keeps track of '(' with "*" as '(' low  keeps track of ')' with "*" as ')' Now '*' taken as '(' is overwhelmed by ')'  then string is unbalanced  so far loop saw more ')' than '(' and '*' combined then it can never be balanced again. So if high dips below 0, return False If after taking '*' as ')' if at any point low goes below 0, then its not "definite" that string is unbalanced (probably some '*' were taken wrongly as ')'). For '*' it is easy, just ignore '*'. For ')' can we ignore it?  in a string seen so far '(' match with ')' in which case '*' seen so far ignore  in a string seen so far '(' are lower than '*' and ')' in that case previously seen '*' taken as ')' to be matched with '('.

RE: Short Java O(n) time, O(1) space, one pass
Anybody understands what's the logic here  what is high and low and why are they being incremented or decremented the way they're in this code?

RE: Java 12 lines solution, backtracking
excellent logic but TLE on python

RE: Simple python solution
nice and clever. I guess it is O(n) time where it checks each character only once and also despite recursion it is O(1) because recursion depth can not exceed 2. Nice one!

RE: Share my two O(logm + logn) solutions
Can somebody tell me why to find a search row this formula is used 
mid = (head+tail+1)//2
Instead of
mid = (head+tail)/2

RE: Python Solution from the Author
it would have helped if you had given optimal substructure and recurrence formula

My python solution
class Solution(object): def largestDivisibleSubset(self, nums): """ :type nums: List[int] :rtype: List[int] """ n = len(nums) if n == 0: return [] nums.sort() dp = [[]]*n dp[0] = [nums[0]] maxdp = dp[0] for i in range(1,n): dp[i] = [nums[i]] for j in range(i): if nums[i]%dp[j][1] == 0 and len(dp[i]) < len(dp[j]) + 1: dp[i] = dp[j] + [ nums[i] ] if len(maxdp) < len(dp[i]): maxdp = dp[i] return maxdp

RE: Clear python code
What could be complexity of this?
while dividend >= divisor: temp, i = divisor, 1 while dividend >= temp: dividend = temp res += i i <<= 1 temp <<= 1
If inner loop runs for say x times, then D gets doubled x times so that
D*2^x > N => x > log(N/D) => O(log(N/D))
And about outer loop
N = 2^x * D + M => such that N > M > D
So next time inner loop will run for log(M/D)
So its basicallylog(N/D) + log(M/D) + log(L/D) + ..... + log(D/D) => log(N/D) * Y
If someone can help simplify for Y, it would be great