By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,412 Members | 978 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,412 IT Pros & Developers. It's quick & easy.

some interview questions.

P: n/a
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
Nov 13 '05 #1
Share this Question
Share on Google+
26 Replies


P: n/a

On Mon, 24 Nov 2003, pandapower wrote:

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

Nov 13 '05 #2

P: n/a
pandapower wrote:

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.

--
Er*********@sun.com
Nov 13 '05 #3

P: n/a
"pandapower" <pa********@SoftHome.net> wrote in message
news:37**************************@posting.google.c om...
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.
Nov 13 '05 #4

P: n/a
Eric Sosman <Er*********@sun.com> wrote in message news:<3F***************@sun.com>...
pandapower wrote:

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?


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.

Nov 13 '05 #5

P: n/a
On Tue, 25 Nov 2003 02:48:15 -0800, Raghavendra wrote:
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?

--
NPV

"the large print giveth, and the small print taketh away"
Tom Waits - Step right up

Nov 13 '05 #6

P: n/a
ra*******************@wipro.com (Raghavendra) wrote in message news:<12**************************@posting.google. com>...
Eric Sosman <Er*********@sun.com> wrote in message news:<3F***************@sun.com>...
pandapower wrote:

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?


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
Nov 13 '05 #7

P: n/a
ra*******************@wipro.com (Raghavendra) wrote in message news:<12**************************@posting.google. com>...
Eric Sosman <Er*********@sun.com> wrote in message news:<3F***************@sun.com>...
pandapower wrote:

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?


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.

Nov 13 '05 #8

P: n/a
Raghavendra wrote:
Eric Sosman <Er*********@sun.com> wrote in message news:
pandapower wrote:

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?


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.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 13 '05 #9

P: n/a

"Raghavendra" <ra*******************@wipro.com> wrote in message
news:12**************************@posting.google.c om...
Eric Sosman <Er*********@sun.com> wrote in message

news:<3F***************@sun.com>...
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.
Nov 13 '05 #10

P: n/a
On 2003-11-25, Raghavendra <ra*******************@wipro.com> wrote:
Eric Sosman <Er*********@sun.com> wrote in message news:<3F***************@sun.com>...
pandapower wrote:
> 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?


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
Nov 13 '05 #11

P: n/a
David Resnick wrote:

ra*******************@wipro.com (Raghavendra) wrote in message news:<12**************************@posting.google. com>...
Eric Sosman <Er*********@sun.com> wrote in message news:<3F***************@sun.com>...
pandapower wrote:
>
> 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?


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


pedantic mood on:

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

at least in c.l.c

Wolfgang
Nov 13 '05 #12

P: n/a
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
hp*****@vcustomer.net
Nov 13 '05 #13

P: n/a
Anuj Heer wrote:
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.

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
Nov 13 '05 #14

P: n/a
Anuj Heer wrote:

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[i] = p;
i = (i + 1) % 5;
}
if (history[i] == NULL) {
/* list too short */
}
else {
/* print *history[i] */
}

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

--
Er*********@sun.com
Nov 13 '05 #15

P: n/a

"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote in message
news:Pi***********************************@unix47. andrew.cmu.edu...

On Mon, 24 Nov 2003, pandapower wrote: <snip>
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. <snip> -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
Nov 13 '05 #16

P: n/a
James Harris <no.email.please> scribbled the following:
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 (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"And according to Occam's Toothbrush, we only need to optimise the most frequent
instructions."
- Teemu Kerola
Nov 13 '05 #17

P: n/a
In article <bq**********@oravannahka.helsinki.fi>,
Joona I Palaste <pa*****@cc.helsinki.fi> wrote:
James Harris <no.email.please> scribbled the following:
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?


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.
Nov 13 '05 #18

P: n/a
pandapower wrote:
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?

David Resnick wrote: 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.
--
Bertrand Mollinier Toublet
"Reality exists" - Richard Heathfield, 1 July 2003

Nov 13 '05 #19

P: n/a
On 24 Nov 2003 13:25:02 -0800, pandapower said:
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[i] = 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.

--
David Neary,
E-Mail: bolsh at gimp dot org
Work e-mail: d dot neary at phenix dot fr
CV: http://www.redbrick.dcu.ie/~bolsh/CV/CV.html
Nov 13 '05 #20

P: n/a
Wolfgang Riedel <wo*************@development.retarus.de> wrote in message news:<3F***************@development.retarus.de>...
David Resnick wrote:

ra*******************@wipro.com (Raghavendra) wrote in message news:<12**************************@posting.google. com>...
Eric Sosman <Er*********@sun.com> wrote in message news:<3F***************@sun.com>...
> pandapower wrote:
> >
> > 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?

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


pedantic mood on:

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

at least in c.l.c

Wolfgang

Entirely agree, brain was totally out of gear.

-David
Nov 13 '05 #21

P: n/a
Dave Neary <re******************@thisoneis.invalid> spoke thus:
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.


Well, technically OP could (correct me if I'm wrong) by changing the
declarations...

int arr[6][7];
int (*ptr)[7]; /* ptr points to an array of 7 elements */
ptr=arr; /* legal, yes? */

Not that that's particularly useful or anything...

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
Nov 13 '05 #22

P: n/a
Wolfgang Riedel wrote:
David Resnick wrote:
.... snip ...
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.


pedantic mood on:

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

at least in c.l.c


I maintained earlier that use of list reversal would simplify
matters. At any rate, just for sport I implemented both that and
the trailing pointer method below. The code has been compiled and
run, and seems correct apart from a one-off error in the trailing
pointer method. I am leaving that error in here, because I think
its existance is instructive. Note that the initialization
displays the list with the head last.

-------------- code begins here ---------------
#include <stdio.h>
#include <stdlib.h>

/* THERE ARE ERRORS HERE - possibly instructive */

#define POSN 5

struct node {
struct node *next;
int val;
};

/* ----------------- */

/* make a list */
static struct node *initialize(void)
{
struct node n, *p;
int i;

n.next = NULL;
for (i = 0; i < POSN + 2; i++) {
p = n.next;
if (!(n.next = malloc(sizeof *(n.next))))
exit(EXIT_FAILURE);
else {
n.next->val = rand();
n.next->next = p;
printf("%d ", n.next->val);
}
}
putchar('\n');
return n.next;
}

/* ----------------- */

/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
static struct node *revlist(struct node *root)
{
struct node *curr, *nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ----------------- */

static void tryreversal(struct node *root)
{
struct node *p;
int i;

root = revlist(root);
p = root;
for (i = 0; i < POSN; i++) p = p->next;
printf("%dth from end via reversal is %d\n", POSN, p->val);

/* This only if original list must be unharmed */
root = revlist(root);
} /* tryreversal */

/* ----------------- */

static void trytrailingptrs(struct node *root)
{
struct node *last, *trail;
int i;

trail = last = root;
for (i = 0; i < POSN; i++) last = last->next;
while (last) {
last = last->next;
trail = trail->next;
}
printf("%dth from end via trailer is %d\n", POSN, trail->val);
} /* trytrailingptrs */

/* ----------------- */

int main(void)
{
struct node *root;

root = initialize();

trytrailingptrs(root);
tryreversal(root);
return 0;
}

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

Nov 13 '05 #23

P: n/a

"Christian Bau" <ch***********@cbau.freeserve.co.uk> wrote in
message
news:ch*********************************@slb-newsm1.svr.pol.co.uk...
In article <bq**********@oravannahka.helsinki.fi>,
Joona I Palaste <pa*****@cc.helsinki.fi> wrote:
James Harris <no.email.please> scribbled the following:
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?


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.


Sorry. Can't answer to either of those.

.... Unless, of course, you are just down the road from me. Hmm,
what a frightening thought also!!!

-J
Nov 13 '05 #24

P: n/a
"CBFalconer" <cb********@yahoo.com> wrote in message
news:3F***************@yahoo.com...
Raghavendra wrote:
Eric Sosman <Er*********@sun.com> wrote in message news:
pandapower wrote:
>
> 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?


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.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!


2 words.... Ring Buffer.

Michael Steve
The Sequel
Nov 13 '05 #25

P: n/a
> > 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:


The only hint i was given was if i could somehow relate it to relative
velocity concepts and find an answer.The answer i gave was as you
suggest,to keep an array of 5 latest members as i traverse the list,
and when i come to the end of the list i print the element.But i am a
bit confused how we can do that too,if the list finishes when in the
middle of the array.Probably we need to move the contents of the array
as we overwrite old values or probably a queue will be a better idea.
regards
Nov 13 '05 #26

P: n/a
pandapower wrote:
.... snip ...
The only hint i was given was if i could somehow relate it to relative
velocity concepts and find an answer.The answer i gave was as you
suggest,to keep an array of 5 latest members as i traverse the list,
and when i come to the end of the list i print the element.But i am a
bit confused how we can do that too,if the list finishes when in the
middle of the array.Probably we need to move the contents of the array
as we overwrite old values or probably a queue will be a better idea.


Over 24 hours ago I published two solutions in a message msgid:
<3F***************@yahoo.com> It would appear you do not read the
answers that appear.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 13 '05 #27

This discussion thread is closed

Replies have been disabled for this discussion.