|
Please help me write a function for a dynamic array of Car objects.
In function I need to dynamicly allocate array size for the Car objects.
Thanks
|
|
|
|
|
|
You don't need to write a dedicated function just to allocate memory. See the new operator.
Five birds are sitting on a fence.
Three of them decide to fly off.
How many are left?
|
|
|
|
|
Shouldn't you be doing the homework by yourself?
--
I can't resist a touch of evil.
|
|
|
|
|
Seeing as you want me to do your homework, you'll first need to send me $20 via paypal. THEN when your next assignment comes in ( which may require THREE actual lines of code ), you won't have a clue what to do, because you didn't do this homework. That'll be $30. And so on, and so on.
Or you could do your own homework.
Christian
I have drunk the cool-aid and found it wan and bitter. - Chris Maunder
|
|
|
|
|
I'll give you a hint.
int* AllocateIntArray(int size)
{
return new int[size];
}
John
|
|
|
|
|
Now why did you go and do that ? Now he'll never do his homework, and we'll have another wanna be programmer who can't write 'hello world' on our hands.
Christian
I have drunk the cool-aid and found it wan and bitter. - Chris Maunder
|
|
|
|
|
I was in a sympathetic mood. Besides he/she will have to figure out what to change to get it to work...
John
|
|
|
|
|
John M. Drescher wrote:
Besides he/she will have to figure out what to change to get it to work
I'm curious what that would be. The function looks completely intact.
Five birds are sitting on a fence.
Three of them decide to fly off.
How many are left?
|
|
|
|
|
My function deals with integers.
John
|
|
|
|
|
|
Hi,
Here's a puzzle. I have a linked list which may or may-not be circular. Using 2 pointers which have to be moving at any given point of time how do i determine if the linked list is circular?
-Mel
|
|
|
|
|
(mmmm, smells like homework)
Given you don't know whether it is or not, I would suggest you need to have a "slow" pointer and a "fast" pointer. For each time you move the slow pointer a single node along the linked list, you move the fast pointer on two nodes.
If there is a circle, once both pointers are inside it the fast pointer will eventually "catch up" to the slow one, and they will both point at the same node (note that this isn't necessarily the "start" node of the circle, just a node within it).
If the fast pointer reaches a terminating node, then there is (obviously) no circle.
The performance characteristics aren't fantastic, but the algorithm should be sound.
--
Ian Darling
"The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky
|
|
|
|
|
Hi,
Nope not homework. It was an interview question of a friend.
I think I missed out some details when I gave the puzzle. We need to determine if the linked list is properly circular or not.
Consider this linked list of 3 nodes
A->B->C and C points back to B instead of A.
Now according to your algorithm both the pointers will converge on some node, but the linked list is not a proper circular linked list.
I was thinking more on the lines of storing the address of each node in some table as I parse down the list. Then if i come across a node whose entry already exists in the table and I haven't passed the starting node twice then it means there is some problem in the list. However my solution doesn't satisfy the condition of 2 pointers etc.
-Mel
|
|
|
|
|
melwyn wrote:
We need to determine if the linked list is properly circular or not.
That wasn't suggested by your original post - it implied that there was a circle of some sort in the linked list, not that the whole list was either circular or straight
If it's properly circular, you only need to move a single pointer, with a second one pointing at the start, and you just wait for it to come around again (or hit the termination node). However, this means you can't determine if your list is "improperly" circular, as the moving pointer will get stuck in a loop and never return to the start.
You can merge the two methods and use three pointers (start, slow and fast), which allows you to identify "properly", "improperly" and "not" circular lists, which would seem to me to be more useful.
(Thinking about it, I'm sure Knuth would have solved this. I'll have to look it up properly tonight )
--
Ian Darling
"The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky
|
|
|
|
|
Your algorithm will work for non-proper linked lists as well. Start at the beginning of the list*. If there is a non-proper cycle in it, your pointers will indeed catch up with eachother sooner or later. Whip out your pen and paper and see for your self
le* first = list->head;
le* second = list->head ? list->head->next;
while(second != first && second != NULL) {
second = second->next;
if(second != first && second != NULL) {
second = second->next;
first = first->next;
}
}
if(second == NULL)
printf("No cycle\n");
else
printf("There is a cycle at %p (v = %d)\n", second, second->value);
* Assume you don't start at the beginning of the list and there exists a cycle on the list prior to your start but no loop back to it. Then it is impossible to detect that cycle, since there is no way back to it. The problem stated a linked list, which I assume is a singly linked list, as doubly linked lists are usually named just that.
A doubly linked list can be a bit trickier. Especially if for some i: i->prev->next != i. Not really sure about the implications of that as I don't feel a particular pressure to find out, but I'm sure it would make the problem a bit more fun.
--
I can't resist a touch of evil.
|
|
|
|
|
Jörgen Sigvardsson wrote:
Your algorithm will work for non-proper linked lists as well.
I know that, that's what I originally set out to do (and I have the scribbles to prove it)
The debate was over truly circular linked lists
Jörgen Sigvardsson wrote:
A doubly linked list can be a bit trickier. Especially if for some i: i->prev->next != i. Not really sure about the implications of that as I don't feel a particular pressure to find out, but I'm sure it would make the problem a bit more fun.
Yes.
Couldn't find anything about this sort of problem in Knuths books at all - I'll have to write my own "solve stupid linked-list puzzles" book
--
Ian Darling
"The moral of the story is that with a contrived example, you can prove anything." - Joel Spolsky
|
|
|
|
|
Ian Darling wrote:
Couldn't find anything about this sort of problem in Knuths books at all - I'll have to write my own "solve stupid linked-list puzzles" book
Be sure to write your own imaginary CPU before you do!
--
I'm your turbo lover. Better run for cover![^]
|
|
|
|
|
Jörgen Sigvardsson wrote:
The problem stated a linked list, which I assume is a singly linked list, as doubly linked lists are usually named just that.
Actually the interviewer had mentioned that the linked list could be considered as doubly linked, if it could help solve the problem in any way.
|
|
|
|
|
Ian Darling wrote:
(mmmm, smells like homework)
It can't be homework! If it were homework, the poster would be smart enough to figure this out - since they were also clever enough to pose it as a "puzzle" instead of homework!
|
|
|
|
|
Believe me it's not homework.
The professors (in my college atleast) weren't that smart enough to pose such type of puzzles ...also if they did pose the problem, they would have to know the solution .
Btw, I graduated over 4 years ago.
|
|
|
|
|
Aha! (Another) classic Microsoft interview question!
/ravi
Let's put "civil" back in "civilization"
Home | Articles | Freeware | Music
ravib@ravib.com
|
|
|
|
|
Have you been an interviewee, or are you an interviewer?
--
I can't resist a touch of evil.
|
|
|
|
|
I have been the former a few times. Sometimes I just go for an interview to test my skills and get some interesting puzzles to solve .
|
|
|
|
|
No, not Microsoft, but it is in the top 5 software companies in the world.
Btw, do you know other Microsoft interview questions?
|
|
|
|