1. Iterating through a k-dimensional array given size of each dimension in an array.
2. Binary Tree Upside down (Leetcode 156)
3. Count the number of occurrences of an element in a sorted array (Binary Search)
4. Determine if a string is a number (handle signed / unsigned, floating point, any number of digits) (Leetcode 65 without considering exp)
5. Isomorphic strings (Leetcode 205)
6. Two-sums (Leetcode 1, 167, 170)
7. Parenthesis matching (Leetcode 20)
8. Search a sorted array for the first element larger than k. (Binary search)
9. Create a stack with the usual push(), pop(), but with an additional function getMiddle() that returns the middle element of the stack in constant time. (Vector-implementation) (See also Leetcode 155)
10. Implement pow(a,b) (Leetcode 50)
11. Shortest word distance (Leetcode 243, 244, 245)
12. Given a nested list of integers, returns the sum of all integers in the list weighted by their depth For example, given the list {{1,1},2,{1,1}} the function should return 10 (four 1's at depth 2, one 2 at depth 1), Given the list {1,{4,{6}}} the function should return 27 (one 1 at depth 1, one 4 at depth 2, and one 6 at depth 3). (See myblog)
13. Three segments of lengths A, B, C form a triangle iff A + B > C, B + C > A, A + C > B e.g. * 6, 4, 5 can form a triangle * 10, 2, 7 can't. Given a list of segments lengths algorithm should find at least one triplet of segments that form a triangle (if any). Method should return an array of either: * – 3 elements: segments that form a triangle (i.e. satisfy the condition above) * – empty array if there are no such segments (sort)
14. How to apply the function of finding a string in the text of vim editor? (KMP)
15. Maximum product subset (Leetcode 152)
16. Given an array of numbers , replace each number with the product of all the numbers divided by the number at that index without using the division operator (Leetcode 238)
17. Print a binary tree level by level (Leetcode 102, 107)
18. Print factors for number (Leetcode 254)
19. Given an input string and a target string, find the minimum substring of the input string that contains all of the characters in the target string (Leetcode 76 *)
20. Two sorted array merge into one sorted array. (Leetcode 88)
21. Implement sqrt() (Leetcode 69)
22. Maximum subarray (Leetcode 53) (Try both linear and nlogn solutions)
23. Text justification (Leetcode 68 *)
24. Colon a tree for mirror (Leetcode 226)
25. Merge Intervals (Leetcode 56)
26. Lowest common ancestor in tree (with or without parent pointers) (Leetcode 235,236)
27. Permutation of a string (Leetcode 46,47,31,60*)
28. Find whether a given binary tree is image of the other one (Leetcode 100,101)
29. Binary tree serialization (Leetcode 297*)
30. Write a log function (math, use the sqrt function)
31. Reverse double linked list (Leetcode 206)
32. Implement parseInt() (Leetcode 8)
33. You have bunch of numbers coming in, and a given a window size, how would you save numbers so that you can return number if present in window and provide average for current window. (Queue + Hash table + running sum)
34. Reverse words in a string (Leetcode 151, 186)
35. Implement decimal to roman and vice versa. (Leetcode 12,13)
36. Multi-threading problem – Consumer/Producer Problem (Check C++11 mutex, unique_lock, lock_guard, condition_variable)
https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem
37. Find the closest K points given a set of N points. (KD-tree optimally, heap for interview)
Public interface PointsOnAPlane {
/** * Stores a given point in an internal data structure */
void addPoint(Point point);
/** * For given 'center' point returns a subset of 'm' stored points that are * closer to the center than others. * * E.g. Stored: (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) * * findNearest(new Point(0, 0), 3) -> (0, 1), (0, 2), (0, 3) */
vector findNearest(Point center, int m);
}
38. Word Ladder (Leetcode 126,127)
39. Given a sorted array with duplicates and a query number, find the range of the number. (Binary search)
40. Celebrity (influencer) (Leetcode 277)
41. Parse the IP in a file (grep – regular expression)
grep -E -w -o "((25[0-5]|2[0-4][0-9]|[1]?[0-9][0-9]?)\.){3}(25[0-5]|2[0-4][0-9]|[1]?[0-9][0-9]?)" test.txt
42. Check if it is a BST. (Leetcode 98)
43. Multi-thread non-blocking thread-safe queue (See Question 36)
44. Climbing Stairs (Leetcode 70)
45. Use two stacks to implement a queue (Leetcode 232)
46. Implement Circular Queues
47. Minimal spanning tree (Prim and Kruskal's algorithms)
48. Evaluate Reverse Polish Notation (Leetcode 150)
49. Program an iterator for a Linked List which may include nodes which are nested within other nodes. i.e. (1)->(2)->(3(4))->((5)(6)). Iterator returns 1->2->3->4->5->6 (deque)
50. Searching a matrix sorted row-wisely and column-wisely. (Leetcode 240, 74)
51. Find the intersection numbers between two sorted arrays. (Merge sort)
52. Given an interface called IntStream with methods 'bool hasNext()' and 'int next()', implement the function 'IntStream merge(IntStream[] streams)' where each input IntStream produces strictly increasing, possibly infinite number of, integers, and the resultant IntStream also produces strictly increasing integers by merging the input streams. The interviewer also provides a simple test harness that prints the first 5000 integers from that function. (Heap)
53. Write a routine to find all collinear points in a plane. Constraint: The time complexity cannot be greater than O (n^2). (use ratio to record slope)
54. Find the second largest element in a binary search tree.(Stack)
55. Implement a routine which returns the set of integers in {1…100} divisible without remainder by 3 but not by 9.
56. Given a grid of size m by n, write an algorithm that computes all paths from 0,0 to m,n such that you can always step horizontally or vertically but cannot reverse. (Leetcode 62,63)
57. Write an algorithm that determines whether or not two binary trees are equivalent. (Leetcode 100)
58. Find k-th largest element in an unsorted array (selection algorithm)
59. Find out k most frequent numbers from incoming stream of numbers one the fly.
60. Given a large document and a short pattern consisting of a few words (eg. W1 W2 W3), find the shortest string that has all the words in any order (for eg. W2 foo bar dog W1 cat W3 — is a valid pattern). (Sliding window, similar to Leetcode 76)
61. Repeated DNA sequences (Leetcode 187)
62. Segment a long string into a set of valid words using a dictionary. Return false if the string cannot be segmented. What is the complexity of your solution? O(n^2) (Leetcode 139, 140)
63. Give an array that has only the values 1, 2 or 3, sort the array in place. (Leetcode 75)
64. Implement a O(1) min function for Stack (Leetcode 155)
65. Find the 100 most frequently occurring words in a set of documents (Trie + minHeap)
66. Given two sorted lists, find the union and intersection of them. Both results should be sorted. (Merge sort)
67. Shuffle an array such that every result is equally like.
68. Suppose you have a long flowerbed in which some of the plots are planted and some are not. Given the fact that flowers cannot be planted in adjacent plots, return how many new flowers can be planted without violating the no-adjacent-flowers rule.
Input: 1, 0, 0, 0, 0, 0, 1, 0, 0
Output: 3
Input: 1, 0, 0, 1, 0, 0, 1, 0, 0
Output: 1
69. Given a list of child->parent relationships, build a binary tree out of it. All of the element IDs inside the tree are unique.
Example:
Given the following relationships:
Child Parent isLeft
15 20 true
19 80 true
17 20 false
16 80 false
80 50 false
50 null false
20 50 true

You should return the following tree structure
50
20 80
15 17 19 16

struct Relation {
int child; int parent; bool isLeft;
};
struct TreeNode {
int val; TreeNode* left; TreeNode* right;
};
TreeNode* build_tree(vector& arr);
(hash table)
70. Write a function to compute the maximum length palindromic subsequence of an array. A sub-sequence of an array is a sequence which can be constructed by removing elements of the array. (Dynamic Programming)
Ex. Given [4, 1, 2, 3, 4, 5, 6, 7, 4, 3, 4, 4, 4, 4, 4, 4, 4] should return 10 (all 4's)
71. There is a particular sequence that only uses numbers 1, 2, 3, 4 and no two adjacent numbers are the same. Write a program that given n1 1s, n2 2s, n3 3s, n4 4s will output the number of such sequences using all these numbers. (Dynamic Programming O(n^4))
72. In the 100 game, two players take turns adding, to a running total, any integer from 1 … 10. The player who first causes the running total to reach or exceed 100 wins. What if we change the game so that players cannot re-use integers? For example, if two players might take turns drawing from a common pool of numbers of 1…15 without replacement until they reach a total >= 100. This problem is to write a program that determines which player would win with ideal play.
Bool canWin(int maxChooseInteger, int desiredTotal); (backtrace+ memorization)
73. Write a program that gives count of common characters presented in an array of strings. For example: given the following three strings:
aghkafgkit
dfghako
qwemnaarkf
The output should be 3. Because the characters a, f and k are present in all 3 strings.
(Bit manipulation)
74. Implement the integral part logn base 2 with bit manipulations. (find the leading bit)
75. Consider this string representation for binary trees. Each node is of the form (lr), where l represents the left child and r represents the right child. If l is the character 0, then there is no left child. Similarly, if r is the character 0, then there is no right child. Otherwise, the child can be a node of the form (lr), and the representation continues recursively. For example: (00) is a tree that consists of one node. ((00)0) is a two node tree in which the root has a left child, and the right child is a leaf. ((00)(00)) is a three-node tree, with a root, a left and a right child.
Write a function that takes as input such a string, and returns -1 if the string is malformed, and the depth of the tree if the string is well-formed.
For instance:
'(00)' -> 0, '((00)0)' -> 1, '((00)(00))' -> 1, ((00)(0(00))) -> 2, ((00)(0(0(00)))) -> 3, 'x' -> -1, '0' -> -1, '()' -> -1, '(0)' -> -1, '(00)x' -> -1, '(0p)' -> -1
(Stack)
76. Provide an implementation of the following interface:
Class Powers {
Public:
long next();
void reset();
}
Next function: returns the next integer a in the arithemtic sequence of integers where a = m^n, m > 1, n > 1, and m and n are both integers. Thus, the first few outputs will be 4, 8, 9, 16, 25, 27, 32, 36 etc.
Reset function: resets the sequence to the beginning, such that the next call to next() will return 4. (Heap + don't add new power base until the last element is used)
77. Write a program to find the element in an array that is repeated more than half number of times. Return -1 if no such element is found. (Leetcode 169)