读过 Programming Interviews Exposed
1, Linked Lists
In C++, the head pointer could also be passed in by reference.
People often say “tree” when they mean “binary tree.”
People often say “tree” when they mean “binary search tree.”
Heaps are trees (usually binary trees) with a twist: Each child of a node has a value less than or equal to the node’s own value. Consequently, the root node always has the largest value in the tree, which means that it’s possible to find the maximum value in constant time: Simply return the root value. Insertion and deletion are still O(log(n)), but lookup becomes O(n).
Recursion implicitly uses a stack data structure by placing data on the call stack. That means there should be an equivalent solution that avoids recursion by explicitly using a stack.
C/C++： In most cases, an array name is equivalent to a pointer constant to the first element of the array
Java： Unlike a C array, a Java array is an object in and of itself, separate from the data type it holds. A reference to an array is therefore not interchangeable with a reference to an element of the array.
You can’t assign one C array to another, you cannot copy C strings using the = operator. Instead, you generally use the strcpy() function.
C++：If you want to create strings that store Unicode values (as in Java or C#), you can define a new variant of basic_string based on the wchar_t (wide character) type.
Java：Java strings are immutable: They cannot be changed once the string has been constructed. Methods that appear to modify a string actually return a new string instance. The StringBuffer and StringBuilder classes (the former is in all versions of Java and is thread safe, the latter is new starting with Java 5 and is not thread safe) create mutable strings that can be converted to a String instance as necessary. The compiler implicitly uses StringBuffer instances when two String instances are concatenated using the + operator, which is convenient but can lead to inefficient code if you’re not careful.
C#：C# strings are also immutable, just like Java strings. Mutable strings are created with the StringBuilder class
7，Monitors and Semaphores
A monitor is a set of routines that are protected by a mutual exclusion lock. A thread cannot execute any of the routines in the monitor until it acquires the lock, which means that only one thread at a time can execute within the monitor; all other threads must wait for the currently executing thread to give up control of the lock.
A semaphore is a simpler construct, just a lock that protects a shared resource. Before using a shared resource, the application must acquire the lock. Any other thread that tries to use the resource is blocked until the owning thread releases the lock, at which point one of the waiting threads (if any) acquires the lock and is unblocked.
8，Interfaces and Abstract Classes
（1）an interface defines an application programming interface (API) that is independent of any class hierarchy. In fact, interfaces can be used in non-OO programming models
（2）Unlike an interface, an abstract class is a proper class: It can have data members and can be a subclass of other classes. Unlike a concrete (nonabstract) class, however, some of its behaviors are deliberately left to be defined by its own subclasses.
（3）An interface is almost identical to an abstract class with no data members and no method definitions. In C++ this is exactly how you’d define an interface: by declaring a class with no data members and only pure virtual functions
（4）In Java, an interface is defined using the interface keyword
A virtual method is a method whose implementation is determined at run time based on the actual type (class) of the invoking object. Nonstatic Java methods are always virtual, so Java programmers may have trouble answering this one; but in C# and C++, methods are only virtual when declared with the virtual keyword—nonvirtual methods are the default.
The problem with multiple inheritance is that it can lead to ambiguity.
There are other complexities with multiple inheritance, such as the order in which the base classes are initialized when a derived object is constructed, or the way members can be inadvertently hidden from derived classes.
11，Binary Two’s Complement Notation
Negative numbers are a little trickier. Two’s complement notation makes a number negative by applying the rule “flip each bit and add 1” to the number’s positive binary representation. For example, to get the number –1, you start with 1, which is 00000001 in binary. Flipping each bit results in 11111110. Adding 1 gives you 11111111, which is the two’s complement notation for –1.
12，Big-endian or Little-endian
Set an integer to 1
Cast a pointer to the integer as a char *
If the dereferenced pointer is 1, the machine is little-endian
If the dereferenced pointer is 0, the machine is big-endian
13，Escaping the Train
The friend keyword is applied to either a function or a class. It gives the friend function or friend class access to the private members of the class in which the declaration occurs.
Garbage collection is not without its disadvantages, however. Garbage-collected programs often run more slowly because of the overhead needed for the system to determine when to deallocate and reclaim memory no longer needed.
（1）One method of garbage collection is to use reference counting. This involves tracking how many variables reference an object. Initially, there will be one reference to a piece of memory. The reference count will increase if the variable referencing it is copied. When a variable referencing an object changes value or goes out of scope, the object’s reference count is decremented. If a reference count ever goes to 0, the memory associated with the object is freed: If no one is keeping a reference to the object, then the object (and hence its memory) is no longer needed.
（2）A second method of garbage collection is known as mark and sweep. In the first pass, the memory manager will mark all objects that can be accessed by any thread in the program. In the second pass, all unmarked objects are deallocated, or swept away.
Any network can be measured by two major characteristics: latency and bandwidth. Latency refers to how long it takes a given bit of information to get through the network. Bandwidth refers to the rate at which data moves through the network once communication is established.
Your résumé must be a marketing tool that sells you and convinces an employer that you’re valuable—quickly.
If he doesn’t see anything he likes after 15 or 20 seconds of looking at the résumé’s first page, the résumé won’t make it any further.
（3）List the Right Information
Explicitly list your skills by name on your résumé.
（4）Be Clear and Concise
Present your experience in bulleted lists and cast it in the best possible light.
（5）Relevant Information Only
（6）Use Reverse Chronological Ordering
Know Yourself 1，Are you a systems programmer or an application developer? 2，Do you li...