Skip to content

Instantly share code, notes, and snippets.

View barrysteyn's full-sized avatar

Barry Steyn barrysteyn

View GitHub Profile
@barrysteyn
barrysteyn / knapsack.cpp
Created July 6, 2013 19:55
The Knapsack algorithm
/* The classic knapsack problem, solved with
* dynamic programming. In the dp array,
* rows represent item subset choice, columns
* represent weights, and individual cells represent
* values. The knapsack algorithm can also be adapted
* to searching subsets for a target value. Just set
* weights equal to values, and one can then search subsets
* for a value.
*
* If there are n values, and the target value is t, then
/*
* The difficult part about this problem was figuring out it was
* only BFS. The restrictions of time O(nlogn) and space O(n)
* were easy to figure out.
*/
#include <algorithm>
#include <queue>
#include <utility>
#include <iostream>
@barrysteyn
barrysteyn / swap_pairs.cpp
Created July 4, 2013 17:50
LeetCode: Swap pairs
/*
* In a competition to see who would use the least pointers
* for reversing nodes in a linked list, I think this solution
* should be entered. There are easier solutions to read/spot,
* but I think this is the most elegant.
*/
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
@barrysteyn
barrysteyn / Readme.md
Created July 3, 2013 18:53
Leetcode: Reverse Linked List II
@barrysteyn
barrysteyn / maxValidParenthesis.cpp
Created July 2, 2013 21:08
Leetcode: Max valid parenthesis
/*
* I found this one tough. I figured out a solution that used O(n) space almost immediately, but this
* solution is much more elegant. The problem states counting the max size of the valid parenthesis.
* For example, (()() would be four. The data structure to use here is a stack, but there is a trick.
* The trick is to note that if the stack is empty, and a right bracket comes along ')', then the
* size calculation must start from 0 again. This is because that is invalid and will never
* produce a valid parenthesis pair. So we initialise a variable called lastRight, which is set at -1
* When the stack is empty, this is the variable that will be used to calculate the size. When a ')'
* comes along, then this variable is updated. When the stack is not empty, then we just substract the
* the current increment value from whatever is on the top of the stack.
@barrysteyn
barrysteyn / duplicate_rotated_array_search.cpp
Last active December 19, 2015 05:19
Leetcode: Search in a sorted array that can have duplicates
/*
* This is the classic problem, but made slightly more difficult by allowing duplicates. If duplicates are allowed,
* then we can get into a pickle: When both the first and last element are the same. In this case, we do not know whether to go
* forwards or backwards. What do we know: That both first and last are the same (duh)! So that basically means we carry
* on either ignoring the first element or the last element (they are the same after all, so it does not matter).
*
* Time complexity = O(N) (bye bye logn binary search). This is because in the worst case, line 28 comes down to
* a linear search.
*/
@barrysteyn
barrysteyn / Leetcode: Search In A Sorted Array.md
Last active December 19, 2015 05:09
Leetcode problem: Search in a rotated array (classic problem)

Leetcode: Search In A Sorted Array

This is a classic binary search problem, which I always struggle to get after not looking at it for some time.

There are many ways to accomplish, I will present 5 ways:

  1. The standard way without knowledge of abstract binary search theory (both iterative and recursive)
  2. Evaluation the following predicate: p(x): A[x] >= target
  3. Evaluation of the following predicate: p(x): A[x] > target
@barrysteyn
barrysteyn / recover_ip_address.cpp
Created July 1, 2013 14:44
Leetcode problem: Recover IP Addresses
/*
* This is a classic backtracking algorithm. It is made difficult due to the following:
* 1) There is a special case, namely 0
* 2) Normally, backtracking employs a for loop, this needs a while loop. Therefore
* conditions for ending the recursion is not normal
*
* All ip addresses consist of octets, which is between 0 and 255. So any number within this
* range should be selected for our ip address. If however we cannot pick such a number
* then we must back track
* Time Complexity O(n^2) Space O(1)
@barrysteyn
barrysteyn / recover_binary_tree.cpp
Created June 30, 2013 15:47
Leetcode problem: Recover the binary tree that has had two nodes swapped/
/* This is an easy problem, but made difficult because you can only use O(1) space
* Traverse the tree use inorder. Its easy to spot nodes that are out of place: They will not be in increasing order
* In order to accomplish this, we need to do an in order traverse and keep track of the previous node
* The first time previous is larger than the current node (root), both previous and root must be added because both could
* potentially be in violation. If however we find another violation (i.e. previous is greater than current), then we can replace
* the last value of the node array with the current (root) node. Why? Because two nodes have been swapped. We find the larger of
* the two first (because of the in order traversal), so the next node must be smaller of the two.
*
* Space: O(1) - only an array of size 2
* Time Complexity: O(n), where n is the number of nodes (i.e. complexity of in-order traversal)
@barrysteyn
barrysteyn / hasPathSum.cpp
Created June 29, 2013 21:42
LeetCode: HasPathSum
/**
* Things to ask in an interview: Can sum ever be zero
* Time: O(n) (n = number of nodes)
*/
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if (!root) {
return false;