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 Technical Screen rounds at xAI.

What role is this question designed for?

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

Explain strings, moves, and concurrency

Quick Overview

This question evaluates understanding of string data structures, ownership and move semantics (including Rust-specific move behavior), and concurrency models such as threads versus asynchronous coroutines, testing competencies in memory management, performance analysis, and concurrent programming.

Company: xAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question What is a string in programming languages? What fields are stored in a typical struct string and how would you implement one yourself? What is the time complexity of copying a string? How can move operations be made more efficient? In Rust, does move only modify the reference? What is the difference between a thread and an asynchronous coroutine?

Quick Answer: This question evaluates understanding of string data structures, ownership and move semantics (including Rust-specific move behavior), and concurrency models such as threads versus asynchronous coroutines, testing competencies in memory management, performance analysis, and concurrent programming.

You are given a list of operations on named strings. Each string is represented only by its length. Compute the total number of character copies performed. Allowed operations (tokens are space-separated): - new x n: Create/overwrite variable x with a string of length n. Cost: n (copying n characters). - copy x y: Set x to a copy of y. Cost: len(y). - move x y: Move y into x (x takes y's contents, y becomes empty). Cost: 0. - concat x y z: Set x to y+z. Cost: len(y)+len(z). - mconcat x y z: Move-concatenate y and z into x; x becomes y+z and both y and z become empty. Cost: 0. Overwriting a variable discards its previous content at no cost. For mconcat, the destination x will be different from y and z. Inputs will reference only existing variables. Return the total copy cost. Input to the function is a list of operation strings in the above formats.

Constraints

1 <= len(ops) <= 200000
Variable names match [A-Za-z_][A-Za-z0-9_]*
0 <= n <= 10^9 for new x n
mconcat x y z will have x distinct from y and z
All reads reference variables that have been defined earlier
Sum of all referenced lengths can be up to 10^12; use 64-bit or big integers
Process should be O(len(ops)) time and O(U) space where U is number of variables

Solution

def total_copy_cost(ops: list[str]) -> int:
    store: dict[str, int] = {}
    total = 0
    for line in ops:
        parts = line.strip().split()
        if not parts:
            continue
        op = parts[0]
        if op == 'new':
            if len(parts) != 3:
                raise ValueError('Invalid new operation format')
            x = parts[1]
            n = int(parts[2])
            store[x] = n
            total += n
        elif op == 'copy':
            if len(parts) != 3:
                raise ValueError('Invalid copy operation format')
            x, y = parts[1], parts[2]
            length = store[y]
            store[x] = length
            total += length
        elif op == 'move':
            if len(parts) != 3:
                raise ValueError('Invalid move operation format')
            x, y = parts[1], parts[2]
            if x != y:
                length = store[y]
                store[x] = length
                store[y] = 0
            # cost 0
        elif op == 'concat':
            if len(parts) != 4:
                raise ValueError('Invalid concat operation format')
            x, y, z = parts[1], parts[2], parts[3]
            ly, lz = store[y], store[z]
            store[x] = ly + lz
            total += ly + lz
        elif op == 'mconcat':
            if len(parts) != 4:
                raise ValueError('Invalid mconcat operation format')
            x, y, z = parts[1], parts[2], parts[3]
            # By constraint, x is distinct from y and z
            ly, lz = store[y], store[z]
            store[x] = ly + lz
            store[y] = 0
            store[z] = 0
            # cost 0
        else:
            raise ValueError('Unknown operation: ' + op)
    return total

Explanation

Maintain a dictionary mapping each variable name to its current string length. Iterate over operations, updating lengths and accumulating copy costs. The only operations that add to the total are new (n), copy (len(y)), and concat (len(y)+len(z)). Move operations and mconcat update ownership and set sources to zero length without adding to the total.

Time complexity: O(n), where n is the number of operations. Space complexity: O(u), where u is the number of distinct variables.

Hints

Track only lengths, not string contents.
Use a dictionary mapping variable names to current lengths.
copy and concat add the source lengths to the total cost.
move sets the destination length and empties the source with zero cost.
mconcat sets destination to sum of source lengths and empties both sources with zero cost.

Quick Overview