some interview questions.

[pandapower]

Hi,
These were some of the interview questions asked,can someone discuss
whats the solution.

1.I have a singly linked list and i have to print the 5th element from
the last.I have to print it in a single pass of the linked list.How do
i print that?

2.If i have a structure, whose elements are an integer,a character and
a character pointer.What will be the size of the structure.Suppose on
the specified platform the alignment is on 4 byte boundaries. where
does the alignment come into picture and why ? How is padding related
to alignment for structures.

3.Suppose i have a

int **ptr ;
How do i initilize this so that iam able to access it like a two
dimentional array.

and conversely if i have something like
int arr[6][7];
int *ptr;
what can i do so that i can assign it like this
ptr = arr;


please feel free to give any comments/suggestions

regards
rohitash

 

[Eric Sosman]

Hi,
These were some of the interview questions asked,can someone discuss
whats the solution.

1.I have a singly linked list and i have to print the 5th element from
the last.I have to print it in a single pass of the linked list.How do
i print that?

This isn't a C question, so the answer is off-topic in
comp.lang.c. Here's a hint, though: How would you attack the
problem if the goal were to print the next-to-last element?

2.If i have a structure, whose elements are an integer,a character and
a character pointer.What will be the size of the structure.

sizeof(struct struct_type) is the only reliable answer.
You know that the value in this case will be at least 3, but
it could be greater.

Suppose on
the specified platform the alignment is on 4 byte boundaries. where
does the alignment come into picture and why ?

Alignment doesn't come into the picture; it's there before
the picture is painted.

How is padding related
to alignment for structures.

Padding can be inserted after any elements of the struct to
ensure that the subsequent elements are properly aligned and that
the sizeof the entire struct is a multiple of the most restrictive
alignment of any of its elements.

3.Suppose i have a

int **ptr ;
How do i initilize this so that iam able to access it like a two
dimentional array.

This is Question 6.16 in the comp.lang.c Frequently Asked
Questions (FAQ) list

http://www.eskimo.com/~scs/C-faq/top.html

and conversely if i have something like
int arr[6][7];
int *ptr;
what can i do so that i can assign it like this
ptr = arr;

Switch to a non-C language. In C, the assignment as
written is illegal.

please feel free to give any comments/suggestions

Read the FAQ, and read your C text or reference.

 

[Arthur J. O'Dwyer]

Hi,
These were some of the interview questions asked,can someone discuss
whats the solution.

Sure, as long as the answers involve standard C and aren't
your homework.

1.I have a singly linked list and i have to print the 5th element from
the last.I have to print it in a single pass of the linked list.How do
i print that?
(Duh.)

2.If i have a structure, whose elements are an integer,a character and
a character pointer.What will be the size of the structure.

Simply:
sizeof (the_structure_in_question)

More complicatedly:
greater than or equal to sizeof(int)+sizeof(char)+sizeof(char*),
noting in passing that sizeof(char) == 1 by definition

Less standardly:
Twelve.

Suppose on the specified platform the alignment is on 4 byte
boundaries.

You need a little more information than that. Some systems
(IIRC Win32/Intel included) have different alignment requirements
for different data types. E.g., floats might align on 4-byte
boundaries, but doubles on 8-byte boundaries.

where does the alignment come into picture and why ? How is padding
related to alignment for structures.

Suppose I have a structure

struct foo {
int i;
char c;
char *p;
};

on a system on which sizeof(int)==4 and sizeof(char*)==4, but all
'int' objects must be aligned along 4-byte boundaries. Then the
compiler will [probably] lay out the struct in memory like this:

0 1 2 3 4 5 6 7 8 9 A B
i i i i c . . . p p p p

where 'i', 'c', and 'p' indicate the bytes used to store those
fields, and '.' indicates a padding byte. Note that if I stored
the struct in nine bytes like this:

0 1 2 3 4 5 6 7 8
i i i i c p p p p

it would be fine for single objects, but if you try to make an
array out of these structs you'll see that the second struct's
'i' field is not aligned properly:

0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1
i i i i c p p p p i i i i c p p p p
^
whoops! 9 is not a multiple of 4!

So that's why padding bytes exist in some structures.

3.Suppose i have a

int **ptr ;
How do i initilize this so that iam able to access it like a two
dimentional array.

Using 'malloc'. Buy a book on C and read it for this one;
it's not exactly esoteric.

and conversely if i have something like
int arr[6][7];
int *ptr;
what can i do so that i can assign it like this
ptr = arr;

You can't. The statement
ptr = arr;
is not a valid C statement as it stands. You could,
of course, write
ptr = (int*) arr;
or
ptr = arr[0];
or even
*(int (**)[6])&ptr = arr;
but none of these are really appropriate in C, and
only the first two of them are even portable (meaning,
'correct'). You want a two-dimensional array, use
a two-dimensional array.

-Arthur

 

[nobody]

Hi,
These were some of the interview questions asked,can someone discuss
whats the solution.
[FAQ-like questions snipped]

please feel free to give any comments/suggestions

Only because you've asked for it. IMHO you don't want
this kind of job. What you will do later, with real
problems? You get to maintain someone's code, ...,
program crashes on client's box (but noy yours), and
you have to debug it remotely via plain terminal session
(if you are lucky enough to have this kind of access)?
And I didn't mean to be rude.

 

[Raghavendra]

This isn't a C question, so the answer is off-topic in
comp.lang.c. Here's a hint, though: How would you attack the
problem if the goal were to print the next-to-last element?

What he might mean is printing 5th element from last position backwards.
Then using recursion we can print in a single pass.

2.If i have a structure, whose elements are an integer,a character and
a character pointer.What will be the size of the structure.

sizeof(struct struct_type) is the only reliable answer.
You know that the value in this case will be at least 3, but
it could be greater.

Suppose on
the specified platform the alignment is on 4 byte boundaries. where
does the alignment come into picture and why ?

Alignment doesn't come into the picture; it's there before
the picture is painted.

How is padding related
to alignment for structures.

Padding can be inserted after any elements of the struct to
ensure that the subsequent elements are properly aligned and that
the sizeof the entire struct is a multiple of the most restrictive
alignment of any of its elements.

3.Suppose i have a

int **ptr ;
How do i initilize this so that iam able to access it like a two
dimentional array.

This is Question 6.16 in the comp.lang.c Frequently Asked
Questions (FAQ) list

http://www.eskimo.com/~scs/C-faq/top.html

and conversely if i have something like
int arr[6][7];
int *ptr;
what can i do so that i can assign it like this
ptr = arr;

Switch to a non-C language. In C, the assignment as
written is illegal.

please feel free to give any comments/suggestions

Read the FAQ, and read your C text or reference.

 

[Nils Petter Vaskinn]

What he might mean is printing 5th element from last position backwards.
Then using recursion we can print in a single pass.

You're going to recurse over a linked list of unknown length, when it can
be done with one or two loops?

 

[David Resnick]

What he might mean is printing 5th element from last position backwards.
Then using recursion we can print in a single pass.

Why use recursion? Keep a pointer to the head of the list, go 4 more
elements into the list, and then increment the two pointers in
parallel. e.g

(untested example, but it compiles)
#include "stdio.h"

typedef struct node {
void *value;
struct node *next;
} node;

node *get_fifth_node_from_end(node *head)
{
node *pfifth = head;
node *ptail = head;
int i;

for (i=0; i < 4 && ptail->next != NULL; i++) {
ptail = ptail->next;
}

if (i != 4) {
fprintf(stderr, "list has less than 5 elements!");
return NULL;
}

while (ptail->next != NULL) {
ptail++;
pfifth++;
}

return pfifth;
}

Seems like the simplest way to do it.

-David

 

[Anupam]

What he might mean is printing 5th element from last position backwards.
Then using recursion we can print in a single pass.

I dont see any point in recursion here. Just iterate n over the list
using n=n->next;
Always check whether n->next->next.....(5 times for the fifth last
....etc.) etc. is NULL.
CAVEAT : The list has to contain atleast 5 elements.. Else check
n!=NULL, then n_>next !=NULL and so on and so forth.

2.If i have a structure, whose elements are an integer,a character and
a character pointer.What will be the size of the structure.

sizeof(struct struct_type) is the only reliable answer.
You know that the value in this case will be at least 3, but
it could be greater.

Suppose on
the specified platform the alignment is on 4 byte boundaries. where
does the alignment come into picture and why ?

Alignment doesn't come into the picture; it's there before
the picture is painted.

How is padding related
to alignment for structures.

Padding can be inserted after any elements of the struct to
ensure that the subsequent elements are properly aligned and that
the sizeof the entire struct is a multiple of the most restrictive
alignment of any of its elements.

3.Suppose i have a

int **ptr ;
How do i initilize this so that iam able to access it like a two
dimentional array.

This is Question 6.16 in the comp.lang.c Frequently Asked
Questions (FAQ) list

http://www.eskimo.com/~scs/C-faq/top.html

and conversely if i have something like
int arr[6][7];
int *ptr;
what can i do so that i can assign it like this
ptr = arr;

Switch to a non-C language. In C, the assignment as
written is illegal.

please feel free to give any comments/suggestions

Read the FAQ, and read your C text or reference.

 

[CBFalconer]

What he might mean is printing 5th element from last position
backwards. Then using recursion we can print in a single pass.

A simpler solution is:

1. reverse the list
2. print the 5th item
3. reverse the list (if original needed)

and the C operation of reversing a singly linked list in place is
extremely easy.

 

[xarax]

Eric Sosman <[email protected]> wrote in message

pandapower wrote:

/snippage/

and conversely if i have something like
int arr[6][7];
int *ptr;
what can i do so that i can assign it like this
ptr = arr;

Switch to a non-C language. In C, the assignment as
written is illegal.

That question is simply asking how to write cast
so that the address of "arr" is stored into "ptr".

A valuable skill for handling interview questions
is knowing how to read between the lines.

 

[James Hu]

What he might mean is printing 5th element from last position
backwards. Then using recursion we can print in a single pass.

Bzzt, wrong answer. Try again, but don't post the answer to
comp.lang.c, because it is still not a C question. Followup set
to comp.programming.
[Rest of Eric's quoted text snipped since it was not addressed.]

-- James

 

[Wolfgang Riedel]

Why use recursion? Keep a pointer to the head of the list, go 4 more
elements into the list, and then increment the two pointers in
parallel. e.g

(untested example, but it compiles)
#include "stdio.h"

typedef struct node {
void *value;
struct node *next;
} node;

node *get_fifth_node_from_end(node *head)
{
node *pfifth = head;
node *ptail = head;
int i;

for (i=0; i < 4 && ptail->next != NULL; i++) {
ptail = ptail->next;
}

if (i != 4) {
fprintf(stderr, "list has less than 5 elements!");
return NULL;
}

while (ptail->next != NULL) {
ptail++;
pfifth++;
}

return pfifth;
}

Seems like the simplest way to do it.

-David

pedantic mood on:

while (ptail->next != NULL) {
ptail = ptail->next;
pfifth = pfifth->next;

at least in c.l.c

Wolfgang

 

[Anuj Heer]

i also thought that keeping two pointers like done in mathematical
induction would be a simple solution.but the question specifically
states that you must use one pass.doing it this way seems like
cheating. i feel recursion would be a much better answer as far as the
interview is concerned.
anuj
(e-mail address removed)

 

[Richard Heathfield]

i also thought that keeping two pointers like done in mathematical
induction would be a simple solution.but the question specifically
states that you must use one pass.doing it this way seems like
cheating. i feel recursion would be a much better answer as far as the
interview is concerned.

It would be a poor answer if the interviewer were knowledgeable. This is a
job for iteration if ever there was one.

 

[Eric Sosman]

i also thought that keeping two pointers like done in mathematical
induction would be a simple solution.but the question specifically
states that you must use one pass.doing it this way seems like
cheating. i feel recursion would be a much better answer as far as the
interview is concerned.

Instead of moving two pointers through the list (which
I agree violates the "single pass" requirement), you could
walk the list once and maintain a five-place array with the
most recent five pointer values:

Node *p;
Node *history[5] = { NULL, NULL, NULL, NULL, NULL };
int i = 0;
for (p = head; p != NULL; p = p->next) {
history = p;
i = (i + 1) % 5;
}
if (history == NULL) {
/* list too short */
}
else {
/* print *history */
}

As for recursion, this task seems to me to lack the
"divide and conquer" flavor; it's more simply framed in
iterative fashion. Besides, I wouldn't want to apply a
recursive solution to a million-element list ...

 

[James Harris]

Simply:
sizeof (the_structure_in_question)

More complicatedly:
greater than or equal to sizeof(int)+sizeof(char)+sizeof(char*),
noting in passing that sizeof(char) == 1 by definition

Less standardly:
Twelve.

-Arthur

The question doesn't require the fields to be in the listed
order. Suggest the answer should include what has already been
said but also state the case if the fields are arranged with the
char last.
- James

 

[Joona I Palaste]

The question doesn't require the fields to be in the listed
order. Suggest the answer should include what has already been
said but also state the case if the fields are arranged with the
char last.
- James

James Harris? The same James Harris from sci.math?

--
/-- Joona Palaste ([email protected]) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"And according to Occam's Toothbrush, we only need to optimise the most frequent
instructions."
- Teemu Kerola

 

[Christian Bau]

James Harris? The same James Harris from sci.math?

It is quite a common name. There is one J. Harris living in the same
road as I, about 200 meters away from my home. What a frightening
thought.

 

[Bertrand Mollinier Toublet]

Hi,
These were some of the interview questions asked,can someone discuss
whats the solution.

1.I have a singly linked list and i have to print the 5th element from
the last.I have to print it in a single pass of the linked list.How do
i print that?

Why use recursion? Keep a pointer to the head of the list, go 4 more
elements into the list, and then increment the two pointers in
parallel. e.g

I would argue that both your pointers go over the first five elements of
the list thereby not respecting the requirement of a single pass through
the list. If this is still ok with whomever proposed the exercise, then
the wording wasn't too good, IMHO.

 

[Dave Neary]

1.I have a singly linked list and i have to print the 5th element from
the last.I have to print it in a single pass of the linked list.How do
i print that?

Save the last 6 elements you've traversed on the list. When you fall off
the end, print the first one of the 6 you've saved (I'm assuming that
the sentinel for the list isn't considered part of the list).

2.If i have a structure, whose elements are an integer,a character and
a character pointer.What will be the size of the structure.Suppose on
the specified platform the alignment is on 4 byte boundaries. where
does the alignment come into picture and why ? How is padding related
to alignment for structures.

This is very platform dependent. I can, for example, suppress padding in
structures on a 16 bit platform with 2 byte ints to give an answer of 5,
or on a 64 bit platform with 4 byte ints, it could be as little as 13 or
as much as 24 (with 8 byte alignment). Or, assuming 4 byte alignment,
and 32 bit pointers and 32 bit ints (big assumptions), it could be 12
or 9, depending oin the order the members are in the struct. So the
answer is "it depends".

3.Suppose i have a

int **ptr ;
How do i initilize this so that iam able to access it like a two
dimentional array.

That's kind of vague... the answer they're looking for is probably

#define ROWS 8
#define COLS 12

int **ptr, i;

ptr = malloc (ROWS * sizeof *ptr);

for (i = 0; i < ROWS; i++)
ptr = malloc (COLS * sizeof **ptr);

Assuming error checking, of course (and appropriate free()s).

and conversely if i have something like
int arr[6][7];
int *ptr;
what can i do so that i can assign it like this
ptr = arr;

You can't.

Cheers,
Dave.