Programming Interview Questions

I. Data Structure Interview Questions


1. Linked List

No. 10 - K-th Node from End
Get the Kth node from end of a linked list. It counts from 1 here, so the 1st 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.

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

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).
 
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.
 
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.
 
Given an array of numbers and a sliding window size, how to get the maximal numbers in all sliding windows?
 
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.

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.


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.

Please implement a function which gets the minimal number of coins, whose value is v1, v2, …, vn, to make change for an amount of money with value t. Any coin with value vi 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.

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, …

10 comments:

  1. It's contains very useful data which i need and i want to see more quality posts in this blog so please update your blog. Thanks for sharing how to create a sql database

    ReplyDelete
  2. Chemistry could be a fascinating subject that enlightens one concerning however the day to day things one uses ar just about created up as a result of numerous chemical reactions or interactions of parts with each other. it's but quite robust to find out and master this vital subject while not skilled facilitate. visit the site

    ReplyDelete
  3. Today is very must to Know how to create database in MySQL is very important as many companies, websites and other applications use this software. this website

    ReplyDelete
  4. When you've made the decision to learn an object oriented programming language such as Java, then you may be left handed and want to start promptly. In this column I am going to reveal to you just how you can create your very first simple program and run it on your own PC. java student project is a good option to know the way about the best java assignemt.

    ReplyDelete
  5. The very first paragraph of your MBA announcement of goal will show that the college why You're interested in that program. Including sharing everything you Wish to learn through this app And exactly why you feel you ought to attend this particular school. click to explore that will help you more to know about the academic papers writing.

    ReplyDelete
  6. The initial section of the MBA statement associated with objective may display how the university the reason why You have in mind which plan. Such as discussing every thing you intend to discover via this particular application As well as precisely why you are feeling you need to go to organic chem help this specific college. click on in order to discover that will help much more to understand concerning the educational documents composing.

    ReplyDelete