## Microsoft Jane Street Interview Question for Software Engineer / Developers

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

``````void reverse(node n, node prev) {
if (n == null) { newroot = prev; return; }
reverse(n.next, n);
n.next = prev;
}

call reverse (root, null);``````

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

Perfect!

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

Nice solution

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

Above code skips last element, following is the working with little modification

``````void LinkedList::Reverse(Node* root, Node* prev)
{
if(root->next == NULL)
{
this->list = root;
this->list->next = prev;
return;
}
Reverse(root->next, root);
root->next = prev;
}``````

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

Awsm solution !!!! gr8..

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

// Simple Solution without confusion
/* Let j be pointer to 1st node of list then initial call ll be list_rec_reverse(&j, NULL, j) */

void list_rec_reverse(list **l, list *prev, list *curr)
{
if(NULL == curr)
{
*l=prev;
return;
}

list_rec_reverse(l,curr,curr->next);
curr->next = prev;
}

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

All short and sweet recursively reversing algorithms have to have this structure..

``````reverseList xs = reverseList' xs []
reverseList' [] coll = coll
reverseList' (x:xs) coll = reverseList' xs (x:coll)``````

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

algopadawan(dot) blogspot(dot)com/2012/05/linked-list-reverse(dot)html

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

1) use a recursive function that provides sublist tail as result (and updates head as side-effect)

2) use two references to adjacent nodes (current and previous), chain current.next to previous

``````public class ReverseLinkedList {

private class Node {
private int value;
private Node next;
public Node(int value){
this.value = value;
}
public int getValue(){ return value;}
public Node getNext(){ return next;}
public void setNext(Node next){ this.next = next;}
}

private Node head;

public ReverseLinkedList(){
}

public void add(int v){
Node n = new Node(v);
n.setNext(head);
head = n;
}

public int remove(){
if( null == head){
throw new IllegalStateException("can't remove from empty list");
}
int v = head.getValue();
head = head.getNext();
return v;
}

public void reverse(){
if( null != head ){
Node newTail = reverseSubList(head);
newTail.setNext(null);
}
}

public void reverse2(){
if( null != head ){
Node previous = head;
Node n = head.getNext();
head.setNext(null);
while( null != n ){
Node oldNext = n.getNext();
n.setNext(previous);
previous = n;
n = oldNext;
}
head = previous;
}
}

public void print(){
Node n = head;
while( null != n ){
System.out.print(n.getValue());
System.out.print(" -> ");
n = n.getNext();
}
System.out.print("null");
}

// n is sublist head
// return sublist tail once reversed
// updates head reference when needed
private Node reverseSubList(Node n){
if( null == n.getNext()){
head = n;
} else {
Node subListTail = reverseSubList(n.getNext());
subListTail.setNext(n);
}
return n;
}

public static void main(String[] args){

ReverseLinkedList list = new ReverseLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);

list.print();

list.reverse();

list.print();

list.reverse2();

list.print();
}
}``````

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

``````public class node
{
public object data;
public node next;

public node()
{
data = null;
next = null;
}
public node(object item)
{
data = item;
next = null;
}

}

public class LinkList
{
private node List;
public int count=0;

public LinkList()
{
List = null;
}
public void AddNode(object item)
{
if (List == null)
{
List = new node(item);
count++;
}
else
{
node temp = new node(item);

node p = List;
while (p.next != null)
{
p = p.next;
}

p.next = temp;
count++;
if (count%1000 == 0)
Console.WriteLine(count);
}

}

public void Revese()
{
node cur, prev=null, l;

if (List !=null)
l = List;
else
return;

while (l != null)
{
cur = l;
l = l.next;
cur.next = prev;
prev = cur;
}

List = prev;

}
}``````

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

void reverse(struct node **p)
{
struct node*temp,*prev;
prev=NULL;
while (*p !=NULL)
{
temp=*p;
*p=temp->next;
temp->next=prev;
prev=temp;
}
*p=prev;
}

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

This problem can be easily solved with the help of recursion.
node* nReverse

node* reverse(node* root)
{
if(root->next == NULL)
{
nReverse = root;
return nreverse;
}

temp = reverse(root->next);
temp->next = root;
return root;
}

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

``````struct node *rev(struct node *head)
{
struct node *a, *b;
a = head;
if(!a || !a->next)return a;
head = rev(head->next);
a->next->next = a;
a->next = 0;
return head;
}``````

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

``````struct node
{
int data;
node *next;
};

//create the LL
//node *head; -> points to start of LL
node *current = head;
node *next = head;
node *prev = NULL;
while(next)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}``````

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

C# version reverse linked list using recursion

``````Node reverseRecurse(Node prev, Node cur)
{
if(cur==null) return cur;

Node head;

//recursion first
if(cur.next!=null)
head=reverseRecurse(cur,cur.next);
else
head=cur;

//revert pointer
cur.next=prev;

//handle last level recursion
return head;
}

main()
{
Node list;
list = reverseRecurse(null, list);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ //sudo code !! nonrecursivereverse(head) { if(head==null || head->next==null) return head; prev = head; curr = head->next; while(curr) { temp = curr->next; curr->next = prev; prev = curr; curr = temp; } head = prev; }
Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//sudo code !!

Node *head;

main()
{
reverse(head)->next = null;
}

node* reverse(curr)
{
if(curr->next) reverse(curr->next)->next = curr;
else head = curr;
return curr;
}``````

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

If there are no restrictions on memory usage, you can use an external stack.

func reverseLinkedList(Node *head)
Node temp = head
while (temp!= NULL)
Stack.push(temp->data)
temp=temp->next;
//Now pop the elements back. you have it in the reverse order

while(Stack.isEmpty)
Node node
if(!head)
head = node
head->next = NULL
else
node->data = pop()
node->next = head
head = node

return head

I haven't done error correction, but the iterative code would be some what like above.
You can also have a recursive version in a similar fashion.

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

void reverse_LL(*root, *head)
{
if(root == NULL || root->next == NULL)
{
head = root;
return;
}

if(root->next->next == NULL)
{
head = root->next;
root->next->next = root;
root->next = NULL;
return;
}

reverse(root->next, head);
root->next->next = root;
root->next = NULL;
return;
}

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

I don't think "if(root->next->next == NULL)" is necessary, since you already considered when root->next == NULL.

so the code would be:

void reverse_LL(*root, *head)
{
if(root == NULL || root->next == NULL)
{
head = root;
return;
}

reverse(root->next, head);
root->next->next = root;
root->next = NULL;
}

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

void reverseListRecur( Node ** pphead)

{ if(!pphead||!*pphead||!(*pphead)->next) return;

Node * first = *pphead;
Node* rest = first->next;
reverseListRecur(&rest);
first->next->next = first;
first->next = NULL;

*pphead = rest;
};

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

the version by euv921, modify to,

// root is the original head, head is the new head of the list.
void reverse_LL(Node ** root, Node** head)
{
if(root == NULL || (*root)->next == NULL)
{
*head = *root;
return;
}

reverse_LL(&(*root)->next, head);
(*root)->next->next = *root;
(*root)->next = NULL;
};

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

help other engineers to save time ......

// my version, works, //
void reverseList( Node ** pphead)

{ if(!*pphead) return;

Node * tmp;
Node* current;
Node * result = NULL;

current = *pphead;

while(current)
{ tmp = current->next;
current->next = result;
result = current;
current = tmp; }

*pphead = result;
};

void reverseListRecur( Node ** pphead)

{ if(!pphead||!*pphead||!(*pphead)->next) return;

Node * first = *pphead;
Node* rest = first->next;
reverseListRecur(&rest);
first->next->next = first;
first->next = NULL;

*pphead = rest;
};

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

Node reverse(Node head){
if(head != null) return rev_help(null,head)
else return head;

}

Node rev_help(Node prev, Node curr){

if(curr.next == null){
curr.next = prev;
return curr;
}else{
Node head = rev_help(curr, curr.next);
curr.next = prev;
return head;
}
}

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

It would mostly work... I hope ;)

``````node* reverse(node* head)
{
node* temp;

if(!head)  // If empty list, empty list would be the result
return NULL;

if(!head->next)  // If it is a single node or last node,
return head;     //it would again be the reversed one

temp = reverse(head->next);  // Reverse the remaining part of the list
head -> next -> next = head;  // Come back, and reverse the link between the nodes
head -> next = NULL;  // This is just a case for the head of the list

return temp;  // Returns the head of the reversed linked list
}``````

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

Correcting the logic

``````struct node* reverseTheList(struct node* head) {

if(head->next != NULL) {
struct node* tmp = reverseTheList(head->next);
head->next->next = head;
head->next = NULL;
return tmp;
} else {
return head;
}
}``````

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

sandy880.blogspot(dot)com/2011/09/linked-lists-reverse-singly-linked-list(dot)html

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

sandy880.blogspot.com/2011/09/linked-lists-reverse-singly-linked-list.html

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

//Create a class Node

public class Node {

String key;

public String getKey() {
return key;
}

public void setKey(String key) {
this.key = key;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

Node next ;

}

//Create a Singly Linked List
public class LinkedList {

Node HEAD;

Node TAIL;

public LinkedList(Node HEAD,Node TAIL) {
this.HEAD = HEAD;
this.TAIL = TAIL;
}

public void traveseList(){
Node n = this.HEAD;

while(n != null){
System.out.println("Value at Node::" + n.getKey());
n = n.getNext();
}
}

public void reverseList(){

Node n,n1,n2;
n = this.HEAD;
n1 = n.getNext();
n2 = n1.getNext();
this.TAIL = n;
n.setNext(null);
while(n1.getNext() != null){
n1.setNext(n);
n = n1;
n1 = n2;
n2 = n2.getNext();
}
n1.setNext(n);
this.HEAD = n1;
}

public static void main(String[] args) {

Node n1 = new Node();
Node n2 = new Node();
Node n3 = new Node();
Node n4 = new Node();
Node n5 = new Node();
Node n6 = new Node();

n1.setKey("JAVA");
n2.setKey("RUBY");
n3.setKey("HTML");
n4.setKey("C++");
n5.setKey("C");
n6.setKey("Obj C");

n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(null);

LinkedList list = new LinkedList(n1, n6);
list.traveseList();
list.reverseList(); // Reverse the list
System.out.println("Revers List...");
list.traveseList();
}
}

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

public void reverse(Listnode n) {
if (n == null) { return; }

if (n.next == null) {
head = n;
return; }

reverse(n.next);
n.next.next = n;
n.next = null;
}

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

the program uses some ideas of tail recursive....

``````node* _rev_list(node*old,node*new)
{
if(!old)
return new;
node* temp=(node*)malloc(sizeof(node));
temp->next=new;
temp->v=old->v;
return _rev_list(old->next,temp);
}
node* rev_list(node*list)
{
return _rev_list(list,0);
}``````

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

/* Let j be pointer to 1st node of list then initial call ll be list_rec_reverse(&j, NULL, j) */

void list_rec_reverse(list **l, list *prev, list *curr)
{
if(NULL == curr)
{
*l=prev;
return;
}

list_rec_reverse(l,curr,curr->next);
curr->next = prev;
}

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

Reversing the linked lists can be in two ways and are explained well in the following location. Anyways, thanks for posting such a useful content here and please keep sharing the information in the future.

cpptutorials.com Reversing the Linked lists in Cpp

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

Reversing the linked lists can be in two ways and are explained well in the following location. Anyways, thanks for posting such a useful content here and please keep sharing the information in the future.

cpptutorials.com Reversing the Linked lists in Cpp

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

``````node *rev(node *root)
{
node *rev = NULL;
node *temp = root;
while (temp){
node *current = temp->next;
temp->next = rev;
rev = temp;
temp = current;
}
return rev;
}

node *rev(node *root)
{
if (!root)
return NULL;
node *head = rev(root->next);
root->next->next = root;
root->next = NULL;
return head;
}``````

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

``````node *rev(node *root)
{
node *rev = NULL;
node *temp = root;
while (temp){
node *current = temp->next;
temp->next = rev;
rev = temp;
temp = current;
}
return rev;
}

node *rev(node *root)
{
if (!root)
return NULL;
node *head = rev(root->next);
root->next->next = root;
root->next = NULL;
return head;
}``````

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

Solution:

``````public void ReverseList()
{
Node loop = Head;
Node reverse = null;
Node temp = null;

Console.Clear();
Console.WriteLine("\nOriginal List.....");
DisplayList();

while (loop != null)
{
temp = loop.Next;
loop.Next = reverse;
reverse = loop;
loop = temp;
}

Head = reverse;
Console.WriteLine("\nReversed List....");
DisplayList();``````

}

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