math.matt
BAN USER 2of 2 votes
AnswersGiven an NxM (N rows and M columns) integer matrix with nonnegative values (0..MAX_INT inclusive). What is the maximum sum from going top left (0, 0) to bottom right (N1, M1) ? The condition is that when you're at point (p, q), you can only move to either right (p, q+1) or down (p+1, q).
 math.matt in United States
Expected time complexity O(N*M)
Expected space complexity O(N+M)
From the space complexity it looks like there is a DP solution, but I couldn't figure it out. Report Duplicate  Flag  PURGE
Samsung Java Developer Matrix
@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 NPComplete. 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 pseudopolynomial time dynamic programming solution. For implementation, you can Google "Subset Sum Problem".
+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.
 math.matt May 23, 2013Short 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];
}

math.matt
May 22, 2013 Open Chat in New Window
If there is a row with all zeros, then there can't be a column with all 1s.
 math.matt September 11, 2013