C++プログラミング、データ構造、アルゴリズム類面接試験問題集.(2)
http://www.mianwww.com/html/2013/03/17814.html
71. index, abcdaf a index， aZe e index
。。。
72. sudoku valid， solution
73. wildcast string matching.
74. dictionary， letters， 、 。 ： pre-processing， letters ， very efficient
， collection， 。
， collection 。
75.
76. string, substring, distance=\sum_i|s1[i]-s2[i]|， substring?
。。。 ？
77 N*N 0/1 ， 0
， O(N^3)
78. linked list
head ，
79. serialize and re-construct binary tree.
pre-order ， ， NULL
Re-construct ， ， node, child,( Node )
80. , prefix tree
CODE prefix tree
81. [Facebook] ，
（ ） ， 65
82. [Facebook] BST
，
83. [Facebook] implement char *remove_badchars(char string[], char bad_chars[]) in place。
bad_chars hash ， remove bad char, code 。。。
84. [Facebook] implement adding two unsigned numbers without using “+”
85. [Facebook] How to implement a smart_pointer
TO LEARN
86. [Facebook] implement sqrt
87. [Facebook] implement reader/writer lock
TO LEARN
88. given a word a and a word b, all are 6-letter. Also given a dictionary. Find a transformation from a to b, such that: (a) each time you can changeone letter; (b) all the changed word should appear in the dictionary
search ， crack the interview. …
89. {10,5,2,1}, input amount， sum ， ， amount = 4, {2,2}.
90. intersection, union
TO LEARN
91. Given an int n, print all the numbers which are less than n and in the following pattern: 1,4,5,9,14… Write a recursive program.
…
92. How to sort a large collection of string?
string ， radix sort. 138 ， America flag sort
93. How to serialize a very sparse tree?
parent->child
94. Given an arbitrarily long string, design an algorithm to find the longest repetitive substring. For example, the longest repetitive substring of “abcabcabc” is “abcabc”.
TO LEARN. Suffix tree
95. reverse a link list within each k blocks
96. BST，
CODE
97. ， 3*3
1 2 3
4 5 6
7 8 9
char, .
, .
， 。。。
98. string， sting strings。 ， 。 string, string ， sting string
，
99. log ， session。session ： userid， log
， map<userid, list<time>> ， ？
100. m*n， O(lgn)
101. n vector<int> getGrayCode(n) getGrayCode(2)， {0,1,3,2}
。。。
102. sorted array A，B， A，B ， x
scan,
103. N ， 0. K ，
: f(x,y,1) = a[x] + … + a[y]
： f(1, n, k) = min(1<=i<=n+1-k)max{f(1,i,1),f(i+1,n,k-1)}
: N , k ， k ， 。
: f(x,y,2) = a[y] – a[x]
: f（1,n,k） = max(2<=i<=n+2-k)min(f(1,i,2), f(i,n,k-1))
104. 。 。
， ， 2pi, 0
105. set target number.
， map<sum, vector<pair<index1,index2>>>
map target number pair( index )， O(N^2).
， target number(T) DP， O(NT)
106. how to implement priority queue (describe) ?
/ ， heapify
107.
108. （A，B） ， ：
1） ,a1,a2,…a2n
2）A ， ,a1 or a2n
3) Ｂ ， ， ， ，
４） 。
， ， 。
DP ：
v[x,y] x y ， ，n[x,y] (x y)
: v[x,x] = a[x], n[x,x] = x
: v[x,y] = max(v[x] + (v[x+2,y] v[x+1,y-1], n[x-1,y] )，
v[y] +（v[x,y-2] v[x+1,y-1]， n[x,y-1] ）)
n[x,y] v[x] v[y] 。
109.
Suffix tree ， TO LEARN
110. graph， circle path
DP ， NP
：
algorithm dag-longest-path is
input:
Directed acyclic graph G
output:
Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G,(v,w)) then
length_to[w] = length_to[v] + weight(G, (v,w))
return max(length_to[v] for v in V(G))
111.
：
K ， ，
buffer, buffer K-way merge 。（ ， ）
：
a) /
b) sort
c) IO sort /
d) （map reduce ?）
e) key ， radix sort
112.
http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_from_normal_distribution
， , 2N (0,1) ， N，
113. linkedIn connection 。（ 100 ， 6 ， space 100^6， 。 bfs, space 2*100^3）
。。。
114. Sorted Array， K smallest element, array1 M，array2 N， O（logM+logN)
68
115. [Facebook] Given a string and a dictionary that maps a character to several
characters, print all combination and tell the complexity.
i.e., string = “face”, f=> f, @, 4, h a=> a, c, e
print: face, @ace, 4ace, …..
116. Merge sort linked list.
。。。
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
Merge sort linked list ： ， O(NlogN), stable
117. example:
char *words[] = {“foo”, “bar”, “baz”, NULL};
setup(words);
1) First step:
isMember(“foo”) -> true
isMember(“garply”) -> false
2) Second step:
isMember(“f.o”) -> true
isMember(“..”) -> false
*/
1. map 。。。
2. words elements 。 ， words 。
118. Given an integer, print the next smallest and next largest number that has the same number of 1 bits in their binary representation.
xxx011100 -> xxx100011
， 1 0 1，xxx011100 -> xxx111100
1 1 0, xxx111100 -> xxx101100
1 ，xxx101100 -> 100011
CODE
119. n ， ， 1， 0.
：a[i]+a[j]>a[k]; a[i]+a[k]>a[j]; a[j]+a[k]>a[i]
，
120 string/file, character, character set
char set, unicode. (map reduce, multi-thread)
TO LEARN， map reduce
121. [Apple] You are given a deck containing n cards. While holding the deck:
1. Take the top card off the deck and set it on the table
2. Take the next card off the top and put it on the bottom of the deck in your hand.
3. Continue steps 1 and 2 until all cards are on the table. This is around.
4. Pick up the deck from the table and repeat steps 1-3 until the deck is in the original order.
Write a program to determine how many rounds it will take to put a deck backinto the original order. This will involve creating a data structure to represent the order of the cards. This program should be written in Python. It should take a number of cards
in the deck as a command line argument and write the result to stdout.
。。。
122. Suppose there is a binary tree having millions of nodes and by mistake one node has two indegree (i.e. There becomes a cycle/loop in that tree. Tou have to find that node which is having two indegree) Constraint is no extra memory can be used and tree representation is in Linked list format.
？？？ ？ memory, DFS/BFS
123. Print the nodes on the exterior of a binary tree in a anti-clockwise order, i.e., nodes on left edge, then leaf nodes, then nodes on right edge.
， left edge, right edge. leaf node（ leaf node ）， CODE ：
http://www.leetcode.com/2010/10/print-edge-nodes-boundary-of-binary.html
124. m ， k 1， 0≤x≤m x
x^(m-x) = m， ^ 。 0≤m<2^n m ， x ， 。
TO LEARN，
125. You can win three kinds of basketball points, 1 point, 2 points, and 3 points. Given a total score X, print out all the combination to compose X. (recursion/ Dp)
。。。
126. n job， 3 ， 。 ：3，5，4 1 job， 5. 15，7，8，10， 4, 15 1 ，7，8 2 ，10，4 3 ， 15.
http://en.wikipedia.org/wiki/Partition_problem
133
127. ， integer n k(k>=2)
x ， n ， ：
x=m+(m+1)+(m+2)+……….+(m+n-1)
m ， m 1 。 ：
x=(2m+n-1)*n/2， m=（2*x/n-n+1)/2
m （2*x/n-n+1)/2>=1 x n 。 n x n m， （2*x/n-n+1) 。
128. how to serialize and deserialize a n ary tree?
79
129.
G(n) = max{G(n-1)+1, g(n-k)*(k-2)}
130. Given a sorted array with duplicates and a number, find the range in the form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3 10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
Binary Search ， 142
131. N ，M bucket， bucket N ， bucket value 。 ， minimize(the max value of all buckets)
NP ， ：
http://en.wikipedia.org/wiki/Job_shop_scheduling
132. Given pairs of connected items ((A, B), (B, C), (C, D)…), find the root
node of this tree.
node
133. There’s a book and each sentence consists of several words. How to find the minimal set of words which can used by the reader to understand half of total number of the sentences. Each sentence is readable if the reader knows all the words.
TO LEARN， dancing links
134. [facebook] ip address(es)
aggregate ， ， ， 。。。
135. ， ， conflicts。
conflicts, O(N^2)， 。。。
136. what’s the best data structure for storing and looking up a huge amount of url’s (presented in a prefix format) like these:
com.google.www -> value1
com.yahoo.finance -> value2
com.yahoo.finance/stocks -> value3
com.yahoo/finance -> value2
1.2.3.4/node/123 -> value4
….
the requirements are:
1. it has to be compact (compression if necessary).
2. lookup time should be fast (constant would be ideal, but a few level of tree lookup is fine too).
， prefix tree?
137. Subset sum problem
138. Dutch National Flag Problem (DNFP)
http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-fl
， America Flag Problem, radix sort
139. ， ， ，
， TO LEARN
140. You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.
DP ， g(n,l,r) ， f(n,l) n block, l block, ：
g(n,l,r) = (1<=k<=n)sum(C(n-1,k-1)*f(k-1,l-1)*f(n-k,r-1))
f(n,l) = (1<=k<=n)sum(C(n-1,k-1)*f(K-1,l-1)*(n-k)!)
f(n,1) = (n-1)!
F(n,n) = 1
F(n,m) = 0 if n < m