## IBM Interview Question Software Engineer / Developers

• 0

come up with a solution, where u r given a single pointer in a single link list and u shoudl be able to return (+/-)nth node from it.

My solution:

``````list * returnN (list *node, int n)
{
if (n>0) {
traverse and reverse list from node to nth node
} else {
traverse and negatereverse from node till nth node
}``````

he asked for algo only, so this worked fine.

eg list=1->2->3->4->5
returnN(1, 3)
output 4
list=1<-2<-3<-4->5

returnN(4, -2)
output 2
list: 1<-2->3->4->5

Any other suggestions??

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it is not possible to get -nth pointer from some node in single linked list, because you have only pointer to the next node, but no pointer to previous.

If you want -nth from there is possible to traverse list from the begin, remember n previous adresses and lineary search the list for the input node, but this is little bit complicated...

Comment hidden because of low score. Click to expand.
0

You can find out this one using distance.
1. You should know the orignal header in the linked list eg) 1
2. Form a Array with given linked element with distance
list=1->2->3->4->5
eg)
a(1)->0,a(2)->1,a(3)->2,a(3)->3,,,,
in this case we need to move forward 3

eg)2
for the backward cursor set the orginal header and set the distance as -{orginal position of newpointer}-{each node position}

as per the second example

a(1)->-4,a(2)->-3,a(3)->-2,a(3)->-1,a(4)->0

This will easy for us to figure it out.

Comment hidden because of low score. Click to expand.
0

Didn't understand the also..
Anyway I missed the fact, He asked not to use any extra memory, i can change anything in list, but no extra memory, and can't convert single list to double list :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

for nth node from the list its straight forward
But for -nth,instead of reversing the list and again setting it back.We can break the list and make it a circular list,find the nth last element in that circular list. And later revert back the changes

Ex:

return N(4,-2)

break the list at 4 and connect the next pointer of 4 to 1
now u have a list 1-2-3-4-1...

now from 1 find the 2nd last element using the mth last element algo with some modification in the termination condition

and now connect 4 back to 5

Comment hidden because of low score. Click to expand.
0
of 0 vote

Since when did IBM start asking such Qs. As far as I knw, it asks only some silly HR Qs.!!

Comment hidden because of low score. Click to expand.
0

dude..this was for IBM RnD Lab:)

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be that second operation has to be performed on the list resulted in first op.

If so, second returnN(4,-2) is also simple same as first. Traverse from the list node 4, swap the links to do the reverse linked list checking for the count.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can not guarantee the (-n) part. You can try:
given ptr;
prev_pointer = (struct single_lnk_lst *) (ptr-(sizeof (struct single_lnk_lst) * 2));
if(single_lnk_lst->next == ptr) // you are lucky to get to -1, now do that n more times.

Comment hidden because of low score. Click to expand.
0

memory allocated to the link list may not be contigous....so this algo will fail i guess...

correct me if i am wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

For -ve, if an extra memory is allowed, its simple. If we are calling the method with (M,N) Push the elements till Mth node onto the stack and pop the N elements then you will get the m-nth element as top of the stack.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void getelement(int p, int d){
int count = 0;
while(n.val != p && n != null){
if(n.sibling == null){
System.out.println("enter correct input");
System.exit(0);
}
else{
count++;
n = n.sibling;
}
}
if(d > 0){
while(n != null && (d-- > 0)){
if(n.sibling == null){
System.out.println("cant move. enter correct input");
System.exit(0);
}
else{
n = n.sibling;
}
}
System.out.println(n.val);
}
else{
int k = count+d;
if(k < 0){
System.out.println("cant move. enter correct input");
System.exit(0);
}
while(res != null && (k-- > 0)){
res = res.sibling;
}
System.out.println(res.val);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Best solution:-

``````There is a head node denoted by list *head.
list * returnN (list *node, int n)
{
Take 2 pointers p1 & p2, make them both point to head.
Now if n<0,
Keep forwarding one pointer p1 to right for |n| times, where |n| = abs(n)
Now forward both the pointers until p1 reaches node.
return p2.
Else if n>0,
p1 point to node.
Just keep forwarding p1 to right for n times.
return p1.``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.