Applied to SDE2 position through referral.
First was online screening test consisting of 2 questions. I forgot the questions, but both questions are available in Leetcode discuss forum.
Round 1:
I was asked 815. Bus Routes problem. There are so many great solutions are available in leetcode.
Round 2
We are a currency exchange that maintains the current exchange rates between currencies. A user can come to us with some amount in one currency and request the equivalent amount in a different currency. Given a list of exchange rates between currencies, write a function that calculates currency rate between any 2 currencies.
Example -
(GBP, EUR, 10) - read as "1 GBP equals 10 EUR"
(EUR, USD, 1.1) - "1 EUR equals 1.1 USD"
(10 GBP, USD) => ? - "10 GBP equals how many USD?"
Answer: 110
Explanation: 10 GBP = 10 x (10 EUR) = 10 x (10 x (1.1 USD)) = 110 USD
Example 2 -
(GBP, EUR, 10) - read as "1 GBP equals 10 EUR"
(EUR, USD, 1.1) - "1 EUR equals 1.1 USD"
(USD, JPY, 108.3)
(10 GBP, JPY) => ? - "10 GBP equals how many JPY?"
Answer: 11913
Explanation: 10 GBP = 10 x (10 EUR) = 10 x (10 x (1.1 USD)) = 10 x (10 x(1.1 x (108.336 JPY))) = 11913 JPY
I have the solution with me as well. Posting here :
#include<bits/stdc++.h>
using namespace std;
template<typename T>
void printVector(vector<T>& elements) {
for(const auto& element: elements) cout << element << " ";
cout << endl;
}
vector<double> getExchangeRates(vector<tuple<string,string,double>>& rates, vector<tuple<string,string,double>>& queries) {
unordered_map<string, vector<pair<string,double>>> graph;
for(const auto& [src, dest, exRate]: rates) {
graph[src].push_back({dest, exRate});
graph[dest].push_back({src, 1 / exRate});
}
unordered_set<string> visited;
unordered_map<string,double> conversionRate;
for(const auto& [srcNode, _]: graph) {
if (visited.count(srcNode)) continue;
visited.insert(srcNode);
queue<pair<string, double>> tracker;
tracker.push({srcNode, 1});
while(!tracker.empty()) {
auto [currNode, exRate] = tracker.front(); tracker.pop();
conversionRate[currNode] = exRate;
for(auto& [childNode, childExRate]: graph[currNode]) {
if (visited.count(childNode)) continue;
visited.insert(childNode);
tracker.push({childNode, exRate * childExRate});
}
}
}
vector<double> ans;
for(const auto& [src, dest, quantity]: queries) {
// if src and dest are not connected, exchange rate doesn't exist
if (!conversionRate.count(src) or !conversionRate.count(dest)) ans.push_back(-1);
// exchange of src to dest = exchange of src to middle * exchange of middle to dest
// = 1 / exchange of middle to src * exchange of middle to dest
double exchangeValue = 1 / conversionRate[src] * conversionRate[dest];
ans.push_back(exchangeValue * quantity);
}
return ans;
}
int main() {
vector<tuple<string,string,double>> rates{{"GBP","EUR",10},{"EUR","USD",1.1},{"USD","JPY",108.3}};
vector<tuple<string,string,double>> queries{{"GBP","USD",1},{"EUR","JPY",2}};
auto ans = getExchangeRates(rates, queries);
printVector(ans);
}Follow up question:
what if graph is not connected? ans - need to maintain connected components, then identify if 2 nodes are connected, exchange rate is possible otherwise -1
Round 3:
It was a bar raiser round. I was asked to design search of application logs. Billions of logs need to be captured and when a word is entered as an input, relevant logs will be matched and given as output.
Constraint : 1G memory, single machine
Round 4
It was Hiring manager round. Questions were pretty much from Amazon LP.
Strong positive feedback for Round 1, Round 2 and Round 4. But there was mixed feedback for Round 3.
I was downleveled from L4 to L3. I rejected as I already had an offer for SDE2 position.