BitGo Interview Experience
Applied online via linkedin
1.) Round:
Coderbyte round : 2 questions in option given,
a.) Array
b.) String
I choose array & below question was given
given string array input with child parent relationship. determine if it can form valid binary tree.
Return string “true” / “false”.
Coderbyte : Array challenge : valid binary tree
given string array input with child parent relationship. determine if it can form valid binary tree.
Return string "true" / "false".
eg :
input: { (4,2) , (7,4) , (38,4) , (11,38) , (1,38) }
output: "true"
2
/
4
/ \
7 38
/ \
11 1
input: { (1,2) , (7,2) , (3,2) }
output: "false"other test cases which I identified are below
1.) input: { "(4,2)" , "(7,4)" , "(38,4)" , "(11,38)" , "(1,38)" }
output: "true"
2
/
4
/ \
7 38
/ \
11 1
2.) input: { (1,2) , (7,2) , (3,2) }
output: "false"
2
/\ \
1 7 3
3.) input: { "(11,38)" , "(7,41)" ,"(1,38)" , "(38,41)" ,"(5,2)" ,"(41,2)","(15,87)","(17,87)" }
output: "false"
2
/ \
41 5
/ \
7 38
/ \
11 1
87
/\
15 17
4.) input: { "(11,38)", "(1,87)" , "(7,41)" ,"(1,38)" ,"(7,41)" , "(38,41)" ,"(87,5)" ,"(5,2)" ,"(41,2)" }
output: "false"
2
/ \
41 5
/ \ \
7 38 87
/ \ /
11 1
5.) input: { "(41,2)", "(2,5)" , "(5,38)" , "(38,41)" }
output: "false"
2
/ \
41 5
\ /
38
Below is my C++ solution
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<iostream>
using namespace std;
bool isConnectedNoCycleGraph(string startNode , set<string> nodesBT , map<string , vector<string>> parentChild){
queue<string> nodeQ;
set<string> visited;
nodeQ.push(startNode);
while( !nodeQ.empty() ){
string front = nodeQ.front();
nodeQ.pop();
if( visited.find(front) != visited.end() ){
cout<<" cycle detected \n";
return false ; // cycle exists;
}
visited.insert(front);
vector<string> childNodes = parentChild[front];
for(string childNode : childNodes){
nodeQ.push(childNode);
}
}
//if all nodes visited then connected else disconnedted
if(visited != nodesBT){
cout<<" nodes not reachable \n";
return false;
}
return true ;
}
string getRootNode(map<string , int> parentCount, set<string> nodesBT ){
for(string node : nodesBT){
if( parentCount.find(node) == parentCount.end() ){
return node;
}
}
cout<<" not able to find root, cycle is der \n";
return "";
}
string isValidBinaryTree(string inputString[] , int len){
map<string , int> childCount , parentCount ;
map<string , vector<string>> parentChild;
set<string> nodesBT;
for(int i = 0 ; i < len ; i++){
string node = inputString[i]; //(4,2)
int commaPosition = node.find(","); // node.find(',');
string child = node.substr(1 , commaPosition-1); // -1 because charcter comma not included , ( is excluded as we are startung from 1 "(," not needed to include
string parent = node.substr(commaPosition+1 , (node.size() - commaPosition -2 ) );
//cout<<"child = ["<<child <<"] len=["<<node.size()<<"] coma=["<<commaPosition<<"]...parent=["<<parent<<"]"<<endl;
childCount[parent]++;
parentCount[child]++;
if(childCount[parent] > 2 || parentCount[child] > 1){
// cout<<" no of child parent propery didn;t matched childCount= ["<<childCount[parent]<<"] parentCount=["<<parentCount[child]<<"]\n";
return "false";
}
nodesBT.insert(child);
nodesBT.insert(parent);
parentChild[parent].push_back(child);
}
// root of the tree node with no parent;
string rootNode = getRootNode(parentCount , nodesBT);
//check if no cycle & connected
if( rootNode.size() == 0 || !isConnectedNoCycleGraph(rootNode , nodesBT , parentChild) ){
return "false";
}
return "true";
}
int main(){
//int inputString[] = getInputStringForQuestion();
//string inputString[] = { "(4,2)" , "(7,4)" , "(38,4)" , "(11,38)" , "(1,38)" }; // true
// string inputString[] = { "(11,38)" , "(7,41)" ,"(1,38)" , "(38,41)" ,"(5,2)" ,"(41,2)","(15,87)","(17,87)" }; // false node not connected
// string inputString[] = { "(1,2)" , "(7,2)" , "(3,2)" };
// string inputString[] = { "(11,38)", "(1,87)" , "(7,41)" ,"(1,38)" ,"(7,41)" , "(38,41)" ,"(87,5)" ,"(5,2)" ,"(41,2)" };
string inputString[] = { "(41,2)", "(2,5)" , "(5,38)" , "(38,41)" };
cout<<isValidBinaryTree(inputString , sizeof(inputString)/sizeof(inputString[0]))<<endl ;
return 0;
}
2.) Round Two : DSA question on coderbyte.
The interviewer was helpful and helped me to run the program by rectifying mistakes like node pointing back to prev or next. Overall it was comfortable to interact and code.
LRU cache implementation (coderbyte 45 min timer)My solution:
#include <iostream>
#include <string>
#include <map>
using namespace std;
struct dL{
dL *prev = NULL, *next = NULL;
string c ;
};
dL *head = NULL, *tail = NULL;
dL* insertChar(string c){
if(head == NULL){
head = new dL();
head->c = c;
tail = head ;
}else{
dL* node = new dL();
node->c = c;
head->prev = node;
node->next = head;
head = node;
}
return head;
}
void removeLastElement(){
if(tail != NULL){
dL* node = tail;
tail = tail->prev;
tail->next = NULL;
delete(node);
}
}
void updatePriority(dL *node){
if(node == head){
return;
}
node->prev->next = node->next;
if(node == tail ){
tail = node->prev;
}else{
node->next->prev = node->prev;
}
node->prev = NULL;
node->next = head;
head->prev = node;
head = node;
}
string ArrayChallenge(string str[], int arrLength , int cacheSize) {
map<string , dL*> mp;
for(int i = 0 ; i < arrLength ; i++){
//cout<<str[i]<<"...."<<endl;
if( mp.find(str[i]) == mp.end() ){
if(mp.size() >= cacheSize){
string c = tail->c;
removeLastElement();
map<string,dL*>::iterator it = mp.find(c);
mp.erase(it);
}
dL* nodeValue = insertChar( str[i] );
mp[str[i]] = nodeValue;
}else{
updatePriority(mp[str[i]]);
}
}
string ans = "";
while(head != NULL){
ans = head->c + "-" + ans;
head = head->next;
}
return ans.substr(0, ans.size()-1);
}
int main(void) {
// keep this function call here
string A[] = {"A", "B", "C", "D", "A", "E", "D", "Z" };
int arrLength = sizeof(A) / sizeof(*A);
cout << ArrayChallenge(A, arrLength , 5);
return 0;
}3.) Round 3 (Machine Coding Round)
1. In-Memory Key Value (KV) Store
Design and implement an in-memory key value datastore. This datastore should be able to support some basic operations such as Get, Set and Delete for string keys and any values.
I would like to see test cases as well as implementation code.
You can assume that the input operations are always valid, but the key to operate on may be non-existent. We won’t worry about concurrent access to the database. You can handle errors however you think is best.
Let’s start with the data structure of this key value store. Implement methods for Get, Set and Delete.
Support Transactions, multiple transactions
A transaction is created with the Begin command and creates a context for the other operations to happen. Until the active transaction is committed using the Commit command, those operations do not persist. And, the Rollback command throws away any changes made by those operations in the context of the active transaction.
Commit() and Rollback() will only happen when inside a transaction.
Note: We won’t worry about concurrency for this part of the question.
——> Add On after the above question. Nested Transaction?
Add support for transactions - Begin, Commit and Rollback.
