There is no super easy way to find the bottom of the stack in x86. There's a register "ebp" which points to the base of the stack frame. The address to which "ebp" points, contains the value of the previous "ebp" for the previous stack frame. Its basically a linked list we can traverse until we get to the NULL ebp (which is the bottom frame of the stack).

raw

ULONG findStackBase()
{
    // EBP points to the previous value of ebp on the stack
    PULONG baseptr;
    __asm {
        mov baseptr, ebp
    }

    // Traverse the list until we get to the end.
    while (NULL != *baseptr)
    {
        baseptr = (PULONG)*baseptr;
    }

    return (ULONG)baseptr;
}

This code snippet gets the value of "ebp" and runs down the list of stack base pointers until we find the end.

This really only has a place as a debugging function. Orrr, maybe a way to control your poorly written recursive loop... Here's an example of program which executes a loop, by recursion. Once the loop makes it close to the bottom of the stack, it does a long jump back up to the top of the stack so that it can keep going.

raw

// precomp.h
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <Windows.h>
#include <setjmp.h>
#include <winnetwk.h>
#include "looper.h"



// looper.h

#pragma once

// Typdef for the function to pass as an argument to the looping function.
typedef VOID(*looperfunc)(ULONG, PVOID);

VOID ExecuteLoop(ULONG count, looperfunc);



// looper.c

#include "precomp.h"
#include <setjmp.h>

#define STACK_RESET_LIMIT 1024 * 800 // 800kb, we should reset

typedef struct _loopcontext {
    ULONG current; // Current count
    ULONG maximum; // Maximum count
    jmp_buf jumpBuffer; // Buffer to store the jump location for longjump
    looperfunc func; // The function to execute 
    ULONG stackStart; // the bottom of the stack
} loopcontext, *Ploopcontext;

ULONG findStackBase()
{
    // EBP points to the previous value of ebp on the stack
    PULONG baseptr;
    __asm {
        mov baseptr, ebp
    }

    // Traverse the list until we get to the end.
    while (NULL != *baseptr)
    {
        baseptr = (PULONG)*baseptr;
    }

    return (ULONG)baseptr;
}

VOID loopHelper(Ploopcontext context)
{
    // Base condition
    if (context->current >= context->maximum)
    {
        return;
    }

    // Get the value of esp
    ULONG currentStackPtr;
    __asm {
        mov currentStackPtr, esp
    };
    // Execute our callback
    context->func(context->current, NULL);

    // Increment the loop counter
    context->current++;

    // Find our distance from the base of the stack (the stack grows downwards)
    ULONG distance = (context->stackStart - currentStackPtr);
    if (distance >= STACK_RESET_LIMIT)
    {
        longjmp((int*)&context->jumpBuffer, 1);
    }

    // Recurse
    loopHelper(context);
}

/// <Summary>
/// Execute a loop, using recursion
/// </Summary>
VOID ExecuteLoop(ULONG count, looperfunc func)
{
    // Initialize the loop context
    loopcontext context;
    context.current = 0;
    context.maximum = count;
    context.func = func;
    context.stackStart = findStackBase();

    setjmp((int*)&context.jumpBuffer);

    // Run the loop
    loopHelper(&context);
}



// main.c

#include "precomp.h"
#include "looper.h"

// This is the func
VOID testfunc(ULONG l, PVOID val)
{
    ULONG buffer[400];
    printf("looping %u \n", l);
}

int main(int arc, char ** argv)
{
    ExecuteLoop(10000, testfunc);
    return 0;
}




There have been a few cases recently where I have needed to keep track of an array of bits. Basically as a record to mark off when sections of something have completed. The simplest scenario is for something like a torrent file transfer. Let's say the file is made up of 100 chunks, which we can keep track of each completed chunk which was written by marking it in our bit buffer.

For example, our buffer "00000000". When the third item completes we can say "00100000", and so on. The simplest way to do this in C# would be to make an array of Booleans. This seemed like a total waste of memory to me, since Booleans in c# take up much more space than a single bit.

raw

public class ByteBitBuffer
{
    /// <summary>
    /// The binary buffer.
    /// </summary>
    private readonly byte[] bytes;

    /// <summary>
    /// Initializes a new instance of the <see cref="ByteBitBuffer"/> class.
    /// </summary>
    /// <param name="length">The length of the buffer.</param>
    public ByteBitBuffer(int length)
    {
        var len = length / 8;
        if(length % 8 != 0)
        {
            len++;
        }

        this.bytes = new byte[len];
    }

    /// <summary>
    /// Sets the value at an index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <param name="value">The value.</param>
    public void Set(int index, bool value)
    {
        byte mask = (byte)(1 << (index % 8));
        if(value)
        {
            this.bytes[index / 8] |= mask;
        }
        else
        {
            this.bytes[index / 8] &= (byte)~mask;
        }
    }

    /// <summary>
    /// Gets the value at an index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <returns>The value.</returns>
    public bool Get(int index)
    {
        return ((this.bytes[index / 8] >> (index % 8)) & 1) != 0; 
    }
}

This is what I ended up with. From a programmers perspective, this is great. I got to do everything that I love: bit manipulation and cramming as much data into as little space as possible. The real question is, how fast is this compared to the basic Boolean[] implementation.

The Boolean implementation is much simpler of course.

raw

public class BitBufferBools
{
    /// <summary>
    /// The boolean array.
    /// </summary>
    private readonly bool[] bools;

    /// <summary>
    /// Initializes a new instance of the <see cref="BitBufferBools"/> class.
    /// </summary>
    /// <param name="length">The length of the buffer.</param>
    public BitBufferBools(int length)
    {
        this.bools = new bool[length];
    }

    /// <summary>
    /// Sets the value at the index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <param name="value">The value.</param>
    public void Set(int index, bool value)
    {
        this.bools[index] = value;
    }

    /// <summary>
    /// Gets the value at the index.
    /// </summary>
    /// <param name="index">The index.</param>
    /// <returns>The value.</returns>
    public bool Get(int index)
    {
        return this.bools[index];
    }
}

C# also provides a class by default which can do the same thing as the two previous implementations named "System.Collections.BitArray".

My test harness for the code:

raw

static void Main(string[] args)
{
    // Run each method once to make sure they are all compiled
    Program.TestBitArray(1, 100);
    Program.TestBooleanArray(1, 100);
    Program.TestByteArray(1, 100);
    Program.TestIntArray(1, 100);
    Program.TestLongArray(1, 100);

    // Get the test values
    Console.Write("Iterations? ");
    var iterations = int.Parse(Console.ReadLine());
    Console.Write("Length? ");
    var length = int.Parse(Console.ReadLine());

    Console.WriteLine($"Performing tests with {iterations} iterations and length {length}.");

    // Test the boolean array
    Program.TestHarness("An array of bools", iterations, length, Program.TestBooleanArray);

    // Test System.Collection.BitArray
    Program.TestHarness("System.Collections.BitArray", iterations, length, Program.TestBitArray);

    // Test custom binary implementations
    Program.TestHarness("byte[]", iterations, length, Program.TestByteArray);
    Program.TestHarness("uint[]", iterations, length, Program.TestIntArray);
    Program.TestHarness("ulong[]", iterations, length, Program.TestLongArray);

    Console.ReadLine();
}

/// <summary>
/// The test harness.
/// </summary>
/// <param name="testName">The name of the test.</param>
/// <param name="iterations">The number of iterations.</param>
/// <param name="length">The length of the bit array.</param>
/// <param name="testAction">The test action.</param>
private static void TestHarness(string testName, int iterations, int length, Action<int, int> testAction)
{
    var watch = Stopwatch.StartNew();

    testAction(iterations, length);

    watch.Stop();
    Console.WriteLine($"Finished test: {testName} -> {watch.ElapsedMilliseconds}ms");
}

/// <summary>
/// Under the hood, just an array of bools.
/// </summary>
private static void TestBooleanArray(int iterations, int length)
{
    var bools = new BitBufferBools(length);

    for(var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bools.Set(l, !bools.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a System.Collections.BitArray
/// </summary>
private static void TestBitArray(int iterations, int length)
{
    var bits = new BitArray(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a byte[]
/// </summary>
private static void TestByteArray(int iterations, int length)
{
    var bits = new ByteBitBuffer(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a uint[]
/// </summary>
private static void TestIntArray(int iterations, int length)
{
    var bits = new IntBitBuffer(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

/// <summary>
/// Under the hood, a ulong[]
/// </summary>
private static void TestLongArray(int iterations, int length)
{
    var bits = new LongBitBuffer(length);

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits.Set(l, !bits.Get(length - l - 1));
        }
    }
}

Here are the results, needless to say I was a little disappointed. But as it turns out, all of the bit manipulations are pretty expensive. So what you do save in space, you lose dearly in performance.

raw

// Iterations? 1000
// Length? 1000000
// Performing tests with 1000 iterations and length 1000000.
// Finished test: An array of bools -> 1255ms
// Finished test: System.Collections.BitArray -> 8127ms
// Finished test: byte[] -> 6462ms
// Finished test: uint[] -> 5609ms
// Finished test: ulong[] -> 5531ms

Since I was a little annoyed, I thought I would try one more thing. Maybe I could improve performance significantly by allocating my custom collections directly onto the stack.

raw

private static unsafe void TestStackAllocInts(int iterations, int length)
{
    var len = length / 32;
    if (length % 32 != 0)
    {
        len++;
    }

    uint * bits = stackalloc uint[len];

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            PointerBitBuffer.Set(bits, l, !PointerBitBuffer.Get(bits, length - l - 1));
        }
    }
}

public static unsafe class PointerBitBuffer
{
    public static void Set(uint * self, int index, bool value)
    {
        var mask = 1U << (index % 32);
        if (value)
        {
            self[index / 32] |= mask;
        }
        else
        {
            self[index / 32] &= ~mask;
        }
    }

    public static bool Get(uint* self, int index)
    {
        return ((self[index / 32] >> (index % 32)) & 1) != 0;
    }
}

This did improve performance a little. But sadly, allocating the Boolean[] directly onto the stack is an even larger performance increase.

raw

private static unsafe void TestStackAllocBools(int iterations, int length)
{
    bool* bits = stackalloc bool[length];

    for (var i = 0; i < iterations; i++)
    {
        for (var l = 0; l < length; l++)
        {
            bits[i] = !bits[length - l - 1];
        }
    }
}

So here are the final results:

raw

// Iterations? 1000
// Length? 1000000
// Performing tests with 1000 iterations and length 1000000.
// Finished test: An array of bools -> 1255ms
// Finished test: System.Collections.BitArray -> 8127ms
// Finished test: byte[] -> 6462ms
// Finished test: uint[] -> 5609ms
// Finished test: ulong[] -> 5531ms
// Finished test: stackalloc uint[] -> 4102ms
// Finished test: stackalloc ulong[] -> 5106ms
// Finished test: stackalloc bool[] -> 723ms

The moral of the story is, C# is incredibly fast with basic arrays. So if space is no constraint, just use a basic Boolean array to store a bit buffer, unless you actually need the ability to write it directly to binary.




Strings in C# are not mutable. Any string operation is actually creating a brand new string and allocating it onto the heap. C# also doesn't provide any sort of tools for you to modify an existing string without creating a new one. Using some clever pointer magic, you can alter a string in place. This is not generally recommended, but it could be useful in some cases.

raw

class Program
{
    private const string HelloWorld = "Hello World";

    static void Main(string[] args)
    {
        Console.WriteLine(HelloWorld);
        Program.ChangeString(HelloWorld, "badflyer");
        Console.WriteLine(HelloWorld);

        const string HelloWorld2 = "Hello World 2";

        Console.WriteLine(HelloWorld2);
        Program.ChangeString(HelloWorld2, "not hello");
        Console.WriteLine(HelloWorld2);

        Console.ReadLine();
    }

    private static void ChangeString(string target, string newValue)
    {
        if(newValue.Length > target.Length)
        {
            throw new ArgumentException("The new string cannot be longer than the current string");
        }

        unsafe
        {
            fixed (char* str = target)
            {
                // Change the length to match our new string. The length is stored as an int right in front of the first character
                *((int*)str - 1) = newValue.Length;

                // Copy the new string
                for(var i = 0; i < newValue.Length; i++)
                {
                    str[i] = newValue[i];
                }
            }
        }
    }
}

Here's the output of this program:

raw

// Hello World
// badflyer
// Hello World 2
// not hello

Long story short, C# stores strings on the heap just as C would store a BSTR. It starts with a 32 bit length, and then the string as a fixed array of two byte chars. When you use the "fixed" expression in c#, you get a pointer to the first character of the string. We can step back 4 bytes to get a pointer to the string length, then we can change the string length to match our incoming string. You can't make the string any longer, because there is no way to know what follows in the heap.




C# has a pretty neat namespace named "System.Reflection.Emit", which allows you to build assemblies at runtime using Intermediate Language. This is a basic example of how to create an assembly, define a global function, and execute that function.

The following is an example. It is designed to be easy to follow, but here is a quick overview. The first thing we do is define a dynamic assembly. Within that assembly, we define a module. The whole assembly vs. module thing can be a little confusing. An assembly contains the manifest, and a collection of modules. Now in practice, an assembly usually only has a single module defined inside of it. Any C# project you create will also follow this 1 to 1 relationship. The module contains all of the actual code. Within the module, we define a global function (unsupported by C#, but IL is cool with it). Using the IL generator on the function, we can load a string onto the evaluation stack ("hello world"), call a function (Console.WriteLine), and then return from our function.

raw

namespace ReflectionEmitHelloWorld
{
    using System;
    using System.Reflection;
    using System.Reflection.Emit;

    class Program
    {
        static void Main(string[] args)
        {
            // Define the assembly and module
            const string AssemblyName = "Badflyer.HelloWorld.dll";
            var assembly = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName(AssemblyName), AssemblyBuilderAccess.RunAndCollect);
            var module = assembly.DefineDynamicModule(AssemblyName);

            // Define the method and get the Intermediate Language generator.
            var methodBuilder = module.DefineGlobalMethod("HelloWorld", MethodAttributes.Final | MethodAttributes.Public | MethodAttributes.Static, typeof(void), new Type[0]);
            var ilGenerator = methodBuilder.GetILGenerator();

            //// Too easy - but this works too
            // ilGenerator.EmitWriteLine("Hello World");

            // Get the method info for writeline
            var writeline = typeof(Console).GetMethod("WriteLine", BindingFlags.Public | BindingFlags.Static, Type.DefaultBinder, new[] { typeof(string) }, null);

            // Load the string onto the evaluation stack
            ilGenerator.Emit(OpCodes.Ldstr, "Hello World");

            // Call writeline
            ilGenerator.EmitCall(OpCodes.Call, writeline, new[] { typeof(string) });

            // Return
            ilGenerator.Emit(OpCodes.Ret);

            // Create the global functions (since that is what we defined)
            module.CreateGlobalFunctions();

            // Get our new method info
            var helloWorld = module.GetMethod("HelloWorld");
            // Invoke our new method.

            helloWorld.Invoke(null, null);

            // Wait for input
            Console.ReadLine();
        }
    }
}

Pretty cool! You can do things in IL which you cannot do from C# directly. Here for example we defined a global function which is not the member of any class. Following is the resulting IL which was generated from saving our generated .dll. Just a warning, dotnet core does not allow you to save the generated .dll. The regular .NET framework does.

raw

// To Save: var assembly = AssemblyBuilder.DefineDynamicAssembly(new AssemblyName(AssemblyName), AssemblyBuilderAccess.RunAndSave);
// To Save: assembly.Save(AssemblyName);
.method public final static 
 void HelloWorld () cil managed 
{
 // Method begins at RVA 0x2050
 // Code size 11 (0xb)
 .maxstack 1
 IL_0000: ldstr "Hello World"
 IL_0005: call void [mscorlib]System.Console::WriteLine(string)
 IL_000a: ret
}

And that's all there is to it! You can do a lot of learning by writing C# code snippets, and viewing the generated IL within the .dll with a tool. (For example ILSpy).




Sep 27, 2017

Here’s another journey through the world of simple programming problems… FizzBuzz, T-SQL edition. So just like the rest of the Fizz Buzz solutions. The idea is simple, for every number 1-100, if it’s divisible by 3 print ‘fizz’, if it’s divisible by 5 print ‘buzz’, if both print ‘fizzbuzz’, otherwise print the number. So here is a basic SQL solution:

raw

WITH ctCounter AS
(
	SELECT 1 AS Number

	UNION ALL

	SELECT Number + 1 AS Number
	FROM ctCounter
	WHERE Number < 100
)
SELECT ISNULL(NULLIF(CONCAT(fizz.f, buzz.b), ''), c.Number) FROM ctCounter c
LEFT JOIN (VALUES('fizz')) fizz(f)
  ON c.Number % 3 = 0
LEFT JOIN (VALUES('buzz')) buzz(b)
  ON c.Number % 5 = 0

This is a common table expression, which generates a row for each number between 1 and 100. Then joins with the values ‘fizz’ and ‘buzz’. After that, it concatenates the fizz and buzz together, and if it still results in an empty string, selects the original number. The NULLIF function is useful for that, because it is basically the inverse of ISNULL. If the first parameter matches the second parameter, it returns null, otherwise returns the first parameter.




Sep 25, 2017

Something which you shouldn’t be doing very often (or ever) is placing locks around chunks of asynchronous code. You’re almost always slowing down your code, and there has to be a better way to do it. Anyway, if you do try it, C# will give you a compile error along the lines of: ‘cannot await in the body of a lock statement’. This all makes sense, because locks are tied to a thread. If you are using the parallel task library, there is really no guarantee that your code is going to pick back up on the same thread where it originally left off. You can run into problems like this if you try to use a class like “ReadWriteLockSlim”, which doesn’t give compile warning about awaiting within the critical section, but will happily deadlock your code. So here is a solution to all your fears. Luckily SemaphoreSlim has async support.

This is a helper class which just makes a generic disposable for some coding sugar:

raw

    /// <summary>
    /// A class which can be disposed.
    /// </summary>
    public class Disposable : IDisposable
    {
        /// <summary>
        /// The action to perform on dispose.
        /// </summary>
        private readonly Action onDispose;

        /// <summary>
        /// Initializes a new dispoable.
        /// </summary>
        /// <param name="onDispose">The action to perform.</param>
        private Disposable(Action onDispose)
        {
            this.onDispose = onDispose;
        }

        /// <summary>
        /// Creates a disposable class.
        /// </summary>
        /// <param name="onDispose">The dispose action.</param>
        /// <returns>A disposable.</returns>
        public static IDisposable Create(Action onDispose)
        {
            return new Disposable(onDispose);
        }

        /// <summary>
        /// Dispose.
        /// </summary>
        public void Dispose()
        {
            onDispose();
        }
    }

This is a dummy object which needs a lock:

raw

public class LockableObject
    {
        private readonly SemaphoreSlim asyncLock = new SemaphoreSlim(1);

        /// <summary>
        /// Gets a lock on this object.
        /// </summary>
        /// <param name="token">The token.</param>
        /// <returns>A disposable which release the lock.</returns>
        public Task<IDisposable> GetLock(CancellationToken token)
        {
            return this.asyncLock.WaitAsync(token).ContinueWith(result =>
            {
                if (result.IsCompleted && !result.IsFaulted && !result.IsFaulted)
                {
                    return Disposable.Create(() => asyncLock.Release());
                }

                throw result.Exception?.InnerExceptions.FirstOrDefault() ?? result.Exception ??
                      new Exception("Failed to aquire the lock for an unknown reason.");
            });
        }
    }

Here is a little demo test program:

raw

class Program
    {
        static void Main(string[] args)
        {
            // This wont work...
            ////var obj = new object();
            ////
            ////lock (obj)
            ////{
            ////    await TestLock();
            ////}

            TestLock().GetAwaiter().GetResult();
        }

        /// <summary>
        /// Test to see if this lock works
        /// </summary>
        /// <returns>An async task.</returns>
        public static async Task TestLock()
        {
            const int number = 10000;
            var someObject = new LockableObject();

            var parallelSum = 0L;

            using (var barrier = new ManualResetEventSlim(false))
            {

                var tasks = Enumerable.Range(0, number).Select(i =&gt; Task.Run(async () =&gt;
                {
                    // Queue up everything behind this barrier so things try to do this all at once.
                    barrier.Wait();

                    using (await someObject.GetLock(CancellationToken.None)) // Comment out this line to make it fail
                    {
                        // Critical Section
                        var t = parallelSum;
                        parallelSum = t + 1;
                    }
                }));

                barrier.Set();

                await Task.WhenAll(tasks);

            }

            if (parallelSum != number)
            {
                throw new Exception($"The counter is wrong. Expected {number}, but got {parallelSum}");
            }
        }
    }

A major caveat here is that this lock is not at all recursive/re-entrant. If you try to call it within the same call stack, you will most certainly deadlock. Other than that, happy locking.




Looking around online, I could not find a great example of how to draw Pascal’s Triangle in SQL. The solution is quite cool in SQL, because management studio prints out a nice grid for you. Here are three examples. The first one is simple and well documented, the second one is a little more squished, and the third one is a complete dumpster fire that I got too by looking up how to code golf in SQL.

raw

CREATE PROCEDURE PascalsTriangle
    @Levels INT
AS
BEGIN
    SET NOCOUNT ON

    -- Declare variables
    DECLARE @counter        INT = 2
    DECLARE @innerCount     INT
    DECLARE @tmp            DECIMAL(38,0)
    DECLARE @tmp2           DECIMAL(38,0)
    DECLARE @dquery         NVARCHAR(2048)

    -- Create the results table with its one column
    CREATE TABLE #result
    (
        [1] DECIMAL(38,0)
    )
    INSERT INTO #result VALUES (1)

    -- For every level beyond 1
    WHILE(@counter <= @Levels)
    BEGIN
        
        -- Add another column to to the table
        EXEC('ALTER TABLE #result ADD [' + @counter + '] DECIMAL(38,0)')

        -- Select the previous row into a temp table
        SELECT *
        INTO #row
        FROM #result
        ORDER BY 1
        OFFSET (@counter - 2) ROWS
        FETCH NEXT 1 ROWS ONLY

        -- Re-initialize the temp variables, and loop counter
        SET @tmp = 1
        SET @tmp2 = 1
        SET @innerCount = 2

        -- For every column beyond 1
        WHILE(@innerCount <= @counter)
        BEGIN

            -- Create a query which selects the current value of the cell to back it up.
            SET @dquery = 'SELECT @t = [' + CAST(@innerCount AS NVARCHAR(10)) + '] FROM #row'
            EXEC sp_executesql @dquery, N'@t DECIMAL(38,0) OUTPUT', @t = @tmp2 OUTPUT

            -- Set the value of this cell in this row to that + @tmp
            EXEC('UPDATE #row SET [' + @innerCount + '] = ISNULL([' + @innerCount + '], 0) + ' + @tmp)

            -- Reset the temp variable
            SET @tmp = @tmp2

            -- Increment the count
            SET @innerCount += 1

        END

        -- Insert the row into result
        INSERT INTO #result
        SELECT * FROM #row

        -- Increment the counter
        SET @counter += 1

        -- Drop the row temp table
        DROP TABLE #row
    END

    -- Output the result
    SELECT * FROM #result
    DROP TABLE #result
END

There is another post in PowerShell which does a much better job actually explaining details about how this triangle works. But long story short, every item is the sum of the two above it added together. So now let’s make the script a little smaller.

raw

CREATE PROCEDURE PascalsTriangle2
	@Levels INT
AS
BEGIN
	SET NOCOUNT ON
	DECLARE @o INT=2
	DECLARE @ INT
	DECLARE @1 DECIMAL(38,0)
	DECLARE @2 DECIMAL(38,0)
	DECLARE @q NVARCHAR(2048)
	CREATE TABLE #o([1] DECIMAL(38,0))
	INSERT #o VALUES(1)
	o:
 		EXEC('ALTER TABLE #o ADD['+@o+']DECIMAL(38,0)')
 		SELECT *INTO #r FROM #o ORDER BY 1 OFFSET(@o-2)ROWS	FETCH NEXT 1 ROWS ONLY
 		SET @1 = 1
 		SET @2 = 1
 		SET @ = 2
 		i:
			SET @q = CONCAT('DECLARE @ TABLE (val DECIMAL(38,0));UPDATE #r SET [',@,']=ISNULL([',@,'], 0)+',@1,'OUTPUT deleted.[',@,']INTO @;SET @t=(SELECT *FROM @)')
			EXEC sp_executesql @q,N'@t DECIMAL(38,0) OUTPUT',@t=@2 OUTPUT  			
  			SET @1 = @2
  			SET @ += 1
 		IF @ <= @o GOTO i
 		INSERT #o
 		SELECT * FROM #r
 		SET @o += 1
 		DROP TABLE #r
	IF @o <= @Levels GOTO o
	SELECT * FROM #o
	DROP TABLE #o
END

As you can see, I removed all the pesky comments which were just getting in the way of looking small. Also, the while loops were all turned into GOTO loops to take up a little less space. The variable names were shortened a little as well.

raw

DECLARE @s NVARCHAR(MAX)='CREATE PROCEDURE PascalsTriangle3
@Levels INT
AS
BEGIN
	SET NOCOUNT ON
	~o |=2~ |~1 &~2 &~q NVARCHAR(2048)CREATE TABLE #o([1] &)INSERT #o VALUES(1)
	o:EXEC(''ALTER TABLE #o ADD[''+@o+'']&'')$|O #r ^#o ORDER BY 1 OFFSET(@o-2)ROWS	FETCH NEXT 1 ROWS ONLY!1 = 1!2 = 1! = 2
 		i:!q = CONCAT(''~ TABLE (val &);UPDATE #r SET ['',@,'']=ISNULL(['',@,''], 0)+'',@1,''OUTPUT deleted.['',@,'']|O @;!t=($^@)'')EXEC sp_executesql @q,N''@t & OUTPUT'',@t=@2 OUTPUT!1 = @2!+=1IF @ <= @o GOTO i
 		INSERT #o$ ^#r!o += 1%#r IF @o <= @Levels goto o$ ^#o%#o
END'
SELECT @s=REPLACE(@s,LEFT(i,1),SUBSTRING(i,2,20))
FROM(VALUES('~ DECLARE @'),('! SET @'),('& DECIMAL(38,0)'),('% DROP TABLE '),('$ SELECT *'),('^ FROM '),('| INT'))a(i)
EXEC(@s)

Now there’s the real beast. It does a bunch of replacements on a string, to make some longer valid SQL, then executes the SQL dynamically to produce the stored procedure. That’s some production quality code.




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).

raw

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.

raw

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.

raw

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}}
    }
}

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




How to create an arbitrary list in SQL. Its a little easier said than done. Heres a code snippet which will do just that. The biggest power of this, is running queries to figure out what kind of ranges do not have any data. For example, consider a table of values between 1 and 10000. If someone were to ask which unique set of numbers existed in the table, that would be pretty easy. But if someone were to ask which set of number did not exist in the table, that query would be pretty tough. You have nothing to join against.

raw

DECLARE @lowInclusive  INT = 3
DECLARE @highInclusive INT = 55

-- Declare a common table expression
;WITH generator AS
(
    -- In the base case, just select our first number as a row
    SELECT
        number
    FROM (VALUES(@lowInclusive)) AS base(number)

    UNION ALL

    -- Now select recursively from the common table until we reach our high number
    SELECT
        number + 1
    FROM generator
    WHERE number < @highInclusive
)
SELECT * FROM generator

There you have it. A row list of numbers. You can expand this do work with things like dates as well.

raw

DECLARE @lowInclusive  Date = GETUTCDATE()
DECLARE @highInclusive Date = DATEADD(DAY, 30, @lowInclusive)

-- Declare a common table expression
;WITH generator AS
(
    -- In the base case, just select our first number as a row
    SELECT
        d
    FROM (VALUES(@lowInclusive)) AS base(d)

    UNION ALL

    -- Now select recursively from the common table until we reach our high number
    SELECT
        DATEADD(DAY, 1, d)
    FROM generator
    WHERE d < @highInclusive
)
SELECT * FROM generator

There you have it. The result ends up looking like this

day
2017-08-12
2017-08-13
2017-08-14
2017-08-15
2017-08-16
2017-08-17
2017-08-18
2017-08-19
2017-08-20
2017-08-21
2017-08-22
2017-08-23
2017-08-24
2017-08-25
2017-08-26
2017-08-27
2017-08-28
2017-08-29
2017-08-30
2017-08-31
2017-09-01
2017-09-02
2017-09-03
2017-09-04
2017-09-05
2017-09-06
2017-09-07
2017-09-08
2017-09-09
2017-09-10
2017-09-11

And now you can easily join to figure out which days of the month someone forgot to pay their bills, or whatever.




Ever been asked FizzBuzz in a programming interview, and thought to yourself, what could I do here that would really throw them off? Well, this. Do this.

raw

private static void FizzBuzz1()
{              
	// Declare all of our variables right here at the top.
	int i, i2;
	string buff;
	Action<string> fb = null;
	goto assignVars;
	loop:
	{
		if (0 == i2 % 3)
		goto dofizz;
		if (0 == i2 % 5)
		goto dobuzz;
		goto donumber;
	}
	endoftheloop:
	if (i --> 0 && (i2 = 100 - i) > 0)
	goto loop;
	goto end;
	dofizz:
	buff += "fizz";
	if (0 == i2 % 5)
	goto dobuzz;
	goto writer;
	dobuzz:
	buff += "buzz";
	goto writer;
	donumber:
	buff += i2;
	writer:
	fb(buff + Environment.NewLine);
	goto justBuff;
	// Do this safely at the end of the function.
	assignVars:
	i = 100;
	fb = Console.Write;
	justBuff:
	buff = string.Empty;
	goto endoftheloop;
	end: ;
}

Nobody can be tooooo mad, since it really is a completely working fizzbuzz. Some may question who taught you that goto works in c#, and why you dont seem to know how to use a for-loop. Some may even question why you assigned Console.Write to an action, or why you didn't just use Console.WriteLine. All good questions. Seems like you would have a lot to talk about during your interview.

Theres nothing like a single method chain which does all of Fizz Buzz. So here's some awesome.

raw

private static void FizzBuzz2()
{
  Console.WriteLine(
    string.Join(
      Environment.NewLine,
      Enumerable.Range(1, 100)
        .Select(
          i =>
            string.Join(
              string.Empty,
              i % 3 == 0 ? "fizz" : null,
              i % 5 == 0 ? "buzz" : null,
              !(i % 5 == 0 || i % 3 == 0) ? $"{i}" : null))));
}




© 2018 - Peter Sulucz | disclaimer

log in