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
Followup : 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;
}
}

mrsurajpoudel.wordpress.com
January 09, 2017 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";
}

mrsurajpoudel.wordpress.com
November 18, 2016 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);
}

mrsurajpoudel.wordpress.com
October 04, 2016 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;
}

mrsurajpoudel.wordpress.com
September 17, 2016 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 ? " " : "");
}
}

mrsurajpoudel.wordpress.com
August 24, 2016 @djway Did the interviewer mention that the graph didn't have cycles?
 mrsurajpoudel.wordpress.com August 19, 2016pseudocode
// 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);
}

mrsurajpoudel.wordpress.com
August 10, 2016 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;
}

mrsurajpoudel.wordpress.com
July 31, 2016 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;
}

mrsurajpoudel.wordpress.com
July 22, 2016 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";
}

mrsurajpoudel.wordpress.com
June 13, 2016 Can use Breadth First Search to find the connectivity between vertices in O(N).
Use improved UnionFind 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);
}
}

mrsurajpoudel.wordpress.com
May 04, 2015 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
November 20, 2014 Open Chat in New Window
 mrsurajpoudel.wordpress.com February 05, 2017