fenghaolw

A message containing letters from  A-Z  is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message  "12" , it could be decoded as  "AB"  (1 2) or  "L"  (12). The number of ways decoding  "12"  is 2. Solution: DP. Use chk[n] to denote the number of decode ways: chk[n] = chk[n-1]*IsValid(s[n]) + chk[n-2]*IsValid(s[n-1], s[n])

Given a linked list and a value  x , partition it such that all nodes less than  x  come before nodes greater than or equal to  x . You should preserve the original relative order of the nodes in each of the two partitions. For example, Given  1->4->3->2->5->2  and  x  = 3, return  1->2->2->4->3->5 . Solution: here I use two queues to store the pointers of ListNodes.  Or we can use two pointers:

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given  board  = [ ["ABCE"], ["SFCS"], ["ADEE"] ] word  =  "ABCCED" , -> returns  true , word  =  "SEE" , -> returns  true , word  =  "ABCB" , -> returns  false . Solution: recursion. Note that if we change vector<vector<char> > &board to vector<vector<char> > board, the code does not pass the large judge. If the vector is transferred by value, the parameter is created a  copy of the vector you send in. Every time the method it called, the temporary variable is created and copied.

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. Solution: straightforward approach: use set to avoid duplicates.

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. Solution: recursion.

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 . Solution: first use binary search to find the row; then use binary search to find the target in this row. O(log m + log n).

Given a  m  x  n  matrix, if an element is 0, set its entire row and column to 0. Do it in place. Follow up: Did you use extra space? A straight forward solution using O( m n ) space is probably a bad idea. A simple improvement uses O( m  +  n ) space, but still not the best solution. Could you devise a constant space solution? Solution: use vectors to count the rows and columns which need to be modified. The following solution only use constant extra space (2 boolean variables). The key is to use the first row and the first column to store whether we should set the entire row/column to 0. Note that two boolean variables are required since we have to check whether the first row/column should be set to 0. These checks have to be done before we scanning the entire matrix; otherwise, the results might be overwritten.

Given an absolute path for a file (Unix-style), simplify it. For example, path  =  "/home/" , =>  "/home" path  =  "/a/./b/../../c/" , =>  "/c" Corner Cases: Did you consider the case where  path  =  "/../" ? In this case, you should return  "/" . Another corner case is the path might contain multiple slashes  '/'  together, such as  "/home//foo/" . In this case, you should ignore redundant slashes and return  "/home/foo" . Solution: Use stack to deal with "..". I use the approach in section 7.3 of  this page to split the string into tokens for given  delimiter . Another approach is to first copy the string into a c_str, then use strtok. Or we can directly traverse through the string and check the delimiter. There is no essential difference.

Given a  m  x  n  grid filled with non-negative numbers, find a path from top left to bottom right which  minimizes  the sum of all numbers along its path. Note:  You can only move either down or right at any point in time. Solution: DP. BUG FREE!

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 . Redo it at Mar. 17, 2014.

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A =  [2,3,1,1,4] The minimum number of jumps to reach the last index is  2 . (Jump  1  step from index 0 to 1, then  3  steps to the last index.) Solution: stupid solution (does not pass large judge) modified solution (passes large judge) Both solutions are BUG FREE! :D

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A =  [2,3,1,1,4] , return  true . A =  [3,2,1,0,4] , return  false . Solution: recursion (does not pass large judge) Record the current maximum reachable index (passes large judge)

Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array  [−2,1,−3,4,−1,2,1,−5,4] , the contiguous subarray  [4,−1,2,1]  has the largest sum =  6 . More practice: If you have figured out the O( n ) solution, try coding another solution using the divide and conquer approach, which is more subtle. Solution: classic algorithm problem for introducing dynamic programming. Check wiki to get the detailed explanation.  O(n) solution divide and conquer version O(nlogn)

Implement pow(x, n). Recursion. It is easy to rewrite this as iterative version.

You are given a string,  S , and a list of words,  L , that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters. For example, given: S :  "barfoothefoobarman" L :  ["foo", "bar"] You should return the indices:  [0,9] . (order does not matter). The following solution passes large judge, but takes 1600+ ms... Thank remlosttime for providing a much faster solution

Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case. Solution: First sort all strings and build a hash map to store the positions of all duplicates (anagrams). Then check the hash map to print out all anagrams.

Given a collection of numbers that might contain duplicates, return all possible unique permutations. Here I use set... maybe other approaches are better Another solution is to use next permutation.

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

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.  Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, ... , ak) must be in non-descending order. (ie, a1 < a2 < ... < ak). The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7, A solution set is: [7] [2, 2, 3] Solution: recursive version without sorting and set . Sorting it first and use set for avoiding duplicates DP (pass large judge)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Solution: merge sort. use an extra list to save. Iterative find the min element in each loop: O(KN) Build a heap in the first run, then use heap insert/delete: O(N logK) Redo it in Mar. 17, 2014

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()". Solution: If we have k < n left brackets, we can add a left bracket. If the number of right brackets < the number of left brackets, we can add a right bracket.

Given an array  S  of  n  integers, are there elements  a ,  b ,  c , and  d  in  S  such that  a  +  b  +  c  +  d  = target? Find all unique quadruplets in the array which gives the sum of target. Note: Elements in a quadruplet ( a , b , c , d ) must be in non-descending order. The solution set must not contain duplicate quadruplets. Solution: here I first generate an array with n(n-1)/2 elements storing the all possible two sums, and the corresponding indices. Then use a hash map to store these indices. Note that the key (the two sums) is not unique! and   I don't know how to write the hash function if using pair<int, int> as a key... Since the keys are not unique, multimap has to be used...

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Sort then scan... the following code is not optimized since we do not need to scan all possible values, once the gap starts increasing, we should stop.

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container. Solution: start from the container between begin and end, then shrink the container.

The string  "PAYPALISHIRING"  is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line:  "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string text, int nRows); convert("PAYPALISHIRING", 3)  should return  "PAHNAPLSIIGYIR". Solution: divide the whole string into subsections. In this example,  "PAYPALISHIRING" is divided to  "PAYP;ALIS;HIRI;NG". Then we will first insert the start character of each subsection to the zigzag version. Then, insert the character next to first subsection, and the character previous to the next subsection.

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1. Solution: use two pointers start and end; use hash map to store the characters. 2013-05-22 redo it. almost the same solution... My solution is inefficient since clearing the hash table is a waste of time. Using pointers to record the position should be a better solution.

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 Remember to initialize pointers to NULL...

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. Solution 1: Iterative DFS. Use a stack to store current path sum. Solution 2: Recursive DFS.

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. BUG FREE! recursion... copy a sub vector might not be efficient? Modified solution (more efficient)

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. Use new array (front to back) Don't use new array (back to front)

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Fibonacci series... DP

Given two binary strings, return their sum (also a binary string).

Validate if a given string is numeric. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. Solution: 1. first remove all spaces at the beginning. 2. then check the +/- sign. 3. '.' can only appear once, and the character before '.' or after '.' must be number. 4. 'e' can only appear once, and the character before 'e' must be number, the characters after 'e' can be '+/-' or numbers. 5. '.' cannot appear after 'e'. 6. ignore the spaces at the end.

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. Solution: DP again, set the number of paths to 0 if reach obstacle

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there?  Solution: DP

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

1.5 Write a method to replace all spaces in a string with ‘%20’. It is inefficient to direct replace all spaces since each replace will move all following characters. The worst case complexity is O(n^2). If we use a new string and dynamically increase the size, the complexity is O(n). If only C-style string is allowed, the solution needs to be modified but is still simple.

1.4 Write a method to decide if two strings are anagrams or not. First sort then compare... O(nlogn) Use indicator vectors... O(n)

1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not. "remove duplicate": make sure each character occurs at most once. The only way to avoid additional buffer is search the string again and again... O(n^2) Or we can use hash map or indicator array for achieving O(n)

1.2 Write code to reverse a C-Style String. (C-String means that “abcd” is represented as five characters, including the null character.) Classic question... Algorithm is simple, but got stuck during initialization... usages of string.c_str() and "abcd" return const char*, and then error happens during swap the elements in const array...

1.1 Implement an algorithm to determine if a string has all unique characters What if you can not use additional data structures? The first thought is to use hash table. If additional data structures are not allowed, we may use a large array corresponding to all possible characters. The array size depends on the characters sets (ASCII has 256 characters, for example). Both methods takes O(n) time.

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 Binary search or linear search...

Given a linked list, swap every two adjacent nodes and return its head. For example, Given  1->2->3->4 , you should return the list as  2->1->4->3 . Your algorithm should use only constant space. You may  not  modify the values in the list, only nodes itself can be changed. Recursive: Iterative: