Transpose File solution and explanation
Google
2 more videos on this problem
The problem
Given a text file file.txt, transpose its content.
You may assume that each row has the same number of columns, and each field is separated by the ' ' character.
Example:
If file.txt has the following content:
name age alice 21 ryan 30
Output the following:
name alice ryan age 21 30
Approach overview
Problem Overview: The file file.txt contains rows of space-separated words. The task is to transpose the file so that the first column becomes the first row, the second column becomes the second row, and so on. Essentially, treat the input as a matrix of words and output its transpose.
Approach 1: Using Arrays for Transpose (Time: O(m*n), Space: O(m*n))
This approach reads the entire file and stores words using a 2D structure. Split each line into tokens and place them in an array using row and column indices. After loading the data, iterate column by column and print elements across all rows. The key idea is treating the input as a matrix where arr[row][col] holds each word. This method is straightforward and mirrors classic matrix transpose logic often used in arrays problems.
Approach 2: Using Stream Processing (Time: O(m*n), Space: O(n))
Instead of storing the entire matrix, process the file line by line and build column strings dynamically. Tools like awk allow referencing fields ($1, $2, etc.) while reading each line. Maintain an array where index i accumulates the i-th column. Each time a new row is read, append the field to its column string. After processing all lines, print the accumulated column strings. This streaming pattern avoids storing every cell individually and is idiomatic for shell scripting.
Recommended for interviews: The array-based approach demonstrates the core idea clearly: load the grid and print columns as rows. It mirrors standard matrix transpose logic, so it’s easy to reason about. The stream-processing approach is more practical for shell environments and large files because it processes input incrementally. Showing both demonstrates that you understand both algorithmic thinking and real-world shell scripting.
Approach 1: Using Arrays for Transpose
This approach involves reading each line from the file, splitting it into words, and storing these words in a 2D array where we can easily access and rearrange the data to perform the transpose operation.
import sys
with open('file.txt', 'r') as file:
lines = file.readlines()
matrix = [line.split() for line in lines]
transposed = zip(*matrix)
for row in transposed:
print(' '.join(row))import java.io.*;
import java.util.*;
public class TransposeFile {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("file.txt"));
List<List<String>> data = new ArrayList<>();
String line;
while ((line = br.readLine()) != null) {
String[] words = line.split(" ");
for (int i = 0; i < words.length; i++) {
if (data.size() <= i) {
data.add(new ArrayList<>());
}
data.get(i).add(words[i]);
}
}
br.close();
for (List<String> row : data) {
System.out.println(String.join(" ", row));
}
}
}#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
using namespace std;
int main() {
ifstream file("file.txt");
string line;
vector<vector<string>> matrix;
while (getline(file, line)) {
istringstream stream(line);
string word;
vector<string> row;
while (stream >> word) {
row.push_back(word);
}
matrix.push_back(row);
}
int numCols = matrix[0].size();
for (int i = 0; i < numCols; ++i) {
for (int j = 0; j < matrix.size(); ++j) {
cout << matrix[j][i] << " ";
}
cout << endl;
}
return 0;
}const fs = require('fs');
fs.readFile('file.txt', 'utf8', (err, data) => {
if (err) throw err;
const lines = data.trim().split('\n');
const matrix = lines.map(line => line.split(' '));
const numCols = matrix[0].length;
for (let i = 0; i < numCols; i++) {
const result = [];
for (let j = 0; j < matrix.length; j++) {
result.push(matrix[j][i]);
}
console.log(result.join(' '));
}
});#include <stdio.h>
#include <string.h>
int main() {
FILE *file = fopen("file.txt", "r");
char line[100];
char words[100][100];
int rowCount = 0, colCount = 0;
while (fgets(line, sizeof(line), file)) {
char *word = strtok(line, " ");
int column = 0;
while (word) {
strcpy(&words[column][rowCount * 100], word);
word = strtok(NULL, " ");
column++;
}
colCount = (column > colCount) ? column : colCount;
rowCount++;
}
fclose(file);
for (int i = 0; i < colCount; i++) {
for (int j = 0; j < rowCount; j++) {
printf("%s ", &words[i][j * 100]);
}
printf("\n");
}
return 0;
}using System;
using System.Collections.Generic;
using System.IO;
class Program {
static void Main() {
var lines = File.ReadAllLines("file.txt");
var matrix = new List<string[]>();
foreach (var line in lines) {
matrix.Add(line.Split(' '));
}
int numCols = matrix[0].Length;
for (int i = 0; i < numCols; i++) {
for (int j = 0; j < matrix.Count; j++) {
Console.Write(matrix[j][i] + " ");
}
Console.WriteLine();
}
}
}The Python solution reads all lines of the file into a list, then splits each line into words to form a 2D array (list of lists). The built-in zip() function is used to transpose the list, which is then printed row by row.
Time Complexity: O(m * n), where m is the number of lines and n is the number of words per line.
Space Complexity: O(m * n) for storing words in lists.
Approach 2: Using Stream Processing
This approach makes use of common stream processing libraries and methods available in different programming languages to handle the file reading and transposing simultaneously, thereby optimizing certain operations such as memory management and I/O handling.
with open('file.txt', 'r') as f:
columns = []
for line in f:
words = line.split()
for i, word in enumerate(words):
if i >= len(columns):
columns.append([])
columns[i].append(word)
for column in columns:
print(' '.join(column))import java.io.*;
import java.util.*;
public class TransposeEfficient {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("file.txt"));
List<StringBuilder> data = new ArrayList<>();
String line;
while ((line = br.readLine()) != null) {
String[] words = line.split(" ");
int index = 0;
for (String word : words) {
if (data.size() <= index) data.add(new StringBuilder());
data.get(index++).append(word).append(" ");
}
}
br.close();
for (StringBuilder s : data) System.out.println(s.toString().trim());
}
}#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
using namespace std;
int main() {
ifstream file("file.txt");
vector<string> buffer;
string line;
int numRows = 0;
while (getline(file, line)) {
stringstream ss(line);
string word;
width_t colIdx = 0;
while (ss >> word) {
if (buffer.size() <= colIdx) buffer.push_back("");
buffer[colIdx] += word;
buffer[colIdx] += " ";
colIdx++;
}
numRows++;
}
file.close();
for (const auto &s : buffer) {
cout << s << endl;
}
return 0;
}const fs = require('fs');
fs.readFile('file.txt', 'utf8', (err, data) => {
if (err) throw err;
const columns = [];
for (const line of data.trim().split('\n')) {
const words = line.split(' ');
words.forEach((word, index) => {
if (!columns[index]) columns[index] = [];
columns[index].push(word);
});
}
columns.forEach(column => {
console.log(column.join(' '));
});
});#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// This C implementation uses a dynamically allocated 2D array for more efficient memory use
int main() {
FILE *file = fopen("file.txt", "r");
char line[100];
char buffer[100][100];
int numRows = 0;
int numCols = 0;
char *data[100];
while (fgets(line, sizeof(line), file)) {
char *token = strtok(line, " ");
int index = 0;
while (token) {
int len = strlen(token);
data[numCols] = (char *)malloc((len + 1) * sizeof(char));
strcpy(data[numCols], token);
buffer[index][numRows] = numCols;
token = strtok(NULL, " ");
numCols++;
index++;
}
numRows++;
}
fclose(file);
int index = 0;
for (int i = 0; i < numCols / numRows; i++) {
for (int j = 0; j < numRows; j++) {
char *value = data[buffer[j][i]];
printf("%s ", value);
free(data[buffer[j][i]]);
}
printf("\n");
}
return 0;
}using System;
using System.IO;
using System.Collections.Generic;
public class TransposeFile {
public static void Main() {
var lines = File.ReadAllLines("file.txt");
List<List<string>> transposedData = new List<List<string>>();
foreach (var line in lines) {
var words = line.Split(' ');
for (int i = 0; i < words.Length; i++) {
if (i >= transposedData.Count) {
transposedData.Add(new List<string>());
}
transposedData[i].Add(words[i]);
}
}
foreach (var column in transposedData) {
Console.WriteLine(string.Join(" ", column));
}
}
}The Python solution uses lists to grow column data dynamically as we read and split each line. By directly appending to lists and outputting using join(), it maintains efficiency both in operations and space use.
Time Complexity: O(m * n), where m is the number of lines and n the number of words.
Space Complexity: O(m * n) to store column data in dynamic lists.
Approach 3: awk
# Read from the file file.txt and print its transposed content to stdout.
awk '
{
for (i=1; i<=NF; i++) {
if(NR == 1) {
res[i] = re$i
} else {
res[i] = res[i]" "$i
}
}
}END {
for (i=1;i<=NF;i++) {
print res[i]
}
}
' file.txtComplexity comparison
| Approach | Complexity |
|---|---|
| Using Arrays for Transpose | Time Complexity: O(m * n), where m is the number of lines and n is the number of words per line. |
| Using Stream Processing | Time Complexity: O(m * n), where m is the number of lines and n the number of words. |
| awk | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array-Based Transpose | O(m*n) | O(m*n) | When you want a straightforward matrix-style implementation and memory is not a constraint |
| Stream Processing (awk/field accumulation) | O(m*n) | O(n) | When processing large files or writing idiomatic shell scripts that avoid storing the full matrix |
Frequently asked questions
Is Transpose File easy or hard?
The problem is rated Medium because the logic is simple but requires familiarity with text processing in shell environments. Implementing the transpose efficiently using awk or similar tools is the main challenge.
Transpose File Python/Java solution
In Python or Java, read each line, split it into words, and store them in a 2D list or array. Then iterate column by column to print the transposed result. The complexity remains O(m*n) time with O(m*n) space.
How to solve Transpose File in O(n)?
The file must still be read completely, so the total runtime is O(m*n). However, space usage can be reduced to O(n) by building column strings during streaming instead of storing the entire matrix.
What is the best approach for Transpose File?
The most practical solution uses stream processing with awk. As each line is read, fields are appended to column-based strings and printed after processing the file. This runs in O(m*n) time and uses only O(n) extra space for column storage.
Is Transpose File asked at Google/Amazon/Meta?
Shell scripting problems like Transpose File appear in system and DevOps-oriented interviews and occasionally in backend screening rounds. They test familiarity with command-line tools, text processing, and field manipulation.
What data structure is used in Transpose File?
Typical implementations use arrays or associative arrays indexed by column. In shell solutions with awk, each column index stores a growing string representing the transposed row.
What is the time complexity of Transpose File?
Both common approaches run in O(m*n) time, where m is the number of rows and n is the number of columns (words per row). Every word in the file must be read and placed into its transposed position.