Solve Python Challenges: Reverse String, Palindrome, Fibonacci, Unique List
Company: OneMain Financial
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
Live coding round – four quick Python exercises
##### Question
Implement a function that reverses a string in-place. Write code that returns True if a given integer is a palindrome, False otherwise. Generate the n-th Fibonacci number iteratively without recursion. Given an unsorted list of integers, return a new list containing only the unique values, preserving original order.
##### Hints
Each task should run in O(n) time or better, and you may not import external libraries.
Quick Answer: This question evaluates fundamental programming skills such as string manipulation, algorithmic reasoning for numeric patterns, sequence generation, and data deduplication within the Coding & Algorithms domain for a Data Scientist role.
Given an unsorted list of integers nums, return a new list containing each distinct value exactly once, preserving the order of their first occurrence. Do not sort or otherwise reorder the input.
Constraints
- 0 <= len(nums) <= 200000
- -1000000000 <= nums[i] <= 1000000000
- Preserve the order of first occurrences
- Do not sort the input
- Target time complexity: O(n)
- Target space complexity: O(n)
- Do not import external libraries
Solution
from typing import List
def unique_preserve_order(nums: List[int]) -> List[int]:
seen = set()
result: List[int] = []
for x in nums:
if x not in seen:
seen.add(x)
result.append(x)
return result
Explanation
Iterate once over nums, maintaining a set of seen values. For each element, if it is not in seen, add it to both seen and the result list. This preserves the order of first occurrences while removing duplicates.
Time complexity: O(n). Space complexity: O(n).
Hints
- Use a hash set to track which values have been seen.
- Append a number to the result only the first time it appears.
- Avoid sorting; membership checks in a set are O(1) on average.