Amazon Interview Question
Software Engineer / DevelopersTeam: kindle
Country: India
Interview Type: Phone Interview
Is this code is working? I am not getting the exact expected o/p.Showing some garbage values.
Is this code is working? I am not getting the exact expected o/p.Showing some garbage values.
bunch of problems in addTo linkedlist function. Fix them and the memset function and you are good to go
char *to = (char*) malloc(sizeof(str)/sizeof(char));
str is a type of (char *) so its size is always 4
here the size allocated to "to" is always 4
Construct Linked interactive with tokenized string by KMP/BM/N-gram method (Depends on time/space consumption condition)
What I meant here is:
1. Tokenize input string with some matching method e.g.) BM (Boyer–Moore string search algorithm)
2. Build linked list from Head with tokenized tokens.
Instead of storing tokenized tokens to array, directory construct Linked List is space efficiently without saying...
The best answer to this question depends on the likely use cases. Is it likely that delims will be a long string? Is efficiency important? If the answer to both questions is yes, we might want to go with a complicated approach like a rolling hash. If the answer to either is no, we can just take a very simple approach where we just search for the search string starting with each character.
We should also clarify what happens if the delimiter overlaps with itself. For example, what if the delimiter is "aba" and we pass in the string "cababac"? Is the answer (c, c) or (c, bac) or something else?
My solution:
struct _Node
{
char* pString;
struct _Node* pNext;
};
struct _Node* strtok(char* pInput ,char* pDelims)
{
int i = 0; // Iterating through the input string
int j = 0; // Iterating through the delimiters
int CurrentStart = 0; // Current start of substring in string.
struct _Node* pHead = NULL; // Head of the result list. This will be returned.
struct _Node* pLastNode = NULL; // Pointer to node which was added last.
if (pInput == NULL || pDelims == NULL)
return NULL;
// For every char in the string
while (i <= strlen(pInput))
{
// Go through all the delimiters
for (j = 0; j < strlen(pDelims); j++)
{
if (pInput[i] == pDelims[j] || (pInput[i] == '\0' && j == strlen(pDelims) - 1))
{
// Current input char is delimiter
// Create new node
struct _Node* pNewNode = malloc(sizeof(struct _Node));
// Get the substring size
int Size = i - CurrentStart;
if (Size > 0)
{
// Allocate a null terminated string
char* pSubString = malloc(sizeof(char)*(Size + 1));
// Copy the substring
strncpy(pSubString, pInput+CurrentStart, Size);
// Null terminate
pSubString[Size] = '\0';
// Set the references
pNewNode->pString = pSubString;
pNewNode->pNext = NULL;
if (pHead == NULL)
{
// If this is the first item put it in the list as head
pHead = pNewNode;
pLastNode = pHead;
}
else
{
// Append it to the last node
pLastNode->pNext = pNewNode;
pLastNode = pNewNode;
}
}
else free(pNewNode);
// Current start is now the next char
CurrentStart = i+1;
// Input can't be another delimiter as well...
break;
}
}
// Look at the next char
i++;
}
return pHead; // Return the result list
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<malloc.h>
typedef struct StrNode
{
char data[30];
StrNode *next;
}sll;
void main()
{
char str[50]="Amapqrzopqrn Repqrcrpqruitmpqrentpqr";
char* pch;
sll *temp, *newNode;
sll *head = (struct StrNode *)malloc(sizeof(struct StrNode));
strcpy(head->data,"");
head->next = NULL;
temp = head;
pch = strtok(str,"pqr");
while(pch != NULL)
{
newNode = (struct StrNode *)malloc(sizeof(struct StrNode));
newNode->next = NULL;
strcpy(newNode->data,pch);
temp->next = newNode;
temp = newNode;
pch = strtok(NULL,"pqr");
}
temp = head->next;
while(temp!=NULL)
{
printf("%s",temp->data);
temp = temp->next;
}
getch();
}
Here is my solution (tested :) )
#include <stdio.h>
#include<conio.h>
#include<malloc.h>
#include<string.h>
struct node{
char *data;
struct node *next;
};
typedef struct node *NODE;
void strtok_my(char* input ,char* delims);
NODE head = NULL;
void insert(char*data, int len)
{
NODE ptr;
NODE nptr;
if(len)
{
if(head == NULL)
{
head = (NODE)malloc(sizeof(struct node));
head->data = (char*)(malloc(sizeof(char)*len + 1));
memset(head->data, NULL,len+1);
strncpy(head->data, data, len);
head->next = NULL;
return;
}
nptr = (NODE)malloc(sizeof(struct node));
nptr->data = (char*)(malloc(sizeof(char)*len + 1));
memset(nptr->data, NULL,len+1);
strncpy(nptr->data, data, len);
nptr->next = NULL;
for(ptr = head; ptr->next != NULL; ptr= ptr->next);
ptr->next = nptr;
}
return;
}
void print()
{
NODE ptr;
for(ptr = head; ptr; ptr= ptr->next)
{
printf(" %s ", ptr->data);
}
}
void main()
{
char *str = "heabcateabcaabcmango";
char *delims = "abc";
strtok_my(str, delims);
print();
getch();
}
void strtok_my(char* input ,char* delims)
{
char *p1; char *p2;
p1= input; p2 = input;
while(*p1 && *p2)
{
if(*(p2+1)== NULL || *(p2+2)== NULL)
{
while(*p2)p2++;
insert(p1,(p2-p1));
return;
}
if((*p2 == 'a') && (*(p2 + 1)== 'b')&& (*(p2+2)== 'c'))
{
insert(p1,(p2-p1));
p2 = p2 + 3;
p1=p2;
}
else
{
p2++;
}
}
}
btw,
can someone help making the code inside the following loop in strtok_my neater :
if(*(p2+1)== NULL || *(p2+2)== NULL){}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
struct node{
char* value;
node* next;
};
node* insertNode(node* root, char* data){
node* temp = NULL;
int len = strlen(data);
if (root == NULL){
root = (node*) malloc(sizeof(node));
root->next = NULL;
root->value = (char*) malloc(len);
strcpy(root->value, data);
}else{
temp = (node*) malloc(sizeof(node));
temp->next = root;
temp->value = (char*) malloc(len);
strcpy(temp->value, data);
root = temp;
}
return root;
}
void displayList(node* root){
if (root == NULL){
return;
}
else{
displayList(root->next);
printf("%s\n", root->value);
}
}
node* myStrTok(const char* origStr, const char* del){
int delLen = strlen(del);
node* list = NULL;
char* delBegin = (char*)del;
char* strBegin = (char*)origStr;
int subStartIndex = 0;
char* p1 = (char*)origStr;
int i = 0;
int copyLen = 0;
char* data = NULL;
while(*strBegin){
data = NULL;
delBegin = (char*)del;
while(*delBegin && *strBegin && *delBegin == *strBegin){
delBegin++;
strBegin++;
i++;
}
if (!*delBegin){
copyLen = i - delLen - subStartIndex;
if (copyLen > 0){
data = (char*) malloc((copyLen +1) * sizeof(char));
strncpy(data, p1, copyLen);
data[copyLen] = '\0';
list = insertNode(list, data);
free(data);
}
p1 = strBegin;
strBegin--;
subStartIndex = i;
i--;
}
strBegin++;
i++;
}
// For the last substring
if(*p1){
copyLen = strBegin - p1;
data = (char*) malloc((copyLen + 1) * sizeof(char));
strncpy(data, p1, copyLen);
data[copyLen] = '\0';
list = insertNode(list, data);
free(data);
}
return list;
}
int main(){
node* head = NULL;
char* origString = "amazonprqisprqrecrutingprq";
char* delim = "prq";
head = myStrTok(origString, delim);
if(head){
displayList(head);
}else{
printf("List is empty");
}
system("pause");
return 0;
}
node* create_node(const string& key)
{
node* elt = new node(key);
return elt;
}
node* strtok(char* str, char* delim)
{
hash_set<char> delim_map;
for(int i = 0; delim[i] != '\0'; ++i)
{
if(delim_map.find(delim[i]) == delim_map.end())
{
delim_map.insert(delim[i]);
}
}
node* head = NULL;
node* tail = NULL;
string key;
for(int i = 0; str[i] != '\0'; ++i)
{
if(str[i] == '\0' || delim_map.find(str[i]) != delim_map.end())
{
if(head == NULL)
{
head = create_node(key);
tail = head;
}
else
{
tail->next = create_node(key);
tail = tail->next;
}
key = "";
}
else
{
key += str[i];
}
}
return head;
}
Here is a solution to the question in C.
- ethioer July 17, 2012