How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Implement Cache and Count Components | Amazon Interview Question

Quick Overview

This question evaluates proficiency in data structure design and management for the LRU cache and in graph connectivity algorithms for counting connected groups, measuring competency in implementing efficient mutable structures and reasoning about component discovery.

You are asked to solve two coding problems.

Problem 1: Implement an LRU Cache

Design a data structure that supports a fixed-capacity least-recently-used cache.

Implement the following operations:

LRUCache(int capacity) : Initializes the cache with a positive capacity.
int get(int key) : Returns the value associated with key if it exists; otherwise returns -1 . Accessing a key makes it the most recently used item.
void put(int key, int value) : Inserts or updates the value for key . If the cache exceeds its capacity, evict the least recently used key.

Both get and put should run in O(1) average time.

Problem 2: Count Connected Groups in an Undirected Graph

You are given an integer n representing nodes labeled from 0 to n - 1, and a list of undirected edges edges, where each edge is [a, b].

Return the number of connected groups in the graph.

Example:

Input: n = 5, edges = [[0,1], [1,2], [3,4]]
Output: 2
Explanation: Nodes {0,1,2} form one group, and nodes {3,4} form another.

Your solution should handle isolated nodes as separate connected groups.

Quick Overview

You are asked to solve two coding problems.

Problem 1: Implement an LRU Cache

Design a data structure that supports a fixed-capacity least-recently-used cache.

Implement the following operations:

LRUCache(int capacity) : Initializes the cache with a positive capacity.
int get(int key) : Returns the value associated with key if it exists; otherwise returns -1 . Accessing a key makes it the most recently used item.
void put(int key, int value) : Inserts or updates the value for key . If the cache exceeds its capacity, evict the least recently used key.

Both get and put should run in O(1) average time.

Problem 2: Count Connected Groups in an Undirected Graph

You are given an integer n representing nodes labeled from 0 to n - 1, and a list of undirected edges edges, where each edge is [a, b].

Return the number of connected groups in the graph.

Example:

Input: n = 5, edges = [[0,1], [1,2], [3,4]]
Output: 2
Explanation: Nodes {0,1,2} form one group, and nodes {3,4} form another.

Your solution should handle isolated nodes as separate connected groups.

Implement Cache and Count Components

Quick Overview

Problem 1: Implement an LRU Cache

Problem 2: Count Connected Groups in an Undirected Graph

Comments (0)

Implement Cache and Count Components

Quick Overview

Problem 1: Implement an LRU Cache

Problem 2: Count Connected Groups in an Undirected Graph

Comments (0)