Author |
Topic: Remove and element from a linked list based Queue (Read 1180 times) |
|
Ved
Junior Member
Gender: 
Posts: 53
|
 |
Remove and element from a linked list based Queue
« on: Dec 23rd, 2011, 8:00am » |
 Quote  Modify
|
I want to build a system with the following APIs :
1. put(n) - stores data in the system
2. get() - will give me the element added the first and so on.
I gave a queue implementation using the LinkedList (using a head and tail pointers). Interviewer asked the complexity of both put and get operations and asked how I would implement "removeElement(n)" - now, given a linkedlist/array implementation of a queue, removeElement(n) is going to be O(n) worst case operation, I could not find any other options.
|
| « Last Edit: Dec 23rd, 2011, 9:56pm by Ved » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Remove and element from a linked list based Qu
« Reply #1 on: Dec 23rd, 2011, 8:43am » |
Quote Modify
|
You add a tree to index the elements, then all three are O(log n).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Ved
Junior Member
Gender:
Posts: 53
|
|
Re: Remove and element from a linked list based Qu
« Reply #2 on: Dec 23rd, 2011, 9:58pm » |
Quote Modify
|
If I get a tree with indices, how can I have removeElement(n) as O(log n) ? I should have been more clear, removeElement(n) does not mean remove nth element, but remove element with value "n". So even in a tree, I will have to traverse all indexes to see if that index contains element with value "n".
|
| « Last Edit: Dec 23rd, 2011, 9:59pm by Ved » |
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Remove and element from a linked list based Qu
« Reply #3 on: Dec 24th, 2011, 4:13am » |
Quote Modify
|
on Dec 23rd, 2011, 9:58pm, Ved wrote:| If I get a tree with indices, how can I have removeElement(n) as O(log n) ? I should have been more clear, removeElement(n) does not mean remove nth element, but remove element with value "n". So even in a tree, I will have to traverse all indexes to see if that index contains element with value "n". |
|
You can you a BST or a B+ tree to index the elements of the linked list. So tree nodes should have pointers to list nodes. Whenever you want to search n, use tree n reach the list node with value n.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print