6
\$\begingroup\$

I was recently given a coding test by an employer. After the test, this was the employer's response:

"I’d say that a lot of his solutions were pretty inefficient and took a very ‘brute force’ approach to a solution. For example, his solution for question 1 took 30 lines (give or take for some spacing). This is normally done in about 8 lines. I did like that he documented all of his answers very well, so that’s a positive, but yeah, just a lot of inefficiency throughout his answers (processing inefficiency, object allocation inefficiency, etc)"

I know this question cannot be answered well without an example so to give an example of question 1:

Write a method that takes a parameter x and then prints out an x by x multiplication table

This is what I wrote:

public void printMultTable(int x)
{
    int totalNumberOfPrints = x * x;
    int rowCounter = 0;
    int columnCounter = 1;
    int number = 0;

    for(int i = 0; i < totalNumberOfPrints; i++)
    {
        if(i < x)
        {
            number = i + 1;
            System.out.print(number + " ");
        }
        else if (i % x == 0)
        {
            columnCounter = columnCounter + 1;
            rowCounter = 2;
            System.out.println();
            System.out.print(columnCounter + " ");
        }
        else
        {
            number = columnCounter * rowCounter;
            System.out.print(number + " ");
            rowCounter = rowCounter + 1;
        }
    }
}

I am experienced, but I read and was told by previous employers that code that is easier to read is better, than complex code that takes only 3 lines. I could have written the code in less lines but I thought this was the way.

So my questions are:

  • What is processing inefficiency and how is that shown in my code?
  • What is object allocation inefficiency(I didn't use any static variables)
  • Is it better to use less lines (I thought it doesn't matter?)
\$\endgroup\$

migrated from stackoverflow.com Apr 9 '15 at 20:07

This question came from our site for professional and enthusiast programmers.

10
\$\begingroup\$

Suggested interviewing technique

When writing code for an interview, always ask questions to seek clarification from your interviewer. There are nearly always technical decisions to be made, and you want to make choices that match what they have in mind. (If you don't have any questions, then you probably haven't thought things through properly.)

For this task, I would ask:

  • "Can I assume that the the input x is a reasonably small positive integer, not requiring validation? It doesn't make much sense to print anything larger than 100 × 100 anyway, right?"
  • "I assume that you want the entries to be aligned nicely in a grid?"
  • "I assume that we don't need row and column headings, and that we don't need to print grid lines?"
  • "I assume that you want a reasonable balance of simplicity and speed?"

Before you even write a single line of code, you can score points by showing that you know how to negotiate software requirements.

Here's a solution that I would have written:

public static void printMultTable(int x) {
    int width = (int)Math.floor(Math.log10(x * x)) + 2;
    String fmt = "%" + width + "d";
    StringBuilder b = new StringBuilder(x * width);
    for (int row = 1; row <= x; row++) {
        b.setLength(0);
        for (int col = 1; col <= x; col++) {
            b.append(String.format(fmt, row * col));
        }
        System.out.println(b);
    }
}

After writing it, explain and defend any technical decisions:

  • "To achieve grid alignment, we need to first determine the width of each entry. String.valueOf(x * x).length() + 1 would have worked, but I think that the mathematical approach is slightly more efficient."
  • "I could call System.out.print() for every entry, but printing an entire row at once should have less overhead. Printing the entire table at once might be even faster, but I figured this was good enough."

Note that other answers are possible. Your interviewer might have answered, "I don't care about any of those requirements. I just want to know that you know how to write a nested loop." In that case, just write the simplest code that prints out the right numbers with sloppy formatting.

Your solution and feedback

My biggest concern is that it is not obvious from inspection what your code does. There are a lot of variables, and the flow of control is convoluted.

  • I think number is superfluous. After each assignment, you use it just once.
  • Why is rowCounter initialized to 0, but columnCounter initialized to 1? Why is there a rowCounter = 2 assignment right in the middle of everything? (I would expect reinitializing to either 0 or 1.) More alarmingly, you increment rowCounter to count the columns printed, and columnCounter to number the current row. That's the kind of trap that makes co-workers hate your code.
  • Three cases is excessive. All of them have System.out.print(… + " "), which makes it cut-and-paste code. Couldn't you lump the first if(i < x) case with the last case? (Hint: setting rowCounter = 0 was a poor move.)

The natural way to write this solution is using a nested for-loop. If you really wanted to do it in one loop, it should be simpler:

public static void printMultTable(int x)
{
    int row = 1, col = 1;
    int totalEntries = x * x;
    for (int i = 1; i <= totalEntries; i++)
    {
        System.out.print((row * col++) + " ");
        if (i % x == 0)
        {
            System.out.println();
            row++;
            col = 1;
        }
    }
}

Note that the function should be static, since there's no reason for it to have any object state.

I’d say that a lot of his solutions were pretty inefficient and took a very ‘brute force’ approach to a solution. For example, his solution for question 1 took 30 lines (give or take for some spacing). This is normally done in about 8 lines. I did like that he documented all of his answers very well, so that’s a positive, …

Comparing your solution against the others posted here, I think you would agree that the logic was unnecessarily convoluted.

but yeah, just a lot of inefficiency throughout his answers (processing inefficiency, object allocation inefficiency, etc)

For all practical purposes, there isn't going to be much user-visible difference in performance of your printMultTable() and the better implementations. I don't think that there's much object allocation to speak of in this particular solution; that feedback probably referred to the solutions you wrote for the other tasks. But judging from the way you used a zoo of variables without any clear purpose, I'm inclined to believe their assessment.

\$\endgroup\$
7
\$\begingroup\$

May be your employer has meant something as straightforward as:

public void printMultTable(int x) {
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= x; j++) {
            System.out.print(i*j + " ");
        }
        System.out.println();
    }
}

BTW this is indeed 8 lines of code. I'd suppose that he/she meant that your code is over-engineered.

\$\endgroup\$
  • \$\begingroup\$ This is definitely less lines. I'm just lost at his terms - Object Allocation inefficiency makes me think I am using too many objects. Processing Inefficiency makes me think it will take longer to produce an output. Again this is just one question out of 6. If you can edit your answer, can you give a brief explanation of both or an example? I am trying to perform better. \$\endgroup\$ – superuserdo Apr 9 '15 at 18:54
  • 1
    \$\begingroup\$ "Over-engineered" is a rather diplomatic assessment, since the bloat doesn't add any value. \$\endgroup\$ – 200_success Apr 10 '15 at 18:26
3
\$\begingroup\$

The answer you have shown is not inefficient in terms of runtime or memory use. However, it is written in a roundabout way which makes it both longer and less readable than a shorter answer could be. How about something like this:

public void printMultTable(int x)
{
   // Print column headings
   System.out.print("\t");
   for(int col = 1; col <= x; col++)
     System.out.println(col + "\t");

   for(int row = 1; row <= x; row++) {
     System.out.print(row + "\t"); // Row heading
     for(int col = 1; col <= x; col++)
       System.out.print((row * col) + "\t");
     System.out.println();
   }
}

If you share more of your answers, I may be able to point out areas where your code could be more efficient in CPU and memory use. But aside from that, please: don't take the comments you received on this interview too personally. We are all learning and can always get better. Don't let it bother you too much, but do keep practicing and improving your craft. And keep going for more interviews, until you get the job you are looking for.

\$\endgroup\$
3
\$\begingroup\$

Just because everything looks like a nail when you're wielding the hammer that is Java 8 streams...

public static void print(int x) {
    IntStream.rangeClosed(1, x).mapToObj(i -> 
        IntStream.rangeClosed(1, x).mapToObj(j -> 
            Integer.toString(i * j))
            .collect(Collectors.joining("\t")))
        .forEach(System.out::println);
}

I find it easier to visualize it as two streams - one horizontal and one vertical. The formula to print the value at [i, j] is of course just i * j, and afterwards it's just a matter of coalescing into a String per row and 'sending' each to the console output.

For a more generic way of handling the output x by y table, you can easily adapt the above method to return a Collection<String>, such as the example below:

public class MultiplicationTable {

    public static void main(String[] args) {
        print(9).forEach(System.out::println);
        print(8, 9).forEach(System.out::println);
    }

    public static Collection<String> print(int x) {
        return print(x, x);
    }

    public static Collection<String> print(int x, int y) {
        return IntStream.rangeClosed(1, y).mapToObj(i ->
                IntStream.rangeClosed(1, x).mapToObj(j -> 
                    Integer.toString(i * j))
                    .collect(Collectors.joining("\t")))
                .collect(Collectors.toList());
    }
}

edit

Attempting to answer your original questions...

What is processing inefficiency and how is that shown in my code?

As mentioned in the comments, your code turns the relatively straightforward question of:

Given x, show us a table from 1 to the square of x with each cell as the product of each row and column number

To a three-clause if statement that involves three different calculations (number, columnCounter and columnCounter * rowCounter) to derive the number to print.

If you think it more like a 2D-array, then my answer quite clearly illustrates just a single formula can do the same thing too.

What is object allocation inefficiency(I didn't use any static variables)

This is probably related specifically to the question (I don't consider concatenating Strings using + as a form of object allocation inefficiency unless that's the last place of bottleneck in a high-performance application), but you had to use four variables to derive the number to print:

int totalNumberOfPrints = x * x;
int rowCounter = 0;
int columnCounter = 1;
int number = 0;

Granted, int primitives are not Java Objects per se, but I'm willing to give the interviewer the benefit of doubt and interpret this particular feedback as 'many allocations going on'.

In my alternative approach, there is only the equivalent of your rowCounter and columnCounter, as i and j.

Is it better to use less lines (I thought it doesn't matter?)

We are not reading gripping novels that require detailed and illustrative characters' backgrounds, so yes, generally the less content to read, the better. Lesser content cuts through boilerplate code templates or complicated logic, and better reflects what a method is doing.

edit 2

200_success's excellent answer prompted me to give my solution a shot at printing a nicely formatted output too. Note that this part on is really just an academic exercise, and may/will seem overly verbose compared to 200_success's solution. This possibly showcases a borderline unhealthy obsession with new language features...

public static Collection<String> print(int x, int y) {
    final Collector<Integer, ?, String> formatter = formatOutput(x);
    return IntStream.rangeClosed(1, y).mapToObj(i ->
            IntStream.rangeClosed(1, x).map(j -> 
                i * j).boxed().collect(formatter))
            .collect(Collectors.toList());
}

public static Collector<Integer, ?, String> formatOutput(int x) {
    return Collector.of(ArrayList::new, 
            (list, element) -> list.add(element), 
            (left, right) -> { left.addAll(right); return left; }, 
            list -> { return String.format(String.join(" ", 
                        Collections.nCopies(x, "%" + 
                                (1 + (int) Math.floor(Math.log10(x * x))) + "d")),
                    list.toArray()); }
            );
}

This updated solution creates a Collector, where the formatting logic is implemented within the finisher argument. We accumulate our Integer objects (thanks to boxed()) into a List, and then finally call String.format() with our format String and list.toArray().

\$\endgroup\$
1
\$\begingroup\$

There are two things that probably caught the reviewers eye.

One is the use of a single loop where two nested loops would be simpler (no need for modulo operations, straightforward code structure and much shorter).

The other is the liberal use of String concatenation, although to be fair if asked to write such a code sample I might also have used it to keep it readable; without knowing the exact wording of the constraints given in the task its hard to say. The String concatenation is an example of allocation inefficiency, each of your x + " "results in a temporary string object created.

\$\endgroup\$
1
\$\begingroup\$

It's hard to tell what the employer was thinking regarding object allocation inefficiency because the provided example only uses primitives and doesn't have objects. For the example, if

Integer totalNumberOfPrints = new Integer(x * x);
Integer rowCounter = new Integer(0);
Integer columnCounter = new Integer(1);
Integer number = new Integer(0);

had been coded I would say that is an object allocation inefficiency. As far as processing inefficiency goes, the employer was probably looking at it from the perspective that the task can be accomplished with one calculation rather than two decisions and multiple calculations.

public void printMultTable(int x) {
    for(int i = 1; i <= x; i++) {
        for(int j = 1; j <= x; j++) {
            System.out.print((j * i) + " ");
        }            
        System.out.println();
    }
}

The above code does the same thing as the posted code, only faster. The processing speed is not noticeable when x is small, like 4 or 50. But when x is 1000 the code in the op ran in 78359ms and the above took 29422ms.

\$\endgroup\$
0
\$\begingroup\$

Honestly your code doenst look that bad. I think the way he wanted it is something like (Off Top of my head, not tested or anything)

    for(int i=0;i<x;i++){
       for(int j=0;j<x;j++){
           System.out.print(i*j);
       }
    System.out.println();
    }

Which would essentially do the same thing but in 5-6 lines of code.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.