Printing an hourglass pattern

Question

In a recent interview I have been asked to write a program to generate the following output:

* * * * *
 * * * * 
  * * *  
   * *   
    *    
   * *   
  * * *  
 * * * * 
* * * * *

I had written the following code in java

public class Triangle
{
    public static void main( String[] args )
    {
        show( 5 );
    }

    public static void show( int n )
    {
        for ( int i = 0; i < n - 1; i++ )
        {
            for ( int j = 0; j < i; j++ )
            {
                System.out.print( " " );
            }
            for ( int k = n - i; k > 0; k-- )
            {
                System.out.print( "* " );
            }
            System.out.println();
        }
        for ( int i = 0; i < n; i++ )
        {
            for ( int j = n - i; j > 1; j-- )
            {
                System.out.print( " " );
            }
            for ( int k = 0; k < i + 1; k++ )
            {
                System.out.print( "* " );
            }
            System.out.println();
        }
    }
}

But the interviewer was not happy. He asked me minimize the number variables I had used. I didn't found a way. Anyone could help? Also, could there be a possibility to optimize the iteration here?

Answer 1

It is very difficult to know what an interviewer really expects. Some want the clearest code possible. Others want to see tricks. Still others want you to play 'code golf.'

Your code is bulky. It is hard to take it all in at once so it can be understood. This is where introducing method named printSpacing(n) to print the left margin spaces and printStars(n) to print the lines with asterisks could be helpful. I don't have a problem with variables like i and j since those are idiomatic loop counter names. All that being said, I have seen interviewees give worse answers to easier problems.

Here's another take on the problem. I realize that the stars are a repeated pattern. And after a fashion, so are the repeated spaces. So I construct these repeated patterns first (so I only have to do it once) then pick out the pieces of them I want to display. This keeps the loops very clean.

public class Stars {
    public static void main(String[] args) {
        Stars s = new Stars();
        s.go(5);
    }

    private void go(int n) {
        String s = "";
        for (int i = 0; i < n; i++) s += " *";
        String w = "";
        for (int i = 0; i < n; i++) w += " ";

        for (int i = n; i > 0; i--) {
            System.out.print(w.substring(i));
            System.out.println(s.substring((n - i) * 2));
        }
        for (int i = 2; i <= n; i++) {
            System.out.print(w.substring(i));
            System.out.println(s.substring((n - i) * 2));
        }
    }
}

Output:

 * * * * *
  * * * *
   * * *
    * *
     *
    * *
   * * *
  * * * *
 * * * * *

Answer 2

The biggest performance boost you could make would be to issue fewer print() and println() calls. Each call involves a lot of overhead for locking, which you normally don't think about. Coalesce everything down to one single print() for optimal performance.

The number of variables isn't that bad. The problem is, rather, that i, j, k, and n are cryptic and headache-inducing. The headache remedy would be to introduce a helper function and rename the variables to be more meaningful. Note that in assigning meaning to the variables, you'll want to reverse one of the i loops to be a countdown, so that i serves the same role in both loops.

public class Triangle {
    public static void show(int maxWidth) {
        // Top
        for (int width = maxWidth; width > 1; width--) {
            System.out.println(repeat(" ", maxWidth - width).append(
                               repeat("* ", width)));
        }

        // Middle and bottom
        for (int width = 1; width <= maxWidth; width++) {
            System.out.println(repeat(" ", maxWidth - width).append(
                               repeat("* ", width)));
        }
    }

    private static StringBuilder repeat(CharSequence block, int n) {
        StringBuilder sb = new StringBuilder(block.length() * n);
        while (n --> 0) {
            sb.append(block);
        }
        return sb;
    }

    public static void main(String[] args) {
        show(5);
    }
}

You could try writing one loop to handle both the top and bottom triangles. Unfortunately, this clever solution is not as elegant as it could be, due to the need to skip 0.

    public static void show(int maxWidth) {
        for (int i = -maxWidth + 1; i < maxWidth; i++) {
            int width = Math.abs(i) + 1;
            System.out.println(repeat(" ", maxWidth - width).append(
                               repeat("* ", width)));
        }
    }

Answer 3

public class Triangle
{
    public static void main( String[] args )
    {
        show( 5 );
    }

    public static void show( int n )
    {
        int i,j,k;
        for (i = 0; i < n - 1; i++ )
        {
            for (j = 0; j < i; j++ )
            {
                System.out.print( " " );
            }
            for (k = n - i; k > 0; k-- )
            {
                System.out.print( "* " );
            }
            System.out.println();
        }
        for (i = 0; i < n; i++ )
        {
            for (j = n - i; j > 1; j-- )
            {
                System.out.print( " " );
            }
            for (k = 0; k < i + 1; k++ )
            {
                System.out.print( "* " );
            }
            System.out.println();
        }
    }
}

In your code, whenever a loop starts it declares new variable. In my code, it will use same variable with initialization. It always matter when you are using nested loops. Suppose n=5, then according to your code: -
i will be declared 1*2 = 2 times,
j will be declared 5*2 = 10 times,
k will be declared 5*2 = 10 times = memory of 22 integer variables.
whereas my code will use 3 integer variables memory.