Hacker News Reader

Comment by segfaultbuserr | Hacker News Reader

Here's a stupid but somewhat relevant case: Recently, I saw a surprisingly insidious variation of the "FizzBuzz" question in C. Like the usual FizzBuzz, but with a twist: You are required to return your answer as "char (star)" with a separator "\n", the memory should be allocated dynamically, assuming the user calls free(). A naive implementation that strcat() / realloc() the string and repeats it a thousand times, a better solution is to overestimate the required memory and malloc(). Adding a different constraint can make the question quickly become effectively "reimplement std::vector in C", and in real applications, something like this occurs daily, all C programmers have their own standard library, so I guess C++ is at least useful for its standard library...

View on HN

How is this a stupid interview question?

There are a lot of positions this would be a great indicator of whether or not the candidate could do the job.

If low level programming is involved the candidate better be able to handle this. Just cause you don't have to solve this problem every doesn't mean you're not going to need those skills for systems programming, writing drivers, embedded programming, etc..

I suspect this would have an extremely high weed out rate actually. A very large % of so called software engineers would fail this, certainly anyone who did all their learning in a dynamic language with automatic garbage collection and who had not branched out into lower level programming.

It's a dumb question if the job position is for a Javascript UI dev of course.. it's not a good question for all positions.

I would also say it's a travesty for any school to award anyone a bachelor's degree in computer science to someone who would fail this question. I've interviewed a large # of candidates with master's degrees who would fail this. Thankfully most of those candidates didn't have a bachelors in computer science + a masters in computer science from a highly ranked US institution.

Also someone who groks this problem and solves it is way less likely to write memory leaks into code in a garbage collected language.

I didn't really meant to criticize the question itself, just use it to make a point on C's stdlib that the OP was talking about.

It's good to measure all the pieces (if you can) or get an upper-bound estimate, allocate once, then move in.

http://www.kylheku.com/cgit/txr/tree/lib.c?id=txr-225#n3897

(The mysterious wini, wref and auto_str macros here allow a C character array on the stack to be a Lisp value with a type tag, recognized and ignored by the garbage collector.)

Am I missing something here? Assuming you're writing `char * fizzbuzz(unsigned n)`, can't you determine exactly how many bytes you need at the outset from `n` and just malloc once?

There are some variations of fizzbuzz that have you print out the number of iterations performed at that point on each line. The memory consumption could still be predetermined, but the math is a bit more complicated. Other variations have you reading integers from a stream (integers are not in any order), printing "Fizz" and "Buzz" when it's a multiple of 3 and 5 respectively, and that does not have a predetermined memory footprint.

While FizzBuzz has become notorious for weeding out total incompetence [1], there are some variations of the problem that are unexpectedly nuanced.

1. https://thedailywtf.com/articles/The-Fizz-Buzz-from-Outer-Sp...

I'm not really sure what's the point of this exercise instead of a regular FizzBuzz. Dealing with strings in C is tedious, error prone and results in very verbose code but it's not really difficult per-se. What is this testing for exactly?

If I had to do something like that in a real program I'd very much overalloc a few bytes (because why not? If those small allocations really become a problem in your app you probably want to use a custom allocation scheme anyway) and then just snprintf the result into it. I'd go even further and say that code that would micro-optimize this to save a couple of bytes at the cost of maintainability shouldn't pass a code review IMO.

Exactly.

It's why call it "stupid", "insidious", but "somewhat relevant", as the parent comment proposes a better stdlib in C to handle strings.

For some jobs, tolerance to tedium is considered a skill.

FizzBuzz covers a lot of (very basic) ground but adding memory manipulation is valuable. I ask a few simple string manipulation interview questions for embedded C developers as a weeder and the point is that we want to see how candidates deal with pointers and low level memory. There are other good follow-ups and alternatives you can build off this. Engineers with years of experience fail these questions all the time. Dealing with 'tedious' things like this is daily part of some developer jobs.

Is it not possible to keep allocating contiguous memory? Just keep appending to the string and allocating more memory. Repeated calls to malloc are not guaranteed to be contiguous but I think you can do this with posix_memalign. Just keep growing the heap segment, and appending more character to it. I suppose it's not going to be contiguous in physical memory, but it should in virtual memory.

You can use realloc. It will try to use the existing contiguous span of memory, but if it cannot, it will malloc a new span and copy the previous bytes in and return a pointer to it.

In that case, you need to test if the memory is contiguous and copy to the new pointer if not. O(N^2) in the worst case, where every memory allocation returns a distinct start pointer.

What I was getting at is that in virtual memory the heap is always contiguous (even if it isn't in physical memory, but we only need it to be contiguous in virtual memory). So one can guarantee that the solution will never require copying data if the program exclusively uses the stack, and the resultant string is the only piece of data on the heap. You always add contiguous memory so your string can dynamically grow without ever copying to a new buffer. This probably requires allocating memory through the use of OS-specific syscalls to request new memory pages instead of malloc or realloc.

O(N) is worst if you realloc exponentially with O(N) worst case possible extra unused space in the end

Yes, the kernel will map virtual to physical however it sees fit, no guarantees there (at least not in user-space via glibc). Realloc will always return a virtually contiguous slice or NULL if it can’t. And you’re right, obviously all those potential subordinate mallocs would be inefficient. :) In this contrived FizzBuzz example case, you could pretty easily do the math and just malloc it all in one go at the start of the function. Fizz and Buzz are the same size, you would just need to add up the iota lengths and the trailing \0. If you take an arg for N (1..N) then stack allocations are not going to work. You need to statically declare their size.

What I'm getting at, though, is that it's possible to implement it without any copies even if the memory consumption cannot be predetermined. Bypass malloc() and realloc() entirely and invoke brk() to increase the program's segment size. This grows the data segment contiguously (in virtual memory), so there will never be a need to copy the result string to a different buffer. In other words point the result pointer to the start of the heap, and never put anything else on the heap.

Reply on news.ycombinator.com