## Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

Coupla quick solutions:

n squared:

``````#!perl -l

use strict;
use warnings;

my @output;

my \$y = 0;
my @lines = <DATA>;
for my \$line (@lines) {
chomp \$line;
for my \$x (0 .. length (\$line) - 1) {
\$output[\$y][\$x] ||= '-';
if (substr(\$line, \$x, 1) eq 'x') {
for my \$i (0 .. length (\$line) - 1) {
\$output[\$y][\$i] = 'x';
}
for my \$i (0 .. \$#lines) {
\$output[\$i][\$x] = 'x';
}
}
}
\$y++;
}

print @\$_ for @output;
__DATA__
-----
-----
---x-
x----
-----``````

Linear:

``````use strict;
use warnings;

my \$y = 0;
my @lines = <DATA>;
my (%x, %y);
for my \$line (@lines) {
chomp \$line;
for my \$x (0 .. length (\$line)) {
if (substr(\$line, \$x, 1) eq 'x') {
\$x{\$x}++;
\$y{\$y}++;
}
}
\$y++;
}

for my \$i (0 .. @lines - 1) {
for my \$j (0 .. length(\$lines[0]) - 1) {
print \$y{\$i} || \$x{\$j} ? 'x' : '-';
}
print "\n";
}
__DATA__
-----
-----
---x-
x----
-----``````

Comment hidden because of low score. Click to expand.
0

You have mistake in complexity calculation
your n squared solution is actually n^3 in worst case. And you linear is actually n squared.

There is no linear solution for this question as you want to check all n^2 cells in origin array

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Attempt1{
boolean[] row = new boolean[n];
boolean[] column = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == "x") {
row[i] = true;
column[j] = true;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || column[j]) {
matrix[i][j] = "x";
}
}
}
System.out.println("Resultant matrix: ");
printMatrix(matrix, n);
return matrix;
}``````

Here is a solution that I can think of. Please provide inputs if there is a better way to solve it. Thank you!

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class StackOver1{
boolean[] row = new boolean[n];
boolean[] column = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == "x") {
row[i] = true;
column[j] = true;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || column[j]) {
matrix[i][j] = "x";
}
}
}
System.out.println("Resultant matrix: ");
printMatrix(matrix, n);
return matrix;
}``````

Here are my questions: 1. Is there a better way to solve this?
2. Should I consider a better data structure?

Comment hidden because of low score. Click to expand.
0

No better solution cause you have at least to check all original array cells, and this takes i*j

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Attempt1{
boolean[] row = new boolean[n];
boolean[] column = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == "x") {
row[i] = true;
column[j] = true;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || column[j]) {
matrix[i][j] = "x";
}
}
}
System.out.println("Resultant matrix: ");
printMatrix(matrix, n);
return matrix;
}``````

Here are my questions: 1. Is there a better way to solve this? 2. Should I consider a better data structure?

Thank you.

Comment hidden because of low score. Click to expand.
0
of 0 vote

We could use a HashSet to store (row,column) values where 'x' is found instead of O(n2) space this would require O(k) space where k is the times 'x' appears in the matrix.

Comment hidden because of low score. Click to expand.
0
of 0 vote

traversing a row till the end can be skipped once a 'x' is found in a row.
once a whole row is set with 'x' it could be marked to prevent duplicate 'x' assignment

Comment hidden because of low score. Click to expand.
-2
of 2 vote

test

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.