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

• プロセスは各プロセスごとにシステムリソース(CPU時間とメモリなど)を割り当てられたインスタンスで、異なるアドレス空間で実行される。そのためプロセス間で他のプロセスのリソースにアクセスしたければ、パイプ、ファイル、ソケットなどのプロセス間通信を行う必要がある。

• スレッドはプロセス内の同じメモリ空間を、複数のスレッドで共有する。そのため一般的に複数のスレッドが同じメモリを読み書きでき、他のプロセスが使用しているメモリにアックセウできないプロセスとはここが大きく異なる。

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.

code

Successor

prblme

Write an algorithm to find the "next" node(i.e., in-order successor) of a given node in a binary search tree. (You may assume that each node has a link to its parent or you can get the root node)

how to solve

"Next" node means that the most nearest parent node which is right side of a given node. So we should find it.

code 1

When I can get the root node

code 2

When I get the parent node of each node

code 3

More easy way

gist.github.com