Some Interview Questions

[Matt]

I had these questions in an interview today:


1. Define a class using C.
2. Write a C functions that does garbage collection: frees all
allocated memories.
3. Define semaphore.
4. What is parallel programming and what kind of problems you will
face in this kind of programmings?


I will appriciate if someone gives some answers to the first and the
second questions.


Regards,
Matt

 

[Jack Klein]

I had these questions in an interview today:


1. Define a class using C.

C doesn't have anything named a 'class'.

2. Write a C functions that does garbage collection: frees all
allocated memories.

Not possible, unless you first write a complete memory management
wrapper that tracks all allocations and deletions.

3. Define semaphore.

C doesn't have anything named a 'semaphore'.

4. What is parallel programming and what kind of problems you will
face in this kind of programmings?

C doesn't have anything named 'parallel programming'.

I will appriciate if someone gives some answers to the first and the
second questions.

The only question of the four that has anything to do with the C
language is the second, and I answered it.

 

[CBFalconer]

I had these questions in an interview today:

1. Define a class using C.
2. Write a C functions that does garbage collection: frees all
allocated memories.
3. Define semaphore.
4. What is parallel programming and what kind of problems you will
face in this kind of programmings?

I will appriciate if someone gives some answers to the first and
the second questions.

C does not have classes. If it is up to you, you could write:

#define class (1)

and it would be legitimate and usable. It may not be what the
idiot interviewer wanted to hear, but it he has not an idiot it
would have been what he did want.

#2 is not possible in standard C. Any garbage collection would
have to be limited to a subset of the possible allocated items.
Bear in mind that it is not permissable to redefine malloc,
realloc, free. Only the C system implementor can get at these
things.

 

[Kelvin@!!!]

I had these questions in an interview today:


1. Define a class using C.
2. Write a C functions that does garbage collection: frees all
allocated memories.
3. Define semaphore.
4. What is parallel programming and what kind of problems you will
face in this kind of programmings?


I will appriciate if someone gives some answers to the first and the
second questions.


Regards,
Matt

out of curiosity... so what's your answers to these questiions??

 

[dandelion]

I had these questions in an interview today:


1. Define a class using C.

DEfine a v-table manually. I.e. define a struct containing
pointer-to-functions for methods and and the data-members. Do not forget to
add a pointer to v-table som you can enjoy the benefits of inheritance.
Polymorhism is more difficult to tackle, since it can (practically) only be
done at compile-time.

Not that difficult, really. Just a waste of time. If you want classes,
inheritance and polymorphism, use C++ (or another OO language).

2. Write a C functions that does garbage collection: frees all
allocated memories.

Walk the defined data-tree, tag all objects encountered, walk the allocated
blocks list, delete all blocks which are not tagged. While doing that, make
sure no one changes, allocates or deallocates memory.

3. Define semaphore.
RTFM.

4. What is parallel programming and what kind of problems you will
face in this kind of programmings?

You'd face the usual concurrency problems: i.e. every shared memory location
must be protected by a semaphore and do that *carefully* unless you'd like
an invitation for "The Dining Philosopers" and take care when allocating or
deallocating resources.

There's plenty of literature on that, btw.

I will appriciate if someone gives some answers to the first and the
second questions.

I.e. You'd like someone to do your homework for you... Well, there it is,
now see you can *explain* it.

 

[Stuart Gerchick]

While C does not directly support OO and does not have a keyword for
class, that does not mean you cannot define a class in C.

You can achieve polymorphism with C!

You start with a C struct. You can write your own constructor and
destructor functions. Pass a pointer to the struct as the first
argument (like C++ has the hidden *this).

For polymorphism you just need to use function pointers.

 

[Stuart Gerchick]

3. Define semaphore

A Semaphore lets processes query or alter status information. They
can be used to monitor and/or control the availability of system
resources such as shared memory segments.

The function semget() initializes or gains access to a semaphore

These are used in IPC. Various things like System V, threads
libraries and POSIX all support semaphores

 

[dandelion]

DEfine a v-table manually. I.e. define a struct containing
pointer-to-functions for methods and and the data-members.

Define a v-table manually. I.e. define a struct containing
pointer-to-functions for methods and and the *static* data-members c'tor and
d'tor.

Walk the defined data-tree, tag all objects encountered, walk the allocated
blocks list, delete all blocks which are not tagged. While doing that, make
sure no one changes, allocates or deallocates memory.

Add: Use wrapper functions for malloc, calloc and free.

 

[xarax]

Define a v-table manually. I.e. define a struct containing
pointer-to-functions for methods and and the *static* data-members c'tor and
d'tor.


Add: Use wrapper functions for malloc, calloc and free.

A garbage collector handles dangling references,
including cyclic references, by freeing a dynamically
allocated chunk of memory when the last reference by
a live thread becomes unreachable. By definition,
a GC frees memory that the programmer cannot (or
forgot to) free. A GC is generally implemented as
a separate thread that periodically scans the call
stacks of every live thread to identify the unreachable
dynamic memory objects.

This presumes that there is a notion of a "thread"
in C. It also presumes that there is a way to scan
the call stack of each live thread to find the
"starting points" (i.e., local variables) that point
to dynamic memory. The latter presumption is generally
impossible with most C compiler implementations, because
the locations of local variables within a single stack
frame can be overlayed by block-scoped declarations.

#include <stdint.h>
void poo(void)
{
{
int * foo; /* [1] */

foo = malloc(sizeof *foo);
}
/* At this point, a garbage collector will
notice that the dynamic memory is unreachable
and perform an automatic free(foo).
*/
{
uintptr_t foo; /* likely at same location as [1] */

foo = 0xdeadbeef; /* quite likely overlays [1] */
/* There is no way at the language level
to retrieve [1] and free it.
*/
}
}

Thus, there is no way to really know the difference
between an integer variable and a pointer variable
that happen to occupy the same stack frame location
(at different times during execution). The C compiler
implementation would have to help the garbage collector;
it's not something that can be done at the language
level.


--
----------------------------
Jeffrey D. Smith
Farsight Systems Corporation
24 BURLINGTON DRIVE
LONGMONT, CO 80501-6906
http://www.farsight-systems.com
z/Debug debugs your Systems/C programs running on IBM z/OS for FREE!

 

[Thomas Matthews]

A Semaphore lets processes query or alter status information. They
can be used to monitor and/or control the availability of system
resources such as shared memory segments.

The function semget() initializes or gains access to a semaphore

These are used in IPC. Various things like System V, threads
libraries and POSIX all support semaphores

Last time I looked, I could not find the function semget()
with the following compilers:
GNU G++
Borland C++
Microsoft C++
Metaware High C/C++
Tasking C / C++
Comeau C++

I did notice that two operating systems, VRTX and
Nucleus Plus, offered support for semaphores, but
didn't have a semget() function.

Hmmm, must be off-topic and implementation specific.


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Michael Wojcik]

#2 is not possible in standard C. Any garbage collection would
have to be limited to a subset of the possible allocated items.
Bear in mind that it is not permissable to redefine malloc,
realloc, free. Only the C system implementor can get at these
things.

According to the question, the only requirement is that it "free
all allocated memories". This is implementation-dependent, but
works on typical hosted implementations:

#include <stdlib.h>
void free_everything(void) { exit(0); }

Problem solved.

On a slightly more serious note, the OP might want to take a look
at the Boehm garbage collector, which is an allocator and garbage
collector for C and C++. It requires that the implementation
behave in certain ways for some types of implementation-defined and
undefined behaviors, so it is not standard C, and as such is off-
topic in comp.lang.c. Nonetheless, it may be enlightening,
particularly on the question of why garbage collection is difficult
to do in C. (The Boehm collector is conservative; it tries to err
on the side of not collecting areas that might have disguised
references to them still in the program. Even though it's been a
while since I looked at it, though, I suspect there may be ways to
fool it.)

--
Michael Wojcik (e-mail address removed)

Pocket #9: A complete "artificial glen" with rocks, and artificial moon,
and forester's station. Excellent for achieving the effect of the
sublime without going out-of-doors. -- Joe Green

 

[E. Robert Tisdale]

I had these questions in an interview today:

Who did you interview with?
What job were you interviewing for?

1. Define a class using C.

C doesn't have classes.
You could improvise with a struct.

2. Write a C functions that does garbage collection:
frees all allocated memories.

Garbage collectors don't free _all_ available memory.
They collect only unreferenced allocated memory objects
and return them to free storage.

3. Define semaphore.

This is an operating system specific question.

4. What is parallel programming
and what kind of problems you will face
in this kind of programming?

You need to ask this question in a forum
that deals specifically with parallel or concurrent programming.

I will appreciate if someone gives some answers
to the first and the second questions.

Although you were asked to give examples in C,
you must realize that these are not actually questions about C.
Evidently, they were trying to find out whether or not
you knew what a class was and what garbage collection was.
If you had attempted a good answer,
they would have probably stopped you and asked another question.
What answers did you give?
I suppose that you didn't feel comfortable with your answers
and that's why you are asking.

 

[Chris Torek]

On a slightly more serious note, the OP might want to take a look
at the Boehm garbage collector ... (The Boehm collector is
conservative; it tries to err on the side of not collecting areas
that might have disguised references to them still in the program.
Even though it's been a while since I looked at it, though, I suspect
there may be ways to fool it.)

There are two:

- nonconforming code, and
- using "%p" to store pointers in formats the collector will not see.

An example of the former is, for instance:

int *p;
...
p = malloc(n * sizeof *p);
if (p == NULL) ... handle error ...
p -= k; /* DANGER */
/* now p[k] is the first valid element, and p[k+n-1] is the last */

The line marked DANGER has defined behavior if and only if k is no
greater than zero and no less than -n -- i.e., if p is still in
the defined-behavior range. For instance, assuming n is at least
1, p += 1 will leave p well-defined, so if k = -1, p -= k will add
1 to p and leave it well-defined.

If p is "moved outside" the range that refers to the actual allocated
area, the Boehm collector may (depending on just how far out of
the area it is) no longer see it as a reference to that area. If
there are no other values that appear to refer to that area, the
area will be collected. Note that saving the original "p" and
modifying a copy:

int *p, *q;
... much as before ...
q = p - k; /* DANGER */
/* now q[k] is the first valid element, and q[k+n-1] is the last */

still gives undefined behavior in a formal sense, but now the
"original p" will keep the Boehm collector from collecting the
region.

For the latter, consider something along these lines:

void *p;
T *q;
...
p = malloc(size);
if (p == NULL) ... handle error ...
n = snprintf(buf, sizeof buf, "%p", p);
... make sure that n is OK so that we can use sscanf later ...
p = NULL;
...
/* collector may cause trouble here */
...
sscanf(buf, "%p", &p);
q = p;
... code that uses q for valid values of i ...

In the section marked "collector may cause trouble here", if the
GC code runs, and nothing else seems to be a reference to the memory
region allocated by the malloc(), it may get freed, despite the
later sscanf() that will recover the original pointer.

Note that even scanning ASCII representations for "%p"-formatted
pointers is not sufficient to rescue the above code, since the
output could be sent to a file instead (fprintf() instead of
sprintf()). The C library could perhaps "protect" %p-printed
pointers "forever" (save them elsewere, for the remaining life of
the program at least, for the GC code to read), but this seems
unlikely to be required in practice.

 

[Dan Pop]

Last time I looked, I could not find the function semget()
with the following compilers:
GNU G++
Borland C++
Microsoft C++
Metaware High C/C++
Tasking C / C++
Comeau C++

Only an idiot would expect to find this function implemented as a
compiler intrinsic. It belongs to the *library* part of one
implementation or another and both GNU C and Comeau C++ can handle code
using semget() on *any* platform with a Unix compatibility library (which
is not exactly something unusual). Most likely, the other compilers
from your list can do it, too.

I did notice that two operating systems, VRTX and
Nucleus Plus, offered support for semaphores, but
didn't have a semget() function.

Hmmm, must be off-topic and implementation specific.

It *is* off-topic, but for a completely different reason: it is not part
of the standard C library. No point in mentioning any compiler or
operating system in order to make this simple statement.

Dan

 

[Dan Pop]

There are two:

- nonconforming code, and

What is nonconforming code?

Keep in mind that practically anything qualifies as a conforming C
program.

Dan

 

[Michael Wojcik]

There are two:

- nonconforming code, and
- using "%p" to store pointers in formats the collector will not see.

Yes, in an earlier draft of my previous post I noted the %p case, but
deleted it in the final one.

The C library could perhaps "protect" %p-printed
pointers "forever" (save them elsewere, for the remaining life of
the program at least, for the GC code to read), but this seems
unlikely to be required in practice.

I think "the remaining life of the program" is sufficient, since
the standard only guarantees reading with %p to produce a valid
object pointer during the same execution as when it was written.

Is copying a pointer to and from a sufficiently large array of
unsigned char guaranteed to yield a valid pointer? If so, is the
collector capable of handling a pointer hidden in such an array?
(I suppose I ought to look at the BGC docs again to answer that.)

 

[Stuart Gerchick]

Only an idiot would expect to find this function implemented as a
compiler intrinsic. It belongs to the *library* part of one
implementation or another and both GNU C and Comeau C++ can handle code
using semget() on *any* platform with a Unix compatibility library (which
is not exactly something unusual). Most likely, the other compilers
from your list can do it, too.


It *is* off-topic, but for a completely different reason: it is not part
of the standard C library. No point in mentioning any compiler or
operating system in order to make this simple statement.

Dan

Never said it was a compiler intrinsic. He was asking what a
semaphore and you are right, that has nothing to do with the C
standard. Was just trying to give an explanation and how it is often
done

 

[Chris Torek]

There are two [ways of hiding pointers from the Boehm collector]:
- nonconforming code, and

What is nonconforming code?

Keep in mind that practically anything qualifies as a conforming C
program.

True enough. "Nonconforming" is the wrong term. Unfortunately,
there was no really "right" term, which is why I gave an example
for what I did mean. I could have said "code that is not strictly
conforming", but plenty of not-strict C code is just fine under
the Boehm collector.

Another thread today just brought up the problem with terminology
here. Some have proposed a phrase like "strongly conforming" code,
to mean "code that works in reasonable situations". This, of course,
invites consternation as to just what is "reasonable".

The example I gave computed pointers "outside" the range of a
malloc()ed block, without saving at least one pointer "inside" the
block. This is an example of code that is at least "borderline
unreasonable" if not "outright unreasonable", yet on most systems
it works anyway, so it might (or might not) fall under the
"strongly conforming" group.

Another example, which I think would definitely fall outside this
"strongly conforming" set of operations, but which does work on
many implementations, is the "xor forward and reverse pointers
together to save space in a doubly linked list" trick. Here, the
Boehm collector will see the head of the list, but not any of the
other elements (unless you get lucky, or perhaps unlucky, as the
case may be).

 

[Chris Torek]

I think "the remaining life of the program" is sufficient, since
the standard only guarantees reading with %p to produce a valid
object pointer during the same execution as when it was written.

Yes. This could be "*too* conservative", of course.

Is copying a pointer to and from a sufficiently large array of
unsigned char guaranteed to yield a valid pointer?

I believe it is.

If so, is the collector capable of handling a pointer hidden in
such an array?

The last time I talked with Mark Weiser about it, the answer was
"only if it is properly aligned and in the machine's native byte
order". If you were to scatter it around the buffer, or otherwise
"hide" it, no.

In other words, the collector simply scans all memory (and registers)
for things that "look like" pointers, regardless of compile-time
data-types.