http://www.itasoftware.com/careers/work-at-ita/hiring-puzzles.h

TO LEARN, hard.

231. 直方图盛水

CODE

232. We have been given a deck of cards and each combination has a rating eg 3 As is higher than 2 As 1K etc. Write an algorithm such that the probability of picking 3 or 5 or 7 cards from the deck results in high rating

DP,写递推公式

233. 求一个unsorted数组中最长的等差数列（int 数组，可递增或者递减）
http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf

难题。。。略

Jump Game:
Given an array start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when u reach the goal in minimum number of jumps.
For ex:
Given array A = {2,3,1,1,4}
possible ways to reach the end (index list)
i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index 4)
ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)
Since second solution has only 2 jumps it is the optimum result.
要求：O(N) time, O(1) space.

类似于DP？反复update jump N+1步后，记录到达当前位置的最小步数

234.一个数组，不考虑重复数字，找出数组中有多少个cycle。cycle：每个element去找他对应的index，如果index在界内，就继续找这个index的值所对应的下一个index直到找到一个cycle，或者出界。
比方说 0，2，1，9，10
对于0， index 0 就是 val 0， 所以是一个cycle
对于2， index 2 是 1， 在界内，就找 index 1，which is 2，所以又是一个cycle
总共4个cycles： 0–>0, 2 -> 1, 9 -> 界外， 10->界外
先要求写了个可以有extra space的，然后要求no extra space

No extra space需要修改原数组吧。。。CODE

235. bool isOverlap(int a, int b, int c, int d)参数取值范围0~6代表星期几。能不能不用大于号和小于号

用一个七个数的数组来标记就行了吧

236.给一个吸地毯的irobot，和一个长方形的屋子，四面有墙，四个指令：
Bool moveForward（）//向前走一格，走不了的话返回false
Void Rotate（int degree）//就是左拐右拐
Bool isClean（）//当前单元格是否干净
Void clean（）
把irobot 扔在屋子任意位置，写代码让irobot清理房间，每一格都要走过（单元格没有坐标）

先走到角落，然后来回扫就行了

237. Edit Distance

见185题

238. {1，5， -5， -8，2， -1，15 } 要把负的扫到左边，正的扫到后边。不能改变顺序得到{-5 -8 -1 1 5 2 15} 这个题有time 低于 n^2 space=O（1）的解法吗

应该没有这样的解？

239.给一个通常的表达式，转成后缀表达式

CODE

240. Given n arrays, find n number such that sum of their differences is minimum. For e.g. if there are three arrays

A = {4, 10, 15, 20}
B = {1, 13, 29}
C = {5, 14, 28}
find three numbers a, b, c such that |a-b| + |b-c| + |c-a| is minimum. Here the answer is a = 15, b = 13, and c = 14

同224题

241. reverse double linked list.

CODE

242. [Facebook] 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

DP，写递推公式，使[0,i]中的元素有序，update时，加入[0,i+1]，要么decrement以前的，要么删掉i+1

243. 在一个平面上有n个点，设计算法看能不能找出四个点构成一个正方形，分析时间复杂度。

TO LEARN

244. Algorithm to find the two numbers whose difference is minimum among the set of numbers.
For example the sequence is 5, 13, 7, 0, 10, 20, 1, 15, 4, 19
The algorithm should return min diff = 20-19 = 1.
Constraint – Time Complexity O(N) & Space is not a constraint [upto O(3N)]
Assumption – Sorting O(nlogn) & comparison of adjacent numbers is already known & is not an option. Try to keep it linear

想不出来。。。

245. Given an array of integers (both positive and negative) divide the array
into two parts (sub-arrays) such that the difference between the sum of
elements in each array is minimum

如果subarray连续的话很简单。。。

246. 给一个string, 比如“facebook”, 可以拆成“face”和“book”, 对任一string, 找出最长的可以拆分成其他单词的子串。