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 91 "153. Find Minimum in Rotated Sorted Array" starting from zero
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!
Posting on Qiita on Day 100 will be separated for the time being. I thought it would be nice if the articles with tags were all my articles, and I thought that it might get in the way of other people who are providing useful information, so I will do this. I decided to. There were many parts that could not be reached, but thank you for your cooperation so far.
I will continue to solve problems and write articles on the above personal blog, and if you are interested, I would be grateful if you could take a look there once in a while. Most of Twitter's accounts are for update notifications, so if you are interested in articles that solve Letcode, you may want to follow that as well.
4. Median of Two Sorted Arrays The difficulty level is Hard.
The problem is that there are two sorted arrays nums1 and nums2 with sizes m and n. Find the median of the two sort arrays.
Note that the overall execution time complexity must be ʻO (log (m + n)), and it may be assumed that neither nums1 nor nums2` is empty.
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
Binary search can be used because it is ʻO (log (m + n))`. However, since the difficulty level is Hard, there are two lists to handle. This will increase the amount of code you write, and the more you write, the more likely you are to make mistakes. And both aren't necessarily the same size list, so keep that in mind.
class Solution:
def obtain_kth_num(self, nums1, nums2, k):
nums1_len, nums2_len = len(nums1), len(nums2)
nums1 = [-2**31] + nums1 + [2**31-1]
nums2 = [-2**31] + nums2 + [2**31-1]
left, right = max(0, k-nums2_len), min(nums1_len, k)
while left <= right:
i = (left+right) // 2
j = k - i
if nums1[i] > nums2[j+1]:
right = i - 1
elif nums2[j] > nums1[i+1]:
left = i + 1
else:
return max(nums1[i], nums2[j])
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums_len = len(nums1) + len(nums2)
mid = self.obtain_kth_num(nums1, nums2, (nums_len+1)//2)
if nums_len % 2 == 0:
mid = (mid+self.obtain_kth_num(nums1, nums2, (nums_len+1)//2+1)) / 2.0
return mid
# Runtime: 116 ms, faster than 35.51% of Python3 online submissions for Median of Two Sorted Arrays.
# Memory Usage: 13.9 MB, less than 92.38% of Python3 online submissions for Median of Two Sorted Arrays.
As with DFS, we implemented a separate function and then called it in the main.
I think I explained before that -2 ** 31 and 2 ** 31-1 use this method because there is no long type in Python3.
The ʻobtain_kth_numfunction takes the givennums1 and num2` as input and returns the kth smallest number in the array.
In addition, I referred to this video for the basic idea in binary search. I want to be strong enough to make videos like this ...
So that's it for this time. Thank you for your hard work.
Recommended Posts