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.
As a countermeasure, it seems that a site called Let Code will take measures.
A site that trains algorithmic power that can withstand coding tests that are often done in the home.
I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day21 starting from zero "448. Find All Numbers Disappeared in an Array"
Basically, I would like to solve the easy acceptance in descending order.
Twitter I'm doing it.
The difficulty level is easy. Excerpt from Top 100 Liked Questions.
It's a problem that requires a basic knowledge of linked lists.
Given a linked list, determine if there is a cycle in it.
To represent the circulation of the specified linked list, use the integer pos, which ends in the linked list position (starting from 0). If pos is -1, it is assumed that there is no circulation.
Example1
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Since there was a solution, which is rare, I implemented it based on the idea of HashTable and HashMap written there.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
hashmap = {}
while head != None:
if head in hashmap:
return True
hashmap[head] = head
head = head.next
return False
# Runtime: 80 ms, faster than 9.62% of Python3 online submissions for Linked List Cycle.
# Memory Usage: 16.9 MB, less than 100.00% of Python3 online submissions for Linked List Cycle.
The element of head is assigned to the prepared hashmap until the element of head is empty, and the next element is assigned to head.
If the element of head is in hashmap, it means that there is a circular point, so it returns True, and if it does not exist even after checking to the end, it returns False.
I also wrote it with reference to Two Pointers, which was in Solution.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next:
return False
pre,cur = head,head.next
while pre != cur:
if not cur or not cur.next:
return False
pre,cur = pre.next,cur.next.next
return True
# Runtime: 84 ms, faster than 8.98% of Python3 online submissions for Linked List Cycle.
# Memory Usage: 16.9 MB, less than 100.00% of Python3 online submissions for Linked List Cycle.
The speed doesn't change that much.
Speaking of linked lists, this is the bible of coding interviews that are famous overseas. [150 Questions to Train Programming Ability to Fight in the World ~ Book to Become a Programmer of Top IT Companies ~ (Japanese) Book (Soft Cover)](https://www.amazon.co.jp/gp/product/4839942390 / ref = dbs_a_def_rwt_bibl_vppi_i2) It was written in the book that many people are not good at linked lists because they have a lot of recurrence processing, but it took a long time to solve them because they are not used frequently in normal development.
By the way, the above book is old, and now there is a new edition, so if you want to buy it, click here. 189 questions of this coding interview to train programming skills to fight in the world and their solutions I recommend you to buy it.
If there is a good way to write it, I will add it.
Recommended Posts