Implement anagram check and odd-even linked list
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two independent coding tasks.
### Task 1: Check if two strings are anagrams
Implement a function that determines whether two given strings are anagrams of each other.
- Input: Two strings `s` and `t` consisting only of lowercase English letters (`'a'`-`'z'`).
- Output: A boolean value indicating whether `t` is an anagram of `s`. Two strings are anagrams if and only if they contain exactly the same characters with the same multiplicities, in any order.
Requirements:
- Design a function, for example `bool areAnagrams(string s, string t)`.
- Time complexity should be O(n), where n is the total length of the strings.
- Use only O(1) additional space (you may assume a fixed-size alphabet of 26 lowercase letters).
You may assume:
- `0 <= len(s), len(t) <= 10^5`.
---
### Task 2: Reorder a linked list by node index parity
You are given the head of a singly linked list of integers. The nodes are indexed starting from 1 at the head, then 2 for the next node, and so on.
Reorder the list so that:
- All nodes that were originally at odd indices (1, 3, 5, ...) appear first, in their original relative order.
- All nodes that were originally at even indices (2, 4, 6, ...) appear after all odd-index nodes, also in their original relative order.
The reordering must be done in-place by changing the `next` pointers; do not allocate or copy list nodes.
- Input: `ListNode* head` pointing to the head of a singly linked list.
- Output: The head of the reordered list.
Example:
- Input list: `1 -> 2 -> 3 -> 4 -> 5 -> null`
- Output list: `1 -> 3 -> 5 -> 2 -> 4 -> null`
Constraints:
- The number of nodes in the list is in the range `[0, 10^5]`.
- Node values are arbitrary integers.
- The algorithm should run in O(n) time and O(1) extra space.
Quick Answer: This multi-part question evaluates string-processing and frequency-counting skills for anagram detection and linked-list pointer manipulation for reordering nodes by index parity, testing competency in algorithmic implementation and in-place data structure updates.
Check Lowercase Anagrams
Return whether t is an anagram of s for lowercase English strings.
Examples
Input: ('anagram', 'nagaram')
Expected Output: True
Input: ('rat', 'car')
Expected Output: False
Input: ('', '')
Expected Output: True
Hints
- Use a fixed 26-count array.
Odd-Even Linked List Order
Given linked-list values in order, return the values after moving original odd-indexed nodes before original even-indexed nodes while preserving relative order.
Constraints
- Indices are 1-based in the original list
Examples
Input: ([1, 2, 3, 4, 5],)
Expected Output: [1, 3, 5, 2, 4]
Input: ([2, 1, 3, 5, 6, 4, 7],)
Expected Output: [2, 3, 6, 7, 1, 5, 4]
Input: ([],)
Expected Output: []
Hints
- In an actual linked list, maintain odd and even chains.