Carbon
BAN USER- 1of 0 votes
AnswersPhone Interview:
- Carbon
The guy who interviewed me is a project leader at Bloomberg. He was very arrogant and
his english was very poor.
First he asked me to explain what I have worked on at current company. So I explained him the distributed system I built at world's 3rd best research organization. The discussion went on for 30 minutes and at the end He laughed at it and claimed that its not a real distributed system!
He then asked following C++ questions:
1. Can you have private destructor and private constructor ? explain your answer.
2. Can you have virtual constructor ? explain your answer.
3. What design pattern is similar to virtual constructor ?
4. Can you have vector of auto_pointer ? explain your answer.
5. is this code valid:
auto_pointer<Object> a(new Object());
auto_pointer<Object> b(new Object());
a = b;
My Answer: Yes its valid ( I checked in the book later)
but he insisted that this is invalid code! what an idiot.
If he comes on the phone to interview you, just say "No Thanks!"| Report Duplicate | Flag | PURGE
Bloomberg LP Financial Software Developer C Terminology & Trivia
- 9 Answers Whats wrong with my code! Microsoft didn't continue interview after reviewing my code !! please help
Hello Friends,
I was being interviewed by Microsoft for one of their Live groups. They asked me to send code for the following questions.
I don't find anything wrong with my code ( I intensionally left out NULL pointer checks because they were obvious and I didn't
want to pollute the code for the "review"). Could you please tell me why they have discontinued the interview process ?
1. Write function to find a string in a string i.e. strstr
2. Write code to reverse a linked list
3. How would you most efficiently return the middle node of a singly-linked list? (provide code for this solution)
4. How would you remove the duplicate characters from an array? (provide code for this solution)
- Carbon April 28, 2008#include <iostream> using namespace std; //////////////////////////////////////////////////////////////// //1. Write function to find a string in a string i.e. strstr /////////////////////////////////////////////////////////////// //KMP implementation// /* The mystrstr() function locates the first occurrence of the string str2 (excluding the terminating null character) in string str1 and returns a pointer to the located string, or a null pointer if the string is not found. If str2 points to a string with zero length (that is, the string ""), the func- tion returns str1. */ void makeTable(const char* str,int* T,int size); const char* mystrstr(const char* str1,const char* str2){ int n = strlen(str1); int m = strlen(str2); if(m==0) return str1; if(m > n) return NULL; int* T = (int*)malloc(sizeof(int)*m); makeTable(str2,T,m); int a = 0; int b = 0; int c = 0; // match count while((a + c) < n){ if(str1[a + c] == str2[c]){ c++; if(c==m){ free(T); return (str1 + a); } } else if(c==0){ a++; } else{ a += c - T[c]; c = T[c]; } } free(T); return NULL; } void makeTable(const char* str,int* T,int size){ int a = 0; int b = 0; int c = 0; T[a] = 0; for(a=1;a<size;a++){ if(str[b] == str[a]){ c++; b++; T[a] = c; continue; } else if(b > 0){ a--; } c = 0; b = 0; } } //////////////////////////////////////////////////// //2. Write code to reverse a linked list /////////////////////////////////////////////////// struct node { int val; node* next; }; void createSampleList(node** head,int size){ node* n = NULL; node* H = NULL; for(int i=0;i<size;i++){ n = new node(); n->val = i; n->next = H; H = n; } *head = H; } void printList(const node* n){ while(n!=NULL){ cout << n->val <<" "; n = n->next; } cout << endl; } /// Iterative solution //////////// void reverse(node** head){ node *Rhead = NULL; node* H = *head; while(H){ node* tmp = H->next; H->next = Rhead; Rhead = H; H = tmp; } *head = Rhead; } //////Recursive solution /////////// node* recreverse(node* prev,node* cur); //Initialization void recursive_reverse(node** head){ if(!*head) return; if(!(*head)->next) return; node* next = (*head)->next; (*head)->next = NULL; *head = recreverse(*head,next); } //Recursive Function node* recreverse(node* prev,node* cur){ node* next = (cur)->next; (cur)->next = prev; if(next == NULL) return cur; return recreverse(cur,next); } //3. How would you most efficiently return the middle node of a singly-linked list? (provide code for this solution) /* * Explanation: Keep two pointers, fast and slow. the fast pointer jumps 2 nodes at a time while slow pointer * jumps only one node. When the fast node point to Nth node, slow pointer will point to floor(N/2)th node * * Complexity O(N) where N is size of the list * */ const node* getMiddleNode(const node* head){ if(!head) return NULL; if(!head->next) return head; const node* slow = head; const node* fast = head; while(fast){ fast = fast->next; if(fast){ fast = fast->next; if(fast) slow = slow->next; } } return slow; } //4. How would you remove the duplicate characters from an array? (provide code for this solution) char* remdupchar(char* str){ if(strlen(str)<2) return str; char* a = str; char* b = str+1; while(*a != '\0'){ if(*a != *b){ a++; *a = *b; } b++; } return str; } /////////////////////////////////////////////////////////////////////// //// ============== Test Functions ============================ //// //////////////////////////////////////////////////////////////////////// void testList(){ cout <<"======List Test======"<<endl; node* head; createSampleList(&head,10); printList(head); reverse(&head); printList(head); recursive_reverse(&head); printList(head); const node* middlenode = getMiddleNode(head); if(middlenode) cout <<"Middle node is :"<<middlenode->val<<endl; } void testStrstr(){ cout <<"======strstr() Test======"<<endl; const char* pattern = "abcde"; const char* text = "xxababcdabccccccxabcdeyyyyyyyy"; char* begin = (char*)mystrstr(text,pattern); if(begin){ cout << begin << endl; } else cout <<"String not found"<<endl; } void testRemoveDups(){ cout <<"======remdupchar Test======"<<endl; char str[100]; strcpy(str,"aaaaaaaabcccccddddddeee"); remdupchar(str); cout << str << endl; } int main(){ testList(); testStrstr(); testRemoveDups(); }
| Flag | PURGE
<--- a --->X<--- b --->
|
c
|
|
X is common node.
a + b = L1 (length of list 1)
c + b = L2 (length of list 2)
Reverse List 1 and traverse list 2 again.
You will get c + a = L3 (length of new list 2)
We have three equations and three unknowns (a,b,c).
Find value of 'a'. and traverse List 1 for 'a' number of nodes.
#include <iostream>
using namespace std;
void combination(int combindex);
const int arysize = 5;
const int outsize = 3;
int ary[] = {1,2,3,4,5};
bool used[arysize];
int comb[outsize];
int main(void){
for(int i = 0;i<arysize;i++){
used[i] = false;
}
combination(0);
}
void combination(int combindex){
for(int i=0;i<arysize;i++){
if(used[i] == false){
comb[combindex] = ary[i];
used[i] = true;
}
else
continue;
if(combindex == outsize-1){
for(int j = 0;j<outsize;j++){
cout <<comb[j]<<",";
}
cout << endl;
}
else{
combination(combindex+1);
}
used[i] = false;
}
}
step 1: Do slow pointer and fast pointer stuff. Start counter M when they start traversing. and stop the counter when they meet ( Mth node from list head)
step 2: Now from meeting point. Start another counter C and move slow pointer until it meets fast pointer ( C is the size of the loop)
step 3: (C - (M - C) )th node from the meeting place is the node you want.
Doubling the size of the vector should make it constant time.
- Carbon April 09, 2008