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 Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Anthropic.

What role is this question designed for?

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

Apply bitwise tricks for performance | Anthropic Coding Question

Apply bitwise tricks for performance

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

For an integer-heavy inner loop, propose bit-level optimizations that reduce branches and memory traffic: e.g., population count usage, fast modulo by power-of-two with masks, branchless conditional updates via bitwise selects, and alignment checks. Provide concise code examples, explain correctness, and analyze the microarchitectural impact (pipeline stalls, ILP, cache behavior).

Quick Answer: This question evaluates proficiency with bitwise operations, branchless programming, low-level performance optimizations, and microarchitectural reasoning about pipeline stalls, instruction-level parallelism, and cache behavior.

You are given a list of non-negative integers `nums`, a `bucket_count` that is guaranteed to be a power of two, an `align` value that is also a power of two, and an integer `threshold`. Simulate the following integer-heavy inner loop and return the final `scores` array: `scores = [0] * bucket_count` `for x in nums:` ` bucket = x & (bucket_count - 1)` ` ones = popcount(x)` ` signed = ones if ones >= threshold else -ones` ` delta = signed if x is aligned to align else -signed` ` scores[bucket] += delta` Here, `popcount(x)` is the number of set bits in `x`, and `x` is aligned to `align` when `x % align == 0`. This problem intentionally mirrors common bit-level performance tricks: - `x & (bucket_count - 1)` replaces modulo when `bucket_count` is a power of two. - `x.bit_count()` is a population count. - A branchless select can be written as `b ^ ((a ^ b) & mask)` with `mask = -int(condition)`. - Alignment can be checked with `(x & (align - 1)) == 0`. Why these tricks are correct: for powers of two, masking keeps exactly the low bits needed for modulo, and alignment means those same low bits are all zero. On real CPUs, these transformations avoid expensive division, reduce unpredictable branches that can cause pipeline stalls, expose more instruction-level parallelism, and keep the hot `scores` array cache-friendly, reducing memory traffic.

Constraints

0 <= len(nums) <= 200000
0 <= nums[i] < 2^63
1 <= bucket_count <= 65536, and bucket_count is a power of two
1 <= align <= 1048576, and align is a power of two
0 <= threshold <= 63

Examples

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

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

Explanation: 5 has popcount 2 and is unaligned, so bucket 1 gets -2. 8 has popcount 1, is aligned, and contributes -1 to bucket 0. 3 has popcount 2 and is unaligned, so bucket 3 gets -2.

Input: ([4, 7, 12, 2], 8, 4, 2)

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

Explanation: 4 contributes -1 to bucket 4, 7 contributes -3 to bucket 7, 12 contributes +2 to bucket 4, and 2 is unaligned with popcount 1 so it flips sign and contributes +1 to bucket 2.

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

Expected Output: [0, 0]

Explanation: No numbers are processed, so every bucket remains 0.

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

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

Explanation: This case includes zero and duplicates. Zero contributes 0. The two copies of 4 both map to bucket 0 and each add +1.

Input: ([15, 16, 31, 32], 8, 16, 4)

Expected Output: [-2, 0, 0, 0, 0, 0, 0, -9]

Explanation: 15 and 31 both have high popcount but are not 16-aligned, so they contribute -4 and -5 to bucket 7. 16 and 32 are aligned but have popcount below the threshold, so they contribute -1 each to bucket 0.

Input: ([1], 1, 1, 0)

Expected Output: [1]

Explanation: With one bucket, every value maps to bucket 0. With align = 1, every value is aligned. Since threshold = 0, the popcount is always taken as positive.

Solution

def solution(nums, bucket_count, align, threshold):
    # Branchless select: returns a if cond else b.
    # If cond is True, mask is -1; otherwise it is 0.
    # Then b ^ ((a ^ b) & mask) picks a or b without an if-statement.
    def select(cond, a, b):
        mask = -int(cond)
        return b ^ ((a ^ b) & mask)

    scores = [0] * bucket_count
    bucket_mask = bucket_count - 1
    align_mask = align - 1

    # In lower-level code, these idioms avoid division, reduce unpredictable
    # branches, improve pipeline usage and ILP, and keep the hot scores array
    # cache-friendly.
    for x in nums:
        # Because bucket_count is a power of two, masking is equivalent to modulo.
        bucket = x & bucket_mask

        # Population count.
        ones = x.bit_count()

        # signed = ones if ones >= threshold else -ones
        signed = select(ones >= threshold, ones, -ones)

        # x is aligned iff its low log2(align) bits are all zero.
        # delta = signed if aligned else -signed
        delta = select((x & align_mask) == 0, signed, -signed)

        scores[bucket] += delta

    return scores

Time complexity: O(n + bucket_count). Space complexity: O(bucket_count).

Hints

Because `bucket_count` is a power of two, `x % bucket_count` can be replaced by a bit mask on the low bits.
Think of each `if` as choosing between two values. A boolean can be turned into a mask and used for a branchless select.

Quick Overview

This question evaluates proficiency with bitwise operations, branchless programming, low-level performance optimizations, and microarchitectural reasoning about pipeline stalls, instruction-level parallelism, and cache behavior.