Q: what are the most common data structures in which to apply them?

A. most people will miss the tree and graph the two data structures. Trees and graphs are useful data structures. If you mention them in your answer, the interviewer may have a further assessment of you.

Q: how do you implement Map, Set and List?

A: although Java has provided a proven and tested implementation of these interfaces, but the interviewer still like to ask, to test your understanding of the data structure. I wrote "Core Java Career Essentials" in a book by the legend and explain in detail the contents of the code.

**Common data structures**

arrayIs the most commonly used data structure. The array is characterized by a fixed length, indexed by index, and all of the elements of the same type. Array of commonly used scenarios: from the database to read the information stored in the employee's EmployeeDetail[], the conversion of a string and stored in a byte array for easy operation and processing, and so on. Try to put the array package in a class, prevent data had been wrong operation. In addition, this is also suitable for other data structures.

array

**list**And the array is very similar, but its size can be changed. List is generally achieved through a fixed size array, and will automatically adjust the size when needed. The list can contain duplicate elements. Commonly used scenarios have, add a line of new items to the order list, the list of all expired goods removed from the list of goods, etc.. Usually the list is initialized to a suitable size to reduce the number of adjustments.

**aggregate**And the list is very similar, but it can not be repeated elements. When you need to store different elements, you can use the set.

**stack**Only the last inserted elements are allowed to operate (that is, the last in first out, In First Out Last - LIFO). If you remove the top of the stack element, then you can manipulate the second elements, followed by analogy. This last in first out of the way is achieved through the only peek (), push () and pop () the mandatory limits of these methods to achieve. This structure in many scenes are very useful, such as analytical like (4 + 2) X3 such mathematical expressions, the source method and abnormal in the order they appear into the stack, check your code to see small brackets and braces is not matching, and so on.

This use of the stack to achieve the last in first out (LIFO) mechanism is very useful in many places. For example, expression evaluation, and syntax parsing, check and parse XML, text editor undo action, in the browser browsing records, and so on. Here are some of the Java interview questions about the stack.

**queue**And the stack is somewhat similar, the difference is that the first insertion of the first element in the queue is also the first to be deleted (ie, the first out). This first out of the structure is to provide Peek (), offer () and poll () these methods to access the data to achieve the limit. For example, waiting for the bus, the bank or the supermarket waiting queue, etc., are able to use the queue to say.

Here is an example of using multiple threads to access blocked queues.

**linked list**Is a data structure consisting of a number of nodes, and each node contains a data and a reference to the next node, in the two-way list, there will be a reference to the previous node. For example, you can use one-way and two-way linked list to achieve the stack and queue, because both ends of the list can be inserted and deleted. Of course, there will be frequent in the middle of the list to insert and delete nodes in the middle of the scene. Apache class library provides a TreeList implementation, it is a good alternative to the list, because it only takes a little bit of memory, but the performance is much better than the list. That is to say, from this point of view the list is not a good choice.

ArrayList is a good implementation of the list. Compared to TreeList, ArrayList in addition to the list in the middle of the insertion or deletion of the elements, the other operations are much faster than TreeList. TreeList implementation is in the internal use of a tree structure to ensure that all the insertion and deletion of the complexity of the action are O (n log). This implementation makes the performance of TreeList is much higher than that of ArrayList and LinkedList in the frequent insertion and deletion of elements.

**HashMap**Close to the stable access time, which is a data structure of key value mapping. This data structure is implemented by an array. It uses the hash function to locate the element, and the collision detection algorithm is used to process the value of the hash to the same location. For example, an employee's information can be stored as an employee's key as a ID, which can be used to store property values that are read from the properties file, and so on, and so on. HashMap at the time of initialization, given a suitable size can reduce the number of adjustments.

**tree**Is a data structure of a consists of nodes and each node contains data elements, and one or more child nodes, each child node pointing to a parent node (translator's note: in addition to the root node) can be expressed in terms of the order relations of hierarchy or data element. Commonly used scenarios have an organization's employee hierarchy, XML hierarchy, and so on. If each child node of the tree has a maximum of two leaf nodes, the tree is called the two tree. Two fork tree is a very common tree structure,
Because of its structure, the insertion and deletion of nodes are very efficient. The edge of a tree represents a shortcut from one node to the other node.

Java there is no direct provision of the implementation of the tree, but it is easy to achieve through the following ways. You only need to create a Node object that contains a ArrayList that points to the leaf node.

As long as the data elements of the relationship can be expressed as nodes and edges of the network structure, it can be usedchartTo express. Tree is a special kind of graph, all of which have only one parent. Different from a tree, the shape of a graph is determined by the abstract of the actual problem or problem. For example, the nodes (or vertices) in the graph can represent different cities, while the edge of the graph can represent the route between the two cities.

Construct a graph in Java, you need to solve the problem of data through what way to save and access. The data structure mentioned above is also used in the diagram. API Java does not provide the implementation of the map. But there are a lot of the third party library provides, such as JUNG, JGraphT, and JDSL (but does not seem to support generic). "Java Career Essential Core," a book contains the use of Java to achieve the available examples.

Q: what do you know about O this symbol, you can according to the different data structures to cite some examples?

A: large O symbols can be used to represent the efficiency of an algorithm, and can also be used to describe the performance of the algorithm when the data elements are added to the worst case. Large O symbols can also be used to measure the performance, such as memory consumption. Sometimes you may choose a slower algorithm to reduce the amount of memory used. Large O symbols can be expressed in the case of a large number of data program performance. However, for measuring the performance of the program in a large amount of data, the only way to compare the actual is line with larger data sets of performance benchmarks, so you can put in the big O complexity analysis does not take into account the contained inside, for example, in the virtual memory use more system will paging. Although the benchmark test results are more practical than the big O notation, but it does not apply to the design phase, so at this time large O complexity analysis is the most appropriate choice.

Various data structures in the search, insert and delete algorithm performance can be expressed in the following way: constant complexity O (1), linear complexity O (n), logarithmic complexity O (log n), exponential complexity O c^n, polynomial complexity O n^c, square complex is O (n ^ 2) and factorial complexity is O (n!), and the N refer to is the number of elements in the data structure. Performance and memory footprint can be weighed against each other. Here are some examples.

**Example 1**:The time complexity of finding an element in a HashMap is constant, i.e., O (1). This is because the lookup element uses a hash function, and the time to compute a hash value is not affected by the number of elements in the HashMap.

**Example 2**:Linear search of an array, list and linked list is the complexity of linear, that is, O (n), which is to find the time to traverse the entire list. That is, if the length of a list is two times the original, then the search took the time is also the original two times.

**Example 3**:A need to compare the complexity of all elements of the array in the sorting algorithm is polynomial, that is, O (n^2). This is because the complexity of a nested for loop is O (n^2). In the search algorithm, there are such examples.

**Example 4**:Two points search for an array or array of the complexity of the list is logarithmic, that is O (n log). In the list to query the complexity of a node is generally O (n). Compared to the array list and array O (n log) performance, with the growth of the number of elements, the list of O (n) complexity of the performance is relatively poor. The time complexity of the logarithm is that if the 10 elements to spend the time is x units, then the 100 elements to spend up to 2x units of time, while the 10000 elements up to spend 4x units of time. If you draw a picture in a plane coordinate, you will find that there is no n (the number of elements) faster than the increase of time.

**Q**:What's the difference between HashMap and TreeMap in performance? Which one do you prefer to use?

**A**:The performance of a balanced tree is O (logn). Java TreeMap with a red black tree to ensure that the sequence of key/value. The red black tree is a balanced binary tree two. Ensure the balance of the two fork tree, making the insert, delete and search are relatively fast, the time complexity is O (n log). But it is not fast HashMap, HashMap the time complexity is O (1), but advantages of treemap is it inside the key is sorted so as to provide the some other useful functions.

**Q**:How to choose which one to use?

**A**:Using the HashSet and HashMap, or the use of ordered TreeSet and TreeMap, depending on your actual use of the scene, to a certain extent, and the size of the data and the operation of the environment. A more practical reason is that if the insertion and updating are more frequent, then the guarantee of the elements of the order can improve the performance of fast and frequent search. If for sorting operations (for example, to generate a report cooperation who run a batch processing program) requirements is not very frequent words, then the data are stored in a disorderly manner and in need of the sort with Collections.sort (... ) to sort, will be more efficient than in an orderly way to store. This is just an alternative way, no one can give you a definite answer. Even the complexity of the theory, such as O (n), the premise is also in the case of N large enough. As long as in the case of n small enough, even if it is O (n) algorithm may also be more than O (log)
N) algorithm more efficient. In addition, an algorithm may be faster on the AMD processor than on the Intel processor. If your system has an exchange area, you have to consider the performance of the disk. The only way to determine the performance of the test is to test and measure the performance and memory usage of the program with the appropriate size of the data. Testing these two metrics on the hardware you have chosen is the most appropriate way to do that.

**Q**:How to trade off the array is a disorderly array or an orderly array of it?

**A**:The greatest advantage of ordered arrays is that n is relatively large, the time spent on the search element O (n log) than the time required for the disorder group O (n) to be much less. The disadvantage of an ordered array is the insertion of the time overhead is relatively large (generally O (n)), because all of the larger values than the insertion elements to move back. The insertion time overhead of the disordered array is constant time, that is, the insertion speed is independent of the number of elements. The following code fragment shows the insertion of elements into an ordered array and an array of disordered arrays.

**Insert an element into a disordered array**

So, how to choose or depends on the actual use of the situation. You need to consider the following questions. Your program is to insert / delete operations, or to find more operations? What is the maximum number of elements that can be stored in an array? Sort of frequency is how much? And what are the results of your performance benchmarks?

Q:How to implement an immutable collection?

A:This function is realized in the Collections class, which implements the encapsulation of the general assembly through the decorative pattern.

**Q:**How to implement an immutable collection?

**A**:This function is realized in the Collections class, which implements the encapsulation of the general assembly through the decorative pattern.

**Q**:What is the function of the following code? Can LinkedHashSet be replaced by HashSet?

A:The code above is passed to a LinkedHashSet to remove duplicate elements from the original list. In this case, LinkedHashSet can keep the elements in the original order. If this sequence is not needed, then the above LinkedHashSet can be replaced with HashSet.

**Q**:What are the best practices in the Java collection framework?

**A**:Select the appropriate data structure according to the actual usage, such as fixed size still need to increase the size, duplication of elements or not and need to maintain an orderly or not, ergodicity is positive or two-way insertion is in the end or in any position, more insertion or more reading, whether to need to parallel access, whether to allow the change, the element type is the same or different, and so on. In addition, as early as possible to consider the number of threads, atomic, memory usage and performance and other factors.

Don't assume that the number of elements in your collection has always remained small, it is also possible to grow over time. So, your collection is better able to give a suitable size.

For the interface programming is better than the implementation of programming. For example, in some cases, LinkedList is the best choice, but ArrayList may become more suitable for performance reasons.

Bad way:

Good way:

In the list, if the result is empty, it is best to return a length of 0 of the collection or array, and do not return null. Because, to return to the words of null may cause the program error. Developers calling your method may forget to handle the return null.

Packaged collection: in general, the collection is not a variable object. So try not to set the member variable exposure to the caller. Because their operations generally do not carry out the necessary checks.

Note: these Java interview questions and answers are extracted from my book "Java Career Essentials Core".

English text:Java-successCompile:ImportNew-Zhu Weijie

Address translation:Http://www.importnew.com/871.html

- top
- Zero

- step on
- Zero

- Guess you're looking for