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 easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

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

Implement list cloning and k-frequency finder

Q: Implement list cloning and k-frequency finder

The first part evaluates understanding of linked data structures and deep-copy semantics, focusing on preserving node values and both next and arbitrary random pointer relationships while reasoning about node identity and cycles, and is commonly asked to assess correctness in memory/reference handling and structural preservation.

You are given two separate coding tasks.

Problem 1: Deep copy a linked list with extra pointers

You are given the head of a singly linked list. Each node has three fields:

val : an integer value
next : a pointer (or reference) to the next node in the list, or null if it is the last node
random : a pointer (or reference) to any node in the list (including possibly itself) or null

The list may contain zero or more nodes.

Task: Implement a function that creates a deep copy of this list. The new list must:

Contain the same number of nodes as the original.
Preserve the val values.
Preserve the structure of both the next and random pointers: for every original node, its copy's next and random should point to the copies of the corresponding original targets.
Share no nodes with the original list (i.e., all nodes in the copied list must be newly allocated).

Return the head of the copied list.

You may assume:

Number of nodes $n$ satisfies $0 \leq n \leq 10^5$ .
The input list may contain arbitrary random pointer configurations, including cycles formed via random pointers.

You should aim for $O(n)$ time complexity and $O(n)$ additional space.

Problem 2: Find the k most frequent integers in an array

You are given an integer array nums and an integer k where $1 \leq k \leq \text{number of distinct elements in } nums$ .

Task: Return any order of the k distinct integers that appear most frequently in nums.

If multiple numbers have the same frequency and they are in the top k by frequency, any order among them is acceptable.
The output should contain exactly k distinct integers.

Examples

Example 1:

Input: nums = [1, 1, 1, 2, 2, 3] , k = 2
One valid output: [1, 2] (because 1 appears 3 times, 2 appears 2 times, 3 appears 1 time)

Example 2:

Input: nums = [4, 4, 4, 5, 5, 6] , k = 1
One valid output: [4] (since it is the most frequent element)

You may assume:

$1 \leq \text{length of } nums \leq 10^5$
$-10^9 \leq nums[i] \leq 10^9$
The number of distinct values in nums is at least k .

Aim for an algorithm that runs in better than $O(n \log n)$ time, where $n$ is the length of nums.

You are given two separate coding tasks.

Problem 1: Deep copy a linked list with extra pointers

You are given the head of a singly linked list. Each node has three fields:

val : an integer value
next : a pointer (or reference) to the next node in the list, or null if it is the last node
random : a pointer (or reference) to any node in the list (including possibly itself) or null

The list may contain zero or more nodes.

Task: Implement a function that creates a deep copy of this list. The new list must:

Contain the same number of nodes as the original.
Preserve the val values.
Preserve the structure of both the next and random pointers: for every original node, its copy's next and random should point to the copies of the corresponding original targets.
Share no nodes with the original list (i.e., all nodes in the copied list must be newly allocated).

Return the head of the copied list.

You may assume:

Number of nodes $n$ satisfies $0 \leq n \leq 10^5$ .
The input list may contain arbitrary random pointer configurations, including cycles formed via random pointers.

You should aim for $O(n)$ time complexity and $O(n)$ additional space.

Problem 2: Find the k most frequent integers in an array

You are given an integer array nums and an integer k where $1 \leq k \leq \text{number of distinct elements in } nums$ .

Task: Return any order of the k distinct integers that appear most frequently in nums.

If multiple numbers have the same frequency and they are in the top k by frequency, any order among them is acceptable.
The output should contain exactly k distinct integers.

Examples

Example 1:

Input: nums = [1, 1, 1, 2, 2, 3] , k = 2
One valid output: [1, 2] (because 1 appears 3 times, 2 appears 2 times, 3 appears 1 time)

Example 2:

Input: nums = [4, 4, 4, 5, 5, 6] , k = 1
One valid output: [4] (since it is the most frequent element)

You may assume:

$1 \leq \text{length of } nums \leq 10^5$
$-10^9 \leq nums[i] \leq 10^9$
The number of distinct values in nums is at least k .

Aim for an algorithm that runs in better than $O(n \log n)$ time, where $n$ is the length of nums.

Implement list cloning and k-frequency finder

Quick Overview

Problem 1: Deep copy a linked list with extra pointers

Problem 2: Find the k most frequent integers in an array

Comments (0)

Implement list cloning and k-frequency finder

Quick Overview

Problem 1: Deep copy a linked list with extra pointers

Problem 2: Find the k most frequent integers in an array

Comments (0)