I recently took the Online Assessment (OA) for TikTok's Software Engineer Internship (2027), and this was one of the problems I encountered. I wasn't able to solve it during the exam. Since sharing the exact questions from the OA is prohibited, the problem below is not the original. I recreated a similar problem from memory to illustrate the type of challenge it was.
Diagonal Sorting
Given an n × n matrix, there are 2n - 1 diagonals running parallel to the main diagonal. Each diagonal starts at its upper point and ends at its lower point.
Since these diagonals have different lengths, extend each one cyclically — that is, once you reach the end of the diagonal, wrap back around to its starting point and continue — until it has exactly n characters.
After constructing all 2n - 1 strings this way, sort them in alphabetical (lexicographic) order. Return an array of 2n - 1 integers representing the 1-based indices of the diagonals in their sorted order.
If two strings are equal, their relative order should be the same as in the original (unsorted) order — i.e., the sort must be stable.
Example
For the following 5 × 5 matrix:
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X YNumbering the diagonals from 1 (top-right corner) to 9 (bottom-left corner), the cyclically-extended strings are:
Sorted alphabetically: AGMSY < BHNTB < CIOCI < DJDJD < EEEEE < FLRXF < KQWKQ < PVPVP < UUUUU
Output: [5, 4, 3, 2, 1, 6, 7, 8, 9]
Constraints
1 ≤ n ≤ 100(adjust based on actual OA limits you recall)- The matrix contains only uppercase/lowercase letters (or whatever the original character set was)
⭐️ What does this problem ask you to solve?
Our goal is to think about how to turn the original matrix into a type that you can use the sort method on.
How to approach this problem, step by step.
You don’t have to understand every line of code in this step; the code provided is to show you what it’s going to actually look like.
The point here is to see how the form transforms each step until it becomes something we can sort.
1. The original matrix array
matrix = [
['A','B','C','D','E'],
['F','G','H','I','J'],
['K','L','M','N','O'],
['P','Q','R','S','T'],
['U','V','W','X','Y'],
];
→ 2. Diagonal String (For each diagonal (2n - 1 total), extract its raw string)
d=4 → s = "E"
d=3 → s = "DJ"
d=2 → s = "CIO"
d=1 → s = "BHNT"
d=0 → s = "AGMSY"
d=-1 → s = "FLRX"
d=-2 → s = "KQW"
d=-3 → s = "PV"
d=-4 → s = "U"
→ 3. Repeat each diagonal string to the length n
→ 4. Push the repeated string to an array “String”.
Strings = [
“EEEEE“,
“DJDJD”,
“CIOCI”,
“BHNTB”,
“AGMSY”,
“FLRXF”,
“KQWKQ”,
“PVPVP”,
“UUUUU”
]
→ 5. Pair each diagonal string with its original 1-based index
indexed = [
{ idx: 1, str: "EEEEE" },
{ idx: 2, str: "DJDJD" },
{ idx: 3, str: "CIOCI" },
{ idx: 4, str: "BHNTB" },
…
]
→ 6. Use .sort to sort the strings in alphabetical order. ⭐️ Keep the index paired with the string
indexed = [
{ idx: 5, str: "AGMSY" },
{ idx: 4, str: "BHNTB" },
{ idx: 3, str: "CIOCI" },
{ idx: 2, str: "DJDJD" },
…
]
Keep in mind,
- When
n = matrix.length,the number of diagonal lines becomes 2n - 1.- In the case of the image above, it becomes nine.
- The range becomes n - 1 ~ - (n - 1)
- -4 ~ 4
Finally, let’s skip to the code part
First, we’ll first define row as “j” - j means one character in the inner array, and column as “i” - i means each array of the outer array.
Most importantly, we’ll be calling the difference between the row and the col (row - column) “d”, which is going to be used to determine which diagonal line the letter is going to sit on. - In the picture above, you can see how A and G end up being in the same diagonal line by both having 0 as the “d”.
1. Original Matrix to Diagonal String
const n = matrix.length;
const strings = [];
for (let d = n - 1; d >= -(n - 1); d--) {
let s = "";
for (let i = 0; i < n; i++) {
const j = i + d;
if (j >= 0 && j < n) {
s += matrix[i][j];
}
}
}d = n - 1: The dimension becomesmatrix.length - 1(4 in the given example)- The range of
dis fromn - 1to-(n - 1). This follows from the problem's constraint that the matrix is square; its outer array (rows) and inner arrays (columns) are the same length,n. - The outer loop indicates looping through the diagonal lines to get the coordinates of each letter.
- The inner loop loops through each letter in the array, and it appends the letter to the “s” string when conditions are met.
if (j >= 0 && j < n) {: This checks if j is still in the cell range. When you look at the d=2 table, it becomes “D” and “J”, of which there are only two. And i still goes up to 5 in this case, which means you will end up having 3 empty cells, and we need to remove the unwanted cells by giving it a condition.
d=-2
i=0, j=-2 → out of range, skip
i=1, j=-1 → out of range, skip
i=2, j=0 → matrix[2][0] = 'K' → s = "K"
i=3, j=1 → matrix[3][1] = 'Q' → s = "KQ"
i=4, j=2 → matrix[4][2] = 'W' → s = "KQW"
final s = "KQW"
2. Extend the string (Still inside the outer loop)
for (let d = n - 1; d >= -(n - 1); d--) {
let s = "";
for (let i = 0; i < n; i++) {
...
}
let full = "";
while (full.length < n) {
full += s;
}
full.slice(0, n);
strings.push(full);
}full.length < n: Whilefull.lengthis smaller than the length of the matrix. → This becomes 5 in the example; therefore, it will append “K”, “Q”, “W” until the string contains 5 characters. (“KQWKQ”)full.length < n - 1doesn't reliably reach exactly the lengthn-depending on the diagonal's original length, the result can end up shorter or longer thann. The original< n+slice(0, n)approach avoids this by always overshooting first, then trimming.
strings = [
"EEEEE", // strings[0] ← (d=4)
"DJDJD", // strings[1] ← (d=3)
"CIOCI", // strings[2] ← (d=2)
"BHNTB", // strings[3] ← (d=1)
"AGMSY", // strings[4] ← (d=0)
"FLRXF", // strings[5] ← (d=-1)
"KQWKQ", // strings[6] ← (d=-2)
"PVPVP", // strings[7] ← d=-3)
"UUUUU", // strings[8] ← (d=-4)
]
3. Turn it into an indexed array, then return;
const indexed = strings.map((str, idx) => ({ idx: idx + 1, str }));
indexed.sort((a, b) => {
if (a.str < b.str) return -1;
if (a.str > b.str) return 1;
return 0;
});
return indexed.map(item => item.idx);- Attach original index:
strings.map(...)pairs each diagonal string with its original 1-based position, since sorting alone would lose that information. - Sort by string value:
indexed.sort(...)reorders the pairs alphabetically bystr, using-1/1/0to tell JS which one comes first (equal strings return0, keeping their original order thanks to stable sort). - Extract indices:
indexed.map(item => item.idx)returns just the original index numbers, now arranged in the new sorted order.
indexed = [ // Before sorting
{ idx: 1, str: "EEEEE" },
{ idx: 2, str: "DJDJD" },
{ idx: 3, str: "CIOCI" },
{ idx: 4, str: "BHNTB" },
{ idx: 5, str: "AGMSY" },
{ idx: 6, str: "FLRXF" },
{ idx: 7, str: "KQWKQ" },
{ idx: 8, str: "PVPVP" },
{ idx: 9, str: "UUUUU" },
]
indexed = [ // After sorting - notice the indices are still kept as they were
{ idx: 5, str: "AGMSY" },
{ idx: 4, str: "BHNTB" },
{ idx: 3, str: "CIOCI" },
{ idx: 2, str: "DJDJD" },I
{ idx: 1, str: "EEEEE" },
{ idx: 6, str: "FLRXF" },
{ idx: 7, str: "KQWKQ" },
{ idx: 8, str: "PVPVP" },
{ idx: 9, str: "UUUUU" },
]
So the final order becomes this way,
[ 5, 4, 5, 2, 1, 6, 7, 8, 9]
Pseudo
// Given a top-right = index 1, bottom-left = last index setup,
// sort the matrix's diagonals alphabetically and return their original indices as an array.
// Matrix = array of arrays
// Problem setup: pick one diagonal direction as the reference
// Build the outer loop - iterate diagonally (range: matrix length - 1 to its negative)
// Calculate the dimension (matrix length * 2 - 1)
// Append same-diagonal characters into an empty string using coordinates: final string - "KQW"
// Cyclically extend the string to match the matrix length (use a while loop)
// Push the extended strings into an array, in order
// Convert the array into a collection of indexed objects
// Sort the objects
// Map the sorted indices in order and return them
Algorithms definitely give you brain trippinig experience, but it’s so fun to solve!
