How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Salesforce.

What role is this question designed for?

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

Remove duplicates and find constrained longest subsequence

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Take-home Project

You are given two independent coding tasks. ## Task 1: Remove duplicates from a linked list Given the head of a **singly linked list** (not necessarily sorted), remove duplicate values so that **each value appears only once**, keeping the **first occurrence** of each value and **preserving the original relative order** of the remaining nodes. - **Input:** `head` of a singly linked list where each node has fields `val` and `next`. - **Output:** the head of the de-duplicated linked list. - **Constraints (example):** number of nodes `n` up to `10^5`; node values fit in 32-bit signed int. **Example** - Input: `1 -> 3 -> 1 -> 2 -> 3 -> null` - Output: `1 -> 3 -> 2 -> null` ## Task 2: Longest subsequence of x that is a substring of y Given two strings `x` and `y`, find **one** longest string `s` such that: 1. `s` is a **subsequence** of `x` (characters chosen in order, not necessarily contiguous), and 2. `s` is a **substring** of `y` (contiguous segment of `y`). If multiple answers have the same maximum length, you may return **any one** of them. - **Input:** strings `x`, `y` - **Output:** a string `s` meeting the conditions with maximum possible length (or an empty string if no non-empty solution exists). - **Constraints (example):** `1 ≤ |x|, |y| ≤ 2000`; characters are lowercase English letters. **Example** - `x = "abac"`, `y = "zzbaczz"` - One valid output: `"bac"` (it is a subsequence of `x` and a substring of `y`).

Quick Answer: This question evaluates data structure manipulation and string-processing competencies, specifically linked-list deduplication and finding the longest string that is both a subsequence of one string and a substring of another.

Remove Duplicates from a Linked List (Keep First Occurrence)

Given a singly linked list (not necessarily sorted), remove duplicate values so that each value appears only once. Keep the FIRST occurrence of each value and preserve the original relative order of the remaining nodes. To keep the challenge language-agnostic and easy to test, the linked list is represented as an ordered array of its node values (the value at index 0 is the head). Return the array of values after de-duplication, in their original surviving order. Example: Input list: 1 -> 3 -> 1 -> 2 -> 3 -> null, represented as [1, 3, 1, 2, 3] Output: [1, 3, 2] (the second 1 and second 3 are removed) Constraints: - 0 <= n <= 10^5 nodes - node values fit in a 32-bit signed integer

Constraints

0 <= n <= 10^5 nodes
Node values fit in a 32-bit signed integer
The list is NOT necessarily sorted
Keep the first occurrence of each value; preserve original relative order

Examples

Input: ([1, 3, 1, 2, 3],)

Expected Output: [1, 3, 2]

Explanation: 1 -> 3 -> 1 -> 2 -> 3: the repeated 1 and 3 are dropped, leaving 1 -> 3 -> 2 in original order.

Input: ([],)

Expected Output: []

Explanation: Empty list stays empty.

Input: ([5],)

Expected Output: [5]

Explanation: Single node has no duplicates.

Input: ([7, 7, 7, 7],)

Expected Output: [7]

Explanation: All values identical collapse to a single node holding the first occurrence.

Input: ([-1, -2, -1, -3, -2, 0],)

Expected Output: [-1, -2, -3, 0]

Explanation: Negative values work the same way; duplicates of -1 and -2 are removed.

Input: ([1, 2, 3, 4, 5],)

Expected Output: [1, 2, 3, 4, 5]

Explanation: No duplicates means the list is returned unchanged.

Hints

Because the list may be unsorted, you cannot rely on duplicates being adjacent — track which values you have already seen.
A hash set of seen values lets you decide in O(1) whether to keep or skip each node, giving an overall O(n) single pass.
Append a value to the output only the first time you encounter it; that automatically keeps the first occurrence and the original order.

Longest Subsequence of x That Is a Substring of y

Given two strings x and y, find one longest string s such that: 1. s is a SUBSEQUENCE of x (characters chosen in order, not necessarily contiguous), and 2. s is a SUBSTRING of y (a contiguous segment of y). Return any one such s of maximum possible length, or the empty string if no non-empty answer exists. For this challenge the answer is made unique with a deterministic tie-break: among all substrings of y that are subsequences of x, return the one of maximum length, and if several share that maximum length, return the one with the smallest starting index in y. Example: x = "abac", y = "zzbaczz" -> "bac" (a subsequence of x and a contiguous substring of y) Constraints: - 1 <= |x|, |y| <= 2000 - characters are lowercase English letters

Constraints

1 <= |x|, |y| <= 2000
Characters are lowercase English letters
s must be a subsequence of x (order preserved, gaps allowed)
s must be a contiguous substring of y
Tie-break for uniqueness: longest length, then smallest start index in y

Examples

Input: ("abac", "zzbaczz")

Expected Output: bac

Explanation: 'bac' is a subsequence of 'abac' (positions a_b_a_c -> b,a,c) and the contiguous substring y[2:5]; it is the longest such window.

Input: ("abcde", "qwerty")

Expected Output: e

Explanation: Only 'e' from y appears in x at all, so the longest common subsequence-substring is the single character 'e'.

Input: ("abc", "xyz")

Expected Output:

Explanation: x and y share no characters, so no non-empty answer exists.

Input: ("aaa", "baaab")

Expected Output: aaa

Explanation: The substring y[1:4] = 'aaa' is a subsequence of x='aaa'; the longer windows contain 'b', which is not in x.

Input: ("abcdef", "abcdef")

Expected Output: abcdef

Explanation: The entire y is a substring of itself and a subsequence of x, so the answer is the whole string.

Input: ("a", "a")

Expected Output: a

Explanation: Single matching character on both sides.

Hints

A substring of y is contiguous, but a subsequence of x is not — so fix the candidate as a window of y and test whether that window can be embedded as a subsequence of x.
Testing whether a string s is a subsequence of x is a single linear two-pointer scan over x: advance through x consuming characters of s in order.
Search by decreasing length and, for equal length, by increasing start index in y; return the first window that is a subsequence of x to satisfy the deterministic tie-break.

Quick Overview

This question evaluates data structure manipulation and string-processing competencies, specifically linked-list deduplication and finding the longest string that is both a subsequence of one string and a substring of another.