IBM Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 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.

- OP November 15, 2011 | Flag Reply
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...

- Anonymous November 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- JobHunter November 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 :)

- Varun November 09, 2011 | Flag
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.!!

- Anonymous November 10, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

dude..this was for IBM RnD Lab:)

- Varun November 21, 2011 | Flag
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.

- Anonymous November 12, 2011 | Flag Reply
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.

- at November 13, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

correct me if i am wrong

- atul.87friend November 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void getelement(int p, int d){
	node n = head;
	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);
		}
		node res = head;
		while(res != null && (k-- > 0)){
				res = res.sibling;
		}
		System.out.println(res.val);
	}
}

- CAFEBABE January 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is not possible to trace -N node from given node in the tree.
However if Head of the list is provided, then it is simple
1. Move one pointer N ahead from head
2. Now Move one pointer from head and another from N, one by one till Given node is found.
3. At this point, you have previous pointer pointing to -N position

This is O(n) solution

- pc June 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 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:

1-2-3-4-5-6-7-8 is the linked list
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

- Anonymous November 09, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how do you know where is 1?

- pc June 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 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.

- Sagnik Majumder January 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

head is not provided

- pc June 02, 2015 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More