emb
BAN USER 1of 1 vote
AnswersYou have an array of unique integer numbers and only one operation: MoveToFront(x) that moves given number to the beginning of the array.
 emb in United States
Write a program to sort the array using the minimum possible number of MoveToFront() calls. Report Duplicate  Flag  PURGE
Facebook Software Engineer Algorithm  6of 6 votes
AnswersYou are given a matrix with N rows and N columns. Elements in matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order.
Find number of 0s in the given matrix.
Example:0 0 1 0 1 1 1 1 1 Answer: 3 0 0 0 0 Answer: 4
Update: Expected complexity is O(log(N)). The best I've seen in comments is still O(N).
 emb in United States
Update2: Alright, guys, sorry for a bit of trolling. Obviously this is not possible to do faster than O(N). Here is why: take a diagonal (N, 1), (N1, 2), ... (1, N). Suppose input matrix has all 0's above this diagonal and all 1's under this diagonal. So only diagonal elements vary. Clearly, diagonal elements do not depend on each other. So we have to analyze each diagonal element which is O(N).
Nice job, @genys :) Report Duplicate  Flag  PURGE
Google Software Developer Algorithm  0of 2 votes
AnswersA robot on a plane has 2 types of commands:
1. move forward by X units (X is integer 0 <= X <= 10000 )
2. rotate by X degrees (X is integer in range [180, 180] )
A robot looks likedef robot(commands): while True: for command in commands: execute(command)
Given a list of commands (of size <= 10000) tell if it's possible to build a wall around the robot such that he will never touch it.
Example:
 emb in United States[move(10), rotate(180), move(10)] > answer is yes [move(10), rotate(45), move(10), rotate(45), move(10), rotate(45)]  answer is no
 Report Duplicate  Flag  PURGE
Google Software Developer Brain Teasers  2of 2 votes
AnswersYou are given a range [first, last], initially white. You need to paint it black.
For this purpose you have a set of triples
[(f, l, cost), ...]  where each triple means that you can paint range [f, l] for `cost` coins (limitations: cost is floating point >= 0, f, l, first, last are integers).
Find minimum cost needed to paint the whole range [first, last] or return 1 if it's impossible
Example:[first, last] = [0, 5] and set of triples is [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]
Clearly the answer is to take [0, 4, 1] and [2, 5, 1]  the total cost will be 2.
Another example:[first, last] = [0, 5] triples are [[1,4, 10], [2, 5, 6]]
answer is 1, because it's impossible to color whole range.
 emb in United States Report Duplicate  Flag  PURGE
Google Software Developer Algorithm  8of 8 votes
AnswersYou are given a graph, some edges are black, some are red. Find a spanning tree with one restriction: if we take some node as root, every path from it to some leaf node must consist of alternating redblackredblack edges. That is, no path from root to leaf must contain sequential blackblack edges or redred edges.
 emb in United States
You are guaranteed that such spanning tree exists. Report Duplicate  Flag  PURGE
Google Software Developer Algorithm  0of 0 votes
AnswersThere are N coins with coordinates (x, y) where x >0 and y >0
 emb in United States
You start at (0, 0) and you can only do steps of form (dx, dy) where dx >0 and dy > 0
Print the maximum number of coins that you can collect.
Clarification: you can do as many moves as you wish, the point is to collect maximum number of coins. If you are located at position (a, b) you may jump to position (a+dx, b+dy) for all dx > 0 and dy > 0
@krbchd: Your algorithm may output incorrect values. Suppose there are points (5, 7), (5, 8), (5, 9) for y coordinates LIS will output 7, 8, 9, however since these points are on the same x axis, you can choose only one of them. Report Duplicate  Flag  PURGE
Facebook Software Developer Algorithm  9of 9 votes
AnswersGiven a packed file with 1Tb of 64bit doubles (first 8 bytes are first double, next 8 bytes are next, etc) find the exact value of median. For simplicity assume the number of doubles is odd.
 emb in United States
You can't modify the file and you have only 8Gb of free memory.
Update: you may use no more than two passes through file and your algorithm shouldn't rely on some nature of file  it should work in all cases. Report Duplicate  Flag  PURGE
Google Software Developer Coding  0of 0 votes
AnswersGiven an array of numbers, find the longest alternating subsequence. That is, a subsequence [a1, a2, a3, ..., ak] where a1 > a2, a3 < a2, a4 > a3, ... or vice versa (Graphically looks like /\/\/\... or \/\/\/\....
 emb in United States Report Duplicate  Flag  PURGE
Google Software Developer Algorithm  0of 0 votes
AnswersGiven a set of numbers {x1, x2, x3, x4, ..., xN} (N>=3) a set of its pairwise sums is {x1+x2, x1+x3, x1+x4, x2+x3,x2+x4,x3+x4, ...,}. (That is s_k = x_i + x_j where i != j)
Restore a set of numbers given a set of its pairwise sums.
Note: you don't know given some k, to which i and j it refers, (i.e. input is given in undefined order)
EDIT: couldn't comment, so here is clarification
Example:S = {1, 5, 10, 100} (n elements) P = {6, 11, 101, 15, 105, 110} (n * (n  1) / 2 elements)
Given P you have to restore S.
Note here means that if you knew which element in P corresponded to which pair of indices in S, you could just solve a simple linear equation
 emb in United Statesx1+x2=a{k1} x2+x3 = a{k2}, ...., x{n1} + x{n} = a{k{n1}, x{n} + x1 = a{k{n}}
 Report Duplicate  Flag  PURGE
Facebook Intern  5of 5 votes
AnswersYou are given a function bool rand_bit_p() that returns true with some unknown probability p and false with probability 1  p.
 emb in United States
Write function rand_bit() using rand_bit_p that will return true and false with equal probability (that is, implement a fair coin, given unfair coin) Report Duplicate  Flag  PURGE
Google Software Engineer Algorithm  6of 6 votes
AnswersGiven a sorted array of size N of int32, find an element that repeats > ceil(N / 2) times. Your algo may assume that there will be always such element. Space/time O(1).
 emb in United States
Follow up question: Now element repeats > ceil(N / 4) times. Space/time O(1) Report Duplicate  Flag  PURGE
Google Intern  1of 1 vote
AnswersGiven integer k and a subset S of set {0, 1, 2, ..., 2^k  1}
 emb in United States
Return the count of pairs (a, b) where a and b are from S and (a < b) and (a & b == a)
& here is bitwise and.
Do it faster than O((2^k)^2), assume k <= 16
Example:
0b111
0b101
0b010
Answer: 2
0b110
0b011
0b101
Answer: 0 Report Duplicate  Flag  PURGE
Facebook Software Engineer Algorithm  2of 2 votes
AnswersYou are given a set of points on x axis (consumers)
 emb in United States
Also you are given a set of points on a plane (producer)
For every consumer print the nearest producer.
Wanted something better than O(n^2) time.
Example:
consumers: 1 5 7
producers: (0, 3), (1,1), (3, 2), (8, 10), (9, 100)
Answer:
for 1 nearest producer is (1, 1), for 5 nearest is (3, 2), for 7 nearest is (3, 2)
Followup question: now both sets are sorted by x coordinate. Could you come up with a linear algorithm? Report Duplicate  Flag  PURGE
Facebook Software Engineer Algorithm  0of 0 votes
AnswersGiven n, return 1 ^ 2 ^ 3 ^ ... ^ n
Where ^ is binary xor.
Note: n is a 64bit number, and 1<<63 is a valid n for this problem.
Examples:
 emb in United States>>> reduce(lambda a,b:a^b, [1,2,3]) 0 >>> reduce(lambda a,b:a^b, [1,2,3,4]) 4 >>> reduce(lambda a,b:a^b, [1,2,3,4,5,6,7]) 0 >>> reduce(lambda a,b:a^b, [1,2,3,4,5,6,7,8,9]) 1
 Report Duplicate  Flag  PURGE
Facebook Software Engineer Intern  2of 2 votes
AnswersYou are given a permutation arr[N]. E.g. arr[3] = {2, 1, 0} or arr[5] = {0,1,2,4,3};
 emb in United States
Then you can prepare somehow and then start serving requests: request(a, b, k) = sorted(arr[a:b])[k], that is, kth order statistic on slice [a:b] of arr.
E.g. if arr is [3,4,5,0,1,2] and a = 2 and b = 5, then arr[a:b] = [5,0,1] and let k = 2, so we sort it  get [0,1,5] and take kth element, that is  5.
Implement request(a, b, k) function. You can preprocess input data, that is, assume there will be only one array and many request() calls. Report Duplicate  Flag  PURGE
Facebook Software Engineer Algorithm  8of 8 votes
AnswersGiven an array int32 arr[] of size n, return the number of nonempty contigious subarrays whose sum lies in range [a, b]
That is, implement the following naive algorithm faster than O(n^2)def naive_algorithm(lst, a, b): result = 0 for i in xrange(len(lst)): for j in xrange(i, len(lst)): if a <= sum(lst[i:j + 1]) <= b: result += 1 return result
Examples:
count([1,2,3], 0, 3) = 3 # [1], [2], [3], [1, 2], [3] count([2,5,1], 2, 2) = 3 # [2], [1], [2, 5, 1]
You may assume that there are no overflows, that is sum(x_i) <= MAX_INT  1
 emb in United States Report Duplicate  Flag  PURGE
Google Software Engineer  1of 5 votes
AnswersYou are given an array of n unique integer numbers 0 <= x_i < 2 * n
 emb in United States
Print all integers 0 <= x < 2 * n that are not present in this array.
Example:
find_missing([0]) = [1]
find_missing([0, 2, 4]) = [1, 3, 5] # because all numbers are [0, 1, 2, 3, 4, 5]
find_missing([]) = []
find_missing([0, 1, 4, 5]) = [2, 3, 6, 7] # because all numbers are [0, 1, 2, 3, 4, 5, 6, 7]
Quirks are about requirements:
Time complexity O(n)  BUT there should be some fixed constant C independent of size of input such that every element of array is written/read < C times, so radix sorting the array is a no go.
Space complexity O(1)  you may modify the initial array, BUT sorted(initial_array) must equal sorted(array_after_executing_program) AND you can't store integers outside range [0, 2n) in this array (imagine that it's an array of uint32_t). Report Duplicate  Flag  PURGE
Google Software Engineer Brain Teasers  1of 1 vote
AnswersYou are given a flat room 1x1 metres, a position of victim in it (v_x, v_y) and a position of a killer (k_x, k_y) both inside this room (in range [0, 1]).
 emb in United States
Then the killer shoots once at some direction. The bullet reflects of the walls as if it was a light ray  if it falls under angle X degrees, it will reflect at angle X degrees, if it gets into the corner it just reflects back. If the bullet hits guardian (see below) it stops and killer fails.
Write a function that will be given coordinates of victim and a killer and will return a list of coordinates of guardians such that it's impossible for a killer to kill victim.
That is, whichever direction the killer will shoot, the bullet will never reach victim, or will be stopped by a guardian.
Here is an example for the case when we assume the walls don't reflect bullet (for simplicity):
killer: (0, 0), victim: (1, 1). The solution to this simplified problem is to place 1 guardian between killer and victim e.g. on (0.1, 0.1).
Your task is to do this with accounting bullet reflection. E.g. in the previous case the killer can shoot at (1/3, 1), the bullet will reflect to (2/3, 0) and finally get to the victim at (1, 1). Report Duplicate  Flag  PURGE
Google Software Engineer Brain Teasers  8of 8 votes
AnswersYou are given a list of n float numbers x_1, x_2, x_3, ... x_n, where x_i > 0.
 emb in United States
A traveler starts at point (0, 0) and moves x_1 metres to the north, then x_2 metres to the west, x_3 to the south, x_4 to the east and so on (after each move his direction changes counterclockwise)
Write an singlepass algorithm that uses O(1) memory to determine, if the travelers path crosses itself, or not (i.e. if it's selfintersecting)
e.g.
2 1 1 2 > crosses
1 2 3 4 > doesn't cross Report Duplicate  Flag  PURGE
Google Software Developer Algorithm  1of 1 vote
AnswersWrite function to determine if given unsigned 32bit number is a power of 3
int is_power_of_3(uint32_t n)
return 1 if yes, 0 otherwise.
e.g.is_power_of_3(27) = 1 is_power_of_3(9) = 1 is_power_of_3(42) = 0 is_power_of_3(0) = 0
Expected the answer not to be straightforward loop, but something faster.
 emb in United States Report Duplicate  Flag  PURGE
Google Software Engineer Math & Computation
How about a merge sort? O(n*log(n)) time, O(n) memory (nah, not in this python pseudocode)
The idea is the following  in both subarrays ranges are sorted by their left bound, shortest first. If one range contains another, just skip it. However, if we have two arrays
(a1, ...) (a2, ....), ...
(b1, ...) (b2, ...), ...
There are 3 cases
1) a1 < b1, then we are sure that (a1, ...) is not a subarray of any of (b1, ...), (b2, ...), etc. Also (b1, ...) is not a subarray of (a1, ...), so neither (b2, ...), (b3, ...) are, since they are already known to be not a subarray of (b1, ...)  emit (a1, ...)
2) a1 = b1,  basically can't happen, since then (a1, ...) would be subrange of (b1, ...) or viceversa
3) a1 > b1, then we are sure that (b1, ...) is not a subarray of any (a1, ...), (a2, ...), etc  emit (b1, ...)
def dumb_algo(ranges):
"""Dumb algorithm for checking correctness of merge sort approach"""
result = []
removed = set()
for i, candidate in enumerate(ranges):
for j, other in enumerate(ranges):
if j in removed:
continue
if i != j and contains(other, candidate):
removed.add(i)
break
else:
result.append(candidate)
return result
def contains(who, whom):
return who[0] <= whom[0] <= whom[1] <= who[1]
def merge_sort(ranges):
if len(ranges) <= 1:
return ranges
mid = len(ranges) / 2
left = merge_sort(ranges[:mid])
right = merge_sort(ranges[mid:])
result = []
i = j = 0
while i < len(left) and j < len(right):
l = left[i]
r = right[j]
if contains(l, r):
j += 1
elif contains(r, l):
i += 1
else:
if l < r:
result.append(l)
i += 1
else:
result.append(r)
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
import random
for i in xrange(500):
ranges = []
for j in xrange(200):
left = random.randrange(100)
right = random.randrange(left, 101)
ranges.append((left, right))
assert sorted(merge_sort(ranges)) == sorted(dumb_algo(ranges))

emb
October 19, 2015 Go through the critical points  that is  end or start of range and check if the kth order statistic lies inside rectangle between this and previous critical point.
"""
0123456789ABC
XXXXXXXXXXXXX
XXXX XXX
XX
"""
def kth(ranges, k):
assert k >= 0
events = []
for start, end in ranges:
events.extend([(start, 1), (end + 1, 0)])
events.sort()
depth = 0
previous_pos = 0
for pos, is_start in events:
length = pos  previous_pos
area = length * depth
if depth and k < area:
return previous_pos + k / depth
k = area
if is_start:
depth += 1
else:
depth = 1
previous_pos = pos
raise ValueError("k is larger than length by", k)
def kth_stupid(ranges, k):
lst = sum((range(s, e + 1) for (s, e) in ranges), [])
return sorted(lst)[k]
import random
for i in xrange(500):
ranges = []
s = 0
for n in xrange(50):
left = random.randrange(99)
right = random.randrange(left + 1, 100)
s += right  left + 1
ranges.append((left, right))
for k in xrange(s):
assert kth_stupid(ranges, k) == kth(ranges, k), (ranges, k)

emb
October 18, 2015 @akaaa, that's just what the problem states  "so that maximum sum among subarrays is minimized"
suppose we have an array of numbers of length n. How many choices are there for the length of first subarray? It can be of length 0, 1, 2, ..., n. So we try each length to see  which minimizes maximum sum. And when we've taken first x elements, we see that now we have to solve the same problem but with n  x elements and k  1 subarrays, so we cache those results in matrix of size [k][length] in order to get polynomial time.
@africa1001, sure
Suppose f(lst, k) is answer to the problem  that is, what is minimal maximum sum if we split lst into k parts.
We see that f(lst, 1) = sum(lst)
Also we see that f(lst, k) = min(max(sum(lst[:i]), f(lst[i:], k  1)) for i in xrange(len(lst))), that is we brute force the length of the first subarray and call recursively to get answer for k  1 subarrays, assuming that first subarray takes first i elements.
sum(lst[:i]) is the sum of the first subarray, f(lst[i:], k 1) is minimum maximum sum of the rest k  1 subarrays.
In the answer above is just that formula, but I compute it rowbyrow, first for k =1, then for k = 2, etc, thus space usage is only O(n).
I assume subarrays may be empty. We can solve it in O(n^2 * k) and O(n) memory using dynamic programming. If the numbers may only be positive, we can do it in O(n * log(n) * k)
Let matrix[k][offset] be the answer to split_minmax_sum(lst[offset:], k)
Then we can build our matrix row by row up until k we want.
candidates = [max(sum(lst[offset: offset + i]), matrix[k][offset + i] for i in xrange(len(lst)  offset)]
matrix[k + 1][offset] = min(candidates)
def split_minmax_sum(lst, k):
assert k > 0
if k == 1:
return sum(lst)
elif not lst:
return 0
s = 0
row = [0] * (len(lst) + 1)
for i in xrange(len(lst)  1, 1, 1):
s += lst[i]
row[i] = s
for n in xrange(2, k + 1):
new_row = []
for offset in xrange(len(lst) + 1):
s = 0
min_result = None
for j in xrange(offset, len(lst) + 1):
result = max(s, row[j])
if min_result is None or min_result > result:
min_result = result
if j != len(lst):
s += lst[j]
new_row.append(min_result)
row = new_row
return row[0]
assert split_minmax_sum([1, 3, 2, 4], 3) == 4
assert split_minmax_sum([1, 2, 3, 2], 2) == 2
assert split_minmax_sum([1, 5, 10], 3) == 10
assert split_minmax_sum([5, 5, 6, 6, 1, 1, 3], 2) == 2
If numbers are positive then candidates array is /\shaped and we can do binary search in it.
Also it seems there is an O(n*k) general solution, if we somehow optimize computing minmax on each row.
Suppose character occurences are x1 >= x2 >= ...>= xk
Solution will exist iff x1  1 <= x2 + x3 + ... + xk, that is for x1 characters we need x1  1 separators to achieve nonneighborhoud.
Suppose at some moment solution exists, let's prove that if we take 2 top characters, it will still exist.
x1  1 <= x2 + x3 + ... + xk # add x1 + 1 to both sides, n is length of string
2x1 <= n + 1
So we have
n + 1 >= 2x1 >= 2x2 >= 2x3
After we take 1 char from x1 and one from x2:
n  1 >= 2x1  2 >= 2x2  2 >= 2x3
We have to prove that n  1 >= 2x3
n  1 >= x1+ x2 + x3  1 >= 3x3  1 >= 2x3, that is x3 >= 1, which is obviously true (unless we've exhausted all characters, then solution is trivial)
So we just have to take two topfrequency characters every time until there are no more characters, that is done with maxheap.
Also you should include characters themself when comparing frequencies (5, 'a') < (5, 'b') for example.
By the way, here is a proof that this works. It's then easy to understand how to move window bounds. (suppose elements are unique)
for(int i = 0; i < n  1; ++i) {
int j = bin_search(arr, i + 1, n, arr[i] + K); // find index of element in arr[i+1:n] whose differenec with current is K
if(j!=1) total++
}
print total
Pseudocode above is obvious and now we think  can we do better? Yep, we observe that we don't need to do bin_search  if we increase i, then j will only increase.
The same technique helped me to understand what to do in all similar questions where we move bounds of window.
Also here is a tip about simpler solution.
Suppose you have an array of partial sums
p1 p2 ... pn
Then you divide it in two equal parts by index.
p1 p2 ... pm and pm+1 .... pn
And then suppose you have both arrays sorted in increasing order.
What happens if we take one partial sum from left array and another from right?
So we have an array
4 2 5 3 1 and a=1 b=0
min =5 so new array is
1 7 0 8 4 a=4 b=5
and now I don't get it, will the naive algorithm account 2 5 3, that is 7 0 8 ?
Isn't the problem is that when you add min to every element, the sum of range becomes sum(old_range) + min * len(old_range) and not sum(old_range) + min?
If I understood your algorithm correctly, it seems like there is a small problem with your approach  it will output more ranges than there are.
Example
array: arr[0]=1 arr[1]=2 arr[2]=3
cumulative: x_0=1 x_1=1 x_2=2
a = b = 3
expected answer: 0
with balanced tree we look for suitable pair for x_1 and see that x_2 suits, since x_1  x_2 = 3 that is in our range. But there is no cumulative sum 3 in this array, since we can only subtract x_i from x_j if i > j
 emb September 26, 2015Alright, here is my answer. O(n^2 * log^2(m)). It finds k'th order statistic. Basic idea  find the longest array, take its mid element and find its rank in the whole matrix by doing binsearch in each array.
Now we now if k > rank or k < rank so we can cut away either left or right half. So we cut and repeat until only one nonempty array left. The code below slices lists but it can be avoided by carefully keeping bounds of each array.
def insert_pos(lst, elem):
left = 0
right = len(lst)
while left < right:
mid_idx = left + (right  left  1) / 2
mid = lst[mid_idx]
if elem <= mid:
right = mid_idx
else:
left = mid_idx + 1
return left
def kth_order(lists, k):
longest_list = max(lists, key=len)
total_length = sum(map(len, lists))
if total_length == len(longest_list):
return longest_list[k]
mid_idx = (len(longest_list)  1) / 2
mid_elem = longest_list[mid_idx]
mid_elem_rank = mid_idx
for lst in lists:
if lst is not longest_list:
mid_elem_rank += insert_pos(lst, mid_elem)
if mid_elem_rank < k:
del longest_list[:mid_idx + 1]
return kth_order(lists, k  mid_idx  1)
elif mid_elem_rank > k:
del longest_list[mid_idx:]
return kth_order(lists, k)
else:
return mid_elem
import random, copy
num_arrays = 10
array_size = 5
arrays = []
for i in xrange(num_arrays):
arrays.append(sorted(random.randrange(100) for j in xrange(array_size)))
new_array = []
for k in xrange(num_arrays * array_size):
new_array.append(kth_order(copy.deepcopy(arrays), k))
assert new_array == sorted(sum(arrays, []))
After we have kth_order function, it's trivial to implement median function.
Probably there are better solutions
Could you elaborate more about x1 x2 y1 y2 and how do you understand that only B rooms are needed for consideration?
My thought process
1) Imagine every room is the same, not reflected anyhow, we will fix this later by reflecting guardian positions in all 4 ways
2) now there is one killer on an infinite plane at (k_x, k_y) and infinite victims {(v_x + n, v_y + m) where n, m integer}
3) shift everybody so that killer is at (0, 0)
4) now we have a set of tangents that we need to protect  {(v_y  k + n) / (v_x  k_x + m)
5) protect them by putting guardians at {(v_x  k_x + n) / 2, (v_y  k_y + m) / 2}. Notice that we need only 4 guardians since they are automatically duplicated to all rooms
7) repeat 1) for every 4 positions of reflected victim, now we have 16 guardians
8) shift everything back
In general case we can just compute Levenshtein distance in O(n^2), and mem O(n), but in this case we can do simple O(n) by just splitting cases.
def is_edit_distance_1(s1, s2):
# tell if only one character differs
if len(s1) == len(s2):
return sum(c1 != c2 for (c1, c2) in zip(s1, s2)) == 1
elif abs(len(s1)  len(s2)) > 1:
return False
else:
if len(s1) > len(s2):
s1, s2 = s2, s1
# alright, now there is one extra character in s2
i = j = 0
while i < len(s1):
if s1[i] == s2[j]:
i += 1
j += 1
# We haven't met an extra character before
elif i == j:
j += 1
# Oops, two extra characters, exit
else:
return False
return True
assert is_edit_distance_1('abc', 'adc')
assert is_edit_distance_1('abc', 'ab')
assert not is_edit_distance_1('abc', 'acb')
assert not is_edit_distance_1('abc', 'cab')
assert is_edit_distance_1('abc', 'abcd')
assert is_edit_distance_1('abcd', 'abc')

emb
September 07, 2015 Unfortunately, I haven't seen the "expected" solutions here, so I'll put them.
1) L=3486784401 is the largest power of 3 that fits into 32 bits, so if L mod x == 0, then x is a power of 3.
int is_power_of_3(uint32_t x) return x ? ((3486784401 % x) == 0): 0
2) We can see that if we take all powers of 3 and take mod 255, all numbers will be unique, so we can use lookup table of size 256 and check "x & 0xFF" in it.
 emb August 30, 2015
Anonymous #2 is right, expected solution is straightforward for O(n*log(n)) case and a little bit trickier for O(n) case.
 emb October 22, 2015