CareerCup

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!


SOLUTION:
BFS

from heapq import heappush, heappop
import numpy as np
def minCostPath(maze):
    if len(maze) is 0 or len(maze[0]) == 0 or maze[0, 0] == -1:
        return
    
    m, n = len(maze), len(maze[0])
    distances = np.zeros(shape = (m, n))
    distances.fill(-1)
    
    heap = []
    heappush(heap, (maze[0, 0], 0, 0))
    value = maze[0, 0]
    distances[0, 0] = value
    neighbors = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while heap and distances[m - 1, n - 1] == -1:
        dist, x, y = heappop(heap)
        for neighbor in neighbors:
            i, j = x + neighbor[0], y + neighbor[1]
            if i >= 0 and j >= 0 and i < m and j < n and maze[i, j] != -1 and distances[i, j] == -1:
                heappush(heap, (maze[i, j] + dist, i, j))
                distances[i, j] = maze[i, j] + dist
    print distances
    
    if distances[m - 1][n - 1] == -1:
        return
 
    x, y = m - 1, n - 1
    path = []
    while x != 0 or y != 0:
        path.append((x, y, distances[x, y]))
        x, y = getMinParent(distances, x, y, neighbors)
    path.append((0, 0, maze[0, 0]))
    
    return path

def getMinParent(distances, x, y, neighbors):
    minDist = distances[x, y]
    fromx, fromy = None, None
    for neighbor in neighbors:
        i, j = x + neighbor[0], y + neighbor[1]
        if i >= 0 and j >= 0 and i < len(distances) and j < len(distances[0]) and distances[i, j] >= 0 and distances[i, j] <= minDist:
            fromx, fromy = i, j
            minDist = distances[i, j]
    return fromx, fromy

A tester

minCostPath(np.array([[4,2,-1,1,1],
                      [1,-1,6,7,1],
                      [4,-1,3,0,1],
                      [4,7,3,10,1],
                      [4,8,6,-1,1],
                                ]))

#4, Djkstra.

#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Label
{
    public:
        Label(int r, int c, int cost, Label* prev)
        {
            r_ = r;
            c_ = c;
            cost_ = cost;
            prev_ = prev;
        }
        int r_, c_, cost_;
        Label* prev_;
};

class LabelComparator
{
    public:
        bool operator()(const Label* l1, const Label* l2)
        {
            return l1->cost_ > l2->cost_;
        }
};

void PushLabel(priority_queue<Label*, vector<Label*>, LabelComparator>& pq, vector<vector<int>> &m, vector<Label* > &labels, int r, int c, Label* prev)
{
    if (r >= 0 &&
        r < m.size() &&
        c >= 0 &&
        c < m[r].size() &&
        m[r][c] >= 0 &&
        m[r][c] != numeric_limits<int>::max())
    {
        int base_cost = prev ? prev->cost_ : 0;
        Label *l = new Label(r, c, base_cost + m[r][c], prev);
        labels.push_back(l);
        pq.push(l);
    }
}

vector<pair<int, int>> ShortestPath(vector<vector<int>> &m, int source_r, int source_c, int target_r, int target_c)
{
    vector<pair<int, int>> path;
    vector<Label*> labels;
    priority_queue<Label*, vector<Label*>, LabelComparator> pq;
    PushLabel(pq, m, labels, source_r, source_c, NULL);
    while (!pq.empty())
    {
        Label* l = pq.top();
        pq.pop();
        if (m[l->r_][l->c_] != numeric_limits<int>::max())
        {
            m[l->r_][l->c_] = numeric_limits<int>::max();
            if (l->r_ == target_r &&
                l->c_ == target_c)
            {
                while (l)
                {
                    path.push_back(pair<int, int>(l->r_, l->c_));
                    l = l->prev_;
                }
                reverse(path.begin(), path.end());
                break;
            }
            PushLabel(pq, m, labels, l->r_ + 1, l->c_, l);
            PushLabel(pq, m, labels, l->r_ - 1, l->c_, l);
            PushLabel(pq, m, labels, l->r_, l->c_ + 1, l);
            PushLabel(pq, m, labels, l->r_, l->c_ - 1, l);
        }
    }
    for (auto l : labels)
    {
        delete l;
    }
    return path;
}

int main()
{
    vector<vector<int>> m = {
        { 1, -1, 6, 7, 1 },
        { 4, -1, 3, 0, 1 },
        { 4, 7, 3, 10, 1 },
        { 4, 8, 6, -1, 1 }
    };
    vector<pair<int, int>> path = ShortestPath(m, 0, 0, m.size() - 1, m[0].size() - 1);
    for (auto p : path)
    {
        cout << "(" << p.first << "," << p.second << ")=>";
    }
    cout << "\n";
    return 0;
}

any java code or simple explanation at least?