## Microsoft Interview Question for Software Engineer in Tests

Country: United States

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

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

Its simple problem if you can you know how to find whether a list have loop or not.
Algorithm :- Take two pointers p1 and p2. Start both from head. Loop until p1 and p2 meet again. But p1 will incre one step i.e. p1 = p1-> next and p2 will two steps i.e. p2= p2->next->next.Once they meet. Do following step.
Now make p1=head and start increment one step by one for both p1 and p2. When they meet again will be the starting point of the cycle.

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

I thought the way you're thinking here... but every element has its next pointer and then returning the same element.
So, I am thinking that every element is starting element in circular linked lists.

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

The code finds the existence of a loop correctly.
But for length of the loop < length of the acyclic part, the code to check the start of the cycle fails.

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

``````public static LinkedList.Node findCircular(LinkedList.Node head)
{
while(!hs.contains(tempNode))
{
prevNode= tempNode;
tempNode= tempNode.next;
}

return prevNode;
}``````

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

My code, check Linkedlist has cycle and return entry node of cycle:
System.out.println("err, no cycle!");
return null;
}
if(slow==null){
System.out.println("err, no cycle!");
return null;
}
if(fast==null){
System.out.println("err, no cycle!");
return null;
}

while(fast!=null){
if(slow==fast){
break;
}
slow=slow.next;
fast=fast.next;
if(fast==null){
System.out.println("err, no cycle!");
return null;
}
fast=fast.next;
}

if(fast==null){
System.out.println("err, no cycle!");
return null;
}
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}

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

{
Node *elem = *start;
while(elem->data < elem->next->data)
{
elem = elem->next;
}
*start = elem->next;
}

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

How you are returning the Node from where cycle is starting. Can you write down steps in seperate lines?

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

firstly, slow node moves one time one step, fast node moves one time two steps.
there is a loop, So when slow encounter fast, slow go back to head and move one time one step.
Now, fast move one time one step too.
when they meet again, the node is entry.

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

It can be proved, and the original proof is easy to find by using google.^_^

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

An additional field, flag may be included in each node. When u visit the node once, set flag to true, the first you'll be visiting twice is the head of the loop.

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

Given two iters A,B, such that A is always ahead of B. If both A,B are in a circle, then going forward from A, it should be possible to reach B. Since we don't know ahead of time how many steps it will take to reach B, let's accelerate after each iteration, i.e. step++; otherwise, if step is constant, it may take many more iterations before A overtakes B...

``````static Node findStart(final Node[] list) {
int step = 1;

if (list.length <= 2) {
return list[0];
}

boolean isLoop = false;

while ((headaccel != null) && !isLoop) {
for (int i = 1; i <= step; i++) {

isLoop = true;

break;
} else if (headaccel == null) {
break;
}
}

step++;
}

}``````

One problem with the above code, though it finds a loop, it doesn't always specify where the cycle starts. In this case, you'd need additional info. Add a visitors integer K such that, if headaccel visits a node N, it sets K to 1. headaccel is only needed with a step of 1 . If headaccel visits N again, increment K to 2. If K=2, then you've detected a loop, and the start of the cycle.

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

I guess not....

The problem with this solution is ensuring that "seen" is marked as false for all the nodes before you start. If the linked list has a loop, it isn't possible to iterate over each node to set "seen" to "false" as an initial value for each node. It might be possible to overcome some of this by using a big integer rather than a boolean and using a random integer as your marker. In that case there is is a good chance that no node will have your inital value, but a small chance that one would and your algorithm would fail.

Even if you are able to solve the initial value problem, each node in a linked list may not have a field to use for this purpose. Requiring such a field in each node would mean that this is not a generic solution. As we will see later, this field is not needed for a perfectly correct and efficient solution anyway.

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

Can we just traverse the list from head and each time check if the node is visited? We can have something like this in the Node class

``````public void setVisited() {
visited = true;
}
public boolean getVisited() {
return visited;
}``````

then we can have a method that traverse the list that returns the first node that's visited twice

``````public Node traverse(LinkedList<Integer> list) {
for (Iterator<Integer> it = list.iterator(); list.hasNext();) {
if (it.next().getVisited()) {
return it.next();
} else {
it.next().setVisited();
}
}
return null;
}``````

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

I guess not....

The problem with this solution is ensuring that "seen" is marked as false for all the nodes before you start. If the linked list has a loop, it isn't possible to iterate over each node to set "seen" to "false" as an initial value for each node. It might be possible to overcome some of this by using a big integer rather than a boolean and using a random integer as your marker. In that case there is is a good chance that no node will have your inital value, but a small chance that one would and your algorithm would fail.

Even if you are able to solve the initial value problem, each node in a linked list may not have a field to use for this purpose. Requiring such a field in each node would mean that this is not a generic solution. As we will see later, this field is not needed for a perfectly correct and efficient solution anyway.

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

Used Floyd Cycle Detection Algorithm/ Tortoise and Hare algorithm

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

No need for slow/fast pointers. Problem definition is using characters, so:

``````Node* cycle_start_node(Node* n) {
bool seen[256];
memset(seen, false, 256*sizeof(bool));
while (n != NULL) {
if (seen[n->val]) return n;
seen[n->val] = true;
n = n->next;
}
return NULL;
}``````

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

I think you really really did not get the question!

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

take two pointers one is incrment by one and another by two and check cond whether next not equal null or the adrres of both pointers are same

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

``````As soon as you find a loop open that loop..
It will look like this..
|-d-3-4-5-5
A-b-c-|
|-3-4-6-8 now intersection point C can be fond quite easily.``````

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.

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