30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Unix Cd Command with Symbolic Link Resolution

Simulate the Unix cd command by implementing path resolution for relative paths ('.' and '..'), absolute paths, and symbolic links while detecting potential cycles. Use stack-based directory traversal for path management and depth-first search to handle symbolic link mappings and cycle detection. Handle edge cases including redundant slashes and invalid path references.

Asked at:

OpenAI

DESCRIPTION

Simulate the behavior of the Unix cd (change directory) command by implementing path resolution for navigating a file system. The program must correctly interpret relative paths, absolute paths, and symbolic links, while ensuring cycle detection for symbolic links that may form loops.

Input:


currentPath = "/foo/bar", command = "boo/./../doe"

Output:


"/foo/bar/doe"

Explanation: First 'boo' is appended, '.' means stay (no change), then '..' goes up one level, then 'doe' is appended

Constraints:

Paths are Unix-style with forward slashes
Absolute paths start with '/', relative paths do not
'..' means parent directory, '.' means current directory
Multiple consecutive slashes should be treated as a single slash
Symbolic links may exist and must be resolved
Cycles in symbolic links must be detected and handled
Cannot go above root directory (/.., /../../ etc. should resolve to /)

Understanding the Problem

Let's understand what we're being asked to do. We have a current working directory (like /foo/bar) and a cd command (like ../boo or /boo), and we need to compute the final path after executing the command.

Tracing through examples:

From /foo/bar, command boo → append to current path → /foo/bar/boo
From /foo/bar, command /boo → absolute path (starts with /) → /boo
From /foo/bar, command ../boo → go up one level (..), then down to boo → /foo/boo
From /foo/bar, command boo/././doe → append boo, . means stay (no change), . again (no change), then doe → /foo/bar/boo/doe

Important constraints: We need to handle symbolic links (shortcuts that point to other directories) and detect cycles (when following links creates an infinite loop). We also need to handle redundant slashes like //foo///bar (should be treated as /foo/bar).

Edge cases to consider: What if we try to go up from root (/..)? What if the path has trailing slashes (/foo/bar/)? What if a symbolic link points to itself or creates a cycle? What if the command is just . or ..?

Building Intuition

A file path is essentially a sequence of directory names separated by slashes. We can break the path into components and process them one by one.

Special components like . (current directory) and .. (parent directory) modify our position in the directory tree. The key insight is that .. means 'go back one level' - this is a last-in, first-out operation where we need to undo the most recent directory we entered.

By treating the path as a sequence of operations (enter directory, go back, stay), we can use a data structure that naturally supports adding and removing from the end.

For symbolic links, we need to track which paths we've visited while resolving links. If we encounter the same path twice, we've found a cycle and should stop to avoid infinite loops.

Think of navigating directories like building a tower of blocks:

Each directory name adds a block to the top
The .. command removes the top block (go back one level)
The . command does nothing (stay at current level)
An absolute path (starting with /) means clear all blocks and start fresh

For symbolic links, imagine following a trail of breadcrumbs. If you ever see the same landmark twice, you're walking in circles and need to stop.

Common Mistakes

Forgetting to handle multiple consecutive slashes (//foo///bar should be treated as /foo/bar) - split by '/' and filter out empty strings

Not checking if stack is empty before popping for '..' - attempting to go above root should be handled gracefully (stay at root)

Failing to detect cycles in symbolic links - must maintain a visited set of paths to avoid infinite loops

Incorrectly handling absolute vs relative paths - absolute paths (starting with /) should clear the stack first, relative paths should build on current path

Not normalizing the final path - ensure no trailing slashes (except for root '/') and no redundant components remain

Optimal Solution

Use a stack-based approach to manage directory traversal. Split the path into components by '/' delimiter. For each component: if it's a regular directory name, push it onto the stack; if it's '..', pop from the stack (go up one level); if it's '.', do nothing (stay at current level). Handle absolute paths by clearing the stack first. For symbolic links, use depth-first search with a visited set to track paths and detect cycles. Join the final stack contents with '/' to produce the resolved path.

def cd_command(currentPath, command):
    """
    Simulate Unix cd command with path resolution.
    Handles relative paths (. and ..), absolute paths, and symbolic links with cycle detection.
    """
    # Define symbolic link mappings for testing
    symlinks = {
        '/usr/local': '/usr',
        '/home/user/docs': '/home/user/documents',
        '/var/log': '/var/logs',
        '/tmp/link': '/tmp'
    }
    
    def normalize_path(path):
        """Remove redundant slashes and trailing slashes."""
        # Replace multiple slashes with single slash
        while '//' in path:
            path = path.replace('//', '/')
        # Remove trailing slash unless it's root
        if len(path) > 1 and path.endswith('/'):
            path = path[:-1]
        return path
    
    def resolve_path(base_path, target_path, visited):
        """Resolve path with symbolic link handling and cycle detection using DFS."""
        # Normalize the target path
        target_path = normalize_path(target_path)
        
        # Determine if absolute or relative path
        if target_path.startswith('/'):
            # Absolute path - start from root
            working_path = target_path
        else:
            # Relative path - combine with current path
            working_path = base_path + '/' + target_path
        
        # Normalize combined path
        working_path = normalize_path(working_path)
        
        # Check for cycle in symbolic link resolution
        if working_path in visited:
            return "Error: Symbolic link cycle detected at " + working_path
        
        # Add current path to visited set for cycle detection
        visited.add(working_path)
        
        # Split path into components for stack-based traversal
        components = working_path.split('/')
        
        # Initialize stack for directory traversal
        stack = []
        
        # Process each component
        for component in components:
            # Skip empty components (from leading/trailing slashes)
            if component == '' or component == '.':
                # Current directory - do nothing
                continue
            elif component == '..':
                # Parent directory - pop from stack if not empty
                if stack:
                    stack.pop()
            else:
                # Regular directory - push onto stack
                stack.append(component)
        
        # Build resolved path from stack
        if not stack:
            resolved = '/'
        else:
            resolved = '/' + '/'.join(stack)
        
        # Check if resolved path is a symbolic link
        if resolved in symlinks:
            # Follow symbolic link recursively with DFS
            link_target = symlinks[resolved]
            return resolve_path(resolved, link_target, visited)
        
        return resolved
    
    # Normalize current path
    currentPath = normalize_path(currentPath)
    
    # Initialize visited set for cycle detection
    visited = set()
    
    # Resolve the path with symbolic link handling
    result = resolve_path(currentPath, command, visited)
    
    return result

Start cd command simulation

0 / 26

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n + m) Where n is the length of currentPath and m is the length of command. We process each character once when splitting and building the path. For symbolic links, DFS visits each unique path at most once.

Space Complexity: O(n + m) The stack stores directory components (O(n) for depth of path). The visited set for cycle detection stores paths we've seen (O(m) in worst case). The final path string is O(n + m).

What We've Learned

Stack-based path traversal: Use a stack to manage directory components when processing paths - push directories onto the stack and pop for '..' operations. This naturally handles nested directory structures and makes backtracking trivial, perfect for any hierarchical navigation problem.
Tokenization before processing: Split paths by '/' delimiters and process each component individually rather than manipulating the raw string. This cleanly handles edge cases like redundant slashes ('/foo//bar'), trailing slashes, and makes '.' and '..' logic straightforward to implement.
Cycle detection with visited set: When resolving symbolic links, maintain a visited set of paths encountered during the current resolution chain. Before following a symlink, check if the target is already in the set - this prevents infinite loops in circular symlink references.
Absolute vs relative path handling: Always check if a path starts with '/' to determine if it's absolute or relative. For absolute paths, clear your stack and start fresh; for relative paths, build upon the current directory stack. Missing this distinction causes incorrect path resolution.
Normalization through reconstruction: After processing all path components with the stack, reconstruct the final path by joining stack elements with '/' and prepending '/'. This ensures a canonical format regardless of input variations (multiple slashes, dots, etc.).
Real-world file system operations: This pattern directly applies to implementing file system utilities, URL path resolution in web servers, package dependency resolution, and any system requiring hierarchical namespace navigation with shortcuts or aliases.

Test Your Understanding

Why is stack the right data structure for this problem?

stack provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late September, 2025

OpenAI

Staff

Early August, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More