CareerCup

If there is a row with all zeros, then there can't be a column with all 1s.

Simple recursive backtracking. Check if the substring in the dictionary, until the whole sentence is processed. Like @Sibendu suggested, implement dictionary as Trie to ignore substrings that are not a word.

LOL @vgeek has a good point. The question asks if the tree has "a" subtree not "the" subtree, meaning any subtree.

@aka Can you elaborate on the DFS or the BFS solution?

This is a recursive solution. The question is clearly asking for a non-recursive solution.

You can get clever here, saying that you're not storing anything, but the recursive function keeps the values in program stack, so it's not in-place.

Check out the C solution at w w w.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/

1. Search the root node of the subtree in the big tree.
2. For every node found,
2.a. traverse at the same time to see if the subtree matches the subtree found in the main
2.b. if found return true
3. Return false (not found)

You can do this in linear time by partitioning the array, with O(1) space. You're suggesting a solution both worse in time and space. How is this better?

@Amm Sokun, Based on your question that you've posted, this problem is simply finding the min(X) for a given list of coordinates.
We cannot make better than linear time for finding the minimum in an _unorganized_ list, because we have to examine every element, otherwise we might miss it. Therefore, the optimal algorithm for finding the minimum element is Ω(n) (that is big Theta). If the elements were in a balanced tree then finding the element would take O(log n) time. If the list were sorted then finding the minimum is trivial and could have been done in O(1), but these are not stated in the problem.

This is the variation of Subset Sum problem, where subset sums to 0. The problem is NP-Complete. Naive algorithm is exponential time, where you try all the combinations in the array and check to see if it adds to the given sum. The running time of the naive implementation is, 2^n subsets and n times addition, O(n* 2^n).

Wikipedia says there is a better exponential time algorithm that runs in O(2^(n/2)) time and a pseudo-polynomial time dynamic programming solution. For implementation, you can Google "Subset Sum Problem".

@Vifi you can find Ymin and Y max in O(n) time, but it doesn't matter, because the BETWEEN condition includes all the Y values so it's irrelevant.

+1 I think the answer at stackoverflow is the closest answer. However, it's still not O(1) as claimed, because you need to iterate the array to calculate the actual sum and the squared sum of the array.

If the sum of all numbers and the sum of squares of all numbers of the array are not given, this question cannot be solved in less than linear time.

As @Sylla pointed out 100! is a very large number and won't fit in any basic primitive data type. You can argue that you can use a language that supports big numbers like Python or Java, but then I don't think that's the intention. @dn suggested the link at stackoverlow and that solution seems more reasonable. Using sum of numbers and sum of square of numbers, which both can be calculated with Gaussian formulas.

Short answer is a "synchronized queue".

If you look at the Java's Thread Pool implementation, I am talking about the java.util.concurrent package specifically, the thread pool Executors uses synchronized queues that implement the BlockingQueue<E> interface and the BlockingQueue<E> interface extends the generic java.util.Queue<E> interface.

You can look at the javadoc and see how the whole system is designed and not reinvent the wheel. Basically your thread pool implementation will use [Abstract]Factory pattern (see ThreadPool, Executor, ExecutorService, ThreadPoolExecutor classes) to create and execute your tasks and your tasks needs to implement the Java Runnable interface which is the Command design pattern. So you can use these design patterns along with a synchronized queue to come up with a Thread Pool implementation in any language of your own.

This is an open ended question. I am sure that's the intention and it's expected of the interviewee to discuss various reasons. This is open ended because the latency could be anything (see Wikipedia Latency_(engineering) ) for various types of latencies).

First I'd ask for more clarification: Is the specific website is slow or all the websites that you're visiting that day is slow?
If yes, then it could be the computer, the browser, and/or any other nodes between you and your ISP (e.g., the routers, DNS server, your network equipment, etc.). In this case it's hard to tell if there is a server latency. You can still use traceroute command to see the latency between the routers/gateways between your computer and the web server.

If no, then there is a a server latency and/or network latency between your ISP and the server. Then you can discuss the possible reasons for server latency and/or network latency.

It's also a good idea to discuss the networks tools, such as ping, traceroute/tracert, etc., that you can use to pinpoint the specific issue.

The solution is pretty easy, unless there is a typo in the question: The condition in the SELECT clause is "Y BETWEEN MIN(Y) AND MAX(Y)", i.e. any X regardless of Y, because all the Y values are between Ymin and Ymax inclusive. Then the problem becomes finding the MIN(X) coordinates. Note that SQL BETWEEN condition is inclusive of the boundary values.

Then you can find the Xmin in O(n) time, just linearly search through the values and then save the Xmin,Y pairs. The problems mentions the duplicates, so instead of a single Xmin,Y coordinate, we need to save all of them. Here is the code in C++11:

vector<const Point> findMinX(vector<Point>& points) {
	unsorted_map<int, vector<Point> >  x_points;
	int min = INT_MAX;
	for (const Point & point: points ) {
		if (p.X < min) min = p.X;
		x_points[pX].emplace_back(point);
	}

	return x_points[min];
}