Google Interview Question for SDE1s


Country: United States




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

The paths from one checkpoint to the next do not need to be counted, since the number of different paths is simply the binomial coefficients nCr, where n is the total number of steps required (Manhattan distance) r is either the number of down steps or the number of right steps.

I could not figure out any reason why the dimensions of the grid would be useful (surely you don't need to check whether any given points are literally outside the entire grid, do you?)

def binom(n, r):
    return factorial(n)/factorial(r)/factorial(n-r)

        
def count_paths(s, f, plist):
    """
    s: (r, c) pair starting point
    f: (r, c) pair end point
    plist: list of pairs NOT INCLUDING s and f
    """
    plist.sort()  #sort the checkpoints
    plist = [s] + plist + [f] #put start and end at beginning and end
    for i in xrange(len(plist) - 1):
        if plist[i+1][1] < plist[i][1] or plist[i+1][0] < plist[i][0]: #if any checkpoint is to the left of or above the previous point, return 0
            return 0
    ans = 1
    for i in xrange(len(plist) - 1):
        downs = plist[i+1][0] - plist[i][0]
        rights = plist[i+1][1] - plist[i][1]
        steps = downs + rights
        ans *= binom(steps, downs)
    return ans

test:
>>> count_paths((1,1), (5,4), [(2,1), (3,3)]) --> 9

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

My idea is to find number of paths from each point (excluding the end point) to each other point. After that, number of paths from the start point to the end point would look like:
number_of_path(start->1) * number_of_path(1->2) * number_of_path(2->3) * number_of_path(3->end) +
number_of_path(start->2) * number_of_path(2->1) * number_of_path(1->3) * number_of_path(3->end) +
and so on, using all permutations of 1, 2, 3.

This can be improved by not generating permutations that are not viable. E.g. if checkpoint 2 is located above or to the left of checkpoint 1, it doesn't make sense to generate permutations containing 1, 2, since, we can't move up or left.

Update: actually, given the constraints (moving only right and down) there is only 1 (or 0) sequence of the checkpoints in which we can visit all of them. So, we can find that sequence (actually, sorting the checkpoints by row and column), e.g. start->1->2->3->end, end then find counts for the segments of the path and multiply the counts.

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

class Perms {
	public:
		static vector<vector<int>> Get(int size)
		{
			unordered_set<int> s;
			for (int i = 0; i < size; ++i) {
				s.insert(i + 1);
			}
			vector<vector<int>> out;
			vector<int> perm;
			PermsRec(s, perm, out);
			return out;
		}

	private:
		static void PermsRec(unordered_set<int> &s, vector<int> &perm, vector<vector<int>> &out)
		{
			if (s.empty()) {
				if (!perm.empty()) {
					out.push_back(perm);
				}
				return;
			}
			vector<int> keys;
			keys.insert(keys.end(), s.begin(), s.end());
			for (int n : keys) {
				perm.push_back(n);
				s.erase(n);
				PermsRec(s, perm, out);
				s.insert(n);
				perm.pop_back();
			}
		}
};

class Point {
	public:
		Point(int r, int c)
		{
			r_ = r;
			c_ = c;
		}
		int16_t r_, c_;
};

uint64_t Key(int from_idx, int to_idx, vector<Point> const &p)
{
	return  (static_cast<uint64_t>(p[from_idx].r_) << 48) |
			(static_cast<uint64_t>(p[from_idx].c_) << 32) |
			(static_cast<uint64_t>(p[to_idx].r_) << 16) |
			p[to_idx].c_;
}

void CountsFromPoint(int m, int n, vector<Point> const &p, int source_idx, unordered_map<uint64_t, uint64_t> &p_to_p_count)
{
	vector<vector<uint64_t>> dp(m, vector<uint64_t>(n, 0));
	auto &s = p[source_idx];
	dp[s.r_][s.c_] = 1;
	for (int r = s.r_; r < m; ++r) {
		for (int c = 0; c < n; ++c) {
			if (r - 1 >= 0) {
				dp[r][c] += dp[r - 1][c];
			}
			if (c - 1 >= 0) {
				dp[r][c] += dp[r][c - 1];
			}
		}
	}
	for (int i = 0; i < p.size(); ++i) {
		p_to_p_count[Key(source_idx, i, p)] = dp[p[i].r_][p[i].c_];
	}
}

uint64_t Count(int m, int n, Point source, Point target, vector<Point> const &checkpoints)
{
	vector<Point> p;
	p.push_back(source);
	p.insert(p.end(), checkpoints.begin(), checkpoints.end());
	p.push_back(target);
	unordered_map<uint64_t, uint64_t> p_to_p_count;
	for (int i = 0; i < p.size() - 1; ++i) {
		CountsFromPoint(m, n, p, i, p_to_p_count);
	}
	auto perms = Perms::Get(checkpoints.size());
	uint64_t total_count = 0;
	for (auto &perm : perms) {
		uint64_t count = p_to_p_count[Key(0, perm[0], p)];
		for (int i = 0; i + 1 < perm.size() && count != 0; ++i) {
			count *= p_to_p_count[Key(perm[i], perm[i + 1], p)];
		}
		count *= p_to_p_count[Key(perm[perm.size() - 1], p.size() - 1, p)];
		total_count += count;
	}
	return total_count;
}

int main()
{
	cout << Count(4, 4, {0, 0}, {3, 3}, {{1, 1}, {2, 2}}) << "\n";
}

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

/** I am not sure why the start and end points or width and height are needed. I think all we need is the list of points we need to encounter.  If the points are arranged so that every point is either below and or to the right of another point, then we're guaranteed that there's at least one path. Sort the points by ascending x-coordinate. If two points p1 and p2  have the same x-coordinate, the point with the larger y-coordinate should occur before the point with the lower y-coordinate. The total number of ways we can get from one point p1 to another p2 can be computed using the equation for permutation of objects with duplicate objects ( n! / r1! * r2!) where n is the total number of objects (in this case the total number of steps) and each r is the number of duplicate steps (in this case the number of vertical steps-r1! and number of horizontal steps r2!). Note n = r1 + r2. **/

public class Point implements Comparable<Point> {
	int xcoord;
	int ycoord;

	public Point(int x, int y) {
		xcoord = x;
		ycoord = y;
}

public int compare(Point p) {
	return xcoord == p.xcoord ? -1 * (ycoord - p.ycoord) : xcoord - p.xcoord
}
}


int[] factorials(int max) {
	int[] arr = new int[max + 1];
	arr[0] = 1;
	arr[1] = 1;
	for(int i = 2; i <= max; i++) {
	arr[i] = i * arr[i - 1];
}
}

public int countWays(Point[] pts) {
	if(pts == null || pts.length == 0) {
	return 0;
}
	Arrays.sort(pts);
	for(int i = 1; i < pts.length; i++) {
		if(pts[i].ycoord - pts[i - 1].ycoord >= 0) {
			return 0;
}
}

	int maxSteps = 0;
	for(int i = 1; i < pts.length; i++) {
		maxSteps = Math.max(maxSteps, pts[i].xcoord - pts[i -1].xcoord + pts[i - 1].ycoord - pts[i].ycoord)
}

int[] fArray = factorials(maxSteps);

int ways = 1;
for(int i = 1; i < pts.length; i++) {
	int horizSteps = pts[i].xcoord - pts[i - 1].xcoord + 1;
	int vertSteps = pts[i-1].ycoord - pts[i].ycoord + 1;//I am assuming pts[i - 1] is above pts[i] since vertically we have to move downwards on the grid.
	
if(horizSteps != 0 && vertSteps != 0) {
ways *= fArray[(horizSteps + vertSteps)]/ fArray[horizSteps] * factorials[verticalSteps];
	}
}
return ways;
}
	
}

/ **Time complexity: O(w*h log w*h + w + h) Space: O(w + h + wh) where w is the width of the grid and h is the height. **/

- divm01986 December 13, 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