Pascal's Triangle II

Pascal's Triangle IIOct 29 '12

Given an index k, return the k^th row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

» Solve this problem

Pascal's Triangle

Pascal's TriangleOct 28 '12

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Regular Expression Matching

Regular Expression MatchingJan 8 '12

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true
Thanks to 1337c0d3r for the solution.
The basic idea is to use recursion for matching * as we dont know how many times we have to match a character preceding a *.

Triangle

TriangleOct 30 '12

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Palindrome Number

Palindrome NumberJan 4 '12

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Reverse Integer

Reverse IntegerDec 26 '11

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Permutations II

Permutations IIMar 17 '12

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Subsets II

Subsets IIJun 25 '12

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Subsets

SubsetsApr 18 '12

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Search a 2D Matrix

Search a 2D MatrixApr 7 '12

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Analysis: The algorithm first finds the row to search by performing the binary search on the first column in log(m) time. Then that row is binary searched in log(n) time to return the result. log(m)+log(n) is the total time complexity.

An elegant solution

Longest Valid Parentheses

Longest Valid ParenthesesMar 1 '12

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Analysis

lastValidIndx keeps track of the index of the starting point of the longest valid parantheses. An empty stack will increment the lastValidIndx. So consider this string )))))( in this case, the lastValidIndx will be 5. Any valid parantheses will be counted from the lastValidIndx as currentIndx-lastValidIndx+1.

maxLength: keeps track of the length of the maximum length of valid parantheses seen so far. 

Unclosed parantheses: Consider the string ()(()(), in this case the length of the maximum parantheses is 4 and not 6. Whenever a ) is seen we pop the current top of the stack. If the, stack is not empty then there is an unbclosed parantheses in the stack. We then count the parantheses as starting from the index of this unclosed parantheses instead of counting it from lastValidIndx as we do for the case of stack empty case (no unclosed parantheses)

Time Complexity:   O(n)

Add Two Numbers

Add Two NumbersNov 1 '11

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder TraversalSep 30 '12

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Binary Tree Maximum Path Sum

Binary Tree Maximum Path SumNov 8 '12

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Letter Combinations of a Phone Number

Letter Combinations of a Phone NumberJan 27 '12

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Search Insert Position

Search Insert PositionMar 3 '12

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Permutations

PermutationsMar 17 '12

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder TraversalSep 30 '12

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Analysis
1. Get an element from the preorder vector
2. Lookup the position of that element in the inorder vector
3. Using that position partition the inorder vector and recursively form the left and right subtrees using these partitions by doing 1 through 3 for every next element in the preorder vector

Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search TreeOct 3 '12

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. Algorithm with inorder traversal avoiding the need to traverse the linked list for midpoint that is required for the previous algorithm with preorder traversal.

Rotate List

Rotate ListMar 28 '12

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Analysis An alternative method to handle the case where k>n is to not wrap around the faster ptr but to traverse the list once to get number of elements in the list and then adjust k=k%n or n

Remove Duplicates from Sorted List

Remove Duplicates from Sorted ListApr 22 '12

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Analysis
This is a O(n) time complexity algorithm that links the last distinct element with the current distinct element, thereby deleting all elements between these two nodes.

Merge k Sorted Lists

Merge k Sorted ListsFeb 14 '12

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Merge Two Sorted Lists

Merge Two Sorted ListsMar 30 '12

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

This is an algorithm with O(n) time complexity. List L2 is merged in list L1 and returned as a new list.

Merge two sorted arrays

Merge Sorted ArrayMay 20 '12

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

String to Integer (atoi)

String to Integer (atoi)Dec 27 '11

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Insert Interval

Insert IntervalMar 27 '12

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Algorithm idea

While traversing the input intervals, merge with all intervals conflicting with the new interval to be inserted. If there are no conflicting intervals, then find the correct position to insert this new interval based on the start value of the new interval relative to the intervals in the input interval vector.

Time Complexity: O(n)
Space Complexity: O(1)