Data Structure Interview Questions from Renowned Companies

1. Reverse a linked list, implementing both recursive and iterative solutions.

Single Linked List Reversal

1. Implement the following 3 functions: 　　(1) Create a doubly linked list 　　(2) Insert a node 　　(3) Delete a node

Doubly Linked List Creation, Insertion, and Deletion

2. Define your own data structure and write a program for: Pre-order traversal of a binary tree.

Yan Weimin - Data Structures Binary Tree Video

3. Implement two functions for a doubly linked list: deleting node P, and inserting a node after node P.

4. Which sorting algorithm is fastest for 12354? a. Quick sort b. Bubble sort c. Merge sort

5. Which data structure, on average, allows the fastest retrieval of a value? a. Binary tree b. Hash table c. Stack

6. Output results of the three traversal methods for a binary tree.

7. Print a linked list in ascending order, deleting each node after it is printed.

8. Choose an algorithm to sort a linked list. Why did you choose this method? Now, do it in O(n) time.

9. Use an algorithm to insert a node into a circular linked list without traversing the entire list.

10. Given two pointers, how do you find the starting point of a cycle in a singly linked list with a cycle?

11. Definitions, differences, advantages, and disadvantages of hash tables and arrays.

12. What are the differences between linked lists and arrays?

Choose any language, define the binary search tree data structure on the spot, and write two functions: initialization and deleting a node, within 20 minutes.

13. Recursive binary search algorithm [language independent]

14. Explain what a B+ tree is, and how to implement B+ tree search and insertion. (With diagrams)

15. Implement two functions for a doubly linked list: deleting node P, and inserting a node after node P.

16. Sorting Method Comparison (Intel) Sorting Method 　 　 Average Time 　 Worst Case Time 　 Auxiliary Space Insertion Sort 　 　 O(N2) 　 　 　 O(N2) 　 　 　 　 O(1) Bubble Sort 　 　 　 O(N2) 　 　 　 O(N2) 　 　 　 　 O(1) Quick Sort 　 　 　 O(Nlog2N) 　 O(N2) 　 　 　 　 O(Nlog2N) Selection Sort 　 　 O(N2) 　 　 　 O(N2) 　 　 　 　 O(1) Heap Sort 　 　 　 　 O(Nlog2N) 　 O(Nlog2N) 　 　 　 O(1) Merge Sort 　 　 　 O(Nlog2N) 　 O(Nlog2N) 　 　 　 O(n) Radix Sort 　 　 　 O(d(n+radix)) O(d(n+radix)) 　 O(radix)

17. Linked list operations, paying attention to code robustness and security. Requirements: (1) Add an element; (2) Get the head element; (3) Pop the head element (get its value and delete it).

18. Internal sorting algorithms

19. Complexity of binary search, with proof.

20. Usage of sizeof() and strlen().

21. Advantages of sequential storage structures, and the concept of hashing.

22. Tower of Hanoi algorithm, without recursion...

23. A linked list node structure:

struct Node
{
int data ;
Node *next ;
};
typedef struct Node Node ;

(1) Given the head node head of a linked list, write a function to reverse this linked list (Intel).

(2) Given two sorted linked lists, head1 and head2, merge them into a single sorted linked list.

(3) Given two sorted linked lists, head1 and head2, merge them into a single sorted linked list, this time using a recursive method. (Autodesk)

24. Implement an optimized Bubble Sort Bubble(int *pIntArray, int L), with the following requirements: elements cannot be swapped using a temporary variable, and it should be optimized for already sorted arrays.