CareerCup

the overall most viewed URL could potentially be the 11th in all servers. So that approach would ignore it.

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 N-1 edges, thus O(2*(n-1)) 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).

I 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

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.

No. Notice than both i and j are 1-indexed (1..n) due to the DP table. Hence the -1 to get the correct characters.

This 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

@Khush, I don't see any issue. The code gives output 3 for that example as expected.

It's just an example. In my opinion, having different sizes doesn't make the problem any easier or harder. It's the same.

Just a correction: O(N) average time, not amortized

don't underestimate a question ;)

@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)

We 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 = nv-1;
  rightw = nw-1;
  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+nth-1]; // check where is the answer
  else
    return w[leftw+nth-1];
}
// use getNth(va, n, vb, n, n)

In that input, there are 2 numbers (2 and 4) larger or equal than 2. So the answer is 2

how so? don't see such an assumption in my algorithm

this 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.

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.

Yes. The sum of any 2 even or 2 odd numbers is even.

Vgeek, 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

I have to say the same about you. Predecessor != Parent

that doesn't help. each parent's predecessors in the matrix still has O(N) elements. it still is O(N^2)

Without 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)

This is incorrect. You're not guaranteed to get the correct frequency just by checking the lowerKey(). A simple counter-example: {3, 1, 2}. You algorithm gives {1, 0, 0} but it should be {2, 0, 0}

Like quicksort, quickselect has O(N^2) worst case time complexity

Alexey, 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.

What 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

this 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 trade-offs.

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 = n-1; i >= 0; i--) {
		result[i] = GetUpTo(tree, values[i]);
		Update(tree, values[i]);
	}
}

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;
}

You're mixing 2d-trees and BST. We would need 2d-trees for a 2 dimensional space. The best time complexity to build a 2d-tree 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

Say we want the K nearest hotels.
a) K is rather small (e.g. K <= 30). Process each hotel, 1-by-1. Use a max-heap 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 median-of-medians algorithm to select the Kth smallest distance. After using this algorithm, the K-1 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
}

This is O(n^2) due to string concatenation being O(n)

Assuming 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, to-1);
	else if (IsPalindrome(s, from, to-1)) 
		return to;
	else if (IsPalindrome(s, from+1, to)) 
		return from;
	return -1;
}
// returns -1 if impossible, 0..len-1 otherwise representing the index to delete
int DeleteCharToPalindrome(const string& s) {
	return s == "" ? -1 : DeleteCharToPalindrome(s, 0, s.size()-1);
}

This code would be incorrect if we must remove a character. e.g. str = "aaaa"

int 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);
}

21! already exceeds that range

Factorize 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+speed-1, speed-1);
}

That approach is too slow for big inputs. You should not revisit the same search states (index, v)

Dynamic 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)

Sure but we also need O(n) for the hash map