A programming question that I’m sure everyone has been asked at some point during the interview is ‘Pascal’s Triangle’. Besides solving it, nothing would impress your interviewer more than solving it in PowerShell, with support for massively huge numbers. Wikipedia could probably explain this better than I can, but the premise is simple: start with ‘1’, then each row is one element longer than the previous and is made up of the to values above it added together (Except for the values on either end, which are always 1).

function Pascals-Triangle { [CmdLetBinding()] param ( # Single parameter is the number of levels [Parameter(Mandatory=$true)][ValidateRange(1, [int]::MaxValue)][int]$Levels ) process { # Create a dummy previous array, just so that we know what is going on. $prev = [System.Numerics.BigInteger[]]::new(0) # Now for each level for($l = 0; $l -lt $Levels; $l++) { # Create the current working array $current = [System.Numerics.BigInteger[]]::new($prev.Length + 1) # We know for sure that the first and the last element are 1 (This avoids bounds checking in the loop below) $current[0] = 1 $current[$current.Length - 1] = 1 # Now for all other elements add the previous two together for($i = 1; $i -lt $current.Length - 1; $i++) { $current[$i] = $prev[$i - 1] + $prev[$i] } # Write out our result Write-Output ([string]::Join(' ', $current)) # Set the previous to the current for the next iteration $prev = $current } } }

This is most likely the solution that any interviewer would be expecting, because it is by far the simplest to follow. The idea is simple, start with an array of zero length and for every level of the triangle allocate an array which is 1 element longer, and populate it by adding together elements from the previous array. I’m not sure why, but whenever I got this question in college I wanted to do it recursively, which totally screwed me. Also, the reason behind using ‘BigInteger’, is that these number expand very rapidly. Try it out with ‘int’ or even ‘ulong’, and you wont be able to do too many levels. Anyway, the results in powershell end up looking like this.

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1

So now, to mix things up, lets do it in a way that doesn’t require us to keep reallocating arrays. This next solution does the whole thing in place, reusing the same array each time. This is not a big deal, because we always know how long the array needs to be when we start. (Length = Levels). We can just go through and add up the values of the previous row each time.

function Pascals-Triangle2 { [CmdLetBinding()] param ( # Single parameter is the number of levels [Parameter(Mandatory=$true)][ValidateRange(1, [int]::MaxValue)][int]$Levels ) process { # Create our working array $row = [System.Numerics.BigInteger[]]::new($Levels) # Now for each level for($l = 1; $l -le $Levels; $l++) { # The first index is always 1, and set our previous $iPrevious = $row[0] = 1 for($i = 1; $i -lt $l; $i++) { # Back up the current value $temp = $row[$i] # Add in the previous value $row[$i] += $iPrevious # Swap out the previous $iPrevious = $temp } # Write out our result Write-Output ([string]::Join(' ', ($row | select -First $l))) } } }

And there we have it. So what about a more obfuscated version for those really hard core interviewees? Lets do it. Taking solution 2 and squishing everything together as much as possible we get a horribly confusing solution.

function Pascals-Triangle3 { [CmdLetBinding()] param ( # Single parameter is the number of levels [Parameter(Mandatory=$true)][ValidateRange(1, [int]::MaxValue)][int]$Levels ) process { ($r=[System.Numerics.BigInteger[]]::new(($l=$Levels)+1))[0]=1 1..$l|%{"$($r|?{$_-ne0})";$t=1;1..$_|%{$a=$r[$_];$r[$_]+=$t;$t=$a}} } }

I’m sure everyone is better at code golf than I am, but this solution already confuses me so it should be a good start.