CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

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

- S February 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect!

- Anonymous February 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution

- Monty January 15, 2012 | Flag
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;
}

- ms September 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awsm solution !!!! gr8..

- sd March 24, 2014 | Flag
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;
}

- Anonymous November 27, 2014 | Flag
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)

- Anonymous January 27, 2015 | Flag
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

- vivekraju.m May 08, 2012 | Flag Reply
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();
	}
}

- syl20j October 26, 2010 | Flag Reply
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;

        }
}

- Kris November 05, 2010 | Flag Reply
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;
}

- yeda_anna November 12, 2010 | Flag Reply
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;
}

- skagrawal10 November 21, 2010 | Flag Reply
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;
 }

- Anonymous December 09, 2010 | Flag Reply
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;
}

- Anonymous December 23, 2010 | Flag Reply
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);
}

- jiangok January 21, 2011 | Flag Reply
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; } - trythis February 09, 2011 | Flag Reply
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;
}

- trythis February 09, 2011 | Flag Reply
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.

- O(1) February 19, 2011 | Flag Reply
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;
}

- Rahul February 21, 2011 | Flag Reply
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;
}

- euv921 March 02, 2011 | Flag
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;
};

- jacky March 18, 2011 | Flag Reply
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;
};

- zhujianle March 19, 2011 | Flag Reply
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;
};

- zhujianle March 19, 2011 | Flag Reply
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;
}
}

- Anonymous June 19, 2011 | Flag Reply
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
}

- Sangeeth Kumar July 12, 2011 | Flag Reply
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;
	}
}

- f2003062 May 01, 2013 | Flag
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

- Anonymous September 14, 2011 | Flag Reply
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

- Anonymous September 14, 2011 | Flag
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();
}
}

- KKR June 25, 2012 | Flag Reply
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;
}

- anky August 22, 2013 | Flag Reply
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);
}

- lispc October 08, 2013 | Flag Reply
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;
}

- Anonymous November 27, 2014 | Flag Reply
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

- Santhi January 27, 2015 | Flag Reply
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

- Santhi January 27, 2015 | Flag Reply
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;
}

- aka July 22, 2015 | Flag Reply
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;
}

- aka July 22, 2015 | Flag Reply
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();

}

- Anonymous November 03, 2010 | Flag Reply


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