This project is a collection of my solutions to programming questions. Most of the questions either came from this book or from various programming websites. Since they're my own solutions, I can't guarantee every single one is correct. I test them to make sure the solution works however there are surely plenty of mistakes that I've missed.
The following are the solutions categorized:
Generic implementation of a binary search algorithm.
Iterative depth-first search that returns the node with the target data.
Iterative depth-first search that returns the node with the target data.
Implementation of Fishes-Yates shuffle algorithm.
Heap sort generic implementation.
Merge sort generic implementation.
Given a binary tree, find all paths (from a node to a leaf) that sum to a given number.
Creates a binary tree and returns the root from a sorted array.
Create a Binary Tree class from scratch with Insert, Remove and Find methods.In addition, add a GetRandom() method that returns a random node. All nodes should be equally likely to be chosen.
Write an algorithm to find the "next" node (in-order successor) of a given node in a binary search tree. You may assume that each node has a link to it's parent.
Find whether a binary tree is a subtree of another binary tree. This implementation defines subtree as sharing the same data for each node and the same children for each node (including null children).
Return a list for each depth of a binary tree. Array-based tree with IEnumerable implemented to move through the array in order.
A monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte. The screen has width w, where w is divisible by 8 (that is, no byte will be split across rows). The height of the screen, of course, can be derived from the length of the array and the width. Implement a function that draws a horizontal line from(xl, y) to(x2, y). Function signiture: drawLine(byte[] screen, int width, int x, int x2, int y).
Given a real number between 0 and 1 that is passed in as a double, print the binary representation. If it cannot be represented in 32 characters, print "ERROR.".
Given an int, you can flip exactly one bit from 0 to 1. Find the longest sequence of 1s you could create.
The code checks if n is a power of two since powers of two are represented as a 1 followed only by 0s. Taking 1 away removes the first 1 and changes all the 0s to 1s meaning the & matches no digits and results in 0. Since n == 0 also returns true but isn't a power of 2 we need to check for n != 0 first.
Given two 32-bit numbers, N and M, and two bit positions, i and j, insert M into N starting at bit j and ending at bit i. You may assume there is enough bits for M to fit.
Swap the even and odd bits in an integer using as few instructions as possible.
Write a function to determine the number of bits you would need to flip to convert int A to int B.
Stack implementation using my linked list.
Simple graph implementation for use in some exercises. Has links to nodes and thats about it.
Generic implementation of a queue using my linked list implementation. Code is largely the same as stack implementation.
Generic implementation of a priority queue using my own queue implementation.
Array based min-heap.
Generic implementation of a linked list. Allows access to elements directly as well as passing nodes in to methods manually, meaning it's unsafe but allows for neat optimizations in certain situations.
Generic implementation of a Binary Search Tree.
Generic implementation of an AVL Tree.
A child is running up a staircase with n steps and can hop either 1, 2 or 3 steps at a time. Count how many possible ways the child could run up the steps.
The power set of any set S is the set of all subsets of S, including the empty set and S itself.
Given a grid, find a path from the top left to the bottom right using only right and down movements. Some squares are off limits and the path cannot contain them.
Return all valid permutations of n pairs of parentheses.
Given an infinite number of coins in denominations: 25c, 10c, 5c and 1c, find all permutations of coins to represent n cents.
You are building a diving board by placing a bunch of planks of wood end-to-end. Using exactly k planks of sizes shorter or longer generate all possible diving board lengths.
Implement a colour fill method, like you would see in a paint application.
Compute all permutations of a string of unique characters.
A magic index in a given array A[0...n-1] is defined to be an index such that A[i] == i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.
The Tower of Hanoi is a puzzle where you must move a tower from one pole to another. The tower is a stack of pieces. You may only move one piece at a time, place smaller pieces onto larger pieces and you must take the top piece of a stack to move. Implement a function to solve this puzzle.
Accepts a function and logs the execution time. Usage: Profiler.ProfileAndExecute(() => yourMethod(args), repeat?, name?);
Generates a README.md file for this GitHub project. Finds every ".cs" file, fetches a description from the comments and generates a relative link to that file.
A couple of extension methods I've used throughout the project.
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Partition a linked list around an element such that all elements less than the partition value come before it and all elements greater come after it. The order of the elements doesn't matter.
Remove duplicates from a linked list.
Two numbers represented by linked lists where each node contains a single digit. The digits are stored in reverse order. eg. 7 1 6 + 5 9 2 = 617 + 295 -> 2 1 9 (912).
Given a circular linked list return the point that the loop begins.
Given a collection of intervals, merge all overlapping intervals eg. [[1,4],[4,5]] -> [[1,5]].
Given a list of people with their birth and death years, compute the year with most people alive. Where int[n][0] = birth year & int[n][1] = death year
Perform multiplication using only bit shift operations, addition and subtraction.
Print all primes to n.
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum value.
Given two arrays of integers, find the smallest difference between any two elements, one from each array.
Given two arrays of integers, find a pair of values (one value from each array) that you can swap to
Write a function to swap a number in place.
Write methods for multiply, subtract and divide (*,-,/) using only the add (+) operator.
Contiguous Sequence Largest Sum
Given an array of integers, find the contiguous sequence with the largest sum.
Return the n-th Fibonacci number.
Given an array of n distinct numbers, find all pairs that have a difference of k.
This file is just for testing solutions.
An animal shelter that operates on a first-in first-out basis housing only cats and dogs. Customers can request either a cat, a dog or any animal. They receive the oldest of that type. Implement a queue with the following operations: enqueue, dequeueAny, dequeueDog and dequeueCat.
Write a function that determines the winner of a game of Tic Tac Toe.
Given two sorted arrays (A and B) where A has enough space at the end to fit B, merge array B into array A.
Implement a stack sorting method using only an additional stack (no other data structures). Methods allowed: Push(), Pop(), Peek(), IsEmpty().
Stack that can also return the minimum value in constant time.
Knuth-Morris-Pratt pattern matching algorithm.
Implement atoi which converts a string to an integer.
Check if a string is made of distinct characters.
Given an integer, return the english words to say that number.
Determine whether a string is a permutation of a palindrome.
Unit tests for AVL Tree.
Unit tests for heap.
Unit tests for linked list.
Unit tests for queue.
Unit tests for stack.
Dummy classes used during unit testing.
This file was created automatically. You can see the code for that here.