barrysteyn

Flatten Binary Tree to Linked List

http://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/

Problem Description

Given a binary tree, flatten it to a linked list in-place.

For example, Given

barrysteyn

/**
 * 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;

barrysteyn

/* 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

/*
 * 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

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

/*
 * 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

/*
 * 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

Leetcode: Reverse Linked List II

http://oj.leetcode.com/problems/reverse-linked-list-ii/

Problem Description

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

barrysteyn

/*
 * 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

/*
 * 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>