Whats wrong with my code! Microsoft didn't continue interview after reviewing my code !! please help

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)

#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();
}

- Carbon April 28, 2008 | Flag |

Email me when people comment.

An error occurred in subscribing you.