[Hỗ trợ - Phỏng vấn] Phỏng vấn tổng quát cho một lập trình viên

 

Các câu hỏi về giải thuật, cấu trúc dữ liệu, kiến thức về lập trình, cơ sở dữ liệu... trong quá trình phỏng vấn một lập trình viên. Bài viết tiếng Anh, nguồn từ www.gurusoft.net

Interview Questions for Programmers

 

So you want to know what they are going to ask? Or maybe you are looking for questions to ask?

Here are some programming questions or puzzles often asked in programming interviews. There are usually more than one answer to these questions. Some of them are open ended questions to test how you think and communicate a technical point.

Popular topics are:

1. Algorithms

2. Strings

3. Arrays

4. Other data structures are Linked List, Tree, Stack, Queue.

5. Object Oriented Programming

6. Multi Threading

7. SQL and Databases

8. Miscellaneous Programming Topics

9. Puzzles

10. Soft Questions


Algorithms

1. Can you discuss the characteristics of different sort algorithms such as bubble sort, heap sort, merge sort, quick sort, hash sort? When would you prefer one of them over the other?
   
2. What does it mean for a sort algorithm to be stable?
   
3. What kind of search algorithms are available to search sorted data?
   
4. How does a hashtable work?
   
5. Which one do you think will perform faster?
   
   • Sorting 1 million Strings using Collections API in Java, or C++ using STL?
   
   
   • A binary search over 1 million Strings in Java? Or a binary search of 1 million strings in C++? (STL)
   
   
   • A lookup of a String key in a Java HashMap, or a lookup of a string key in an STL HashMap? Does STL have a HashMap implementation in the first place? What Map implementations are available in STL? (We are not just talking Visual C++)
   
   
   • To tackle above problems (storing, sorting 1 million strings), what kind of classes (or frameworks) would you use in Java and in C++? What are their cons and pros? How does Java and it’s libraries compare with C++ with regard to these frameworks?

C Style Strings:

1. Find a substring inside a string.


2. Find a 4 byte substring inside a string. (Instead of comparing bytes or characters, can you now compare as 32 bit integers? What would you do to make your function to be portable across 16,32, 64 bit architectures?)


3. Find and replace a substring inside a string with another string.
   
   
   • Using secondary storage.
   
   
   • Not using any other storage, assuming existing char* has space to hold the final string. (Or it does not and you need to guard for that.)
   
   
   • What happens when string to find is shorter than string to replace with. What happens if it is longer.
   
   
4. Reverse the contents of the string.
   
   • Using extra storage.
   
   
   • Without using extra storage (in place).


5. Reverse the words of the string.
   
   • Using extra storage.
   
   
   • Not using extra storage.


6. How do you go about solving above problems in Java? What are the differences in handling strings in C, C++ and Java. What options are available? What are the cons and pros?

Arrays

1. How do you declare and allocate 2-D and 3-D arrays in C? What are possible options?


2. How do you declare and allocate 2-D and 3-D arrays in Java? (Or, is there such thing as 2-D, 3-D arrays in Java in the first place?) What are possible options?

Data Structures

1. What is Linked List (single, double), tree, que, stack, map, hashtable? In Java, if you want to map string keys to string values, which implementation classes are well known to fit this purpose? What would you use, if you wanted to access the keys in sorted order?


2. How do you detect that a linked list is circular?


3. How do you traverse a tree in depth first order?


4. There is the following tree: Root is 1, under it, left node is 2, right node is 3. Under 2, there is 4 and 5. Under 3, there is 6 and 7. What is the algorithm to be able to print them in the order 1,2,3,4,5,6,7 ?

Object Oriented Programming

1. What is Inheritance, Encapsulation, Polymorphism? Give examples to illustrate how they are useful. In C++ and/or Java what language syntax and constructs help implement these concepts?


2. What is a constructor? What is a destructor in C++?


3. Does Java have a destructor?


4. Why do we declare destructors to be virtual in C++?


5. What are private, protected, public modifiers for class members? In Java, what is the default? (no modifiers specified? What is the impact?)


6. What is "final" used for as in final class MyClass in Java?


7. Why does C# have a overrides keyword to override virtual functions where as Java does not have it?


8. Why is the java.lang.String final?


9. When would you override equals() method?


10. When would you override hashCode() method? What else would you do if you override hashCode()?


11. What are auto pointers? What are smart pointers? Have you seen them in action? Where are they used?


12. Is Windows API object oriented? In what way it is, what way it is not?

Multi-Threading

1. How is multi-threading beneficial? What do we gain out of it? What are the pitfalls and dangers we are faced with when we build multi-threaded systems?


2. In Java, what basic language elements are available to aid multi-threading?


3. What is synchronized, wait, notify?


4. How is notifyAll() different than notify()?


5. What is a Semaphore?


6. What is a Critical Section?


7. What is a Mutex?


8. What is InterlockedIncrement?


9. Can you please implement a Semaphore in Java?


10. There are 2 threads. You want these 2 threads to do some work and then reach a certain point but not proceed until the other thread also reaches a certain point. How do you implement this in Java? How do the 2 threads wait for each other? Once they reach that certain point, how will they know when they both can proceed?


11. There is an array of sorted elements. Assuming that the cost of inter-thread communication is insignificant compared to the cost of accessing these elements, how can we design a multi-threaded algorithm to search for a value within this sorted data set?

Another question:

In a multi-threaded system, assume that there is 1 writer that modifies the contents of an integer array. There are multiple readers who take consistent snapshots of this array for their use. If the writer definition is as below, what is the reader implementation going to be like?

Writer: declare int c = 0; global variable at the beginning (reader threads can see this variable).

c++;
write();
c++;

Assume that c++; is an atomic operation.

SQL and Databases

1. What is a Primary Key?


2. What is a Candidate Key?


3. What is a Unique Key?


4. What is Index?


5. What is Unique Index?


6. What is Cluster Index?


7. What are ACID properties?


8. What is a transaction?


9. How do you start a transaction, how do you end it?


10. What is 2 phase commit? When is it needed?


11. What is DDL, what is DML?


12. What are commonly used isolation levels? Their names? Their purpose?


13. How does READ_UNCOMMITED differ compared to READ_COMMITED? Are there differences between major databases with regard to isolation levels? Can you compare READ_COMMITTED isolation level of Oracle versus DB2 or SQL Server?


14. When would you use READ_UNCOMMITED? READ_COMMITTED? REPEATABLE_READ? SERIALIZEABLE_READ? What are the cons and pros?


15. What is a shared lock? What is an exclusive lock? When would a database acquire these locks?


16. There is an EMPLOYEES(ID, NAME, MANAGER_ID) table. MANAGER_ID points to the ID column of the same table. Given a manager name (assuming ID is unique and NAME is unique), what kind of SQL query would you write to retrieve all employees directly managed by this manager? What is the query to get employees 2 levels down? Is there a way to write a query to get employees N levels down? Is there another way of organising this table (different columns?) to hold these kinds of tree structures?


17. What is a View? How is a View useful?


18. What is a Trigger? How is a Trigger useful?


19. What is a Stored Procedure? How is a Stored Procedure useful?


20. What is a sub select query?


21. What is a correlated sub select?

Miscellaneous

1. What is a calling convention such as cdecl or stdcall? What are the differences between cdecl, stdcall and pascal calling conventions? Why do we care about them? What is the calling convention used in Windows API?



2. In cdecl calling convention, who maintains the stack when a function is called? The caller, or the called function? In what direction are the parameters passed? Left to right, or right to left?



3. In Pascal (or Delphi) can you write a printf(...) function that takes variable number of arguments as in C? Why not?



4. In C, is it Ok to have lots of return statements in a function? How does this compare to having lots of exit calls in a Pascal (Delphi) function?



5. When do we use increment like i++ versus ++i ?



6. What is a strongly typed language? Is C type safe? How about C++? What about Java libraries? What does Java 5 bring into picture to improve type safety?



7. In Java, what is a Soft Reference, Weak Reference, and Phantom Reference? When do we need them?
   How would you count the set bits of a 16 bit integer?

Puzzles

1. You want to climb a mountain. But you do not have enough food or water to carry along with you yourself. What would you do? (Ideas: You could carry food half way with multiple trips and that point would become your new base, you would start building a new base higher repeating the same process until you reach the ground. Alternatively, you could start with 100 people, they all go to 1st base, then with the help of the resources that this 100 people brought to the first base, 20 of them continue to go to 2nd base which is higher, and then maybe 4 could go higher and at last 1 could reach the top and the mountain would be conquered by the team. You get the idea.)



2. There is a paper, it is divided into squares like a checker board. To get each square separated, how many times would you need to cut this paper? (Let’s say it is 5x5 checker board). How many cuts would you need if the square index number 2x2 was already missing? What if 2x1 is missing? What if 2x2 and 2x3 is missing? Is there a mathematical formula? Can you calculate how many cuts is needed given the size of the paper (5x5 for example) and which squares are already cuts out (missing)?



3. There are 23 prisoners in a prison. The guard tells them that whenever he wants, he will take 1 of them to a room where there are 2 switches. Each switch is either on or off. The prisoner must switch one of the switches and then go back to his cell. At any time if a prisoner correctly tells the guard that all 23 of them have been to that room at least once, then they will all be freed. Any wrong answer will lead them all to death. The prisoners will have a one time meeting together to decide on their strategy before this process starts. Nobody knows the initial state (on or off) of the switches. What should be their strategy to become free?

Soft Questions

How would you describe your own code?

1. What is the end to end process that you use to write a function (or a group of them)?



2. If you add the total time you spend on coding, design and architecture, how much time did you spend writing code versus designing software?



3. Have you ever worked with a hard to work person, how did you go about that? What kind of problems did arise? How did you solve them?

 

(this article is from http://www.gurusoft.net)