checkcheckzz/coding-questions

Coding interview questions with solutions from top IT companies and hot startups

Table of Contents

• Statement
• Problem
  • Array
  • String
  • Linked List
  • Heap
  • Tree
  • Math
  • Bit Manipulation
  • Graph
  • Sortiing and Search
  • Dynamic Programming
  • Other

⬆ Statement:

Most questions come from IT company interview. Some solutions are NOT my original work, but I don't know who wrote them. Difficulty of questions changes greatly, and the special topics include several advanced ones.

Total Number (not including the problem in the special topics) of Problems: about 210 (120 done).

Although I try to execute every program, bugs may still exist because I didn't run enough tests, welcome to find bugs. The solution may not be optimal, welcome to give your better solution. You can send the corresponding pull request.

By default, the time complexity indicates the worst time and the space complexity doesn't include the stack space.

⬆ Problem:

⬆ Array:

• Calculate the rotation distance for a sorted rotated array
• Celebrity problem
• Detect cycle in an array
• Detect the longest cycle in an array
• Diagonal elements sum of a spiral matrix
• Find a partition in an array to minimize the sum of two parts
• Find a small rectangle with four corners one in a large rectangle
• Find elements in the first array but not in the second one
• Find independent parts in an array
• Find the id with most posts
• Find the largest sum of three integers in a row in an array
• Find the longest consecutive increasing subarray in a grid
• Find the maximal item a[i], such that a[i]=a[x]+a[y] in an array
• Find the minimal difference between two sorted arrays
• Form an ascending array by removing elements from an existed array
• Given an array a[i], build b[i] = a[0]a[1]…a[n-1]/a[i]
• Given an array and a number k, check if there exists an element arr[i] such that its duplicates lies in arr[i-k] and arr[i+k]
• Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array
• Given an integer array and a range, find all subarrays such that their sum lie in the range
• Given an integer sequence, generate all sequences such that s1 < s2 >s3 < s4 >s5 <s6 ...
• Given an unsigned integer array with size n, the sum of array equals a, calculate a number k such that the sum of array becomes b when all numbers in the array greater than k is replaced by k
• Given m number of sets, generate a new array arr (size m), where a[i] comes from set i, output all possible new arrays
• Given three arrays, select each number a, b, c from each array to minimize max(a-b,b-c,c-a)
• Given two binary arrays A and B, i.e., containing only 0s and 1s each of size N. Find indices i, j such that sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum possible value
• Length of first subarray that sums to zero in an array
• Length of shortest subarray with sum greater than s in in array
• Nearest greatest element in an array
• Print all K-complementary in an array
• Recover the queue
• Running average in a sliding window
• Stable two way partition
• Water flow path

--

⬆ String:

• Binary string matching
• Check whether two strings match by insert or delete or replace one char
• Delete repeating strings
• Find a vowel product sum of an ASCII string
• Find the first anagram of a given string in another string
• Find the replace rule
• Generate all possible interleaves of two input strings
• Generate parentheses with different types
• Given a dictionary and a word, find all words with edit distance<=1 in this dictionary
• Given a string, delete all char A，and double all char B
• Given a string, print out the chars with maximal number of consecutive counts
• Given a string s and a dictionary, find the word break way of the string with minimal number of words
• Given a string s, check whether it is k duplicates of a string t
• Given k numbers, get a target with certain arithmetic operators
• Given string of digits, insert addition operator in between to make sum to be a value
• Given two string arrays, sort the strings in first array according to the strings order in second one
• Implement regular expression
• Implement string.split()
• Isomorphic Strings
• Longest substring containing just two unique chars
• Longest substring which appears more than once
• Longest substring which begins and ends with two unique chars
• Name numbers
• One-byte or two-byte encoding
• Ordered minimum window substring
• Pair with largest common words
• Permutation array of strings
• Remove comments
• Reverse index search
• String encode and decode
• Two Words
• Valid Phone Number

--

⬆ Linked List:

• Flatten a list
• Given linked list as a-x-b-y-c-z, output it as a-b-c-z-y-x
• Insert a node into a cyclic Sorted List
• List Level Sum

--

⬆ Heap:

• Kth maximal element of array c, where c[k]=a[i]+b[j], a, b are another two arrays
• Sliding Window Maximum
• Two dimensional top k elements
• Water in a two dimensional histogram

--

⬆ Tree:

• Binary search tree Iterator
• Binary tree Iterator
• Check whether a tree exists
• Construct a tree by a list of pairs
• Construct a xml tree
• Find the largest BST subtree in a binary tree
• Find the right most node in each level of binary tree
• Flip a binary tree
• Generate all binary trees according to preorder traversal
• Heapify a binary tree
• Immediate right neighbor of given node (parent links, no root) in a binary tree
• Implement getNextNode()
• Large tree preorder traversal
• Longest distance between two nodes of a binary tree
• Maximal path sum of a n-way tree
• Morris traversal of a binary tree
• PreInPostorder travel of a binary tree with stack
• Printing all nodes at a given distance from a starting node in a binary tree
• Second largest node in BST
• SerializeDeSerialize a binary search tree
• SerializeDeSerialize a binary tree
• SerializeDeSerialize an arbitrary nodes tree
• Shortest distance between two nodes of a binary tree
• Size of the largest complete subtree in a binary tree
• Statistical binary search tree
• Switch a binary tree to make equal
• Trim a binary search tree
• Total weight of a subtree below this node in a binary tree
• Vertical sum in a binary tree

--

⬆ Math:

• Angle between the hour and minute hands
• Calculate (m^n)%(10^k)
• Change a m base number to a n base number
• Delete k digits from a number to get minimal number
• Divide a plane of points into two equal halves
• Factorial digit sum
• Find all numbers less than N, such that n = a^3 + b^3 = c^3 + d^3
• Find k from 1~n such that k=a^2 +b^2 (a, b positive integer)
• Find largest triangle in convex hull aside from brute force search
• Find the complement domino pairs
• Find the LCM and GCD of two numbers
• Find the longest 0s surrounded by 1s in a binary expression
• Form a triangle
• For some N, print all the solutions of AB = CD where A, B, C, D are all 1~N
• GetDecimal
• Get original number including digit 7
• Given a list of integers of length n in the range of 1 to n-1, find the duplicate element (only one duplicate)
• Given a positive integer N, print all combinations of non-negative integer sum to N
• Happy Number
• Highest 1 position of binary expression
• Implement the cancall() function
• Last digit of a^b
• Magic Number
• Nearest greater palindrome
• Output true with probability 1/2^N given a function outputing true with probability 0.5
• Print all numbers including digit 5 smaller than number N
• Print prime factors of a given number
• Random generator with blacklist
• Read a line from a file randomly
• Return the duplicate indexes with equal probability
• Sieve of Eratosthenes algorithm
• Smallest positive number that can not be represented

--

⬆ Bit Manipulation:

• Count the longest continuous 0 bits in an array
• Flip bits

--

⬆ Graph:

• Black white reverse board game
• Boggle puzzle
• Calculate the distance from each empty room to nearest guard
• Calculate the number of all 0s submatrix
• Catch that cow
• Check whether a graph exists
• Graph components
• How many carrots can the rabbit eat
• Largest X structure in a grid
• Number of closed rectangles in a matrix
• Spreadsheet calculation
• Total shortest path
• Travel a grid

--

⬆ Sorting and Search:

• Find the first target in a sorted array with duplicates
• Find the minimal number in a given left turned array
• Find the smallest missing number in a sorted array
• Kth element in two sorted arrays
• Search a target in an array with unknown length
• Sorting

--

⬆ Dynamic Programming:

• Climb ladder
• Harry potter in the maze
• Jump the river
• Maximal path gain of two persons on board
• Maximal production subarray
• Merge stack of stones
• Minimal subset sum
• Paint K houses
• Pizza picking problem
• Thief Problem

--

⬆ Other:

• Closest pair problem
• Copy on write string
• Cover board with tile
• Deep iterator
• Design a structure which supports insert, delete and getRandom
• Divide integers
• Equation solution
• Family relation
• Final perimeter multiple rectangles cover
• Find the latest version
• Group contact by email list
• Implement a recommendation function
• Implement iterator interface
• Implement malloc and free
• Implement memmove and memcopy
• Last n lines of a file
• Matrix iterator
• Number of online user
• Number of squares
• Number of subsequence
• Operation number with limited functional deque
• Print all lines in a file reversely
• Producing 64bit digest
• Password lock
• Present black and white graph with quadtree
• Quack class
• Query relationship
• Racer score
• Random algorithm
• Read and Write UTF8
• Readk() to implement int read(int size,char* buffer)
• Skyline
• Smart pointer
• Test a random shuffle program
• Total area multiple rectangles cover
• Turn off lights