You are given two ascending arrays to merge in place and a separate grouping task: Part A — In-place merge without known sizes: - Array A contains sorted integers followed by empty slots, but the counts m (valid values) and k (empty slots) are not provided. Empty slots are represented by a sentinel (e.g., None). Array B contains n sorted integers. You must merge all values from B into A so that A becomes fully sorted, using O( 1) extra space. - Tasks: 1) Describe and implement an O(m+n)-time algorithm that determines m and then performs the merge in place. State assumptions, edge cases (duplicates, negatives, one array empty), and time/space complexity. 2) Follow-up: Can you merge by scanning from the beginning of both arrays instead of from the end? Explain why or why not for an in-place algorithm without extra buffers, and give a concrete example illustrating overwrite/instability or the conditions under which forward merging would work. Part B — Group strings by uniform cyclic shift: - Given an array of lowercase strings, group strings that are equivalent under a uniform cyclic letter shift (wrapping modulo 26) and have the same length. For example, "abc" and "bcd" belong together; "az" and "ba" belong together. - Tasks: 1) Define a canonical key/normalization for grouping and implement an algorithm to return all groups. 2) Analyze time and space complexity. Discuss handling of mixed lengths, empty strings, and non-letter characters if present.

This question evaluates array-manipulation and string-normalization competencies, specifically in-place merging of sorted arrays without extra space and grouping strings by cyclic-shift equivalence.

How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

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

Implement merge-in-place and group cyclic-equivalent strings

You are given two ascending arrays to merge in place and a separate grouping task:

Part A — In-place merge without known sizes:

Array A contains sorted integers followed by empty slots, but the counts m (valid values) and k (empty slots) are not provided. Empty slots are represented by a sentinel (e.g., None). Array B contains n sorted integers. You must merge all values from B into A so that A becomes fully sorted, using O(

extra space.

Tasks:
1. Describe and implement an O(m+n)-time algorithm that determines m and then performs the merge in place. State assumptions, edge cases (duplicates, negatives, one array empty), and time/space complexity.
2. Follow-up: Can you merge by scanning from the beginning of both arrays instead of from the end? Explain why or why not for an in-place algorithm without extra buffers, and give a concrete example illustrating overwrite/instability or the conditions under which forward merging would work.

Part B — Group strings by uniform cyclic shift:

Given an array of lowercase strings, group strings that are equivalent under a uniform cyclic letter shift (wrapping modulo

and have the same length. For example, "abc" and "bcd" belong together; "az" and "ba" belong together.

Tasks:
1. Define a canonical key/normalization for grouping and implement an algorithm to return all groups.
2. Analyze time and space complexity. Discuss handling of mixed lengths, empty strings, and non-letter characters if present.

You are given two ascending arrays to merge in place and a separate grouping task:

Part A — In-place merge without known sizes:

Array A contains sorted integers followed by empty slots, but the counts m (valid values) and k (empty slots) are not provided. Empty slots are represented by a sentinel (e.g., None). Array B contains n sorted integers. You must merge all values from B into A so that A becomes fully sorted, using O(

extra space.

Tasks:
1. Describe and implement an O(m+n)-time algorithm that determines m and then performs the merge in place. State assumptions, edge cases (duplicates, negatives, one array empty), and time/space complexity.
2. Follow-up: Can you merge by scanning from the beginning of both arrays instead of from the end? Explain why or why not for an in-place algorithm without extra buffers, and give a concrete example illustrating overwrite/instability or the conditions under which forward merging would work.

Part B — Group strings by uniform cyclic shift:

Given an array of lowercase strings, group strings that are equivalent under a uniform cyclic letter shift (wrapping modulo

and have the same length. For example, "abc" and "bcd" belong together; "az" and "ba" belong together.

Tasks:
1. Define a canonical key/normalization for grouping and implement an algorithm to return all groups.
2. Analyze time and space complexity. Discuss handling of mixed lengths, empty strings, and non-letter characters if present.

Implement merge-in-place and group cyclic-equivalent strings

Quick Overview

Comments (0)

Implement merge-in-place and group cyclic-equivalent strings

Quick Overview

Comments (0)