Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
For the first part, do you think a hashed array of linked lists could work. The lists contain employee details which are hashed by manager name. So insertion, deletion of employee under a manager is simple.
Maybe you can, but there is a major flaw here as you are hashing by manager name. Here “key” is the “name”, so you might land up with lots of duplicate keys. Duplicate keys are always bad.
You may want to hash it by using a unique number such as employee id...
Hi Snehasish Barman,
I think instead of a Binary Heap, something like a N-Way Heap is better as each node can have many childs.
Hi Srikant,
You can have a N-way Heap and by doing that i assume you want to achieve constant-time performance and add more complexity. But the catch is that a “Binary Heap” will give you logarithmic performance for most operations. Most of the time you will perform insert and delete operations on the heap which are very efficient using binary. If we can sacrifice small performance for complexity/maintainability, its better for all of us.
Hey guys...
good discussion... I'd like to jump in...
if we have an N-way heap the complexity would remain logarithmic. The only thing is before it was Log-base-2 and now it would be log-base-(max n).... n is a constant and hence in terms of complexity we could any time change it to base-2 and ignore the constant generated.... so we're all fine
enum EMPLOYEE_TYPE
{
CEO,
VP,
MANAGER,
EMPLOYEE,
};
typedef struct employee
{
enum EMPLOYEE_TYPE type;
char *name;
struct employee *lead;
struct employee *employee;
struct employee *co_emp;
}employee;
typedef struct node
{
char *name;
struct node *next;
}node;
node *get_employees(employee em)
{
node *head, *current_employee;
employee *child = em->employee;
while(child != NULL)
{
node *temp = (node *)malloc(sizeof(node));
if(head == NULL)
head = temp;
else
current_node->next = temp;
current_node = current_node->next;
child = child->co_emp;
}
return head;
}
Can we use a binary tree, with each node has one pointer to first child and second to the sibling. This will make deletion and addition in the hierarchy very fast.
And we can have a trie to keep name or id of employee to keep pointer of those employee node in the tree, a hash table will also work.
I don’t know much about the first question, but you can use a Binary Search Tree.
- Snehasish Barman January 27, 2012For second question, one can definitely use a “Binary Heap”( a heap-ordered complete binary tree ). Whenever you add a new member into the organization, you move up the member, so that the member(parent) is larger than its children. Whenever you delete a member, you move down. At any point you move up/down to restore the heap ordering - (organizational hierarchy)