Quick Overview

This question evaluates proficiency in linked list manipulation, duplicate detection and removal, and algorithmic complexity analysis for both sorted and unsorted data.

Remove duplicates in linked list

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

##### Question Given a linked list, remove all duplicate values so that each value appears only once. Provide solutions for both sorted and unsorted linked lists, along with their time and space complexity analyses.

Overview: This question evaluates proficiency in linked list manipulation, duplicate detection and removal, and algorithmic complexity analysis for both sorted and unsorted data.

You are given the node values of a singly linked list in order as an array values and a boolean is_sorted indicating whether the list is in non-decreasing order. Remove all duplicate values so that each value appears only once. Preserve the original relative order of the first occurrences. Return the resulting array of values.

Constraints

  • 0 <= len(values) <= 200000
  • Values fit in 32-bit signed integer range
  • If is_sorted is True, values is non-decreasing
  • Preserve the relative order of first occurrences in the output
  • Expected time: O(n); Space: O(1) if is_sorted else O(n)

Hints

  1. If the list is sorted, compare each value to the last kept value to skip duplicates.
  2. If the list is unsorted, use a hash set to track seen values and keep only the first occurrence.
  3. Ensure the output preserves the order of first occurrences.

Loading coding console...

Show the approach

Approach

For sorted input, duplicates appear consecutively. Iterate once and append a value only if it differs from the last kept value, yielding O(n) time and O(1) extra space. For unsorted input, maintain a hash set of seen values and append values not seen before, preserving the order of first occurrences. This uses O(n) time and O(n) extra space.

Time complexity:
O(n) for both cases
Space complexity:
O(1) if is_sorted is True; otherwise O(n)