FastPrepShuffle a String by Swapping Tree Children
Problems/Shuffle a String by Swapping Tree Children

Shuffle a String by Swapping Tree Children

Nutanix logoNutanix● HardINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: An on-campus internship report gives this as the second of two questions in its first coding round. The author found it the harder one. The idea is to build a binary tree over the first string, swap the two parts under some of its nodes, and see whether the second string comes out. The report walks through one five-letter word as its example.

The report does not say where the tree can be cut, how many nodes can be swapped, which letters appear, or how long the strings are. Here every node can be cut into two non-empty parts at any position. Any number of nodes can be swapped (none is fine too). Both strings have the same length, from 1 to 40, and use only lowercase English letters. You return true or false.

Our version is about 90% the same as the reported question.

You are given two strings s1 and s2 of the same length.

Build a binary tree from s1. The root holds all of s1. Any node that holds two or more letters can be cut into two non-empty parts at any position you like: the left part becomes its left child and the right part becomes its right child. A node with one letter is a leaf. You choose every cut.

A shuffle picks one node that has two children and swaps them, so that the node now reads as its right part followed by its left part. You may shuffle any number of nodes, including none. Reading the leaves from left to right then gives the new string.

Return true if some choice of cuts and shuffles turns s1 into s2. Otherwise, return false.

Function

canShuffleInto(s1: String, s2: String) → boolean

Examples

Example 1

s1 = "great"s2 = "taerg"return = true

Cut great into gr and eat, and swap them.

Cut eat into e and at, and swap them. Then cut at into a and t, and swap those too. Now eat reads tae.

Cut gr into g and r, and swap them to get rg.

The leaves now read tae followed by rg, which is taerg.

Example 2

s1 = "lamp"s2 = "palm"return = true

Cut lamp into lam and p, and swap them, so p comes first.

Cut lam into la and m without a swap, and cut la into l and a with a swap. Now lam reads alm.

The result is p followed by alm, which is palm.

Example 3

s1 = "lamp"s2 = "aplm"return = false

Both strings use the same letters, but no tree works.

Whatever the first cut of lamp is, the result is one shuffled part followed by the other. So s2 must start with a block that holds exactly the letters of one part.

  • Cut l | amp: s2 would start with l or end with l. It does neither.
  • Cut la | mp: the first two letters of s2 would be l and a, or m and p. They are a and p.
  • Cut lam | p: s2 would start with p or end with p. It does neither.

So the answer is false.

Constraints

  • 1 <= s1.length <= 40
  • s2.length == s1.length
  • s1 and s2 contain only lowercase English letters.

More Nutanix Online Assessment questions

  • Good SubsequencesOA · Seen Jul 2026
  • Min Cost to Connect All PointsOA · Seen Jun 2026
  • Digit Changes for a Multiple of 9OA · Seen Aug 2025
  • Gas Station Loop StartOA · Seen Aug 2025
  • Number of Players (for MTS2)OA · Seen Oct 2024
  • Work Schedules (for MTS2)OA · Seen Oct 2024
  • Minimum Operations to Convert ArrayOA · Seen Apr 2024
  • No Adjacent CharactersOA · Seen Apr 2024
  • Build a BST From a ListOA · Seen Nov 2022
  • Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022

Similar questions at other companies

  • Maximum Crayon Removal ScoreWells Fargo · OAWells Fargo interview questions
  • Scramble StringExpedia · ONSITE INTERVIEWExpedia interview questions
  • Edit DistanceAstrotalk · PHONE SCREEN
  • Validate a Palindrome After Limited DeletionsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
  • Minimum Dictionary SegmentsGoogle · PHONE SCREENGoogle interview questions
  • Wildcard Pattern MatchingMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Every Result of Grouping an ExpressionC3.ai · ONSITE INTERVIEWC3.ai interview questions
  • Lexicographically Smallest Grid Path with One Letter ChangeInfosys · OAInfosys interview questions
  • Minimum Merge ConflictsAmazon · OA
  • String Formation (Also for AI/ML Software Engineer Intern :)Snowflake · OASnowflake interview questions

Interview reports that mention this question

  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public boolean canShuffleInto(String s1, String s2) {
        // Write your code here.
    }
}
Checking account…