It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
Apparently, many engineers take measures on the site called LetCode.
It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.
I wrote it in a big way, but I have no plans to have such an interview at the moment.
However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.
I'm solving it with Python3.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day 90 starting from zero "1011. Capacity To Ship Packages Within D Days"
Twitter I'm doing it.
** Technical Blog Started! !! ** ** I think the technology will write about LetCode, Django, Nuxt, and so on. ** This is faster to update **, so please bookmark it!
153. Find Minimum in Rotated Sorted Array The difficulty level is Medium. This is an excerpt from Leet Code 60 Questions I Want to Solve for Coding Interview Preparation.
The problem is, let's say you rotate an array sorted in ascending order with a pivot you don't know in advance. (It may be helpful to think of an example where [0,1,2,4,5,6,7] becomes [4,5,6,7,0,1,2]. )
Find the smallest element in the list.
It can be considered that there are no duplicate elements in the array.
Example 1:
Input: [3,4,5,1,2] Output: 1
Example 2:
Input: [4,5,6,7,0,1,2] Output: 0
class Solution:
def findMin(self, nums: List[int]) -> int:
low,high = 0,len(nums)-1
while low < high:
mid = (high+low)//2
if nums[mid] > nums[high]:
low = mid + 1
else:
high = mid
return nums[low]
# Runtime: 36 ms, faster than 92.74% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
# Memory Usage: 13.9 MB, less than 83.16% of Python3 online submissions for Find Minimum in Rotated Sorted Array.
It's an algorithm that returns the smallest element each time when the start and end points of a sorted list are swapped while keeping the order. I think that binary search (O (logn)) is an appropriate algorithm, so if I write it as it is, the speed will be good. Recently, I have been re-studying the computational complexity of typical algorithms, so I would like to be able to select the appropriate algorithm as much as possible. It's just a few, so I feel like I have to devote myself.
Anyway, it's good to explain this problem binary search ... Linear search runs out of time, so isn't it very good to look at that? I thought it was a choice of problems.
So that's it for this time. Thank you for your hard work.
Recommended Posts