Canonical Medium Interview Questions

Background: Canonical develops various applications and systems that require efficient memory management and data retrieval. An LRU (Least Recently Used) Cache is critical in optimizing performance in systems like cloud storage and computing resources.Problem statement: Implement an LRU Cache that supports the following operations: get and put. The get(key) method returns the value of the key if the key exists in the cache, otherwise returns -1. The put(key, value) method updates the value of the key if the key already exists and if the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item. Your implementation should optimize for time complexity of O(1) for both operations.Function/class signature:

• class LRUCache:


• def __init__(self, capacity: int):


• def get(self, key: int) -> int:


• def put(self, key: int, value: int) -> None:

Example 1:
Input:

cache = LRUCache(2)  
cache.put(1, 1)  
cache.put(2, 2)  
output1 = cache.get(1)  # returns 1
cache.put(3, 3)  # evicts key 2
output2 = cache.get(2)  # returns -1 (not found)

Output:

1, -1

Explanation: The key 2 was evicted as it was the least recently used.Example 2:
Input:

cache = LRUCache(1)  
cache.put(2, 1)
output1 = cache.get(2)  # returns 1
cache.put(3, 2)  # evicts key 2
output2 = cache.get(2)  # returns -1 (not found)

Output:

1, -1

Explanation: The cache capacity was 1, key 2 was evicted after the insertion of key 3.Constraints:

• 1 <= capacity <= 3000


• 0 <= key <= 10000


• 0 <= value <= 10000


• Each get and put operation will be called at most 10^4 times.

Background: As a leading provider of open-source software solutions, Canonical needs to ensure its applications run smoothly on Linux-based systems. Identifying resource leaks is crucial for system reliability and performance.
Problem statement: Write a Python function find_resource_leaks that takes a list of system logs (strings) as input. Each log entry contains a timestamp and the resource usage details. The function should identify which resources (e.g., CPU, Memory) exceed a predefined threshold consistently over multiple log entries and return them as a list of resources that have potential leaks.
Function/class signature:

• def find_resource_leaks(logs: List[str], threshold: Dict[str, int]) -> List[str]:

Example 1:

• Input: find_resource_leaks(["2023-10-01T12:00:00 CPU:50 Memory:200", "2023-10-01T12:01:00 CPU:70 Memory:250"], {"CPU": 60, "Memory": 225})


• Output: ['CPU']


• Explanation: The CPU usage continuously exceeds the threshold of 60.

Example 2:

• Input: find_resource_leaks(["2023-10-01T12:00:00 CPU:30 Memory:100", "2023-10-01T12:01:00 CPU:20 Memory:90"], {"CPU": 25, "Memory": 95})


• Output: []


• Explanation: No resources exceed their respective thresholds.

Constraints:

• 1 <= len(logs) <= 1000


• Each log entry is a formatted string


• 0 <= threshold values <= 1000

Background: In many of Canonical's cloud services, real-time monitoring of system metrics is crucial. Frequently, companies need to identify the top values from a stream of data for alerts and performance tuning. This problem relates to processing system logs or metrics efficiently.
Problem statement: Given a stream of integers, implement a method to find the Kth largest element at any point in the stream. You need to support adding new elements to the stream and reporting the Kth largest.
Function/class signature:

• def __init__(self, k: int) -> None


• def add(self, num: int) -> None


• def kth_largest(self) -> int

Example 1:
Input:

kth_largest = KthLargest(3)
kth_largest.add(3)
kth_largest.add(5)
kth_largest.add(10)
kth_largest.add(9)
kth_largest.add(4)

Output: 5
Explanation: The stream contains [3, 5, 10, 9, 4] and the 3rd largest is 5.
Example 2:
Input:

kth_largest = KthLargest(1)
kth_largest.add(3)
kth_largest.add(5)
kth_largest.add(10)

Output: 10
Explanation: The stream contains [3, 5, 10] and the 1st largest is 10.
Constraints:

• 1 <= k <= 1000


• -10^4 <= num <= 10^4


• At most 10^4 calls will be made to add.


• The Kth largest element will be called at least once after each insertion.

Background: Canonical's Snapcraft platform requires unique identifiers for various snaps (software packages). This is crucial for avoiding conflicts and ensuring smooth deployment across systems.Problem statement: Given a string representing a series of snap names, write a function to determine the longest substring that contains only unique characters. Return the length of this substring. Use the input to check for unique snap names in the deployment process.Function/class signature:

• def longest_unique_substring(s: str) -> int:

Example 1:
Input: "snapcraft"
Output: 8
Explanation: The longest substring with all unique characters is "snapcraft" (length 8). Example 2:
Input: "ubuntuubuntu"
Output: 7
Explanation: The longest substring with all unique characters is "ubnto" (length 7). Constraints:

• 1 <= len(s) <= 1000


• s consists of only lowercase English letters.

Background: Canonical frequently processes user inputs and logs data, where understanding character distributions can help optimize storage and processing tasks. This problem models that need by ensuring efficient retrieval and counting capabilities in applications dealing with text data.
Problem statement: Given a string s, implement a function that finds the frequency of each character in the string and returns a dictionary with characters as keys and their corresponding counts as values. The function needs to handle both uppercase and lowercase letters as case sensitive.
Function/class signature:

• def count_character_frequencies(s: str) -> dict:

Example 1:

• Input: "Hello World"


• Output: {'H': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'W': 1, 'r': 1, 'd': 1}


• Explanation: The character 'l' appears 3 times, while others appear as noted.

Example 2:

• Input: "Canonical"


• Output: {'C': 1, 'a': 2, 'n': 2, 'o': 1, 'i': 1, 'c': 1, 'l': 1}


• Explanation: Counts reflect the frequency of each character.

Constraints:

• 1 <= len(s) <= 10^4


• The string will only contain printable ASCII characters.