Author |
Topic: malloc and quicksort (Read 3984 times) |
|
eviljed
Newbie
Posts: 16
|
|
malloc and quicksort
« on: Aug 5th, 2002, 7:49am » |
Quote Modify
|
Unless other conditions are going to be put on these functions, then there is no point in having these problems here. You can get a working version of quicksort from any worthwile data structures book in several languages, and you can get a version of malloc from any in-depth programming language book (for instance, "The C Programming Language" by Kernighan and Ritchie). If you want to show me how to allocate real memory in Java, that may be more fun. Or run a quicksort in Assembly (have fun... use ARM), then that would be a challenge. Heck.. do it in forth or prolog
|
|
IP Logged |
|
|
|
-D-
Guest
|
I'd like to throw an argument at this. At the very top of the page there is the statement: [ hardcore tech-interview style riddles, not gaussian elimination logic puzzle fluff ] First, while solving these riddles in a group manner is certainly an enjoyable passtime, it's not the only purpose for this site. If you were to limit the puzzles to those which would be tailored to being solved in online and group discussions you would eliminate a multitude of general algorithm problems and be confined to those problems whose solutions are very discrete and exact. Secondly, during the discussion on /. there was a lot of talk about how "useless" riddles are in interviews. That could be true for problems such as "how do I make 24 from these numbers" but certainly an interviewer would want to know how well you can problem solve. Problem solving is an important asset in a candidate while programming skill is not critical. Programming skill can be learned, problem solving is an evolved process. Implement malloc, or implement an efficient sorting routine for these criteria. This is the kind of question I would ask a candidate on an interview. Malloc more so than "quicksort" takes thinking and planning and problem solving. It doesn't require the interviewee to demonstrate programming ability and instead relies on design abilities, a more important trait. Problems such as this one, and the data collection problem are prime examples of test problems to solve for interview prep. Problems such as the C for-loop problem are great for discussion but not so applyable to the other half of the purpose of this website. -D- ps. do you know how malloc and free work?
|
|
IP Logged |
|
|
|
Earendil
Newbie
Gender:
Posts: 46
|
|
Re: malloc and quicksort
« Reply #2 on: Mar 9th, 2004, 8:51am » |
Quote Modify
|
The question is how to implement malloc in C? If so I really can't imagine how it is done If anyone can answer I'd be grateful
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: malloc and quicksort
« Reply #3 on: Mar 9th, 2004, 9:12pm » |
Quote Modify
|
on Mar 9th, 2004, 8:51am, Earendil wrote:The question is how to implement malloc in C? If so I really can't imagine how it is done If anyone can answer I'd be grateful |
| Generally there is an OS function that hooks into the kernel's memory manager to allocate memory. The C function usually asks for slightly more than the user requests, and prepends the size onto the memory block. "free()" uses the pointer and the prepended size to return this block to the kernel's memory manager. The C standard library side of the fence generally is very small and simple, all the hard work is done in the kernel. Of course in C++ you may write custom handlers, and I think you can in C too but I've never done it. Anyway, you can allocate on humungous chunk and allocate smaller chunks within your program. This bypassing the OS's memory protection, however, but it is possible and in some cases more efficient.
|
|
IP Logged |
x = (0x2B | ~0x2B) x == the_question
|
|
|
|