Data Structure Interview Questions

1. Linked List

No. 10 - K-th Node from End
Get the K^th node from end of a linked list. It counts from 1 here, so the 1^st node from end is the tail of list.

No. 18 - Reverse a Linked List
Implement a function to reverse a linked list, and return the head of the reversed list.

No. 29 - Loop in List
How to check whether there is a loop in a linked list? If there is a loop in a linked list, how to get the entry node of the loop?

No. 40 - Add on Lists
Nodes in a list represent a number. Please implement a function/method to add numbers in two lists, and store the sum into a new list.

2. Binary Tree

No. 01 - Binary Search Tree and Double-linked List
Convert a binary search tree to a sorted double-linked list. We can only change the target of pointers, but cannot create any new nodes.

No. 04 - Paths with Specified Sum in Binary Tree
All nodes along children pointers from root to leaf nodes form a path in a binary tree. Given a binary tree and a number, please print out all of paths where the sum of all nodes value is same as the given number.

No. 06 - Post-order Traversal Sequences of Binary Search Trees
Determine whether an input array is a post-order traversal sequence of a binary tree or not. If it is, return true; otherwise return false. Assume all numbers in an input array are unique.

No. 31 - Binary Search Tree Verification
How to verify whether a binary tree is a binary search tree?

No. 45 - Closest Node in a Binary Search Tree
Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k.

No. 46 - Nodes with Sum in a Binary Search Tree

Given a binary search tree, please check whether there are two nodes in it whose sum equals a given value.
 

3. String

No. 07 - Reverse words in a sentence
Reverse the order of words in a sentence, but keep words themselves unchanged. Words in a sentence are divided by blanks. For instance, the reversed output should be “student. a am I” when the input is “I am a student”.

No. 13 - First Character Appearing Only Once
Implement a function to find the first character in a string which only appears once.

For example: It returns ‘b’ when the input is “abaccdeff”.

No. 19 - Left Rotation of String
Left rotation of a string is to move some leading characters to its tail. Please implement a function to rotate a string. For example, if the input string is “abcdefg” and a number 2, the rotated result is “cdefgab”.

No. 43 - Minimal Number of Palindromes on a String
A string can be partitioned into some substrings, such that each substring is a palindrome. For example, there are a few strategies to split the string “abbab” into palindrome substrings, such as: “abba”|”b”, “a”|”b”|”bab” and “a”|”bb”|”a”|”b”.

No. 55 - Translating Numbers to Strings
Given a number, please translate it to a string, following the rules: 1 is translated to 'a', 2 to 'b', …, 12 to 'l', …, 26 to 'z'. For example, the number 12258 can be translated to "abbeh", "aveh", "abyh", "lbeh" and "lyh", so there are 5 different ways to translate 12258. How to write a function/method to count the different ways to translate a number?

4. Array and Matrix

No. 22 - Turning Number in an Array
Turning number is the maximum number in an array which increases and then decreases. This kind of array is also named unimodal array. Please write a function which gets the index of the turning number in such an array.
For example, the turning number in array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 10, so its index 5 is the expected output.

 

No. 24 - Intersection of Sorted Arrays

Please implement a function which gets the intersection of two sorted arrays. Assuming numbers in each array are unique.

 

No. 34 - String Path in Matrix
How to implement a function to check whether there is a path for a string in a matrix of characters? It moves to left, right, up and down in a matrix, and a cell for a movement. The path can start from any entry in a matrix. If a cell is occupied by a character of a string on the path, it cannot be occupied by another character again.

No. 41 - Group of 1s in a Matrix
Given a matrix with 1s and 0s, please find the number of groups of 1s. A group is defined by horizontally or vertically adjacent 1s.

No. 56 - Maximal Value of Gifts
A board has n*m cells, and there is a gift with some value (value is greater than 0) in every cell. You can get gifts starting from the top-left cell, and move right or down in each step, and finally reach the cell at the bottom-right cell. What’s the maximal value of gifts you can get from the board?

5. Stack and Queue

No. 02 - Stack with Function min()

Define a stack, in which we can get its minimum number with a function min. In this stack, the time complexity of min(), push() and pop() are all O(1).
 

No. 17 - Queue Implemented with Two Stacks

Implement a queue with two stacks. Please implement two functions: appendTail to append an element into tail of a queue, and deleteHead to delete an element from head of a queue.

 

No. 21 - Push and Pop Sequences of Stacks

Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not. 

For example, if 1, 2, 3, 4, 5 is a push sequence, 4, 5, 3, 2, 1 is a corresponding pop sequence, but the sequence 4, 3, 5, 1, 2 is not.

 

No. 33 - Maximums in Sliding Windows

Given an array of numbers and a sliding window size, how to get the maximal numbers in all sliding windows?

 

No. 39 - Stacks Sharing an Array

How can you implement n (n >= 2) stacks in a single array, where no stack overflows until no space left in the entire array space?