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

Perfect!

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

Nice solution

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

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

{
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

Awsm solution !!!! gr8..

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

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

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

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

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;}
}

}

Node n = new Node(v);
}

public int remove(){
throw new IllegalStateException("can't remove from empty list");
}
return v;
}

public void reverse(){
newTail.setNext(null);
}
}

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

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

// return sublist tail once reversed
private Node reverseSubList(Node n){
if( null == n.getNext()){
} else {
Node subListTail = reverseSubList(n.getNext());
subListTail.setNext(n);
}
return n;
}

public static void main(String[] args){

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;
}

}

{
private node List;
public int count=0;

{
List = null;
}
{
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 *a, *b;
if(!a || !a->next)return a;
a->next->next = a;
a->next = 0;
}

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 *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;

//recursion first
if(cur.next!=null)
else

//revert pointer
cur.next=prev;

//handle last level recursion
}

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

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

//sudo code !!

main()
{
}

node* reverse(curr)
{
if(curr->next) reverse(curr->next)->next = 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.

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
else
node->data = pop()

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

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

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

root->next->next = root;
root->next = NULL;
return;
}

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

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

so the code would be:

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

root->next->next = root;
root->next = NULL;
}

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

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

};

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

the version by euv921, modify to,

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

(*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, //

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

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

};

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

};

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

}

Node rev_help(Node prev, Node curr){

if(curr.next == null){
curr.next = prev;
return curr;
}else{
curr.next = prev;
}
}

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

It would mostly work... I hope ;)

{
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

}

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

Correcting the logic

struct node* reverseTheList(struct node* head) {

return tmp;
} else {
}
}

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

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

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 ;

}

Node TAIL;

this.TAIL = TAIL;
}

public void traveseList(){

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

public void reverseList(){

Node n,n1,n2;
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);
}

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

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) {
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;
root->next->next = root;
root->next = NULL;
}

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;
root->next->next = root;
root->next = NULL;
}

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

Solution:

public void ReverseList()
{
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;
}

Console.WriteLine("\nReversed List....");
DisplayList();

}

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.