|
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?
|
|
|
|
|
Hi,
I've an application which another app needs to get a handle to. I plan to use FindWindow but the window name obviously changes (ie has "- untitled" appended to name). Therefore I guess I need to get it by class name. How can I specify a name for the class of the window?
I've looked at modifying it in PreCreateWindow but it seems really complex. Can anyone suggest a simple way of doing this?
(I used Microsoft Spy++ to get the current class of the app window but it says this nonsense: Afx:00400000:b:00010013:00000006:03720353. I'd prefer something more easy to read!)
Thanks,
Simon
|
|
|
|
|
Okay,
So I kept going at this and I think I managed to register the window class...but now the app won't open. It gives me a message: "Failed to create empty document." What's that about?
S
|
|
|
|
|
That's one of MFC's self-generated window classes. It tries to cut down on the number of unique classes by generating a class name derived from some of the options in WNDCLASS. The sequence is Afx: followed by- Instance handle (base address of executable/DLL)
- Style bits (here
CS_HREDRAW | CS_VREDRAW | CS_DBLCLKS ) - Cursor handle
- Background brush handle (
COLOR_WINDOW + 1) - Icon handle
You'll need to call AfxRegisterClass to register your own class and use that instead.
BOOL CMyWnd::PreCreateWindow(CREATESTRUCT& cs)
{
WNDCLASS wc = { 0 };
wc.style = CS_HREDRAW | CS_VREDRAW;
wc.lpfnWndProc = DefWindowProc;
wc.hInstance = AfxGetInstanceHandle();
wc.hIcon = ::LoadIcon( IDR_MAINFRAME );
wc.hCursor = AfxGetApp()->LoadStandardCursor( IDC_ARROW );
wc.hbrBackground = (HBRUSH) ( COLOR_WINDOW + 1 );
wc.lpszMenuName = NULL;
wc.lpszClassName = _T( "Your Class Name Here" );
if ( !AfxRegisterClass( &wc ) )
return FALSE;
cs.lpszClass = wc.lpszClassName;
return TRUE;
} should do the trick.
|
|
|
|
|
Mike,
Thanks so much for your time and advice. This seems a much clearer way of doing things. The only problem is I get this error message on compile relating to the line:
wc.lpfnWndProc = DefWindowProc;
error:
cannot convert from 'LRESULT (__thiscall CWnd::* )(UINT,WPARAM,LPARAM)' to 'WNDPROC'
Any idea how to deal with this?
|
|
|
|
|
Oops! It's picked up CWnd::DefWindowProc, but it should be ::DefWindowProc (i.e. the Windows function of that name). Add the :: before.
Most other examples say to use AfxWndProc, but the MFC source itself (in AfxRegisterWndClass) uses DefWindowProc, so that's what I suggested.
|
|
|
|