fenghaolw

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

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Essentially this problem is equivalent to find all unique lines. Note that each line can be represented by a pair: slope and a fixed point. Here, we use the point where y = 0. If y = 0 is impossible, we use the point where x = 0. Also, we use a map to store the line and the points which lie on this line.

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:  get  and  set . get(key)  - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value)  - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. My first thought is to use min heap to track the usage; and use another hashmap to guarantee constant complexity for get method. However, heap structure is not helpful for "recently used". Instead, we can use doubly linked list to store the <key, value> pair. Hashmap is still required for get method. The logic is:  get(key): use hashmap to find the corresponding node in the linked list. Remove the node, and then add it to the tail, i.e., this node has been used recently. set(key, value): search the hashmap, if the node