Hi Ryan,
The question was really to find out whether you will assume some stuff
or will ask for enough details. Looking at your code you didn't assume
much, but didn't tell them, which is not a good thing. The point is
that the array might have been big enough and you probably only had to
find the insertion point, move the rest of the elements to the end of
the array and replace the element at the insertion point (this is the
worst case - best case is you append). Also, a sorted list could have
been a sorted linked list, not array, but you didn't ask what is the
actual data structure and hence assumed it's an array, which is a bad
thing.
Anyway, these are tricky questions and I'll never ask one on a
interview. Was your interview @ Microsoft? ;)
Btw, the fact that you used a binary (and not a linear) search is
good, but you should have asked whether you were supposed to grow the
list if there's not enough space, whether to report a falure if the
item was already there, you should have asked the type of the integer
(could be short, long or unsigned), stuff like that. As a general
advice - don't assume anything on an interview (and take it easy).
Cheers,
Stoyan
On 10/8/05, Ryan Graham <[EMAIL PROTECTED]> wrote:
> I totally bombed this question in an interview so I'm posting my answer here
> for comments and suggestions... perhaps (god help me) I'm just not that
> bright, but this works and seems to be fairly efficent. The idea was simple,
> insert an integer into a list that has already been sorted.
>
> private int[] _list;
> ...
> public void Insert(int value)
> {
> int[] tempArray;
>
> // check for special cases
> if (this._list == null)
> { // first item added create new array
>
> this._list = new int[1];
> this._list[0] = value;
> return;
> }
> else if (this._list[this._list.Length-1] <= value)
> { // item to be added is greater than the last
> // item in the array, append item to end
>
> tempArray = new int[this._list.Length+1];
> Array.Copy(this._list, tempArray, this._list.Length);
> this._list = tempArray;
> this._list[this._list.Length-1] = value;
>
> return;
> }
> else if (this._list[0] >= value)
> { // item to be added is less than the first
> // item in the array, insert item to the beginning
>
> tempArray = new int[this._list.Length+1];
> Array.Copy(this._list, 0, tempArray, 1, this._list.Length);
> this._list = tempArray;
> this._list[0] = value;
>
> return;
> }
>
> int left = 0;
> int right = this._list.Length;
> int middle = 0;
> int mod = 0;
>
> // binary search loop
> while (left <= right)
> {
> // modify the pivot point
> middle = (left + right) / 2;
>
> if (value > this._list[middle])
> { // item is greater than the pivot point
>
> //Debug.WriteLine(value + " > " + this._list[middle]);
> mod = 1;
> left = middle + 1;
> }
> else if (value < this._list[middle])
> { // item is less than the pivot point
>
> //Debug.WriteLine(value + " < " + this._list[middle]);
>
> mod = 0;
> right = middle - 1;
> }
> else
> { // item is equal to the pivot point
>
> //Debug.WriteLine(value + " = " + this._list[middle]);
> break;
> }
> }
>
> // modify the pivot point again
> middle += mod;
>
> // rebuild array to allow space for new item
> tempArray = new int[this._list.Length+1];
> Array.Copy(this._list, 0, tempArray, 0, middle);
> Array.Copy(this._list, middle, tempArray, middle+1, tempArray.Length -
> (middle +1));
>
> // insert new item
> this._list = tempArray;
> this._list[middle] = value;
> }
>
> ===================================
> This list is hosted by DevelopMentor(r) http://www.develop.com
>
> View archives and manage your subscription(s) at http://discuss.develop.com
>
--
Cheers,
Stoyan
===================================
This list is hosted by DevelopMentor® http://www.develop.com
View archives and manage your subscription(s) at http://discuss.develop.com
