## Google Interview Question for SDETs

Country: United States

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

``````/**
* The algorithm takes O(k) space (for PriorityQueue and HashMap).
* The runtime is (O (k) + O((n - k) log k) to build up the heap and O(n) to iterate through the length of the matrix.
*/
public int findShortestPath(@Nonnull int[][] matrix, int k) {
if (matrix.length == 0 || matrix[0].length == 0 || matrix[0].length != matrix.length) {
return -1;
}
PriorityQueue<Integer> minHeapForMaxDistance = new PriorityQueue<>(k);

int currentDistance = 0;
// determine the longest distances that will be skipped later. The longest distance will be added
// into the min heap. If the current distance is > then the min, it will be replaced.
// This takes (O (k) + O((n - k) log k)
for (int i = 1; i < matrix.length; ++i) {
currentDistance = matrix[i - 1][i];
while (minHeapForMaxDistance.size() >= k &&
minHeapForMaxDistance.peek() < currentDistance) {
minHeapForMaxDistance.poll();
}

if (minHeapForMaxDistance.size() < k) {
minHeapForMaxDistance.offer(currentDistance);
}
}

int shortestPath = 0;
// after we found all max distances, we put them into a HashMap. The key is the max distance and the value the
// amount of max distances in the matrix. s represents source, t represents target position.
Map<Integer, Integer> maxDistances = from(minHeapForMaxDistance);
for (int s = 0, t = 1; t < matrix.length; ++t) {
currentDistance = matrix[s][t];

// found a max distance. Skip it. e.g. the path from a-800->b-300->c and a-400->c. B will be skipped
// and a->c will be used.
if (maxDistances.containsKey(currentDistance) &&
maxDistances.get(currentDistance) > 0) {
maxDistances.put(currentDistance, maxDistances.get(currentDistance) - 1);
} else {
shortestPath += currentDistance;
s = t;
}
}
return shortestPath;
}

/**
* Converts the priority queue to the HashMap. The key is the distance, the value the amount of the distance.
*/
private Map<Integer, Integer> from(PriorityQueue<Integer> minHeapForMaxDistances) {
Map<Integer, Integer> maxDistances = new HashMap<>();

int current;
while (!minHeapForMaxDistances.isEmpty()) {
current = minHeapForMaxDistances.poll();
if (maxDistances.containsKey(current)) {
maxDistances.put(current, maxDistances.get(current) + 1);
} else {
maxDistances.put(current, 1);
}
}
return maxDistances;
}``````

EDIT: On second thought this approach might not work in case we have the same max distance more then k times. Then there is a difference how we follow the path

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

Top down dynamic programming. O(n^2 * k) time and O(n^3 * k) space.

``````#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Path {
public:
Path()
{
distance_ = 0;
}
vector<int> cities_;
int distance_;
};

Path ShortestPath(int n, vector<vector<int>> const &distances, unordered_map<uint64_t, Path> &memo,
int k, int16_t idx = 0, int16_t prev_idx = -1)
{
if (idx < 0 ||
idx >= n)
{
return Path();
}

uint64_t memo_key = (static_cast<uint64_t>(k) << 32) | (static_cast<uint32_t>(idx) << 16) | prev_idx;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}

Path path = ShortestPath(n, distances, memo, k, idx + 1, idx);
path.cities_.push_back(idx);
if (prev_idx != -1) {
path.distance_ += distances[prev_idx][idx];
}
if (k > 0) {
Path skip = ShortestPath(n, distances, memo, k - 1, idx + 1, prev_idx);
if (skip.distance_ < path.distance_) {
path = skip;
}
}

memo[memo_key] = path;
return path;
}

int main()
{
int n = 5;
int k = 2;

vector<vector<int>> distances(n, vector<int>(n, numeric_limits<int>::max()));
distances[0][1] = 2;
distances[0][2] = 9;
distances[0][3] = 7;
distances[0][4] = 5;
distances[1][2] = 7;
distances[1][3] = 1;
distances[1][4] = 5;
distances[2][3] = 1;
distances[2][4] = 8;
distances[3][4] = 1;

unordered_map<uint64_t, Path> memo;
Path path = ShortestPath(n, distances, memo, k);

cout << path.distance_ << ": ";
for (int i = path.cities_.size() - 1; i >= 0; --i) {
cout << path.cities_[i] << "->";
}
cout << "\n";
}``````

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.

### 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.