Motorola Interview Question
Software Engineer / Developerslinked list doesn't take advantage of the fact that it's sorted at all. delete, insert, and lookup are all O(n).
the problem w/ a BST is that you have to balance it to get search times other than O(n). if you just insert sorted names into a BST, that's just a list.
a hash table is O(1) for insert, lookup and delete. i can't see how this is not the best solution.
Linked list is usually the worst choice, Vector or array is much better choice.
Add O(1)
Delete O(1)
Search O(lg n) (Binary Search)
Linked list (add = O(1), delete = O(1), search = O(n))
The names are in sorted order.
When you construct a tree from that list your binary tree will be a right going chain. then how will the search be in O(n) ?
I would suggest using a hash table
The records are sorted. Why and how you want to use hashtable?
For a sorted link list, delete takes O(1)?? How do you locate the element you want to delete?
Array - Inserting an element would require shifting the elements. Worst case it takes O(n)
Linked list - Searching an element would be sequential and it does not take advantage of sort order
Binary search tree could be a solution, taking the mid element as the root would give a balanced tree which will make search, insert and delete all of them in O(n)
it's a linked list whose each node is of the type:
- champaklal June 12, 2010note: create a dummy head first. delete method requires it.
public class StringList
{
String data;
StringList nxt;
public StringList(String s)
{
this.data = s;
this.nxt = null;
}
// using this basic insert, write a code to insert the string s just after any string str.
public void Insert (String s)
{
StringList sl = new StringList(s);
for( ;this.next != null; this = this.nxt);
this.nxt = sl;
}
public void Delete(String s)
{
for( ; this.nxt != null ; this = this.nxt)
{
if(this.nxt.data == s)
{
this.nxt == this.nxt.nxt;
}
}
}
}