5 ms·

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 wit

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...

ben7799 7y ago
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.
- segfaultbuserr 7y ago
  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.
simias 7y ago
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.
- segfaultbuserr 7y ago
  Exactly. It's why call it "stupid", "insidious", but "somewhat relevant", as the parent comment proposes a better stdlib in C to handle strings.
- partialrecall 7y ago
  For some jobs, tolerance to tedium is considered a skill.
- jly 7y ago
  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.
kazinator 7y ago
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 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.)
Steven_Vellon 7y ago
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.
- termie 7y ago
  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.
  - Steven_Vellon 7y ago
    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.
    - unkulunkulu 7y ago
      O(N) is worst if you realloc exponentially with O(N) worst case possible extra unused space in the end
    - termie 7y ago
      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.
drng 7y ago
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?
- Steven_Vellon 7y ago
  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-Space https://thedailywtf.com/articles/The-Fizz-Buzz-from-Outer-Sp...

ben7799 7y ago

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.

segfaultbuserr 7y ago
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.

simias 7y ago

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.

segfaultbuserr 7y ago
Exactly. It's why call it "stupid", "insidious", but "somewhat relevant", as the parent comment proposes a better stdlib in C to handle strings.
partialrecall 7y ago
For some jobs, tolerance to tedium is considered a skill.
jly 7y ago
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.

kazinator 7y ago

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 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.)

Steven_Vellon 7y ago

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.

termie 7y ago
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.
- Steven_Vellon 7y ago
  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.
  - unkulunkulu 7y ago
    O(N) is worst if you realloc exponentially with O(N) worst case possible extra unused space in the end
  - termie 7y ago
    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.

drng 7y ago

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?

Steven_Vellon 7y ago
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-Space https://thedailywtf.com/articles/The-Fizz-Buzz-from-Outer-Sp...