|
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.
|
|
|
|
|
Mike,
That's solved all my problems! Thanks so much for your help.
All the best,
Simon
|
|
|
|
|
Now I can replace icon resource in a .exe file from other .exe file.
I copy code from MSDN about UpdateResource.
But I can not update icon resource from a icon file.
|
|
|
|
|
In almost the same way. When copying from one EXE to another, you used LoadImage() /LoadResource() followed by LockResource() to get a pointer to the icon's data. You then called UpdateResource() with that pointer. When using an ICO file, the only difference is to use CreateFile() to open the ICO file, followed by ReadFile() to get a pointer to pass to UpdateResource() . Make sense?
Five birds are sitting on a fence.
Three of them decide to fly off.
How many are left?
|
|
|
|
|
Hello!
How to get handler to window, when i have its ID and its name?
|
|
|
|
|
HWND hWnd = ::FindWindow(NULL, "Window name");
Cheers,
Fredrik
"Felix qui potuit rerum cognoscere causas."
|
|
|
|
|
Using MSDN documentation I can do it with functions SetFileSecurity or SetNamedSecurityInfo but for the folder these permissions do not visible in 'securyty' property sheet of IE(right mouse click on folder->properties). Inspite of this they work fine. How to make them visible there ?
I found VBasic example HOWTO: Set Security on a NTFS Folder Programmatically.
There they set permissions 'for the folder' and for the files... Some one face such a problem.
Appreciate any information.
|
|
|
|
|
Just as the suject.
Rap off for you,for me,for our human.
|
|
|
|
|
Blade
Best Wishes and Happy Holiday's,
ez_way
|
|
|
|
|
|
Hi,
I've made a dll for use within a PowerBuilder application. When I compile this dll under Windows Xp it runs well under Windows Xp and Windows 2000. On Windows NT however, it crashes. The problem is due to the fact that, when compiled under Xp the size of the MENUITEMSTRUCT I use is set to 48 while it's 44 on NT. How can I change the coding so it runs on both Xp and NT.
This is the code I use for setting the size:
MENUITEMINFO info
info.cbSize = sizeof MENUITEMINFO;
Thanks in advance,
Aart
|
|
|
|