GO ALGORITHMS

Soluciones de lógica con Golang

Linked Lists

Linked List Reversal

Easy

Reverse a singly linked list.

Example:

Remove the Kth Last Node From a Linked List

Medium

Return the head of a singly linked list after removing the kth node from the end of it.

Example:

Constraints:

  • The linked list contains at least one node.

Linked List Intersection

Easy

Return the node where two singly linked lists intersect. If the linked lists don’t intersect, return null.

Example:

Output: Node 8

How the custom test cases work:

The input is designed to describe how the two input linked lists intersect. Here’s how the skip inputs work:

  • skip_A: The number of nodes to skip in list A (from the head) to reach the intersection node.
  • skip_B: The number of nodes to skip in list B (from the head) to reach the intersection node.

For a linked list with no intersection, set skip_A and skip_B to the length of their respective linked lists, which effectively skips all nodes in each linked list.

LRU Cache

Hard

Design and implement a data structure for the Least Recently Used (LRU) cache that supports the following operations:

  • LRUCache(capacity: int): Initialize an LRU cache with the specified capacity.
  • get(key: int) -> int: Return the value associated with a key. Return -1 if the key doesn’t exist.
  • put(key: int, value: int) -> None: Add a key and its value to the cache. If adding the key would result in the cache exceeding its size capacity, evict the least recently used element. If the key already exists in the cache, update its value.

Example:

Input: [
  put(1, 100),
  put(2, 250),
  get(2),
  put(4, 300),
  put(3, 200),
  get(4),
  get(1),
],
  capacity = 3
Output: [250, 300, -1]

Explanation:

put(1, 100)  # cache is[1: 100]
put(2, 250)  # cache is[1: 100, 2: 250]
get(2)       # return 250
put(4, 300)  # cache is[1: 100, 2: 250, 4: 300]t
put(3, 200)  # cache is[2: 250, 4: 300, 3: 200]
get(4)       # return 300
get(1)       # key 1 was evicted when adding key 3 due to the capacity
             # limit: return -1

Constraints:

  • All keys and values are positive integers.
  • The cache capacity is positive.

Palindromic Linked List

Easy

Given the head of a singly linked list, determine if it’s a palindrome.

Example 1:

Output: True

Example 2:

Output: False

Flatten a Multi-Level Linked List

Medium

In a multi-level linked list, each node has a next pointer and child pointer. The next pointer connects to the subsequent node in the same linked list, while the child pointer points to the head of a new linked list under it. This creates multiple levels of linked lists. If a node does not have a child list, its child attribute is set to null.

Flatten the multi-level linked list into a single-level linked list by linking the end of each level to the start of the next one.

Example:

How the custom test cases work

The input is a nested list representation of a multi-level linked list. Each element in the list represents a node which includes a value and a child list, with the entire data structure using the following structure:

[[val_1, [child_list_1]], [val_2, [child_list_2]], ...]

Each child list follows this same structure.