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 Confluent.

What role is this question designed for?

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

Implement Tail and Find Monster Cost | Confluent Coding Question

Implement Tail and Find Monster Cost

Company: Confluent

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

This entry contains two coding tasks from the same interview category. ### Task A: Implement a file tail operation Implement a function `tail(filePath, n)` that returns the last `n` lines of a text file in their original order. Requirements: - The input is a real file path, not an in-memory string. You should be comfortable creating a small text file as a test case and reading it back. - If the file has fewer than `n` lines, return all lines. - If `n == 0`, return an empty result. - A trailing newline at the end of the file should not create an extra empty line. - Discuss or implement an approach that does not load the entire file into memory when the file is very large. ### Task B: Find minimum monster cost in a grid You are given a 2D grid representing a dungeon: - `S` is the start cell. - `E` is the exit cell. - `.` is an empty cell with cost `0`. - `M` is a monster cell with cost `1` to enter. - `#` is a wall that cannot be entered. From any cell, you may move up, down, left, or right. Return the minimum total monster cost required to travel from `S` to `E`. If the exit is unreachable, return `-1`. Follow-ups: - Return one path that achieves the minimum cost. - Extend the grid so each monster cell has an arbitrary non-negative integer cost instead of cost `1`.

Quick Answer: This question evaluates competency in efficient file I/O and streaming techniques for implementing tail, and in graph search and shortest-path algorithms with path reconstruction for computing minimum monster cost in a grid.

Part 1: Tail the Last N Lines of a Text File

Implement a function that returns the last n lines of a text file in their original order. Return lines without trailing newline characters. If the file has fewer than n lines, return all of them. If n is 0, return an empty list. The official interview version takes a real file path. For the self-contained example tests in this JSON, the first argument may also be a dictionary like {"path": "example.txt", "contents": "..."}; in that case, create the file first and then tail it.

Constraints

0 <= n <= 10^5
The file is a UTF-8 text file.
Your approach should avoid loading the entire file into memory when the file is very large.

Examples

Input: ({"path": "tail_case_1.txt", "contents": "alpha\nbeta\ngamma\n"}, 2)

Expected Output: ["beta", "gamma"]

Explanation: The file ends with a trailing newline, but that should not create an extra empty line.

Input: ({"path": "tail_case_2.txt", "contents": "one\ntwo"}, 5)

Expected Output: ["one", "two"]

Explanation: The file has fewer than n lines, so return all lines.

Input: ({"path": "tail_case_3.txt", "contents": "a\nb\nc\n"}, 0)

Expected Output: []

Explanation: When n is 0, the result is empty.

Input: ({"path": "tail_case_4.txt", "contents": "x\n\ny"}, 3)

Expected Output: ["x", "", "y"]

Explanation: Blank lines inside the file are real lines and must be preserved.

Hints

A fixed-size deque can keep only the most recent n lines while streaming through the file.
Iterating over a file line by line will not create an extra empty line just because the file ends with a trailing newline.

Part 2: Minimum Monster Cost from S to E

You are given a rectangular grid of characters. 'S' is the start, 'E' is the exit, '.' is an empty cell with cost 0 to enter, 'M' is a monster cell with cost 1 to enter, and '#' is a wall that cannot be entered. You may move up, down, left, or right. Return the minimum total monster cost needed to travel from S to E, or -1 if E is unreachable.

Constraints

1 <= rows, cols <= 300
The grid is rectangular and contains exactly one 'S' and one 'E'.
Movement is allowed only in four directions.

Examples

Input: ["SE"]

Expected Output: 0

Explanation: The exit is adjacent to the start and entering 'E' costs 0.

Input: ["S#", "#E"]

Expected Output: -1

Explanation: Walls block every possible route.

Input: ["S#E", "MMM", "..."]

Expected Output: 2

Explanation: The cheapest route goes around the wall and enters exactly two monster cells.

Input: ["S.M", "..E"]

Expected Output: 0

Explanation: A slightly longer route avoids the monster completely.

Hints

Because each move has weight 0 or 1, a 0-1 BFS with a deque is a natural fit.
The cost is paid when you enter the next cell, not when you leave the current one.

Part 3: Return One Minimum-Cost Path from S to E

Using the same dungeon rules as Part 2, return one path from 'S' to 'E' that achieves the minimum monster cost. The path must include both the start and end cells and should be returned as a list of [row, col] coordinates using 0-based indexing. If several paths have the same minimum monster cost, prefer one with the fewest steps. If the exit is unreachable, return an empty list.

Constraints

1 <= rows, cols <= 200
The grid is rectangular and contains exactly one 'S' and one 'E'.
Movement is allowed only in four directions.

Examples

Input: ["SE"]

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

Explanation: The shortest valid path is just the start followed by the exit.

Input: ["S#", "#E"]

Expected Output: []

Explanation: No path exists.

Input: ["S..", ".#E"]

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

Explanation: This is the unique minimum-cost path with the fewest steps.

Input: ["S#E", "M#M", "M.M"]

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

Explanation: Walls force the path to go around the bottom, and every valid route has the same monster-cost structure here.

Hints

Store a parent pointer for each cell whenever you improve its best known state.
You can run Dijkstra on a pair (monster_cost, steps) so that minimum cost is primary and path length is secondary.

Part 4: Minimum Exit Cost with Arbitrary Monster Weights

You are given the same dungeon grid as before, but now every monster cell can have its own non-negative entry cost instead of always costing 1. The grid still uses 'S', 'E', '.', 'M', and '#'. A second matrix costs of the same size is provided; when you enter a cell containing 'M', you pay costs[r][c]. For all other cell types, the corresponding number in costs is ignored. Return the minimum total cost to travel from S to E, or -1 if the exit is unreachable.

Constraints

1 <= rows, cols <= 200
0 <= costs[r][c] <= 10^9
The grid is rectangular, costs has matching dimensions, and the grid contains exactly one 'S' and one 'E'.

Examples

Input: (["SME"], [[0, 5, 0]])

Expected Output: 5

Explanation: The only path enters one monster cell with cost 5.

Input: (["SM.", ".#E", "M.M"], [[0, 8, 0], [0, 0, 0], [1, 0, 1]])

Expected Output: 2

Explanation: The direct route costs 8, but the longer detour uses two cheaper monsters with total cost 2.

Input: (["S#", "#E"], [[0, 0], [0, 0]])

Expected Output: -1

Explanation: Walls make the exit unreachable.

Input: (["SME"], [[0, 0, 0]])

Expected Output: 0

Explanation: Monster cells may also have zero cost.

Hints

Once weights are arbitrary non-negative integers, 0-1 BFS no longer applies directly; use Dijkstra instead.
Only 'M' cells contribute a cost from the costs matrix; '.', 'S', and 'E' still cost 0 to enter.

Quick Overview

This question evaluates competency in efficient file I/O and streaming techniques for implementing tail, and in graph search and shortest-path algorithms with path reconstruction for computing minimum monster cost in a grid.