Miguel Oliveira
BAN USERI enjoy algorithms, puzzles and programming competitions :)
 1 Answer Interview "red flags"
Hi,
 Miguel Oliveira September 09, 2013
In the beginning of CtCI book, Gayle talks about the case of a student which she referred but had too many "red flags".
Could you elaborate more on the "red flags"? Maybe with a few more examples of these kind of mistakes that we should avoid in an interview? Flag  PURGE
In this case, we need to look to the overall algorithm complexity and not a single ++/ complexity. Since the problem statement does not guarantee the BST is balanced, *one* ++ or  operation can take O(n) in the worst case.
However, the amortized time of ++/ operations is O(1). This is because the iterators will traverse each tree edge twice: 1  going to a child, 2  go back to the parent. A tree has N1 edges, thus O(2*(n1)) is O(n) *total* time.
Hence, the algorithm takes O(n) total time.
The successor/predecessor actually take O(n) time because the tree is not guaranteed balanced. However, the amortized time over the N operations is O(1). Hence the overall O(n).
 Miguel Oliveira February 05, 2015I don't think your inorder traversals are correct. Example
if (p>right) then we want the leftmost child of p>right
Same as searching the sum of 2 numbers in an array. Instead of having 2 pointers: start and end, we have 2 tree iterators.
if tree_size < 2
// no answer
return null
start = tree.begin(); // smallest element
end = tree.rbegin(); // last element  largest
while start != end
if start>value + end>value == target
return start, end
if start>value + end>value > target
end
else
start++
// no pair sums up to target
return null

Miguel Oliveira
January 26, 2015 You misunderstood what I wrote. That's the point of steps 3 and 4. Equal urls will be sent to (3) and combined by (4) the same machine.
 Miguel Oliveira December 12, 2014No. Notice than both i and j are 1indexed (1..n) due to the DP table. Hence the 1 to get the correct characters.
 Miguel Oliveira December 03, 2014This is not a normal edit distance. I do not allow substitutions. If you run the code, you'll see that ModifiedEditDistance("abc", "cba", 1) returns 4 which is larger than 2*K
 Miguel Oliveira November 09, 2014@Khush, I don't see any issue. The code gives output 3 for that example as expected.
 Miguel Oliveira September 08, 2014It's just an example. In my opinion, having different sizes doesn't make the problem any easier or harder. It's the same.
 Miguel Oliveira August 15, 2014Just a correction: O(N) average time, not amortized
 Miguel Oliveira August 08, 2014don't underestimate a question ;)
 Miguel Oliveira July 30, 2014@Murali, that would be O(N)
@Anonymous, in each step, the range of one of the arrays is reduced in half. maybe you want to check it more carefully
As mentioned in another post, the median is Nth and (N+1)/2. Just call this function twice. Still O(log N)
 Miguel Oliveira July 26, 2014We can reduce this to finding the Nth element in 2 sorted arrays. This can be done in O(log N) with a binary search.
My approach is to have the usual indices for binary searching an array, but for both arrays. Then, find how many elements are smaller or equal to the middle elements in each array. If the amount of numbers less or equal to the middle elements is less than N, then the answer can't be one of the numbers smaller or equal than the smallest middle element, so advance the binary search indices for them. Example:
v[] = {1,2,7,9}
w[] = {3,4,5,6,8}
nth = 4
1) v[midv] = 2, w[midw] = 5, the amount <= middles = 5 which is > N so decrease the largest middle
2) v[midv] = 2, w[midw] = 3 (left=0, right=1); amount = 3 <= N, advance midv, N = 2
3) v[midv] = 7 (3,4), w[midw] = 3 ; amount = 2 <= advance midw, N = 1
4) v[midv] = 7, w[midw] = 4 (1,1) ; amount = 2 > N, advance midv
...
leftv > rightv, answer is w[leftw] = 4
int getNth(int* v, int nv, int* w, int nw, int nth) {
int leftv, rightv, midv, leftw, rightw, midw;
leftv = leftw = 0;
rightv = nv1;
rightw = nw1;
while (leftv <= rightv && leftw <= rightw) {
midv = (leftv+rightv) / 2;
midw = (leftw+rightw) / 2;
int a = midv  leftv+1, b = midw  leftw+1;
if (a+b > nth) {
if (v[midv] > w[midw])
rightv = midv  1;
else
rightw = midw  1;
} else {
if (v[midv] < w[midw]) {
leftv = midv+1;
nth = a;
} else {
leftw = midw+1;
nth = b;
}
}
}
if (leftv <= rightv)
return v[leftv+nth1]; // check where is the answer
else
return w[leftw+nth1];
}
// use getNth(va, n, vb, n, n)

Miguel Oliveira
July 25, 2014 In that input, there are 2 numbers (2 and 4) larger or equal than 2. So the answer is 2
 Miguel Oliveira July 25, 2014how so? don't see such an assumption in my algorithm
 Miguel Oliveira July 23, 2014this fails {2, 3, 0} for example.
it might work with an extra pass over the array though
I believe the predecessor term here is the same as ancestor. Meaning that a predecessor appears in the path between the root and the node.
 Miguel Oliveira July 17, 2014I believe the predecessor term here is the same as ancestor. Meaning that a predecessor appears in the path between the root and the node.
 Miguel Oliveira July 17, 2014Yes. The sum of any 2 even or 2 odd numbers is even.
 Miguel Oliveira July 10, 2014Vgeek, I think you mixed something up. If you had sorted an array with the numbers, the median is just the middle element(s) (if n is odd/even).
The usual answer with 2 heaps was given by Zhia above.
The 'n' in the question refers to the number of values. In that input, there are 5 values >= than 5. The fact that the values are >= 900 is not an issue.
Adriana, my M is the number of values. In the worst case, all M values are processed. So it's just O(M).
create some examples. you'll see why this is incorrect
 Miguel Oliveira July 01, 2014I have to say the same about you. Predecessor != Parent
 Miguel Oliveira June 28, 2014that doesn't help. each parent's predecessors in the matrix still has O(N) elements. it still is O(N^2)
 Miguel Oliveira June 28, 2014Without further assumptions, this binary tree may be just a line with depth N. Hence, in such cases, each node has O(N) predecessors. So, just writing the results to the matrix uses O(N^2)
 Miguel Oliveira June 27, 2014This is incorrect. You're not guaranteed to get the correct frequency just by checking the lowerKey(). A simple counterexample: {3, 1, 2}. You algorithm gives {1, 0, 0} but it should be {2, 0, 0}
 Miguel Oliveira June 26, 2014Like quicksort, quickselect has O(N^2) worst case time complexity
 Miguel Oliveira June 25, 2014Alexey, the worst case is not when all numbers belong to the interval because we're only counting them. It is if the tree is actually a line. If you prefer, treat the complexity as O(depth), which is O(log n) if the tree is balanced.
 Miguel Oliveira June 23, 2014What part of my explanation you didn't understand?
In my approach, we only recurse in one child thanks to having the size of the left subtree, so the time complexity is O(depth) which is O(log n) in a balanced tree.
Your approach just traverses the whole tree in the worst case. It's quite different.
This has O(N^2) complexity. The sublist part is O(N), for each one of the N integers
 Miguel Oliveira June 22, 2014this was the only question that I haven't seen online already. just notice that actual interview questions are not this precisely defined.
My interviewer didn't mention "You can assume that you already have some extra information at each node", the questions are open to discussion and I asked if I could use extra information. The point is to discuss different approaches and their tradeoffs.
I think the simplest approach to code and achieve O(n log n) is to use a Binary Indexed Tree. It's a good data structure when we want the frequencies up to some value.
We can either assume the values in the array are between 0 and some MAXVAL or preprocess the array  there are at most N distinct values and we only care about their relative order of magnitude.
const int MAXVAL = 10000;
int GetUpTo(int* tree, int val) {
int sum = 0;
for (; val > 0; val = val & val)
sum += tree[val];
return sum;
}
void Update(int* tree, int val) {
for (; val < MAXVAL; val += val & val)
tree[val]++;
}
void Solve(int* values, int n, int* result) {
int tree[MAXVAL] = {};
for (int i = n1; i >= 0; i) {
result[i] = GetUpTo(tree, values[i]);
Update(tree, values[i]);
}
}

Miguel Oliveira
June 22, 2014 Lets say the array has M numbers. For the purpose of this problem, negative values and 0s are irrelevant. Also, numbers larger than M can be treated as M because the answer is never larger than M.
So, we can count the number of existing values between 1 and M. Then, process the values backwards (M to 1) to find the answer, adding the counts of the values processed so far.
This yields an O(M) algorithm with extra O(M) memory.
int Solve(const vector<int>& values) {
int n = values.size();
vector<int> count(n+1, 0);
for (auto val: values)
if (val >= n)
count[n]++;
else if (val > 0) // ignore negative values
count[val]++;
int am = 0;
for (int i = n; i > 0; i) {
am += count[i]; // amount of numbers >= i
if (am >= i)
return i;
}
return 0;
}

Miguel Oliveira
June 21, 2014 You're mixing 2dtrees and BST. We would need 2dtrees for a 2 dimensional space. The best time complexity to build a 2dtree is O(n log n) as shown on Wikipedia.
I believe you didn't include the heap operations time complexity in your overall query complexity. Your doing multiple heap operations per query, so it will not be just O(log N) on average.
The question states "You are given information about hotels in a country/city. X and Y coordinates of each hotel are known. ", so that's not an issue.
Going for trees only make sense if we have multiple queries (as the algorithm is much more complex). The question didn't mention multiple queries.
it is not asymptotically optimal, as I showed in my answer
 Miguel Oliveira June 20, 2014Say we want the K nearest hotels.
a) K is rather small (e.g. K <= 30). Process each hotel, 1by1. Use a maxheap to keep the K nearest hotels seen so far. If an hotel is closer than the Kth in the heap, remove it and add the closer one. Time complexity will be O(N log K) with extra O(K) for the heap.
b) K is large and we can use additional O(N) memory. Calculate the distance of each hotel to point (x, y). Use the medianofmedians algorithm to select the Kth smallest distance. After using this algorithm, the K1 closest hotels are to the left of the Kth one, in no particular order. This algorithm takes O(N) time and memory (see wikipedia /wiki/Median_of_medians).
Interesting, this was one of the questions of my second interview. This was my answer:
 Suppose we know the size of the left subtree for each node.
 We want the number of values in the interval [A, B]. This is the same as the number of values up to B minus the number of values less than A.
 So we can reduce this question to finding the number of values up to X.
1) Start at the root
2a) If the value we search is less or equal to current node value. Then this node and all values to the right are larger or equal to this value and we can ignore them. Recurse on the left subtree
2b) The value we search is larger than the current node value. Then this node and all values in the left subtree are less than this value. Recurse on the right subtree.
On a balanced BST, this algorithm takes O(log N) time.
struct TreeNode {
TreeNode * left, * right;
int val, left_subtree_size;
};
int getLess(TreeNode* node, int v) {
if (node == NULL)
return 0;
if (v <= node>val)
return getLess( node>left , v);
return 1 + node>left_subtree_size + getLess(node>right, v);
}
int Solve(TreeNode * root , int from, int to) {
return getLess(root, to+1)  getLess(root, from); // to+1 to get #values <= to
}

Miguel Oliveira
June 19, 2014 This is O(n^2) due to string concatenation being O(n)
 Miguel Oliveira June 06, 2014Assuming we must delete a character, we can use 2 pointers: from the start and from the end of the string and check if they're equal. If not, we must remove one of them and check if the remaining string is palindrome.
We only do at most 2 checks for palindrome, so this code runs in O(n), n = string.length
bool IsPalindrome(const string&s, int from, int to) {
for (; from < to; from++, to)
if (s[from] != s[to])
return false;
return true;
}
int DeleteCharToPalindrome(const string& s, int from, int to) {
if (from >= to) // s is palindrome. if its size is even, we can
return to; // just remove one of the middle elements if the size
// is even or the middle element if size is odd
if (s[from] == s[to])
return DeleteCharToPalindrome(s, from+1, to1);
else if (IsPalindrome(s, from, to1))
return to;
else if (IsPalindrome(s, from+1, to))
return from;
return 1;
}
// returns 1 if impossible, 0..len1 otherwise representing the index to delete
int DeleteCharToPalindrome(const string& s) {
return s == "" ? 1 : DeleteCharToPalindrome(s, 0, s.size()1);
}

Miguel Oliveira
June 05, 2014 This code would be incorrect if we must remove a character. e.g. str = "aaaa"
 Miguel Oliveira June 05, 2014int SwapBit(int n, int i, int j) {
int bit_i = (n & (1 << i)) >> i; // get bit i
int bit_j = (n & (1 << j)) >> j; // get bit j
int mask = ~((1 << i)  (1 << j)); // mask to unset bits i and j
return (n & mask)  (bit_i << j)  (bit_j << i);
}

Miguel Oliveira
June 05, 2014 21! already exceeds that range
 Miguel Oliveira June 03, 2014Factorize y into a product of prime powers: p_1^e_1 * p_2^e_2 * ... * p_k^e_k
Then, we just need to check for each prime p_i if x! contains p_i at least e_i times.
A simple method is to check each prime power, e.g. p_i = 2 => x/2 + x/4 + x/8 + ..
This is bounded by the factorization algorithm. The usual O(sqrt(y)) factorization method is probably good enough.
Search all options but do not revisit states (position, speed).
unordered_set<pair<int, int>> visited;
bool CanCross(vector<bool> field, int i, int speed) {
if (i >= field.size())
return true;
pair<int, int> state(i, speed);
if (!field[i]  speed <= 0  visited.count(state))
return false;
visited.insert(state);
return CanCross(field, i+speed, speed)
 CanCross(field, i+speed+1, speed+1)
 CanCross(field, i+speed1, speed1);
}

Miguel Oliveira
May 26, 2014 That approach is too slow for big inputs. You should not revisit the same search states (index, v)
 Miguel Oliveira May 26, 2014Dynamic programming. Suppose you process the floor column by column. You either put a tile vertically (filling 2 rows and 1 column) or 2 tiles horizontally (filling 2 columns and 2 rows)
 Miguel Oliveira May 20, 2014Sure but we also need O(n) for the hash map
 Miguel Oliveira May 20, 2014Open Chat in New Window
the overall most viewed URL could potentially be the 11th in all servers. So that approach would ignore it.
 Miguel Oliveira November 07, 2015