Motorola Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

it's a linked list whose each node is of the type:
note: 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;
}
}
}
}

- champaklal June 12, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

linked 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.

- jeff October 04, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))

- Zubair June 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 13, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry I meant O(lg n)

- Anonymous June 13, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- kulang June 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Even for deleting and searching in linked list it can not take O(1) because before deleting and for searching you need to first locate it. Even you must have doubly liked list to search it in binary manner but its not specified. So SortedDictionary or HashMap is much better option.

- Harit June 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is already said to use trie!

- Anne June 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You mean "tree"?

- Anonymous September 22, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Divya February 28, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More