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";
}``````

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