fenghaolw

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.  Try to solve it in linear time/space.  Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range. In order to solve this in linear time, we cannot use general sorting algorithm. Here we use bucket sort. First, we scan the array to find the min and the max values.   We can then create n - 1 buckets with equal size. Suppose we have n elements in total, then we have n - 2 elements except the min and the max. Scan the array again to put the n - 2 elements into these buckets. We should have at least one empty bucket. For each bucket, we record the min and the max for all the elements within that bucket.  Finally, we scan all the buckets, and maintain the maximum gap. Note that the maximum gap between the successive elements in the sorted array can only be the gap between

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2. Binary search. If mid is the peak, return it. If mid is not the peak, it must be less than or equal to one of its neighbors. Suppose it is less than or equal to its left, then the left half must contains a peak. Why? If the left half is not monotonically decreasing, there must contains a peak. If the left half is monotonically decreasing, the peak is the first element.

Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return  null . The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory. This is a classic problem. geeksforgeeks has a very detailed discussion.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.  push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. This problem is included in CC150 (See 3.2 in Chapter 3 ). Further improvement could be save the counter of duplicates (the current version push some duplicates into two stacks).

Follow up for " Find Minimum in Rotated Sorted Array ": What if duplicates are allowed? Would this affect the run-time complexity? How and why? When num[mid] == num[tail], we need to linearly move the pointer. The worst case complexity is O(n), but the average will still be better than simple linear search.

Given an array A, generate an array B such that  B[i] = A[0]*A[1]*...A[i-1]*A[i+1]*...A[n-1]. The brute-force approach takes O(n^2) time. One simple improvement would be pre-calculating the product of A[0], A[1] ... and A[n-1]. Then for each A[i], we can easily generate B[i] by dividing the total product by A[i]. We only need O(2n) in time. A few corner cases need to be considered: What if there is one zero in the array, i.e., A[i] = 0? The total product will be 0, and the divide operations are invalid. In this case, B[j] = 0 if j not equals to i, and B[i] is the only non-zero element in the array. What if there are more than 2 zeros in the array? The entire B should be 0. Follow-up: what if divide is not allowed? If divide operation is not allowed, we can still have a linear time solution. The idea is to generate two helper arrays, and then calculate B[i] based on these two arrays. Follow-up: what if extra space is not allowed? Actually there is a pretty neat so

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. You may assume no duplicate exists in the array. Classic binary search.

http://www.itint5.com/oj/#26 Evaluate an arithmetic expression. For simplicity, the following assumptions are made: There are only positive integers. There is no overflow.  Only plus, minus, and multiply operations are supported. No parenthesis, divide, and modulo. All inputs are valid arithmetic expressions. Example: Input: 1+4*3-5 Output: 8 Input: 2-3-5*2 Output: -11 Note that multiplication has higher priority than plus and minus. Every time we meet a '*' , we will calculate the number. If we meet a '+' or '-' , we will call the recursion, or push the number into a data structure. Recursive version: Note that for minus operations, instead of using prevNum - calc(expr, currNum, pos) , we need to convert it to negative number (i.e., prevNum + calc(expr, -currNum, pos) ). Otherwise the result will be incorrect. For example, 5-4+2 , if we use the first approach, the result will be 5-(4+2)=-1 . However, it should be 5+(-4+2)=3 . Iterative v

http://www.itint5.com/oj/#4 In a complete binary tree every level, except possibly the last, is completely filled, and all nodes are as far left as possible. How can we count the total number of nodes in a complete binary tree? A straightforward method is to traverse the tree, which takes O(n) in time, where n is the number of nodes. However, this method does not utilize the property of complete binary tree. Since we know the tree is complete, it is very easy to find the height of the tree; the tricky part is how can we find the number of nodes in the last level. We can utilize a binary search method to figure out how many nodes are in the last level. For each node, we check the "left height" of its left subtree and its right subtree, respectively. "Left height" means the depth of the leftmost leaf node. If the "left heights" are the same, we know that the left subtree is full; if the "left heights" are not the same, we know that the r

http://www.itint5.com/oj/#8 Classic DP problem, which has also appeared in Leetcode as Maximum subarray . The only difference is, in this problem, empty subarray (where sum is 0) is allowed. So instead of return ret, we could simply return max(0, ret). http://www.itint5.com/oj/#9 Calculate the maximum subarray for a circular array. For example, [1, 3, -2, 6, -1], we should return 9 since 6 + (-1) + 1 + 3 = 9. The following solution might not be optimized. Suppose that the maximum subarray is from A[i] to A[j]. The idea is, consider the following different scenarios: i <= j: it is the same as classic problem. i > j: the sum is A[i : end] + A[start : j]. So we can use two additional arrays: left[j] = maximum subarray, starts from A[start] and ends no later than A[j] right[i] = maximum subarray, starts no earlier than A[i] and ends at A[end] The following code passes the online judge. However, we need O(4n) in time and O(2n) in space. Not sure how to improve this.

Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6. Solution: Similar to  Maximum Subarray  which considers sum instead of product. The main difference is, the largest product could be a product of two negatives. Hence, besides maintaining a maximum product to the current pointer, we also need to record a minimum product to the current pointer.

Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the". Clarification: What constitutes a word?  A sequence of non-space characters constitutes a word.  Could the input string contain leading or trailing spaces?  Yes. However, your reversed string should not contain leading or trailing spaces.  How about multiple spaces between two words?  Reduce them to a single space in the reversed string. Python version is super easy... Following version works, however, iterator library is not included in leetcode... Or, we can use any methods in Simplify Path to split the string. Following is an example.

http://www.itint5.com/oj/#23 The row and column indices in Excel are denoted by: A, B, C, ..., Z, AA, AB, ... AZ, BA, ... The corresponding decimal numbers are: 1, 2, 3, ..., 26, 27, 28, ... Implement two functions to transform decimal numbers to Excel numbers and vice versa. Excel number is a numeral system based 26.

Implement wildcard pattern matching with support for '?' and '*'.  '?' Matches any single character.  '*' Matches any sequence of characters (including the empty sequence).  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", "*") → true  isMatch("aa", "a*") → true  isMatch("ab", "?*") → true  isMatch("aab", "c*a*b") → false Use two pointers to save the position of last '*' and the position of corresponding char in s. First time when we meet '*', we assume it is an empty string. Once we do not find the match, backtrack to the last '*', and assume it matches a string of length

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 If the next character of p is not *: check current *s and *p, and recursive search. If the next character of p is *: search all possibilities.

https://www.hackerrank.com/challenges/stockmax Related problems:  Best Time to Buy and Sell Stock I ,  Best Time to Buy and Sell Stock II ,  Best Time to Buy and Sell Stock III . In previous problems in Leetcode, we can only hold up to one stock. Now, we can hold multiple stocks and try to achieve the maximum profit. The idea is to scan the array from back to front. Try to find out a monotonic increasing sequence; For example, if the stock prices are [1, 7, 2, 4, 5, 9, 1, 2, 6] We start from 6, and store the increasing sequence as [9, 6]. Note that we actually store the index instead of the value. This sequence represents the points we want to sell the stocks. In other words, the optimal strategy is to continuously buy the stock if it is possible to gain profit. Once we achieve a highest point, sell all of the previous stocks. In this example, we should buy 1, 7, 2, 4, 5. Then sell all these five stocks at the point 9, get the profit of 8 + 2 + 7 + 5 + 4 = 26. After tha

https://www.hackerrank.com/challenges/median Test cases:  https://s3.amazonaws.com/hr-testcases/104/input01.txt (input00.txt to input09.txt) This is a classic problem: finding the moving median for an integer stream. The key idea is to use two ordered structures (one for the smaller half and another for the larger half). If we can make sure that these two half are size-balanced, we can easily obtain the median. Remarks: 1. If the delete operation is not required, priority_queue could be used. Here I use multiset to implement add/remove/search in O(logn). Find median is O(1). Note that instead of using set, multiset should be used for handling duplicated values. 2.  multiset<int, greater<int> > defines a multiset in descending order. In this case, the begin() iterator points to the largest number. On the other hand, multiset<int, less<int> >, which is by default, defines a multiset in ascending order. 3. I spend a lot of the times on the output forma

https://www.hackerrank.com/challenges/coin-on-the-table Solution: I can only figure out the DFS solution. No idea how to do the DP.

9.1 A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. A simplified version is in leetcode as  Climbing Stairs . 9.2 Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0, 0) to (X, Y)? FOLLOW UP Imagine certain spots are "off limits", such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right. This problem is in leetcode as  Unique Paths  and  Unique Paths II . 9.3 A magic index in an array A[1... 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. FOLLOW UP What if the values are not distinct? 9.4 Write a method to ret

8.1 Design the data structure for a generic deck of cards. Explain how you would subclass the data structures to implement blackjack. Following codes implement blackjack. Note that syntax highlighter automatically changes some upper case letters to lower case.   8.2 Imagine you have a call center with three levels of employees: respondent, manager, and director. An incoming telephone call must be first allocated to a respondent who is free. If the respondent can't handle the call, he or she must escalate the call to a manager. If the manager is not free or not able to handle it, then the call should be escalated to a director. Design the classes and data structures for this problem. Implement a method dispatchCall() which assigns a call to the first available employee. 8.3 Design a musical jukebox using object-oriented principles. 8.4 Design a parking lot using object-oriented principles. 8.5 Design the data structures for an online book reader system. 8.6 Implement a ji

7.1 You have a basketball hoop and someone says that you can play one of two games. Game 1: you get one shot to make the hoop. Game 2: you get three shots and you have to make two of three shots. If p is the probability of making a particular shot, for which values of p should you pick one game or the other? Game 1: the winning probability is p. Game 2: the winning probability is p^2(1 - p) * C^2_3 = 3p^2(1 - p) We can easily get if p < 0.5 we should choose Game 1. 7.2 There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Assume that each ant randomly picks a direction, with either direction being equally likely to be chosen, and that they walk at the same speed.  Similarly, find the probability of collision with n ants on an n-vertex polygon. Clearly, each ant has two choices. In total, there are 2^3 = 8 possibilities. To make sure that they do n

6.1 You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the scale once. Take one pill from Bottle #1, two pills from Bottle #2, and so on. The total weight should be 1 + 2 + ... + 20 + overweight = 210 + overweight. Overweight is 0.1 grams times the index of the heavy bottle. 6.2 There is an 8x8 chess board in which two diagonal opposite have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer. It is impossible. A good proof from the book is: original board has 32 black and 32 white squares. By removing two opposite corners (which could be both black or both white), we have 30 of the one color and 32 of the other color. However, each domino always take one white and one black. 6.3 You have a five-quart jug, a three-qua

5.1 You are given two 32-bit number, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through i have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2. EXAMPLE Input:  N = 10000000000, M = 10011, i = 2, j = 6 Output: N = 10001001100 Using bitset is trivial... Better solution should be use a mask. According to the solution, the problem can be divided into three steps: 1) clear the bits j through i in N; 2) Shift M so that it lines up with N; 3) Merge M and N. 5.2 Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR". Note that in the follow

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Binary search. Each time we could eliminate half of the A or half of the B. Note that if m + n is even, we need to return the mean value of (m+n)/2 and (m+n)/2+1.

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively. Recursive backtracking (DFS)

Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. You may assume that there will be only one unique solution. Recursive version: Still trying to write iterative version

4.1 Implement a function to check if a binary tree is balanced. For the purpose of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one. This problem is in leetcode as  Balanced Binary Tree . 4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes. Both BFS and DFS works. Here I use iterative BFS. 4.3 Given a sorted (increasing order) array, write an algorithm to create a binary search tree with minimal height. This problem is in leetcode as  Convert Sorted Array To Binary Search . Related problem:  Convert Sorted List To Binary Search . 4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you will have D linked lists). This problem is equivalent to  Binary Tree Level Order Traversal . Related problem:  Binary Tree Zigzag Level Order Traversal

3.1 Describe how you could use a single array to implement three stacks. If we assume that all three stacks have the same size, we could easily do this by recording the indice for the top elements. Here I ignore the dynamic implementation in the book since it is way too complicate. 3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop, and min should all operate in O(1) time. Use an additional stack to store the current and historic minimum elements. Note that here we used a pair to handle duplicates. Instead of push all duplicated minimum elements to the stack, the following code is more efficient for saving space. Note that we did not assert the pop operation. For the original stack class in C++, pop a empty stack does not throw an error. 3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the p

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.  For example, given s = "leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code". Intuitive backtracking approach got Time Limits Exceed. DP: use a binary array to describe whether the first part of the string is in the dict. For each non-zero element in the array, update the elements by checking the second part of the string.

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Follow up: Can you solve it without using extra space? Hashset approach: A trick one is to use slow/fast runner. Slow runner moves forward one step where fast runner moves forward two steps. If there is a cycle they will eventually meet. Suppose that the cycle size is c, and the distance between the head and the begin node of the cycle is x. When the slow runner meets the fast runner, the slow runner moves y steps and the fast one moves 2y steps. Then we have y = x + k1*c + b 2y = x + k2*c + b x + b = k*c Now we move the slow runner to the head and keep the fast runner at the place they meet. The distance between two runners are x + b; since the distance can be divided by c, if we move both runners at the same pace, they will meet at the beginning of the cycle. 

Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space? A straightforward way is to use hashset. A trick one is to use slow/fast runner. Slow runner moves forward one step where fast runner moves forward two steps. If there is a cycle they will eventually meet.

2.1 Write code to remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed? Related problems:  Remove Duplicate from Sorted List  and  Remove Duplicate from Sorted List II . Following code defines a class LinkedList, which provides several methods: CreateList: create a linked list from a given vector of integers PrintList: print out the linked list for debugging removeDuplicates: remove duplicates using a hash set removeDupNoBuffer: remove duplicates without buffer (O(n^2) in time) 2.2 Implement an algorithm to find the kth to last element of a singly linked list. This problem is in leetcode as  Remove Nth Node From End of List . 2.3 Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node. The only way is to copy the next node to the current node, and then delete the next node. If the node to be deleted is the last one, you cannot delete it. Probably we co

5th Edition 1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? Check  here . 1.2 Implement a function void reverse(char * str) in C/C++ which reverses a null-terminated string. Check  here . 1.3 Given two strings, write a method to decide if one is a permutation of the other. Check  here . 1.4 Write a method to replace all spaces in a string with '%20'. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the "true" length of the string. Check  here . 1.5 Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string. 1.6 Given an image represe