Google Interview Question SDE1s
Country: United States
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";
}
/** 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. **/
This algorithm is based on BFS. Start from point e (end) and for each point n (neighbor) northwest of e, add 1. Repeat for each of the neighbors until reaching s.
The idea here is to find the northwest neighbors of each point dynamically using a formula. inRectangle is a simple O(v) scan but it may potentially be improved with binary search.
O(v) space, O(v^2) time
where v is the number of points.
x
s7 x2
x3 x
x1
x2 x1
e
x x
func countTheWays(points []Point, s, e Point) int {
points = inRectangle(points, s, e)
count := map[Point]int{}
q := NewQueue()
q.Push(e)
while !q.Empty() {
p := q.Pop()
for n := range inRectangle(points, s, p) {
count[n]++
q.Push(n)
}
}
return count[s]
}
func inRectangle(points []Point, tl, br Point) []Point {
result := []Point{}
for p := range points {
if p.X>=tl.X && p.X<br.X && p.Y>=tl.Y && p.Y<br.Y {
result = append(result, p)
}
}
return result
}
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 anstest:
- robshowsides December 12, 2017>>> count_paths((1,1), (5,4), [(2,1), (3,3)]) --> 9