TopCoder srm 708a SafeBetting
problem
Limak is in a casino. He has b dollars. He wants to have at least c dollars (to be able to buy flowers for a girl he likes). In order to achieve that, he must win the money he’s missing.
The casino allows guests to risk some of their money on bets. Limak can make as many bets as he likes, but he has to make them one after another. Each time Limak makes a bet, he chooses the amount he wants to bet. The amount must be a positive integer. Each bet has two possible outcomes: either Limak loses the money, or he gets it back doubled.
For example, suppose Limak has 20 dollars. If he bets 5, he will be left with 20 - 5 = 15 dollars. If he loses the bet, that is his new total. If he wins the bet, he’ll get back 2*5 = 10 dollars, which will bring his total up to 15 + 10 = 25 dollars.
Limak doesn’t want to lose all his money. More precisely, he wants to make sure that at any moment he will have at least a dollars. He will not make a bet if losing the bet would mean that he will have less than a dollars.
For example, suppose Limak currently has 20 dollars. If a = 15, in the next round Limak can bet 1, 2, 3, 4, or 5 dollars. Note that a bet of 6 dollars is not allowed: if he lost it, he would have 20 - 6 = 14 dollars, which is less than a.
You are given the s a, b, and c. We will assume that Limak follows the rules described above when choosing the amounts to bet. Compute and return the smallest B such that Limak can reach his goal (i.e., have at least c dollars) after making B bets.
code
Tread vs Process
problem
What is the difference between a thread and a process?
answer
English
A process can be thought of as an instance of a program in execution. A process is an independent entity to which system resources( cpu time and memory) are allocated. Each process is executed in a separate address space, and one process cannot access the variables and data structures of another process. If a process wishes to access another process' resources, inter-process communications have to be used. These include pipes, files, sockets and other forms.
A thread exists within a process and shares the process' resources (including its heap space). Multiple threads within the same process will share the same heap space. This is very different from processes, which cannot directly access the memory of another process. Each thread still has its own registers and its own stack, but other threads can read and write the heap memory.
Japanese
Paths with Sum
problem
You are given a binary tree in which each node contains an integer value(which might be positive or negative). Design an algorithm to count the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go down wards(traveling only from parent nodes to child nodes).
how to solve
solution1: brute force in recursively.
In the brute force approach, we just look at all possible paths. To do this, we traverse to each node. At each node, we recursively try all paths downwards, tracking the sum as we go. As soon as we hit our target sum, we increment the total.
code
solution2: using hash table.
code
Sparse Search
problem
Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string.
how to solve
If it were not for the empty strings, we could simply use binary search. With empty strings interspersed, we can implement a simple modification of binary search. We just find closest non-empty string if mid is empty.
code
Sorted Matrix Search
problem
Given an M * N matrix in which each row and each column is sorted in ascending order, write a method to find an element.
how to solve
http://articles.leetcode.com/searching-2d-sorted-matrix-part-ii/
The above link is very easy understanding.
We begin with the upper right corner. Instead of traversing diagonally each step, we traverse one step to the left or bottom. Essentially, each step we are able to eliminate either a row or a column. This algorithm runs in O(n+m).
code
Minimal Tree
problem
Given a sorted(increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.
How to solve
This minimal tree means creating height balanced tree. Firstly, we want the root to be the middle of the array, since this would mean that half the elements would be less than the root and half would be greater than it. We proceed with constructing our tree in a similar fashion. The middle of each subsection of the array becomes the root of the node. The left half of the array will become our left subtree, an the right half of the array will become the right subtree. We do this in recursively we create a height balanced tree in O(N).
- Insert into the tree the middle element of the array.
- Insert (into the left subtree) the left subarray elements.
- Insert (into the right subtree) the right subarray elements.
- Recurse.
code
Group Anagrams
problem
Write a method to sort an array of strings so that all the anagrams are next to each other.
how to solve
I use hash table. once we have grouped all the words into these lists by anagram. we can then put them back into the array.