Student
more
i def did not skip a day
Today I got to solve a problem called first bad version. What you essentially do is try to find which is the bad version given that a function tells you whether or not it is a bad version. All versions after a bad version become bad. For example
FFTTTTTTT
,
The index at 2 or the 3rd item is bad. All the items after are bad.
TTTT
,
Works as well. Here all the items are bad since the very first version is bad.
FT
,
FFFFFFFFFFT
,
Too. A case of only two items is possible and so is a case where the very last one is the only bad one. There has to be at least 1 bad item
Maybe I got lucky, because the solution is really just binary search again. I just implemented it again using a few more conditions to make sure I got all possible corner cases.
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
left = 1
right = n
while(left <= right):
print(left, right)
mid = int((left+right)/2)
if( not isBadVersion(mid) ):
left = mid + 1
else:
if( mid == 1 ):
return 1 # this means all the products are bad
else:
# check if before is false
if( not isBadVersion(mid-1) ):
return mid
else:
right = mid - 1
And with that I was able to get the right answer. What I didn’t show was the work I did on my paper, but I essentially had to figure out what was important. Like looking back one space… nesting conditions for when you can actually move the right index… etc. Anyways, I’m honestly just surprised it was better than 99% of the solutions. Thought it was pretty normal. Maybe the submissions with like infinite time is the reason it is a top 1 percentile solution.
Holy cow this was so hard… I think I need to go back to the drawing board. : 11/16/2021
I will come back in the future…
Okay, so I tried to take notes but it was so boring. I’d rather do questions. There’s this thing called study plan on leetcode which I’m prolly just gonna follow. I clicked on all three study plans: algorithms and dynamic programming (DP). And lemme just say I kinda struggled with the two already for data structures. I started at around 12:30 PM and now it’s 2:06 PM. Contains Duplicate The...
read more
Okay, so I’m premed who likes to code, so I’m just gonna start now. I did a question yesterday on binary search and I will attempt to answer it again right now. Binary Search def binary_search(nums, target): left = 0 right = len(nums) - 1 while(left < right): mid = int((left+right)/2) if( nums[mid] < target ): left = mid + 1 elif( nums[mid] > target ): right = mid -...
read more