Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>There's more than one way to do it, but I'd probably run over the input string twice: once to count how many bytes are required for the output, then allocate the output buffer and go again to actually generate the output.</p> <p>Another possibility is to allocate up front twice the number of bytes in the input string (plus one), and write the output into that. This keeps the code simpler, but is potentially very wasteful of memory. Since the operation looks like a rudimentary compression (RLE), perhaps it's best that the first implementation doesn't have the output occupy double the memory of the input.</p> <p>Another possibility is to take a single pass, and reallocate the output string as necessary, perhaps increasing the size exponentially to ensure O(N) overall performance. This is quite fiddly in C, so probably not the initial implementation of the function, especially in interview conditions. It's also not necessarily any faster than my first version.</p> <p>However it's done, the obvious "special case" is an empty input string, because the obvious (to me) implementation will start by storing the first character, then enter a loop. It's also easy to write something where the output may be ambiguous: "1122" is the output for the input "122", but perhaps it is also the output for the input consisting of 122 <code>1</code> characters. So you might want to limit run lengths to at most 9 characters (assuming base 10 representation) to prevent ambiguity. It depends what the function is for - conjuring a complete function specification from a single example input and output is not possible.</p> <p>There's also more than one way to design the interface: the question says "returns a string", so presumably that's a NUL-terminated string in a buffer newly-allocated with <code>malloc</code>. In the long run, though, that's not always a great way to write all your string APIs. In a real project I would prefer to design a function that takes as input the string to process, together with a pointer to an output buffer and the length of that buffer. It returns either the number of bytes written, or if the output buffer isn't big enough it returns the number which would have been written. Implementing the stated function using this new function is easy:</p> <pre><code>char *stated_function(const char *in) { size_t sz = new_function(in, NULL, 0); char *buf = malloc(sz); if (buf) new_function(in, buf, sz); return buf; } </code></pre> <p>I'm also confused what "print" means in the question - other answerers have taken it to mean "write to stdout", meaning that no allocation is necessary. Does the interviewer want a function that prints the encoded string <em>and</em> returns it? Prints and returns something else? Just returns a string, and is using "print" when they don't really mean it?</p>
    singulars
    1. This table or related slice is empty.
    1. POC interview question---run-length coding of strings
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USSteve Jessop
    1. USSteve Jessop
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POC interview question---run-length coding of strings
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CO+1 for the detailed answer.
      singulars
      1. PO
      1. USJamie Keeling
    2. COI admit you'd never get that far in an actual interview, though...
      singulars
      1. PO
      1. USSteve Jessop
    3. COThe other alternative is to allocate the maximum size, build the string, then `realloc` once to trim it down to the actual size.
      singulars
      1. PO
      1. UScaf
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload