adoba
BAN USERyes it is reasonable first to assume characters will be keys for bst. but you know common strings have repeated chars( in diff patterns). how do you deal with that to ensure the right order when u do an inorder traversal of the tree ? e.g: dafa => "aadf" inorder in normal bst.
finally about these kind of ambiguous question in interviews :
my opinion is the employer wants to figure out
what kind of problem solver are you ?
are you the kind that will complain to the clients about their requirements(because they dont fit the standard way you expect things to work) and make them leave OR are you the kind that can adapt and deliver a product/solution that fits the client's requirements.
hypothetically if we were auditioning for a contract and this question was the requirement: your answer to the client would be "sorry i can't. my bst does not work for this purpose" and I will say "yes here is the product". Guess who gets the contract !
@loler cause it's an interview and that's what you were asked to do( probably to test your understanding of bst + coding skills ) But I do agree though that there needs to be clarifications from the interviewer about the purpose of the tree. are you just making a bst lookalike or are you going to use the tree you build later ( search, insert , remove) ?
if you are going to use that tree, then the bst node should be modify to store a key in order to agree with definition of bst. For this implementation, the array index of each char would make a perfect key.
struct Node
{
char character;
struct Node *left;
struct Node *right;
}
struct Node * create_bst(char * array )
{
if( ! array )
return NULL;
int size = strlen(array);
int limit = size / 2;
struct Node *root = build_left_side(array, 0, limit); // left side include middle element
root->right = builder_right_side(array, ++limit, size - 1);
return root;
}
/* chars forming the left side are from index start to end */
static struct Node * build_left_side(char * array, int start, int end)
{
struct Node *root = create_node(array[start++]);
while( start <= limit )
{
struct Node *node = create_node(array[start++]);
if ( root->right )
{
node->left = root;
root = node;
}
else
{
root->right = node;
}
}
}
/* chars forming the right side are from index start to end */
static struct Node *build_right_side(char *array, int start, int end)
{
struct Node *root = create_node(array[end--]);
while( end >= start )
{
struct Node *node = create_node(array[end--]);
if( root->left )
{
node->right = root;
root = node;
}
else
{
root->left = node;
}
}
return root;
}
/* create a new bst node with char c as value */
struct Node * create_node( char c)
{
struct Node *node = malloc(sizeof(struct Node *));
if( ! node )
msg_malloc_failed();
node->character = c;
node->left = NULL;
node->right = NULL;
return node;
}
/* print mem error msg and exit */
void msg_malloc_failed()
{
printf("malloc failed \n");
exit(-1);
}
awesome approach jtr.hkcr . I try implementing it just to see if i could ( didn't check for bugs though ). I am a senior in college and I am trying to transition from college style coding ( check for correct results only) to industry style ( correct result + best practices ) so if you find flaws in my style, don't hesitate to mention them.
- adoba March 03, 2013
- adoba June 12, 2015