Programming Interview Questions

I. 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?
 

II. Algorithm Interview Questions

 1. Dynamic Programming
No. 03 - Maximum Sum of All Sub-arrays
A sub-array has one number of some continuous numbers. Given an integer array with positive numbers and negative numbers, get the maximum sum of all sub-arrays. Time complexity should be O(n).

For example, in the array {1, -2, 3, 10, -4, 7, 2, -5}, its sub-array {3, 10, -4, 7, 2} has the maximum sum 18.

No. 16 - Maximal Length of Incremental Subsequences

Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

No. 25 - Edit Distance

Implement a function which gets the edit distance of two input strings. There are three types of edit operations: insertion, deletion and substitution. Edit distance is the minimal number of edit operations to modify a string from one to the other.

No. 26 - Minimal Number of Coins for Change

Please implement a function which gets the minimal number of coins, whose value is v₁, v₂, …, v_n, to make change for an amount of money with value t. Any coin with value v_i may duplicate for any times to make change.

For example, the minimal number of coins to make change for 15 out of a set of coins with value 1, 3, 9, 10 is 3. We can choose two coins with value 3 and a coin with value 9. The number of coins for other choices should be greater than 3.

No. 44 - Dynamic Programming on Stolen Values

There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

No. 49 - Longest Substring without Duplication
Given a string, please get the length of the longest substring which does not have duplicated characters. Supposing all characters in the string are in the range from ‘a’ to ‘z’.

No. 52 - Maximal Product when Cutting Rope
Given a rope with length n, how to cut the rope into m parts with length n[0], n[1], ...,n[m-1], in order to get the maximal product of n[0]*n[1]* ... *n[m-1]? We have to cut once at least. Additionally, the length of the whole length of the rope, as well as the length of each part, are in integer value.

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?

2. Search and Sort 

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. 47 - Search in a Rotation of an Array

When some elements at the beginning of an array are moved to the end, it gets a rotation of the original array. Please implement a function to search a number in a rotation of an increasingly sorted array. Assume there are no duplicated numbers in the array.

For example, array {3, 4, 5, 1, 2} is a rotation of array {1, 2, 3, 4, 5}. If the target number to be searched is 4, the index of the number 4 in the rotation 1 should be returned. If the target number to be searched is 6, -1 should be returned because the number does not exist in the rotated array.

No. 57 - Integer Identical to Index

Integers in an array are unique and increasingly sorted. Please write a function/method to find an integer from the array who equals to its index. For example, in the array {-3, -1, 1, 3, 5}, the number 3 equals its index 3.
 

3. Backtracking

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.

4. Bit Operation

No. 20 - Number of 1 in a Binary
Please implement a function to get the number of 1s in an integer. For example, the integer 9 is 1001 in binary, so it returns 2 since there are two bits of 1s.

No. 50 - Numbers Appearing Once
In an array, all numbers appear three times except one which only appears only once. Please find the unique number.

No. 51 - Next Number with Same Set of Digits
Given a number n, please out put all numbers with n bits of 1 in increasing order. For example, if the input is 3, the output are numbers 7, 11, 13, …