mrsurajpoudel.wordpress.com
BAN USER- 0of 0 votes
AnswerYou have a web scraper that pulls car listing from Craiglist and other web sites. Design the system and API for the users to read the data.
- mrsurajpoudel.wordpress.com in United States
Follow-up : How will you scale your system?| Report Duplicate | Flag | PURGE
Triplebyte Software Engineer System Design - 0of 0 votes
AnswersDesign a cache for larger objects(>1MB) using memcached. You need to use API provided by memcached(which has constraint of not using more than 1MB of data per key). API are
- mrsurajpoudel.wordpress.com in United Statesmemcache.set(key, value) memcache.get(key)
| Report Duplicate | Flag | PURGE
Triplebyte Software Engineer System Design - 0of 0 votes
AnswersWrite a program that reads a maze from a file and outputs from 'X' to 'O'. Example,
- mrsurajpoudel.wordpress.com in United StatesInput: ########## X # # # # # # # # O ########## Output: ########## +++#+++++# # +#+ # +# # +++ # ++ ##########
| Report Duplicate | Flag | PURGE
Software Engineer Algorithm
I think encoding the path traversal while finding the max height can be useful information.
pair<int, string> longestPath(Node* node) {
if(!node) return make_pair(0, "");
auto L = longestPath(node->left);
auto R = longestPath(node->right);
if(L.first < R.first) return make_pair(R.first + 1, "R" + R.second);
else return make_pair(L.first + 1, "L" + L.second);
}
void printLongestPath(Node* node){
auto P = longestPath(node);
Node* n = node;
for(int i = 0; i < P.second.length(); i++) {
cout << n->val <<" ";
if(P.second[i] == 'L') n = n->left;
else n = n->right;
}
}
unordered_set<int> possible_sums(int i, vector<int>& coins, vector<int>& quantity) {
if(i == int(coins.size())) return unordered_set<int>{0};
auto remaining = possible_sums(i + 1, coins, quantity);
unordered_set<int> ret_set;
for(int q = 0; q <= quantity[i]; q++) {
for(int next_sum : remaining) {
int curr = next_sum + q * coins[i];
if(ret_set.find(curr) == ret_set.end()) ret_set.insert(curr);
}
}
return ret_set;
}
int main(int argc, char** argv) {
vector<int> coins{10, 50, 100, 500};
vector<int> quantity{5, 3, 2, 2};
auto ret = possible_sums(0, coins, quantity);
for(int r : ret) {
cout << r << " ";
}
cout << "\n";
}
What does it mean by longest sequence? Does it necessarily mean longest path in which case its always leaf to leaf?
- mrsurajpoudel.wordpress.com October 17, 2016By an array of "1 billon number" do you mean numbers from 1 to 10^9 where few 100 (O(10^3)) are missing?
- mrsurajpoudel.wordpress.com October 08, 2016Node* leaf_from_tree(stack<Node*>& inorder_tree) {
while(!inorder_tree.empty()) {
Node *top = inorder_tree.top();
inorder_tree.pop();
if( top->right == NULL && top->left == NULL) return top;
else if(top->right != NULL) {
Node *node = top->right;
while( node != NULL) {
inorder_tree.push(node);
node = node->left;
}
}
}
return NULL;
}
void initialize(Node* root, stack<Node*>& st) {
Node *node = root;
while(node != NULL) {
st.push(node);
node = node->left;
}
}
pair<int, int> first_unmatched_leaves(Node* root1, Node* root2) {
stack<Node*> tree1; stack<Node*> tree2;
initialize(root1, tree1); initialize(root2, tree2);
Node *leaf1, *leaf2;
do{
leaf1 = leaf_from_tree(tree1);
leaf2 = leaf_from_tree(tree2);
if(leaf1->value != leaf2->value) return make_pair(leaf1->value, leaf2->value);
}while(leaf1 != NULL && leaf2 != NULL);
return make_pair(-1, -1);
}
vector<int> merge_k_elements(vector<int>& a, vector<int>& b, size_t k) {
assert( a.size() + b.size() >= k );
vector<int> merged_vec(k);
size_t i = 0, // a's iterator
j = 0; // b's iterator
while( i + j < k ){
if( j >= b.size() || ( i < a.size() && a[i] <= b[j] ) ) {
merged_vec[i + j] = a[i];
i++;
}
else {
merged_vec[i + j] = b[j];
j++;
}
}
return merged_vec;
}
iterative approach:
void reconstruct(string sentence, unordered_set<string>& dict)
{
vector<int> dp(sentence.size() + 1, -1);
dp[0] = 0;
for (int i = 1; i <= sentence.size(); i++) {
for (int j = 0; j < i; j++) {
if (dict.find(sentence.substr(j, i - j)) != dict.end() && dp[j] != -1) {
dp[i] = j;
}
}
}
int i = sentence.size();
vector<string> words;
while (i != 0) {
words.push_back(sentence.substr(dp[i], i - dp[i]));
i = dp[i];
}
for (int j = words.size() - 1; j >= 0; j--) {
cout << words[j] << (j != 0 ? " " : "");
}
}
@djway Did the interviewer mention that the graph didn't have cycles?
- mrsurajpoudel.wordpress.com August 19, 2016pseudo-code
// preprocess your input graph to the following structure
// node -> hash set of neighbors
// hash set to enable amortized O(1) deletions
vector<unordered_set<int>> topology(n);
vector<int> metadata(n); // contains the population count
vector<int> current_leaf_set;
int global_sum = 0;
for each node id i in topology{
if(topology[i].size() == 1 ) current_leaf_set.push_back(i);
global_sum += metadata[i];
}
int i = 0;
vector<int> sum(n), max(n); // initialize them to zero
while(i < current_leaf_set.size()){
int node_id = current_leaf_set[i++];
std::cout << node_id << " : " << (std::max( max[node_id], global_sum - metadata[node_id] - sum[node_id] )) << "\n";
if( topology[node_id].size() == 0 ) continue; // Thanks @helloru
int next_node = *(topology[node_id].begin()); // will only have one neighbor
sum[next_node] += ( metadata[node_id] + sum[node_id]);
max[next_node] = std::max( max[next_node], ( metadata[node_id] + sum[node_id]) );
topology[next_node].erase(node_id);
if( topology[next_node].size() == 1 ) current_leaf_set.push_back(next_node);
}
uint64_t count_stepping_numbers(int N) {
uint64_t arr[2][12];
for(int i = 0; i < 12; i++) { arr[0][i] = 0; arr[1][j] = 0; }
uint64_t sum = 0;
for(int i = 2; i <= 10; i++) { arr[0][i] = 1; sum++;}
for(int i = 1; i < N; i++) {
sum = 0;
for(int j = 1; j <= 10; j++) {
arr[i & 1][j] = arr[ (i & 1) ^ 1 ][j - 1] + arr[(i & 1) ^ 1][j + 1];
sum += arr[i & 1][j];
}
}
return sum;
}
Assume that by removing an element A_k from [ A_1, A_2,......A_n] it is possible to have two sets S_1 and S_2 such that len(S_1) = len(S_2) && ( Sum(S_1) - Sum(S_2)) == 0.Now lets assume that we next remove A_r [ r != k ]. Then (Sum(S_1) - Sum(S_2)) + (A_k - A_r) should also be equal to zero which is only possible if (A_k - A_r) == 0. Since k is arbitrary and r can be any other elements, so all the elements of the array must be equal for it to hold for removing any elements.
So the code follows as
bool check(vector<int>& v) {
for(int i = 0; i < v.size() - 1; i++){
if(v[i] != v[i + 1]) return false;
}
return true;
}
Isn't it possible to remove 1 and split [2, 2] into two sets of equal length with the same length (i.e [2] and [2] ) in case of Input [1, 2, 2]? Or do you mean that it should be left and the right of the number removed that should have equal sum and equal length?
- mrsurajpoudel.wordpress.com July 22, 20161. Generate the Prefix Sum Array starting A1, A1 + A2, A1 + A2 + A3......
vector<int> prefix_sum;
2. auto itr = std::lower_bound(prefix_sum.begin(), prefix_sum.end(), l )
3. box number = (itr - prefix_sum.begin() + 1)
Complexity per query = O( log<base 2> N )
1. Use MaxHeap(heap_id = 0) for current 5 taxis with minimum distances from (p, q) and MinHeap(heap_id=1) for the rest taxis.
2. Keep metadata information for taxis e.g. taxi_id --> heap_id --> index_location
3. Compare updated taxi_id distance with top of heap with id ( 1 - heap_id ) to either switch the taxi_id to different heap or to update position inside the same heap. O(NLogN) initial heap creation and then O(logN) for each update.
1. HashMap to reference the hotel_id to its BinarySearchTree node.
2. BinarySearch Tree(RB Tree implementation) with average score as the key.
add_hotel h
- node* n = map.get(h.id)
- tree.erase(n)
- n.count++
- n.score_sum += h.score
- tree.insert(n)
get_list(avg_score):
- Binary Search to get to first node greater than equal to avg_score
- Traverse through the remaining nodes in the right to get the list of ids
- O(log n + k) [ k is the size of output]
long long approx_cubth_root( long long n) {
long long min = 1, max = n;
long long mid;
while( min < max ) {
mid = min + ( max - min) / 2;
if( mid * mid * mid == n) return mid;
else if( mid * mid * mid < n ) min = mid + 1;
else max = mid - 1;
}
if(min * min * min < n ) return min;
else return max;
}
void print_good_numbers(long long n) {
long long cubth = approx_cubth_root(n);
unordered_set<long long> level1;
set<long long> level2;
for(long long i = 1; i <= cubth + 1; i++) {
for( long long j = i; j <= cubth + 1; j++ ) {
long long cur = i * i * i + j * j * j;
if( cur <= n ) {
if( level1.find( cur) == level1.end()){
level1.insert( cur );
} else{
level1.erase(cur);
level2.insert(cur);
}
}
}
}
for(auto itr = level2.begin(); itr != level2.end(); itr++) {
cout << *itr << " ";
}
cout << "\n";
}
Can use Breadth First Search to find the connectivity between vertices in O(N).
Use improved Union-Find to find connectivity in O(log N).
Key maps to a binary search tree in HashMap. First the key is mapped to a binary search tree and then the time is searched in the binary search tree to find either the time or smallest time less than the searched time. The skeleton of the design is presented below:
BinarySearchTree<K, V>{
.......... // balanced binary search tree with K as key and V as the value
}
TimeStampHashMap<K, V>{
Map<K, BinarySearchTree<Float, V>> keyToBSTMap;
V get(K k, Float time){
return keyToBSTMap.get(k).binarySearch(time).getValue();
}
void put(K k , Float time, V value){
keyToBSTMap.get(k).insert(time, value);
}
}
doesn't work for array = [5 1 3] and val = 3
- mrsurajpoudel.wordpress.com February 10, 2015@ ranan.fraer : Could you explain this for A = 5 where the smallest number divisible by A with only ones and zeroes is "10" ?
- mrsurajpoudel.wordpress.com February 07, 2015Could u elaborate? I could only think of a O(n^2) solution with suffix tree. But this is easily achievable with DP in O(n^2).
- mrsurajpoudel.wordpress.com December 02, 2014What if the longest substring palindrome is of odd length?
- mrsurajpoudel.wordpress.com November 30, 2014what if b represents for an empty string? then a equals "redblue" which makes sense right?
- mrsurajpoudel.wordpress.com November 27, 2014Naive approach :( O(n^2)
public class PalindromeAddFront{
public static void main(String[] args){
String str = "racexyzart";
int length = lengthToMakePalindrome(str);
StringBuilder sbr = new StringBuilder(str.substring(str.length() - length));
sbr.reverse().append(str);
System.out.println(sbr);
}
public static int lengthToMakePalindrome(String str){
int i = 0, j = str.length() - 1;
int count = 0;
while(i < j){
if(str.charAt(i) == str.charAt(j)){
i++;
j--;
}else{
j += (i - 1);
i = 0;
count++;
}
}
return count;
}
}
- mrsurajpoudel.wordpress.com February 05, 2017