questions.tex

\documentclass[a4paper]{article}
\usepackage{CJKutf8}
\usepackage{listings}
\lstset{basicstyle=\ttfamily}
\usepackage{dejavu}
\usepackage[T1]{fontenc}
\usepackage{xparse}
\usepackage{xifthen}
\usepackage{hyperref}
\usepackage{url}
\usepackage[top=0.75in,bottom=0.75in,left=0.75in,right=0.75in]{geometry}
\usepackage{tikz}

\NewDocumentEnvironment{Q}{o m}{
	\item
		\IfNoValueTF{#1}
			{\relax}
			{\textnormal{[}\textbf{#1}\textnormal{]}}
}{

	\ifthenelse{\isempty{#2}}
		{\relax}
		{\href{#2}{Link}\\}

}

\newcommand{\ilcode}[1]{
	\framebox[\width]{\texttt{#1}}
}

\title{Questions}
\author{
	Bin \textless lanb @ MITBBS \textgreater \\
	\url{https://github.com/lanxx019/mitbbs-iq/releases}
}
\date{11/27/2012}

\begin{document}
\maketitle
\begin{CJK}{UTF8}{gbsn}
\begin{enumerate}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t1/JobHunting/32267699_0_1.html}
一个String当中，求出现多于一次的最长的substring。\\
eg: "abcabcaacb" -> "abc"\\
eg: "aababa" -> "aba"
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t1/JobHunting/32267699_0_1.html}
string edit distance的递归解法。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32259233.html}
给两个ascend排序的integer array，找出他们的union，并且descend排序。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32268159.html}
为移动应用设计一自动推荐地点的系统 displays a list of locations recommended by to each client. 你可以考虑是同一类的地点，比如旅游或餐馆，也可以in general的locations. 
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32266793.html}
	2个BST，按大小顺序打印两棵树的所有节点。
\end{Q}

\begin{Q}[Cloudera]{http://www.mitbbs.com/article_t/JobHunting/32058461.html}
Write a program that takes an integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors.  In other words, if your output contains $4 * 3$, you should not print out $3 * 4$ again as that would be a repeating set.  Note that this is not asking for prime factorization only. Also, you can assume that the input integers are reasonable in size; correctness is more important than efficiency.
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32267935.html}
给定\ilcode{bool isWord(string s)} create function to print all words based on a string.\\
For example, input: ``thisisdesktop''\\
output is: ``this is desk top'', ``this is desktop''
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32268547.html}
给一个$N$个node的BST，给一个$key$，返回与$key$最接近的$m$个node$(m<N)$.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32268547.html}
用一个数组来表示二维数组，但是每一行的元素个数可以不同，实现get，set函数。
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32263975.html}
Give a list of events in the following structure. Set the conflict flag to true if the event conflicts with any other event in the list.
\begin{lstlisting}
class Event
{
    int start;
    int end;
    bool conflict;
}
\end{lstlisting}
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32263975.html}
给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序的。输出这个国家的语言的字母顺序。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t1/JobHunting/32262719_0_1.html}
两个不知长度的 int 数组，实现相加。
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32266691.html}
给一字典,求其中某单词的最短缩写。比如internationalization可以缩写为i18n而不产生歧义。\\
举例：一字典有6个单词：\\
hello\\
world\\
would\\
lord\\
hell\\
language\\
依次可以缩写为\\
hello -> 4o or h4\\
world -> 2r2\\
would -> 2u2\\
lord -> l3 or 3d\\
hell -> 3l or h3\\
language -> 8
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32026399.html}
编程题： 有一个\ilcode{observer}类，监视另一个类\ilcode{foo}的成员变量的值，每当那个值被修改，就要调用该\ilcode{observer.updated()}方法。需要实现\ilcode{foo.register(ob)}，\ilcode{foo.unregister(ob)}，\ilcode{foo.changeValue(newvalue)}。要考虑thread safe。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32026403.html}
Boggle game。从一个字符开始找邻居字符然后继续找，形成一个word。条件是，形成了word之后要继续找，因为可能有更长的word。一旦用了一个字符以后，就不可以重复使用了。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32026413.html}
Binary Tree的Serialization和Deserialization, 随便用什么方法实现。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32026413.html}
Large file, multiple lines, how to get any line in equal probablity, 文件
太大内存无法装入。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32026413.html}
用pre-order in-order sequence重构binary tree.
\end{Q}

\begin{Q}[Bloomberg]{http://www.mitbbs.com/article_t/JobHunting/32062921.html}
一个矩阵行列都是递增序， 查找一个数
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/31376671.html}
一个大楼,10层,4个电梯,怎么设计类来实现这样一个系统?
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32061173.html}
Suppose you are given a dictionary of words based on an alphabet with a fixed number of characters. Please write a method/function which will find the longest word in the dictionary such that it can be built from successively adding a single character to an existing word in the dictionary (in any location). For instance, ``a'' -> ``at'' -> ``cat'' -> ``chat'' -> ``chart''.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32061183.html}
Given an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are:\\
1) Decrement with cost = 1\\
2) Delete an element completely from the array with cost = value of element
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32064107.html}
两根不均匀的绳子，每根单独燃烧，可以燃烧一个小时。请问如何: 根据这个性质，给出45分钟的时间段？
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32067899.html}
求树的最大宽度。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32070393.html}
一个很大的文件 怎么去掉duplicate
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32068265.html}
Clone a graph
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32068175.html}
Given $P$ machines, each containing an array of $N$ elements, find the medium of the array resulted by concatenating all the arrays on the machines. You cannot move data across machines.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32071251.html}
给一个二叉树，如何把它转成他的mirro image。
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32070295.html}
找二叉树两个最大的相同子树。
\end{Q}

\begin{Q}[Bloomberg]{http://www.mitbbs.com/article_t/JobHunting/32075437.html}
Find minimum number of characters that need to be inserted into a string (anywhere in the string) to make it a palindrome.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32078587.html}
iterator has only \ilcode{bool hasNext()} and \ilcode{T next()} method, write a wrapper for iterator, to support \ilcode{peek()}.
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32074175.html}
Given a sequence of data (it may have duplicates), a fixed-sized moving window, move the window at each iteration from the start of the data sequence, such that \\
(1) the oldest data element is removed from the window and a new data element is pushed into the window\\
(2) find the median of the data inside the window at each moving.
\end{Q}

\begin{Q}[Amazon, Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32080539.html}
就是将数组里的负数排在数组的前面，正数排在数组的后面。但不改变原先负数和正数的排列顺序。\\
例：input: -5，2，-3, 4，-8，-9, 1, 3，-10\\
output: -5, -3, -8, -9, -10, 2, 4, 1, 3
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32082935.html}
3个已经排序的整数数列，找到common elements
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32079701.html}
Given an input string and an order string, e.g., ``house'' and ``soup'', print out characters in input string according to character order in order string. For characters in input string but not in order string, output them in the end, their relative order doesn't matter.

So for ``house'', ``souhe'' and ``soueh'' are valid outputs.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32078073.html}
You are given a String number containing the digits of a phone number (the number of digits, n, can be any positive integer) . To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups:

• Excellent: A group that contains only the same digits. For example, 000 or 77.

• Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.

• Usual: A group in which all the digits are distinct. For example, 123 or 90.

The quality of a group assignment is defined as 2 × (number of excellent groups) + (number of good groups), Divide the number into groups such that the quality is maximized. Design an efficient algorithm to return the solution that maximizes the quality.
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32088539.html}
Write a function that takes an array of five integers, each of which is between 1 and 10, and returns the number of combination of those integers that sum to 15. 

For example, calling the function with the array [1, 2, 3, 4, 5] should return 1, while calling it with [5, 5, 10, 2, 3] should return 4 (5 + 10, 5 + 10, 5 + 5 + 2 + 3, 10 + 2 + 3).
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32089027.html}
Given a set of n integers, each in the range $0 \ldots K$, partition the integers into two subsets to minimize $|S1 - S2|$, where $S1$ and $S2$ denote the sums of the elements in each of the two subsets.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32063239.html}
Giving lots of intervals $[a_i, b_i]$, find a point intersect with the most number of intervals
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t1/JobHunting/32096259_0_1.html}
一个大数组，在1到25000之间，只有4K memory, 打印出其中正好只出现过一次的数。没出现过，出现过2次，3次，或更多，都不打印。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32104785.html}
Given a dictionary and a string, write a program to output the valid words while minimizing the numbers of skipped characters. The substring that consists of a valid word in the dictionary may swap the characters. For example, Given a dictionary d = {window, cat} and a string ``iwndowdcta'', the output is ``window cat''. In this case, there is only one number of skipped character which is 'd'. 
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32081285.html}
How to find if a number is present equal to or more than $n / 2$ times in an array of size $n$? 
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32110581.html}
given an array of n unsorted integers and each number is at most k positions away from its final sorted position, give an efficient sorting algorithm.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32112869.html}
假设你是一个剧院的IT Manager，有一天你的老板跑来问你，最近有很多乐队要来演出，你能告诉我如何安排么？最多满足多少个乐队的要求？只有一个舞台。每个乐队演出的价格一样，需要最优解。
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32113351.html}
在一个大串中查找和另外一个字符串是anagram的子串:
\begin{lstlisting}
GetAnagram(``abcdbcsdaqdbahs'', ``scdcb'') ==> ``cdbcs''
\end{lstlisting}
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t1/JobHunting/32113349_0_1.html}
处理一个字符串，删除里面所有的A，double所有的B

例子，输入 CAABD, 输出是CBBD
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32076263.html}
how to design a queue, in addition to \ilcode{insert()}, \ilcode{delete()}, also has a function \ilcode{min()} which returns the minumum element? Can you do all functions in $O(1)$ time?
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32118339.html}
Write the code to count number of 1's in binary expression of a given integer.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32118339.html}
Design file system. How about adding symbolic link.
\end{Q}

\begin{Q}[Bloomberg]{http://www.mitbbs.com/article_t/JobHunting/32118339.html}
8个球有一个球比其他的重。用天平最少称几次能找出来。
\end{Q}

\begin{Q}[Bloomberg]{http://www.mitbbs.com/article_t/JobHunting/32118339.html}
1-100共100个数missing 1个，如何找出来；missing 2个呢？
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32123673.html}
怎么实现\ilcode{boolean isBST(Node *root)}? 
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32123951.html}
Stream of characters, at any point you should be able to answer what is the most recent character that happened only once
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32119891.html}
Three coke machines. Each one has two values $min$ and $max$, which means if you get coke from this machine it will load you a random volume in the range $[min, max]$. Given a cup size $n$ and minimum soda volume $m$, show if it's possible to make it from these machines.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32122887.html}
Given a string of sorted integers, e.g. ``1 52 69 456789 994546566'' and a  a number e.g. 69. You need to tell if it is in the input, e.g. 69=>true.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32137389.html}
for an integer, find out all the prime factors whose product is the integer itself, eg: $12 = 2*2*3$. Print out those factors in a list.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32069949.html}
Check if a binary tree is symmetric
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32152557.html}
一个数组$a_1,a_2,a_3\ldots a_n,b_1,b_2,b_3\ldots b_n$, 怎么in place地转化成$a_1,b_1,a_2,b_2,a_3,b_3 \ldots a_n,b_n$.
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32156015.html}
N组整数，每组都由小到大排列，如何快速找出N组都有的最大数？
\end{Q}

\begin{Q}[Linkedln]{http://www.mitbbs.com/article_t/JobHunting/32160693.html}
Find a number in a matrix which is sorted by row and column
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32162111.html}
Given preorder of a binary tree, print out all the binary trees.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32167761.html}
Given a list of points in 2D and a single reference point, find k nearest neighbors.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32112363.html}
Given an array $A$ of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are:

1) Decrement with cost = 1

2) Delete an element completely from the array with cost = value of element
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32173227.html}
$4 * 4$的矩阵，左上走到右下，可以走上下左右四个方向，不能走走过的格子，多少种unique的走法？
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t1/JobHunting/32164103_0_1.html}
有$2*N$个文件，文件的大小保存在\ilcode{size[2*N]}中。然后想要分成$N$份（每一份可以有1或者多个文件),要使这N份中的文件size之和的最大值最小，如何实现?
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32175465.html}
找到字符串A在字符串B中出现的次数，可以重复使用字母，比如 A: aba  B: ababa, 那么返回2.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32175265.html}
告诉我一个游戏，叫做“生或者死”，在一个棋盘上，规则如下：

每格有两种状态：生，或者 死

每一轮，如果有少于两个邻居是活着的，这格就死掉

如果刚好有两个邻居活着，这格保持原有状态

如果有三个邻居活着，这格可以重生，就是如果原来是死的，现在活过来了

如果有三个以上邻居，这格就被挤死了

要在白板上写每轮如何更新整个棋盘的状态
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32173223.html}
给一个无向图找出给定起始点到给定结束点的所有最短路径并打印
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32186343.html}
设计一个集合数据结构(set,只存unique的value)要求能在$O(1)$时间内insert，delete，random query(比如目前set中有n个元素，给一个介于1到n的随机数k，可以在O(1)时间内返回第k个value)
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32186573.html}
Imagine there is a square matrix with $n * n$ cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels;
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32191139.html}
给一个包含数字的数组，求该数组的最长的子数组（这里说的子数组是下标连续），要求这个子数组中的数组是一个连续的序列（不需要排好序）。

例如，给一个数组$[4,5,1,5,7,6,8,4,1]$， 最长的满足条件的子数组是$[5,7,6,8,4]$。因为该子数组中，$5,7,6,8,4$是一个连续的序列。
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32190689.html}
两个排序好的数组，求和最小的M 个pair, 比如$A={1, 2, 4, 5, 6}$, $B={3, 5, 7, 9}$, $m=3$, 那么Results就是$(1, 3),(2, 3),(1, 5)$
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32188347.html}
Describe a data structure for which 

\ilcode{getValue(int index)}

\ilcode{setValue(int index, int value)}

\ilcode{setAllValues(int value)} 

are all $O(1)$.
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32193593.html}
Given an array of 32bit unsigned integers in which every number appears exactly twice except three of them, find those three numbers in $O(n)$ time using $O(1)$ extra space. The input array is read-only. What if there are $k$ exceptions instead of 3?
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32189139.html}
the longest repeated substring problem is the problem of finding the longest substring of a string that occurs at least twice.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32189053.html}
给定两个二叉排序树，可能结构不同，问是否他们具有完全相同的值。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32189053.html}
给定n个数，每个数有一个出现得概率，这样就形成了一个分布，根据这个分布，生成k个数。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32189053.html}
有一个很长的DNA串，给定一个短的DNA串，问你短的子串是否出现在长DNA串中。延伸问题,如果只是找和短串相似的长串中子串怎么办？ 延伸问题二，加入长串太长了，内存放不下怎么办?
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32196075.html}
搜索提示是怎么做的?

比如你输入一个字母A, 马上就会提示AMAZON

问提示的内容, 排序, 和数据结构的实现
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32195851.html}
unordered array of size $N$, already know more than half of the elements are number $x$(duplicate). the rest of the array is unknown. find the number $x$ efficiently (that means $O(N)$)
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32194831.html}
给一个int数组, 求出所有和为0的子数组
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32150635.html}
Given an array, find the longest subarray which the sum of the subarray less or equal then the given MaxSum.
\end{Q}

\begin{Q}[Facebook, Amazon]{http://www.mitbbs.com/article_t/JobHunting/32198853.html}
写一个二叉树中序遍历的iterator
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32199747.html}
给定一个数字数组 ，其中每个元素是从末端数小于原数组中该元素的个数。求原数组。原数组中元素是从$1$到$n$。Example:

原数组$4,1, 3, 2$

Count array  $3, 0, 1, 0$
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32197927.html}
Find a connection between two people if there is one, or return false. Everyone has father and mother and the connection means if there are any common relatives.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32195497.html}
怎么快速从一堆超大log文件中找出所有的Customer ID。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32172205.html}
You are given N ranges of date offsets when N employees are present in an organization. Something like

1-4 (i.e. employee will come on 1st, 2nd, 3rd and 4th day )

2-6

8-9

..

1-14

You have to organize an event on minimum number of days such that each employee can attend the event at least twice. Write an algorithm (there is apparently an $O(n)$ algorithm for this).
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32101029.html}
给你一个\ilcode{char* read4096()}的API，一次返回小于或者等于4096个字符。如果返回是小于4096个字符，意味着已经读到文件末尾`\textbackslash 0'。

用\ilcode{read4096()}这个API，写一个\ilcode{char* readline()}的function。要求：

1) \ilcode{readline()} returns when reading `\textbackslash n' or `\textbackslash 0'.

2) \ilcode{readline()} may be called multiple times on a file, the return value should be correct.

3) \ilcode{readline()} may return char array longer than 4096 chars.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32203533.html}
一个大型cluster 包括thousands of nodes.  需要定期upgrade 每个server跑的 OS image (也就是重装).  如何设计一个方案加速该过程。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32203533.html}
一个sensor network有很多sensors, 一个server定期query每个sensor的值。sensor may fail。如何让server避免被block。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32203533.html}
设计题是一堆机器生成unique ID，这些机器之间不能互相通信，也没有master。
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32202393.html}
Two elements of BST are swapped by mistake. You have to restore the tree without changing its structure.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t1/JobHunting/32205611_0_1.html}
How to sort 1 million integers with 2MB of memory and with no external storage?
\end{Q}

\begin{Q}[Apple]{http://www.mitbbs.com/article_t/JobHunting/32205855.html}
There are three boxes, one contains only apples, one contains only oranges, and one contains both apples and oranges. The boxes have been incorrectly labeled such that no label identifies the actual contents of the box it labels. Opening just one box, and without looking in the box, you take out one piece of fruit. By looking at the fruit, how can you immediately label all of the boxes correctly? 
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32205129.html}
如何实现StringBuilder中的insert

\ilcode{public void insert(string str, int index)}

要求就是少用空间，问你要用什么数据结构。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32207861.html}
Write a function that computes $log2()$ using $sqrt()$.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32197465.html}
An array with n elements which is K most sorted. 就是每个element的初始位置和它最终的排序后的位置的距离不超过常数K,设计一个排序算法。should be faster than $O(n*lgn)$
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32197465.html}
一个排序好的不知道长度的数组，在其中search 一个给定值
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32197465.html}
$1..n$这些数有两个missing,find out which two are missing.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32204809.html}
find number of unique numbers in a stream input of integers. need accurate number if the result is small, need rough number if the result is large.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32205729.html}
$N * N$ integer矩阵。每一行取一个数, 且取出的每一个数必须不同列。取出$N$个数使得其sum最小. 求取法。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32210665.html}
If there is an tree structure data, design an algorithm for function \ilcode{next()} which returns one data each time and this function will access all the data only once.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32206157.html}
Given two sorted array, return the intersection part. follow-up: test cases ?
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32206157.html}
Suppose we are building a web browser that tell the user if a URL is malware. Given a URL and a URL malware list, determine if the URL exists in the malware list.

1st follow-up question: what if the malware list is so big (2GB) that can't fits in the memory of the user's computer? 

2nd follow-up: what if the  malware list is so big (2TB) that have to store on the server-side?
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32212121.html}
print all path from root to leaf nodes
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32212121.html}
calcualte int Power(int x, int y), extend to calculate double Power(double x, double y)
\end{Q}

\begin{Q}[Linkedin]{http://www.mitbbs.com/article_t/JobHunting/32219391.html}
Reverse postfix order
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32221085.html}
在一个$n*n$的字符矩阵上,问有多少个有效的字符串.一个有效的字符串可以从矩阵中任何一个字符开始,到任何一个字符结束.下一个字符是上一个字符8个相邻字符中的一个.而且字符不能重复使用.
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32224933.html}
有一堆螺栓和螺母，每一个螺栓只可能配一个螺母，螺栓与螺栓之间不能比较，螺母与螺母之间也不可以比较，只有螺栓与螺母之间可以比较，配对所有的螺栓和螺母。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32224635.html}
假设有一很长的数字，比如$11224444$，被压缩存储为pairs，如$(1, 2)$, $(2, 2)$, $(4, 4)$.然后写个Iterator，要求有constructor(to take pairs as input)，\ilcode{next()} to give out the digit and move to the next position, \ilcode{hasNext()} to indicate if there's any more digit left.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32222805.html}
手机键盘位设计，用户输入数字，随时跳出Popup的菜单查询的单词. 打一个c，就输出所有名字c开头的record，打一个ca，就输出所有名字ca开头的.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32225593.html}
3维空间有若干个点，求一平面包含最多的点。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32226949.html}
Partition a set of numbers into two such that difference between their sum is minimum, and both sets have equal number of elements.

For example: $[1, 4, 9, 16]$ is partitioned as $[1,16]$ and $[4,9]$ with diff: $17-13=4$.
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32227979.html}
从$n$个无重复正整数的数组里选$m$个数，要求这$m$个数的总和是$<=S$的最大解。

比如从$[1,3,9,15]$选 $m=2$个,$<=13$, 答案就是$[3,9]$。如果$<=10$,答案就是$[1,9]$
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32229453.html}
Write a function to find the first share node for two linked list
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32228745.html}
问给一个set，比如1122334，其中只有一个数字出现奇数次，其余均为偶数次，如何找出该数

如果有两个数出现奇数次，怎么找
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32280389.html}
从字符串里找出重复奇数次的字符。

比如  abaadefbe  -->adf (顺序不限）
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32230483.html}
Write a program to determine whether $n/2$ distintinctve pairs can be formed from given $n$ integers where $n$ is even and each pair's sum is divisible by given $k$. Numbers cannot be repeated in the pairs, that means you can only form total $n/2$ pairs.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32233741.html}
You are given the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32233741.html}
How to add a counter to www.google.com to track the billionth user.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32227891.html}
	\begin{lstlisting}
		public class person {
			public int age;
			public int weight;

			public person(int x, int y) {
				  age = x;
				    weight = y;
			}
		}
	\end{lstlisting}
写一个函数，让person能够被用作hashmap的key。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32224083.html}
Given an input string and an order string, e.g., ``house'' and ``soup'', print out characters in input string according to character order in the order string. For characters in input string but not in the order string, output them in the end, their relative order doesn't matter. For example, for input string ``house'', ``souhe'' and ``soueh'' are valid outputs.
\end{Q}

\begin{Q}[Google, Amazon]{http://www.mitbbs.com/article_t/JobHunting/32234437.html}
一道电面题，让实现随机洗牌算法，然后设计测试，判断是否每种shuffle后的组合都是等可能出现的。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32206313.html}
一个matrix上， 有$n$个人，这$n$个人要找一个地方开会，问哪个地方让大家移动的距离最近。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32229821.html}
You are going to work with “bigNums”, which are objects containing a positive integer with an unlimited number of decimal digits.

a) declare a struct to represent “bigNums”

b) write a function that takes as arguments a bigNum and a positive integer between 0 and 9, adds them and returns the answer (a bigNum)
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32229821.html}
You are given two very large files of unsigned 64 bit integers. Write to an output file all the numbers that appear in both files, but there should be no duplicates in the output file 
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32241209.html}
一数组: $[2, 3, 4, 5]$要求返回一个数组: $[60, 40, 30, 24]$， 其中每个element是其他元素的乘积。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32241025.html}
Given random generator \ilcode{rand(int n)}. Now, design a random generator such as \ilcode{rand(int n, int[] except)}

example, $n=10$, random $1-10$, $except[3]=[1,5,6]$, then \ilcode{rand(10, except)} output $[2,3,4, 7, 8, 9,10]$
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32240607.html}
在数组中，找重复元素中的最远的距离。

Example: 2 3 2 5 4 3 => 4

两个2的距离是2

两个3的距离是4

所以答案是4
\end{Q}

\begin{Q}[Twitter]{http://www.mitbbs.com/article_t/JobHunting/32238797.html}
去注释
\begin{lstlisting}
abc//xyz\nwwe*/*sdfsd/*sdfda*/sd*/cvcd  => abc\nwwe*sd*/cvcd
\end{lstlisting}
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32242053.html}
Find deepest nodes in a binary tree.

Q: binary search tree? A: no

Q: all of the deepest nodes, or just one? A: find the right-most deepest node
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32242053.html}
Suppose you have a dictionary of words. Given a abbreviation like ``i18n'', determine if it is unique in the dictionary.

Q: rephrasing the question, determine if no other words can be abbreviated as ``i18n'', correct? A: yes
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32061495.html}
两个1 terabyte的文件，只有一个byte不一样，怎么样可以最有效的找到不同byte的位置
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32239977.html}
设计

\begin{lstlisting}
class  webcounter {
	void  increment();
	int  lastmin();
	int  lasthour();
	int  lastday();
}
\end{lstlisting}
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32239977.html}
打印函数,奇数行完全打印,偶数行隔一个打印
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32245159.html}
Anagram Buckets

Anagram: abc, cba, cab

Input: [abc, def, xyz, fde, fed, cab]

Output: [[abc, cab], [def, fde, fed], [xyz]]
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32063647.html}
reverse each pair of node in singly-linked list

就是1->2->3->4->5

得到2->1->4->3->5
\end{Q}

\begin{Q}[IXL]{http://www.mitbbs.com/article_t/JobHunting/32247615.html}
如果n-1 和 n+1 都是 prime number, 证明 n 能够被6 整除。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32247449.html}
You are given $N$ ranges of date offsets when $N$ employees are present in an organization. Something like

1-4 (i.e. employee will come on 1st, 2nd, 3rd and 4th day )

2-6

8-9

..

1-14

You have to organize an event on minimum number of days such that each employee can attend the event at least twice. Write an algorithm (there is apparently an $O(n)$ algorithm for this).
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32247051.html}
implement a graph class, including several methods like \ilcode{addNode()}, \ilcode{addEdge()}, etc. Then implement to clone a graph.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32156867.html}
求一个数字数组里的最大连续数字的个数。

3, 4, 4, 4, 2, 2, 3, 4  =>  return 3
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32156867.html}
两个字符串，第二个字符串是第一个的缺了几个，打印第二个字符串缺了的字符位置。

``abc'',`` ab'' => print  ``2''

``abc'', ``b'' => print ``0 2''

``abc'', ``ac'' => print ``1''

``aab'', ``ab'' =>  print ``0''   OR   print ``1''
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32156867.html}
一个数字数组，给一个window，长度$k$，window从数组头开始往后滑动，每次滑动一个，求每次窗口中的最大值。

3, 4, 5, 7, 3, 5, 2, 9 

$k = 3$

print  ``5 7 7 7 5 9''
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32249603.html}
假设一家utility bill company， 分段收取utility，写程序实现charge。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32249233.html}
Given three integers a, b,c. Write a function: int median (int a,int b,int c) to get the median number among a,b,c. Can not use sort, the times of integer operations (e.g. compare, + - * /, bit computing) the less the better. Analyze the best and the worst situation. 
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32252131.html}
given a list of words (string), let compound word be the combination of any two words in the array, check the numbers of duplicated words (to check if there are duplicated compound words, and if the compound word is the same as some word in the original list, it is also considered as duplicated) 

[``am'', ``eat'', ``a'', ``meat''] ``am''+``eat''=``a''+``meat'' outout =1 
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32252131.html}
Design a system for members to borrow books from a library
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32252019.html}
newspaper截取letters能否拼出ransom
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32233991.html}
有一种压缩方式，把food->f2d, tea->t1a，这种，然后现在要搞一个dictionary，问如何设计，还要实现判断isUnique方法.
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32071771.html}
Longest subarray with equal number of 1 and 0
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32251141.html}
给一个string array, 除了一个string出现了奇数次外，其他所有string都出现了偶数次。返回出现奇数次的string。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32251141.html}
一个单链表，返回倒数第N个node
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32251521.html}
Given $N$ node BST, and a key $K$, find $m$ ($m<N$) nodes in tree which are close to key value？
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32251307.html}
有两个int的数组，怎么merge他们起来，而且没有duplicate的数字。
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32257199.html}
求出10 million以内，所有是palindrome的质数。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32256015.html}
lowest common ancestor in a binary tree.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32256565.html}
Given 2D coordinates , find the k points which are closest to the origin. Propose a data structure for storing the points and the method to get the k points. Also point out the complexity of the code.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32257529.html}
一个矩阵，比如$m*n$，从一个点可以访问它的八个相邻点（上、下、左、右、左上、左下、右上、右下）

如果一个方向上的点已经被访问过了，则可以继续访问这个方向上的下一个未被访问的点（比如当前点是(5,5)，如果（5,4）已经被访问，则可以访问(5,3)，如果(5,3)也被访问了，则可以访问（5,2）…… 对角线方向的也是如此,(5,5)可以访问(4,4)，如果(4,4)已经被访问，可以访问(3,3)……）

现在需要遍历这个矩阵上的所有点，则有多少种可能性？（起点和终点不限）
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32249655.html}
找linkedlist middle node
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32260335.html}
Given a array of integers , find 3 indexes $i,j,k$ such that, $i<j<k$ and $a[i] < a[j] < a[k]$. 
\end{Q}

\begin{Q}[Palantir]{http://www.mitbbs.com/article_t/JobHunting/32265303.html}
你有25匹马, 5个lane, 怎么在没有工具的情况下, 最快找出最快的3只
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32263975.html}
给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序的。输出这个国家的语言的字母顺序。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32259233.html}
写一段code，检测一串数字是否是Fabonacci系列。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32271035.html}
实现encode,decode函数encode的参数是字符串的链表, 返回字符串. decode参数是字符串返回字符串链表. 最后\ilcode{list.equals(list.decode(encode(list))}
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32271789.html}
给定一个0和1的矩阵，返回连成一片的1的block的个数，只考虑前后左右四个neighbor。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32273209.html}
假如你的朋友信息用hash表来存储，姓名是key，现在想随机挑选一人。朋友表是动态增减的。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32271053.html}
一个数组，比如$[1,2,3,7,19,8,6,11,34,23,67]$. Find local min，就是比它左右都小，比如这个里面的6比8,11小，23比34,67小，都是local min。找到任意一个local min就可以

A.K.A Local minimum
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32273501.html}
写一个int转成链表的函数 链表每个节点存一个digit，要注意表示负数的情况
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32273655.html}
一个M*M的矩阵里，随机放着很多石头，让找最大的空的矩形，并返回位置。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32274397.html}
Write a function which returns the next palindrome greater than the given number n.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32279127.html}
数组的值是下次跳的索引位置，数组有环，求最长环的长度.
\end{Q}

\begin{Q}[Twitter]{http://www.mitbbs.com/article_t/JobHunting/32277677.html}
Given a matrix with all elements sorted on each individual row and column find the K-th smallest one.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32198853.html}
给一个单向链表,随机选择一个node in one pass
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32279123.html}
Sort string a based on the order of the letters in string b.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32281037.html}
一个特殊的国家忌讳7这个数字，所有包含7的数字他们都不用，改用下一个数字，比如7他们用8代替，17用19代替，给定这个国家的数字，翻译成我们用的数字。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32281281.html}
bst 给一个数，找出在bst中离这个数最近的节点
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32281281.html}
大数据的平方$X^2$, $X$很长不能用int long 之内的表示
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32281281.html}
给一个很长的bit array，要求reverse，bit array存在byte array中，bytes数很大，
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32281281.html}
bst，分层打印各层最大的节点数值
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32282115.html}
给一个字符串，输出一个文件，里面每一行是一个出现的字符，后面跟着它出现的次数。要根据出现次数降序排列。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32282399.html}
Check if a number power of 3.
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/clubarticle_t/InterviewHackers/31150493.html}
a file with unknown number of float number, how to sort.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/clubarticle_t/InterviewHackers/31150493.html}
find first unique character of a string
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/clubarticle_t/InterviewHackers/31150493.html}
Given a function which reads data from a data resource \ilcode{int recv(char *buf, int len)}, implment a function \ilcode{readLine()}; 
\end{Q}

\begin{Q}[Facebook, Google]{http://www.mitbbs.com/clubarticle_t/InterviewHackers/31150493.html}
longest increasing subsequence for an integer list
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/clubarticle_t/Topcoders/31364843.html}
Given an array with length of $N$, there's a sliding window with length of $K$ ($K <= N$). The window will slide from the beginning to the end, find all the max numbers in the window.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/clubarticle_t/Topcoders/31342583.html}
Given an input array $A$ of integers of size $n$, and a query array $B$ of integers of size $m$, find the smallest window of input array that contains all the elements of query array and also in the same order.

例如：

$A = [1,9,3,4,12,13,9,12,21]$

$B = [9,12,21]$

那么应该返回$A[6..8] = [9,12,21]$
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/clubarticle_t/Topcoders/31342599.html}
一个int，转换成$sign * a * 2 ^ b$的格式。例如： 

$7 = +1 * 7 * 2^0$

$-14 = (-1) * 7 * 2 ^ 1$
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/clubarticle_t/Topcoders/31347555.html}
一个BST，节点是double，输入一个k，找到和这个k最接近的节点。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32284907.html}
判断字符串不考虑标点空格的情况下是回文.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32286605.html}
四位数字 \_ \_ \_ \_ ，要求填写这四位数，满足每位数字都是unique，而且前两位 + 后两位的和为100， 比如2 4 7 6， 问有多少种组合。 
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32286605.html}
两个string数组，比如A = [``abc'', ``mn'']，B = [``pa'', ``d'']返回一个string为两个数组中string的交叉组合直到其中一个数组的string已经耗尽，上例中string = ``apbacd''
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32286605.html}
一个图像的二维矩阵，给两个坐标，返回这两个坐标形成的长方形里面的点的和。如何预处理这个矩阵，使得获取结果的时间为constant time。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32286605.html}
Or两个四叉树，树的节点，有两种情况--没有child，有四个children，每个节点的值为$T$ or $F$，要求$or$两个四叉树，如果一个节点和另一个节点中所有children $OR$的结果相同，那么合并为一个节点。
\end{Q}

\begin{Q}[Twitter]{http://www.mitbbs.com/article_t/JobHunting/32286951.html}
让找一棵树(不一定是二叉树)里面的longest path. Path为tree里面任意2个node之间的距离。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32288151.html}
大概是这样的，有一个长为L的木料需要割开，割的位置在一个数组里A[1\ldots N]，从一个地方切开的cost是当前所切木料的长度，按不同的顺序切割，得到的total cost是不一样的，问怎么切cost最小。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t1/JobHunting/32287847_0_3.html}
输入两个整数，然后得出他们商的结果，在循环部分打括号

比如输入1，3，输出0.（3）

输入1，2，输出0.5（0）
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32071355.html}
数二进制文件的1的个数
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t1/JobHunting/32126949_0_1.html}
Given a matrix with 0 and 1, return the number of connected component（四向）with edge 1

e.g

1 0 1

1 0 1

0 1 1

return 2
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t1/JobHunting/32126949_0_1.html}
a bunch of bars on table, two players, each one could only take n(n = 1, 2, 3) bars at one time, the loser is the one taking the last bar. If you play first, figure out the strategy to make sure you could win
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32119043.html}
一个很简单的函数 如果能被5整除输出buzz，能被3整除输出fizz，同时能被这两个数整除输出fizzbuzz，如果都不能被这两个数整除输出这个数。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32149793.html}
有一个大的catalog，总共有500 Million个entry，每个entry内容是 （ID， document），每个document大小约10KB，不同的ID对应的document可能相同，怎样设计一个程序，对每个给定的一个ID，找出与该ID对应着相同的document的所有其他ID。Follow Up: 如果每台机器内存只有1GB，硬盘100GB，怎么做
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32115945.html}
Given a logfile:

a A

b B

a B

c E

a C

where left column is user ID, right column is page ID. Find the most frequent pattern of 3 consecutive page visits of all the users.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32162663.html}
给你一个二叉树，除了最后一行全都是满的，最后一行可能是满的也可能不是满的。逆时针打印这个二叉树的最外面一圈。比如：

\begin{tikzpicture}[
	level distance=1cm,
	level 1/.style={sibling distance=5cm},
	level 2/.style={sibling distance=3cm},
	level 3/.style={sibling distance=1.5cm}
]
\node {苹果}
	child {node {梨}
		child {node {桃子}
			child {node {勺子}}
			child {node {镜子}}
		}
		child {node {李子}
			child {node {盘子}}
			child {node {刀子}}
		}
	}
	child {node {番茄}
		child {node {茄子}
			child {node {傻子}}
		}
		child {node {筷子}}
	}
;
\end{tikzpicture}

结果是 苹果-梨-桃子-勺子-镜子-盘子-刀子-傻子-茄子-筷子-番茄
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32291111.html}
BT树结构, 中间节点是算数运算符(只有+ - * / 4种操作), 叶节点是数字, 要求给出算数表达式 (要求没有冗余括号)，比如：

\begin{tikzpicture}[
	level distance=1cm,
	level 1/.style={sibling distance=3cm},
	level 2/.style={sibling distance=1.5cm}
]
\node {*}
	child {node {+}
		child {node {1}}
		child {node {2}}
	}
	child {node {*}
		child {node {4}}
		child {node {5}}
	}
;
\end{tikzpicture}

表达式 = $(1 + 2) * 4 * 5$, 不能是$(1+2)*(4*5)$
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32246347.html}
从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（就是距离为2）。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32248787.html}
给一个文件，里面有name，address, zip code,每行一个数据。格式什么的没问题，都是comma separted， 问怎么列出来所有的zip code，结果不能有重复。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32259945.html}
Implement LRU(least recently used) cache.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32259945.html}
1-100的整数，有一个数出现两次，其余的数出现一次。找到出现两次的那个数。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32271487.html}
给一个Set of word, 查找某一个词是否在这个set里。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32282115.html}
给一个字符串，输出一个文件，里面每一行是一个出现的字符，后面跟着它出现的次数。要根据出现次数降序排列。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32282115.html}
OO design来表示formula，比如$1+2*3$. 要求有\ilcode{calculate()}和\ilcode{tostring()}函数。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t1/JobHunting/32292525_0_1.html}
An operation ``swap'' means removing an element from the array and appending it at the back of the same array. Find the minimum number of ``swaps'' needed to sort that array.

Eg: 3124

Output: 2 (3124->1243->1234)
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32026405.html}
有个封装好的函数\ilcode{int blockRead(char[] buf)}。内部有个静态文件指针，只能向文件末尾移动，不能rewind每次只能读取4K的block到buf里，返回读取的字节数（除非到文件尾，否则总是4K）要求实现\ilcode{int anySizeRead(char[] buf, int size)}从文件的当前位置读取任意大小的数据存入buf，并返回实际读到的数据字节数
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32026405.html}
Skip list, http://en.wikipedia.org/wiki/Skip\_list。写code实现。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32026405.html}
a set of intervals, how to tell if a given value is in any of the intervals
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32060089.html}
写一个程序，模拟投硬币的过程，每次投硬币，直到出现正面为止，返回之前出现反面的次数。重复N次上述的过程，问一共出现多少次反面
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32064283.html}
$10^9$个star，亮度为double类型，找出前一千个最亮的
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32067247.html}
给三个数组，怎么穷举所有的组合。。。比如$arr1=[a,b]$, $arr2=[3,4,5]$, $arr3=[true, false]$。如果不是三个，不确定个数的数组怎么穷举。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32079701.html}
Design and implement a class to train from a input string like ``ape apple ace'' to generate new words based on conditional probability of $P(c_i|c_j)$. e.g., $P(p|a)$, $P(e|p)$, $P(l|p)$.

\begin{lstlisting}
class TokenGenerator {
	public void train(String t) {\ldots}
	public String generate() {\ldots}
}
\end{lstlisting}

How to optimize \ilcode{generate()} method.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32107851.html}
两个BST，求他们merge后的BST。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32128895.html}
有一個map的interface，要實現\ilcode{get()}, \ilcode{put()}, \ilcode{remove()}, \ilcode{getRandom()}。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32119891.html}
About Inheritance and polymiorphism. A class, like LinkedList in Java, has two methods \ilcode{add()} and \ilcode{addall()}. Write a subclass to count how many times \ilcode{add()} is called. 
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32175265.html}
一个游戏，叫做“生或死” a.k.a. Game of Life，在一个棋盘上，规则如下：每格有两种状态：生，或者死

每一轮，如果有少于两个邻居是活着的，这格就死掉

如果刚好有两个邻居活着，这格保持原有状态

如果有三个邻居或者，这格可以重生，就是如果原来是死的，现在活过来了

如果有三个以上邻居，这格就被挤死了
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t1/JobHunting/32195653_0_1.html}
写一个类是timer的东西， 例如给个数值t和函数，等t时间之后call 这个函数。（然后问有多个这些如果支持多次调用怎么办，有哪些问题之类的）
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t1/JobHunting/32195653_0_1.html}
二个人轮流打枪的问题算概率， 就是6发装弹夹里面有一颗子弹。然后轮流对照自己头打，然后在shuffle对方接着打。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t1/JobHunting/32195653_0_1.html}
写个函数输入7张牌，然后输出是否有同花顺，顺子，和同花。 
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t1/JobHunting/32195653_0_1.html}
一个billion of urls, 然后让你输出最长的相同的prefix，包含这个prefix url必须占$75\%$以上。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32224635.html}
假设有一很长的数字，比如11224444,被压缩存储为pairs，如(1, 2), (2, 2), (4, 4).然后让我写个Iterator，要求有\ilcode{constructor()}，\ilcode{next()} to give out the digit and move to the next position, \ilcode{hasNext()} to indicate if there's any more digit left.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32262719.html}
两个不知长度的 int 数组，实现相加
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32279127.html}
给个数组，打乱了，比如

索引 0 1 2 3 4

值   3 2 1 4 0

数组的值是下次跳的索引位置，这样的话数组有环，比如 0->3->4->0->1->2->1，求最长环的长度.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32281037.html}
给两个同样长度排序好的数组，找第K个最小的数。扩展，给两个很长的数组，给定其中一个数，找离这个数距离最短的第K个数。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32281281.html}
大数据的平方$X^2$，X很长，不能用int，long 之内的表示
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32282399.html}
check if a number power of 3.
\end{Q}

\begin{Q}[Bloomberg]{http://www.mitbbs.com/article_t/JobHunting/32295307.html}
Find digits that are duplicated inside an integer. Find their order as well.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32295415.html}
两颗二叉树，但是一个节点可能有多个PARENT,判断是否相同。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32298851.html}
Given a string, find the longest substring that contains at most 2 distinct characters.
\end{Q}

\begin{Q}[Apple]{http://www.mitbbs.com/article_t/JobHunting/32299051.html}
Design a storage system to store files, while those files may have large amount of duplicate content. 
\end{Q}

\begin{Q}[Apple]{http://www.mitbbs.com/article_t/JobHunting/32299051.html}
Count words in a document. 如果文件很大，内存装不下怎么办?
\end{Q}

\begin{Q}[Apple]{http://www.mitbbs.com/article_t/JobHunting/32299051.html}
N casino 30 day max profit, 每个赌场每天的盈利情况不一样，每天只能在一个赌场，第二天只能跳跃到相邻的赌场
\end{Q}

\begin{Q}[Apple]{http://www.mitbbs.com/article_t/JobHunting/32299051.html}
3 sorted linked lists find the min($|x-y|$, $|x-z|$, $|y-z|$)
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32299047.html}
Given input as an array of strings, such as: [``apple Orange'', ``ORANGE apple'', ``APPLe oRange'', ``HI There'', ``THERE hI''], return an array of strings. In the above case, will return ``APPLe, oRange'', ``THERE hI''.

Here are the rules:

1. two strings are the same when words matches(case insensitive) and order doesn't matter, so ``apple Orange'' == ``APPLe oRange'' == ``ORANGE apple''.

2. if multiple identical strings exist, only return the one that occurs at the last location, so ``APPLe oRange'' and ``THERE hI'' will in the result.

3.  the relative order cannot be changed, so we cannot have result as ``THERE hI'', ``APPLe oRange''.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32300077.html}
以$1/(2^n)$的概率返回1，其它的时候返回0，题目应该假设有个函数可以生成1或者0，以$1/2$的概率

Follow up: 以任意概率生成1。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32298851.html}
Given a string, find the longest substring that contains at most 2 distinct characters.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32279127.html}
给一个数组，打乱了，比如

index 0 1 2 3 4

value 3 2 1 4 0

数组的值是下次跳的索引位置，这样的话数组有环，比如 0 -> 3 -> 4 -> 0, 1 -> 2 
-> 1，求最长环的长度.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32279127.html}
直线上有一个机器人从原点开始移动，每次可以向左移，也可以向右移，移动n步，再回到原点的概率是多少,
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32324613.html}
给个数组，和一个整数swapTime，求怎样能返回最大数组（低位index是数的高位，每次swap只能在相邻的数进行）

e.g [1,2,3] 2 ->[3,1,2]
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32324613.html}
数组里只会出现0到9，给一个数组，一个数target，找到用数组里的数字组合成的大于target的最小数字，数组里数字可以任意组合，重复使用。

[1,2] 11 -> 12

[1] 2222 -> 11111

[1,5,7] 56 -> 57

[1,5] 56 -> 111
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32324203.html}
Word breaking: How many spaces can we add to a word such that all subwords can be found within a given dictionary 

Example: 

fireman 

fire man -> 2 words 

fir em an -> 3 words 

DICT: [a, an, em, fir, fire, ire, ma, man]
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32322891.html}
一个$m*n$二维区域，每个点上有一定数量的钱，考虑路径 : 从坐下角$[m-1, 0]$出发，终点是右上角$[0, n-1]$, 在每个点只能向右或者向上走，现在有两个人，从起点出发，走到终点，问怎么样求出这两个人能拿到的钱的和的最大值
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32322891.html}
一个服务器上有一个很大的integer array A, 客户端会每次通过两个index start, end，来拿到$A[start, \ldots, end]$这个sub array上的minimum, 如何在服务器上实现快速的找出$A[start, \ldots, end]$的最小值.
\end{Q}

\begin{Q}[Twitter]{http://www.mitbbs.com/article_t/JobHunting/32326159.html}
非二叉树，每个节点有一个值0-9,从根节点到叶节点的路径，组成一个数字。求把所有数字加起来的和。
\end{Q}

\begin{Q}[Twitter]{http://www.mitbbs.com/article_t/JobHunting/32326159.html}
有向图，从A节点走到B节点，正好走N步，有多少种走法？走过的节点可以重复走。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32328363.html}
实现像database里的outer join. 表1, 有a, b两列，表2有b,c两列. 要求实现表1 outer join 表2.

比如：

a b    b c

1 2    3 4

2 5    2 8

结果:

a b c

1 2 8

- 3 4

2 5 -
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32328245.html}
传一些string进去，string都是整数加小数，部分， say, 1.2, 3.4. sort这些string, 按照以下规则

1. 先比较整数部分

2. 再比较小数部分，say 0.15 > 0.2

\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32333649.html}
给一个list of sentences, 然后找出一个pair,common words最大。举例：

This is a good day

This is a bad day

That was good day
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32331513.html}
From the set of natural integer numbers

Let x = 1234 = {1, 2, 3, 4}

Let y = 2410 = {2, 4, 1, 0}

Write an algorithm to compute the rearrangement of x that is closest to y but still greater than y. Both x and y have the same number of digits.
\end{Q}

\begin{Q}[Google]{}
有一个国家有一个字典，被1到1 mapping成另一个字典了，给这个被翻译后的字典，求那个mapping。假如dict1 = [ab, ac, bac], mapping = [a->b, b->c, c->a], dict2就应该是[bc, ba, cba]。现在给你dict2，求mapping。dict2是已经排序好的。
\end{Q}

\begin{Q}[Google]{}
判断一个图是不是二分图
\end{Q}

\begin{Q}[Google]{}
一堆interval，查询一个点是不是在一个interval里面
\end{Q}

\begin{Q}[Google]{}
估算从1970年到现在的时间，以百万分之一秒为单位，问需要多少byte存储
\end{Q}

\begin{Q}[Google]{}
一个很长的整数stream，求中位数，内存放不下，估算既可
\end{Q}

\begin{Q}[Google]{}
每个interval表示一个会议，只有一个房间，最大化能开的会
\end{Q}

\begin{Q}[Groupon]{http://www.mitbbs.com/article_t/JobHunting/32338601.html}
有一个unfair的coin，出现head的概率是1/4, 出现tail的概率是3/4，有个对应的返回值为boolean的function，当是head的时候返回true，是tail返回false，现在，你如何利用原有方程，再写一个function，使得返回true和false的概率一样。
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32334369.html}
Given a random matrix of characters, find all the locations of the following list of words: cat, dog, ate. We have to look in 8 directions.

e g o d

a c a t

e a t e

k t q z
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32334369.html}
Given an equation (Ex. ``$2*5+1+3*6$'' or ``$3/6-1*4+1$'') as a string, calculate the equation. So ``$2*5+1$'' becomes $10+1=11$.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32335553.html}
2维平面的一堆点，假设有一个在坐标原点的viewport,任给range(eg: 30度), 问什么角度viewport可包含最多的点。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32335553.html}
quadtree intersection
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32335553.html}
transpose an image
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32335813.html}
有一种新型存储设备，特点是：

1. 价格贵，稳定性高

2. 可读写，但写入的内容不能修改

如何利用它的特点设计一个存储系统。如果有个人写了个脚本不停用同样的内容写你的文件系统怎么办，怎么判断每次写入的东西是不是新的呢。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32334247.html}
给n个2维的点，找出其中离原点最近的k个。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32334247.html}
给n个positive int，计算他们两两之间hamming distance的和
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32334247.html}
有一溜n个房子，每个房子里面的东西的value是给定的一个正整数，小偷准备去偷东西来maximize gain，但是有一个条件是不能偷连续两幢房子的东西，因为房主挨偷以后会告诉左右邻居。要求给出能偷到的最大value的值。
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32334657.html}
给两个链表，找出第一个链表中不在第二个链表中的元素，不能有重复
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32339031.html}
给个字符串S，判断它是不是某个字符串T复制K次的结果。K未知，T未知。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32339377.html}
给一个board充满了字符，一个cell可以与其八方向连接，返回整个board所有可能的单词的vector。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t1/JobHunting/32335597_0_2.html}
binary matrix coloring (0->1, 1->0 except 1s surrounded by 0s)
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32341161.html}
Given a list of integers of length n, find the duplicate element. The integers are all in the range of 1 to n-1. There is only one duplicate element.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32226949.html}
Partition a set of numbers into two such that difference between their sum is minimum, and both sets have equal number of elements. For example: $[1, 4, 9, 16]$ is partitioned as $[1,16]$ and $[4,9]$ with $diff = 17-13=4$.
\end{Q}

\begin{Q}[Google]{}
有一瓶药片，总共有n片。每天需要吃半片。现在每天随机地从瓶中取出一片，如果恰好是一个半片，则吃掉。如果是一个整片，则将其瓣成两半，并吃掉其中的一半，然后剩下的半片放回瓶中。问：到第d天结束是，瓶中恰好剩余w个整片和h个半片的概率是多少？即求$P(n, w, h)$。（其中d的值可以根据n，w和h这三个值推算出来，所以未将其作为独立的参数。）
\end{Q}

\begin{Q}[Google]{}
有一个系统，用户可以提交很多task去运行，每个task有起止时间和占用的内存，设计一种算法来统计任意用户的所有task占用的峰值内存，并写出实现的代码。
\end{Q}

\begin{Q}[Google]{}
求两个有序数组A和B的共同元素（intersection）。怎么优化？如果两个数组都未排序怎么办？如果其中一个数组很大，另一个数组很小，怎么优化？如果两个数组都很大，无法全部放在内存中，且数据分布在很多台机器上，怎么办？
\end{Q}

\begin{Q}[Google]{}
设计一种队列，可以push(), pop(), getMax(), getMin()，要求时间复杂度尽可能小。
\end{Q}

\begin{Q}[ZocDoc]{http://www.mitbbs.com/article_t1/JobHunting/32343179_0_2.html}
给一个array，要求判断存不存在一个subarray的和是0。subarray的长度不限。要求$O(n)$
\end{Q}

\begin{Q}[Google]{}
设计一个方法来encode和decode 32 bit integer。要求能节省空间。比如：

如果int是1，可以用1个byte

如果int是256，可以用2个bytes
\end{Q}

\begin{Q}[Twitter]{http://www.mitbbs.com/article_t/JobHunting/32361483.html}
给一个字典，里面有一堆词。然后给一个词，word，求返回，与word编辑距离<=1的所有出现在字典里的词。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t0/JobHunting/32364859.html}
Write code to do arithmetic expression validation: 

digits: 0..9

operators: +, -, (, )

E.g.:

1+2-3  valid

1+(2-(3+4)) valid

-2 not valid
\end{Q}

\begin{Q}[Microsoft]{http://www.mitbbs.com/article_t/JobHunting/32369055.html}
一个人与人之间认识的关系网，单向的，就是我认识你，你不一定认识我。每两个人之间至少有一种认识关系。如果一个人被别人认识，但都不认识别人，叫做celebrity。问是否存在这样的celebrity，如果存在，可否存在多于一个的celebrity。然后问怎么去represent这样的关系
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32370913.html}
有一个只能产生0和1的随机函数，写一个能产生0到n-1的随机函数
\end{Q}

\begin{Q}[Apple]{http://www.mitbbs.com/article_t/JobHunting/32371887.html}
Find the lonely celebrity(celebrity: everyone knows him, he knows no one). Given a function \ilcode{boolean knows(A, B)}, which tells you if A knows B. 

Implement function: \ilcode{List<String> getLonelyCelebrity(Set<String> names)}.
\end{Q}

\begin{Q}[Apple]{http://www.mitbbs.com/article_t/JobHunting/32371887.html}
You got $2^{40}$ positive 4 byte integers on disk, 16M memory, how to find the first missing integer.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32078587.html}
现在有一个容器的iterator,支持\ilcode{bool hasNext ()}是否还有元素,\ilcode{T next ()}取出下个元素，并迭代器后移.现在要你写一个wrapper类:

\begin{lstlisting}
class wrapper {
   wrapper (iterator it);
   bool hasNext ()
   T next ()
   T peek ()
}
\end{lstlisting}
\end{Q}

\begin{Q}[Rocket Fuel]{http://www.mitbbs.com/article_t/JobHunting/32402829.html}
给一个unsigned int数组，size为$n$，数组的$sum = a$，计算一个$k$的值，将数组中所有大于$k$的数改为$k$之后，数组的sum变为$b$。Ex, $[1,2,5,7,7,8] = a = 30$, $b = 26$, 那么$k = 6$，因为$[1,2,5,6,6,6] = 26$。要求时间复杂度是$n*logn$.
\end{Q}

\begin{Q}[Rocket Fuel]{http://www.mitbbs.com/article_t/JobHunting/32402829.html}
给一张$L*W$的纸，给一堆$l(i)* w(i)$的模板，每个size的模板有各自的price $p(i)$，求这张纸所能剪出的最大值。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32416381.html}
Question: For some $N$, print all the solutions of $A * B = C * D$ where $A, B, C, D$ are all $1$ -- $N$.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32407699.html}
输出count最多的连续的字符。

\begin{lstlisting}
"this is a sentence" => [t, h, i, s, i, s, a, s, e, n, t, e, n, c, e]
"thiis iss a senntencee" => [i, s, n, e]
"thiisss iss a senntttenceee" => [s, t, e]
"thiisss iss a sennnntttenceee" => [n]
\end{lstlisting}
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32394795.html}
Sort a linked list in $O(nlog(n))$ time with $o(1)$ space complexity. Recursion doesn't work here.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32394795.html}
Given 3 integer arrays, find an item from each array s.t. $a+b+c=0$ in $O(nlog(n))$ time
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32113349.html}
处理一个字符串，删除里面所有的A，double所有的B要求in space , $O(1)$, no extra memory cost, 字符串处理变长的空间不算。例子，输入CAABD, 输出是CBBD
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32432949.html}
给一个整数a和一个整数b，找到最小的一个数（比数a大），而且是b的整数倍。注b一定大于0，而且是2的整数倍,例如2,4,8,16,32等等。a是任意。

例如，

如果 $a = 4$, $b = 4$, 那么返回4

$a = 5$, $b = 8$, 返回8

$a = 9$, $b = 8$, 返回16
\end{Q}

\begin{Q}[TripAdvisor]{http://www.mitbbs.com/article_t/JobHunting/32428727.html}
Given a binary tree, implement a method to calculate the sum of all nodes of a given depth。
\end{Q}

\begin{Q}{http://www.mitbbs.com/article_t/JobHunting/32434477.html}
给定一个数组$a$（所有元素都是unique），找到所有的pair($a_i, a_j$)符合条件：$i < j$并且 $a[i] > a[j]$。
\end{Q}

\begin{Q}[Linkedin]{http://www.mitbbs.com/article_t/JobHunting/32447951.html}
factorial digits sum。比如input为10，因为$10! = 3628800$，就返回sum的值$3+6+2+8+8+0+0$
\end{Q}

\begin{Q}[RocketFuel]{http://www.mitbbs.com/article_t/JobHunting/32401359.html}
一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下score等于所有出发比自己晚但是到达比自己早的racer数量之和，所有的出发时间和到达时间没有重复的，要求时间复杂度$o(nlog(n))$.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32449063.html}
Count inversions
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32440405.html}
Given a string, find longest substring which contains just two unique characters.
\end{Q}

\begin{Q}[Amazon]{http://www.mitbbs.com/article_t/JobHunting/32448779.html}
两个人，找出共同拥有的电话号码。两个人同时有1百万个电话，有台1g内存的电脑怎么高效的查出共同拥有的号码。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32447621.html}
有一个gym，用block表示。里面有健身器材，还有障碍物。让找一个最佳的位置放置椅子，使得椅子到所有健身器材的曼哈顿距离最短。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32445561.html}
从给定的sorted的array如何build的一个balanced的binary tree？开始给了一个recursive的方法，后来要一个iterative。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32445561.html}
给的一个double linkedlist，给定一个array，包含若干double linkedlist的节点的地址，统计这个array包含的互相独立部分的数目。一个double linkedlist是A<>B<>C<>...<>X<>Y<>Z（一共26个节点，从A到Z）。如果array是[ Z,A ]，那个return 2，因为A和Z两个不相邻的。如果array是[ A,D,B ]，那个return 2，因为AB是一个部分，D是另外一个独立的部分。如果array是[ A，B，C，。。。，Y，Z ]，那么return 1，因为AtoZ是一个独立的部分。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32439261.html}
Write code to compute the shortest unique prefix of each word in a set of words.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32449259.html}
给定二维网格里N个点的坐标，取其中任意一个点，找到所有距离这个点不超过K的坐标点。距离的定义是X轴距离+Y轴距离。
\end{Q}

\begin{Q}[Twitter]{http://www.mitbbs.com/article_t/JobHunting/32436737.html}
括号匹配，给定字符串，输出括号是否匹配.要求必须用递归写.
\end{Q}

\begin{Q}[Twitter]{http://www.mitbbs.com/article_t/JobHunting/32436737.html}
最长连续上升子串，给定字符串，输出最长连续上升子串的起始点和长度.
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32455493.html}
回到1980年代，一台计算机内存1KB, 主频 1MHz, 设计一个在这台机器上跑的时间最长(但能确定会正常结束)的程序，证明为什么是最长，并计算时长。
\end{Q}

\begin{Q}[10gen]{http://www.mitbbs.com/article_t/JobHunting/32455661.html}
给一个interface：

\begin{lstlisting}
public interface Stream {
    int getNext();
}
\end{lstlisting}

Stream都是infinite的。getNext()永远return一个比上次return的值还要大或者相等的int。让你实现一个class：

\begin{lstlisting}
public class MergeStream implements Stream {
}
\end{lstlisting}

要求这个class在constructor里面accept一个array的Stream，然后同时实现getNext() method，也要永远返回比上一次大或者相等的int。最后问了如果有N个Stream，然后getNext被用了K次的话，复杂度是个什么情况。
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32184907.html}
Given an array of integers where each element points to the index of the next element how would you detect if there is a cycle in this array?
\end{Q}

\begin{Q}[Google]{http://www.mitbbs.com/article_t/JobHunting/32466847.html}
A binary search tree is given. Find the ceiling value present in the BST of a given key. eg:

\begin{tikzpicture}[
	level distance=1cm,
	level 1/.style={sibling distance=5cm},
	level 2/.style={sibling distance=3cm},
	level 3/.style={sibling distance=1.5cm}
]
\node {8}
	child {node {3}
		child {node {2}}
		child {node {6}
			child {node {4}}
		}
	}
	child {node {12}
		child {node {10}}
		child {node {15}}
	}
;
\end{tikzpicture}

key - 13 => 15 

key - 4 => 6 

key - 8 => 10

\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32469031.html}
given an array, find out the max sum of a set that each elements are non-ajacent.
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32429075.html}
给一堆F的用户，以及朋友关系，朋友之间的关系是双向的。问能否将朋友的关系图分成两个partition。使得任何有直接朋友关系的两个人必须处在不同的partition里。
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32429075.html}
三个数组，从三个数组各取一数，找出和为某个值的组合
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32429075.html}
平面上一堆点，找出四个点，使得四边形面积最大。问题简化成找三个点，使得三角形面积最大。
\end{Q}

\begin{Q}[Pinterest]{http://www.mitbbs.com/article_t/JobHunting/32295631.html}
给一组字符串，找最长的公共前缀，至少两个字符串公共
\end{Q}

\begin{Q}[Pinterest]{http://www.mitbbs.com/article_t/JobHunting/32295631.html}
给一个数组和一个位置，从该位置起左右jump，检测能否jump到值为0的位置

\ilcode{canJump(int a[], int pos)}
\end{Q}

\begin{Q}[Facebook]{http://www.mitbbs.com/article_t/JobHunting/32468029.html}
一个链表1->2->3->4->5转换成1->5->2->4->3
\end{Q}

\begin{Q}[Yelp]{http://www.mitbbs.com/article_t/JobHunting/32466727.html}
给定一些字母和一个字典，找这些字母能组成的所有的词,如何scale
\end{Q}

\end{enumerate}
\end{CJK}
\end{document}