Dropbox Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

Are you saying you want lines L which are paths from column 0 to column m-1 in a matrix where adjacent pixels are m[c+1][r-1], m[c+1][r], m[c+1][r+1] from pixel m[c][r] if that pixel is 1. I assume with tallest line you mean the line l of L that reaches the highest point, that is minimum r (row), if we assume upper-left is r=0, c=0? If there are multiple with the same minimum r, pick the one that has most points on that height.

- Chris December 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let's assume my interpretation is correct (see my other post), the solution is using a DFS-like approach. It-s more efficient than BFS because I expect a route to be found starting on a early row and if there is a choice, the upper row wins if there is a path to the right through that element. So, if I run BFS it will use that very primitive heuristic to expand the upper routes first.

A BFS, opposed to that, will explore all routes simultaneously looking for a shortest path. So it will expand a lot of routes it doesn't need to if the desired route doesn't start from the very bottom. How ever, worst case scenario is the same, has the same big-O properties.

That would be O(m*n) time and O(m*n) space complexity.

#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

// return the sequence of rows to be choosen if columns start at 0 and end at n-1
vector<int> find_highest_path(const vector<vector<bool>>& matrix)
{
	vector<int> path;
	int m = matrix.size();
	if (m == 0) return path; 
	int n = matrix[0].size();
	if (n == 0) return path;
	vector<vector<int>> parent(m, vector<int>(n, -1));

	int lr = -1;
	for (int i = 0; lr == -1 && i < m; ++i) {
		stack<pair<int, int>> s;
		if (!matrix[i][0]) continue;
		s.push({ i, 0 });
		while (!s.empty()) {
			int r = s.top().first;
			int c = s.top().second;
			s.pop();
			if (c == n - 1) {
				lr = r;
				break;
			} 
			for (int nr = min(r + 1, m - 1); nr >= max(0, r - 1); --nr) {
				if (matrix[nr][c + 1] && parent[nr][c + 1] == -1) {
					parent[nr][c + 1] = r;
					s.push({nr, c + 1});
				}
			}
		}
	}

	// back track path
	int c = n - 1;
	while (lr != -1) {
		path.push_back(lr);
		lr = parent[lr][c];
		c--;
	}
	reverse(path.begin(), path.end());
	return path;
}

template<class T>
ostream& operator <<(ostream& os, const vector<T>& c)
{
	os << "{";
	bool first = true;
	for (auto e : c) {
		if (!first) os << "," << e;
		else os << e;
		first = false;
	}
	os << "}";
	return os;
}

int main()
{
	cout << find_highest_path(
	{
		{ 0,0,1,1,0,1,1,0,0,0,0,0 },
		{ 1,1,0,0,1,0,1,1,1,1,0,1 },
		{ 0,0,1,0,0,0,0,1,0,0,1,0 },
		{ 1,1,1,1,0,0,1,1,0,1,0,0 },
		{ 0,0,0,1,1,1,0,1,1,0,0,0 },
		{ 0,0,1,0,0,1,0,0,0,1,1,1 },
		{ 1,0,0,0,0,0,1,1,1,1,1,1 },
	}) << endl; // should return 1,1,0,0,1,0,0,1,1,1,2,1

	cout << find_highest_path(
	{
		{0,0,1,1,0,1,1,0,0,1,0,0},
		{1,1,0,0,1,0,0,1,1,0,0,1},
		{0,0,1,0,0,0,0,1,0,0,1,0},
		{1,1,1,1,0,0,1,1,0,1,0,0},
		{0,0,0,1,1,1,0,1,1,0,0,0},
		{0,0,1,0,0,1,0,0,0,1,1,1},
		{1,0,0,0,0,0,1,1,1,1,1,1},
	}) << endl; // should return 1,1,2,3,4,4,3,3,4,3,2,1
}

- Chris December 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK Hi Chris based on my description your interpretation is right but interviewer said that numbers in the matrix represent the 'Goodness' factor of how confident we are about this line. Thats where it got fuzzy for me. Anyways the problem we ended up solving was much more simpler.

Basically from pixel m[c][r] you need to pick the max value of m[c+1][r-1], m[c+1][r], m[c+1][r+1] . This will repeat for every cell in 0th column. Once you reach the end then on this path you will pick the smallest pixel value. After doing this for all cells in 0th column you will have R total values and from these you pick the smallest one which will be your ans.

To achieve above I mentioned this can be done by greedy approach to which he said there is better way that if you can actually work your way backwards from nth column to 0th column (actually this doesn't make any sense to me as it makes no difference if you start from the 0th column or nth column)

Anyways I got reject, I think mostly because I fail to understand what exactly was the problem

- sachin323 December 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@sachin323: You should pick the path with smallest p, where p is an element of each path from (0,{0..n-1}) to (m-1,x) where (c[i+1], {r[j+1], r[j-1], r[j]} is the largest value). This sounds strange... surely possible, but what for? I see no connection to tallest horizon.

Anyway, if that's the task, I'd scan the matrix for minimal value that can be reached from any of the 3 left hand pixels. Then I know through which pixel the path goes. From there I'd expand right and left: O(n*m), no extra space, except to store the path.

I assume he wanted something else, like detecting a couture, like maybe an upper edge of a scanned page or so... but I can't see that in here.

anyway, sorry to hear it didn't work out this time.

- Chris December 04, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More