[CC150] Chapter 7 Mathematics and Probability

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 not collide, they have to choose the same direction, clockwise or counter-clockwise. In other words, the probability of collision is 1 - 2/8 = 3/4.
For n-vertex polygon, there are 2^n possibilities, and the probability of collision is 1 - 2/2^n = 1 - 2^(1-n).

7.3 Given two lines on a Cartesian plane, determine whether the two lines would intersect.

 Check whether the slopes are the same. Note that we should not use x == y; instead, (x - y) < epsilon should be used due to the accuracy of floating point numbers.

7.4 Write methods to implement the multiply, subtract, and divide operations for integers. Use only the add operator.

 TBF.

7.5 Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis.

 TBF.

7.6 Given a two-dimensional graph with points on it, find a line which pass the most number of points.

 This problem is in leetcode as Max Points on a Line.

7.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.

 The main idea is to create three queues.
Remark: 1. Priority queue could also be used to reduce the find minimum operation.
2. To avoid duplicates, we only push from the chk[minidx] to the end.

Comments

Post a Comment

Popular posts from this blog

Maximum Gap

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
Read more

[ITint5] Maximum Subarray for a Circular Array

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.
Read more

[CC150] Chapter 4 Trees and Graphs

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
Read more