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 Take-home Project rounds at J.P. Morgan.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at J.P. Morgan during technical interviews.

Group anagrams and count string in grid | J.P. Morgan Coding Question

Group anagrams and count string in grid

Company: J.P. Morgan

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

Part 1 — Group Anagrams: Given an array of strings, group together strings that are anagrams of one another and output both the grouped lists and the count of groups. Specify the time and space complexities. Part 2 — Count Target in Grid: Given a 2D matrix of characters and a target string, count how many distinct paths in the grid spell the string by moving to orthogonally adjacent cells (up, down, left, right). You may start at any cell; a cell cannot be reused within a single match. Return the total count, or -1 if the string does not occur at least once. Discuss an efficient algorithm and its complexity.

Quick Answer: This question evaluates algorithmic problem-solving skills in string processing, hashing/grouping and grid traversal/backtracking, along with the ability to analyze time and space complexity and trade-offs.

Part 1: Group Anagrams

Given an array of lowercase strings, group together words that are anagrams of one another. Two words are anagrams if they contain the same letters with the same frequencies. Return both the grouped lists and the number of groups. To make the output deterministic, groups must appear in the order their anagram signature is first seen in the input, and words inside each group must remain in their original input order.

Constraints

0 <= len(words) <= 10^4
0 <= len(words[i]) <= 100
Each word contains only lowercase English letters
Duplicate strings are allowed

Examples

Input: (['eat', 'tea', 'tan', 'ate', 'nat', 'bat'],)

Expected Output: ([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']], 3)

Explanation: 'eat', 'tea', and 'ate' are anagrams; 'tan' and 'nat' are anagrams; 'bat' stands alone. Group order follows first appearance in the input.

Input: ([],)

Expected Output: ([], 0)

Explanation: An empty input produces no groups.

Hints

Two words belong in the same group if they have the same character-frequency signature.
If the result order must be deterministic, store groups in the order each signature first appears.

Part 2: Count Target in Grid

Given a rectangular 2D grid of characters and a target string, count how many distinct paths in the grid spell the target. You may start from any cell. From each cell, you may move only up, down, left, or right. A cell cannot be reused within the same path. Return the total number of valid paths, or -1 if the target cannot be formed at least once.

Constraints

The grid is rectangular
0 <= number of rows, number of columns <= 6
1 <= len(target) <= 12
Each grid cell and each character in target is an uppercase English letter

Examples

Input: (['AB', 'CA'], 'ABA')

Expected Output: 2

Explanation: There are exactly two valid paths: (0,0)->(0,1)->(1,1) and the reverse path (1,1)->(0,1)->(0,0).

Input: (['AA', 'AA'], 'AA')

Expected Output: 8

Explanation: Each of the 4 cells can start a path, and each start has 2 orthogonal neighbors, giving 4 * 2 = 8 paths.

Hints

Use DFS/backtracking starting only from cells that match the first character of the target.
Keep a visited structure so a path never reuses a cell, and prune early if the grid does not contain enough copies of some character in the target.

Quick Overview

This question evaluates algorithmic problem-solving skills in string processing, hashing/grouping and grid traversal/backtracking, along with the ability to analyze time and space complexity and trade-offs.