Bloomberg LP Amazon Interview Question for Financial Software Developers Software Engineer / Developers






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

Since space is not a restriction, a simple solution would be to use a stack...

Start from the first node of the linked list and enter every element to the stack as you move on...
Once you reach the end of the LL, just print the stack contents...

Time complexity : O(n)
Space Complexity : O(n)

- Rahul Arakeri January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is the efficient solution! :)

- victor January 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is the efficient solution! :)

- victor January 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How stack is different from Recursion ...Please try to understand the intention of interviewers and also intention of questions ..

- Anonymous January 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A stack used in an iterative algorithm differs from recursion by, well, not being recursion, strictly speaking. This could be useful if, for example, a programming language didn't support recursion but supported dynamic data structures. Hey, they said ANY space usage...

I'd also note that you could just put the contents into an array and read it backwards.

- eugene.yarovoi January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree with eugene. But, apart from stack based solution, showing the understanding that recursion uses system stack will convince the interviewer on the candidates understanding of the concepts.. If any complexity, the solution metioned by 'sun', below, works.. :-)

- saga January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

to atleast store the data into the stack from a given linked list, you will have to make use of a pointer!!!

- anonymous January 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

void printRev(const node* node) {
    if (node) {
        printRev(node->next);
        cout << node->value << endl;
    }
}

- Anonymous July 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good Solution!!!

- Amit July 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree, a nice solution. Reminds me of the print a number in reverse problem.

It is essentially similar to the following, where we use an explict stack instead of relying implicitly on the recursion stack.

One advantage of below is we are not limited by the stack size as opposed to the recursive version.

void printRev(const Node *node)
{
    stack <node *> st;
    const Node *cur = node;
    
    while(cur)
    {
        st.push(cur);
        cur = cur->next;
    }
    
    while(!st.IsEmpty())
    {
        cur = st.pop();
        cout << cur->value << endl;
    }
}

- LOLer July 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I forgot new/delete for the stack, but you get the idea.

Better yet would be to use some kind of auto_ptr.

- LOLer July 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

What do you mean by linked list is dynamic?

I guess I'm missing something very crucial. I was thinking of using a stack to keep the pointers of the linked list. No recursion, and I'm not manipulating the pointers in the list itself. Can you elaborate on the "dynamic"?

- crdmp January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think what he means is that
EITHER
Linked List can grow or shrink dynamically i.e. even while computing the reverse order of the objects, someone can insert/delete nodes from the list.
OR
Linked List comprises of heterogenous kind of elements.
Anyways, leaving it to ano neemiss for actual explanation.

- Learner January 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think what he means is that
EITHER
Linked List can grow or shrink dynamically i.e. even while computing the reverse order of the objects, someone can insert/delete nodes from the list.
OR
Linked List comprises of heterogenous kind of elements.
Anyways, leaving it to ano neemiss for actual explanation.

- Learner January 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

my idea, have an extra pointer and a count.
in first iteration, loop through the end of linked list, and count the number of nodes in linked list.
print the last element.
decrement the count.
then on loop through the linked list count number of times and print the last element.
continue till count is 0.
time complexity O(n^2)

- sun January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

private static void reverse(LinkedList<Integer> lList) {
LinkedList<Integer> temp = new LinkedList<Integer>();
LinkedList<Integer> lList2 = new LinkedList<Integer>();
lList2 = lList;
int len = lList.size();
int t;
for (int i = 0; i < len; i++) {
t = lList2.getLast();
lList2.removeLast();
temp.add(t);
}
System.out.println("Linked List:" + lList2);
System.out.println("reverse Linked List:" + temp);

}

- ben January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

another simple method, hve 3 pointers , back , middle, front

reverse(list *header)
{
middle = header;
front = middle->next;
back = null ;
while(1)
{
// reverse the link for middle node
middle->next = back ;
// reached end of list break
if (front == NULL) break;

// move ahead one node @ a time all the 3 pointers
back = middle;
middle = front;
front = front->next;
}
// middle now points to the last node in the original list.
header = middle ;
}

- Arvind January 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good one Arvind!

- Shyam February 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

my soln:

print(list *head)
{
if( head)
print(head->link);
printf("%d",head->data);
return;
}

- Dinakaran.A .GCT August 02, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the first solution is clear enough, avoiding the machine stack depth.

- googler August 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Stack solution however is of order Omega(2N), but doing things iteratively naturally leads to less memory usage (bar stack allocation) due to unstacked function calls.

- Mathematician December 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct node
{
int a;
struct node*link;
};


struct node*head;


void rev_linklist()
{

struct node* prev_ptr , *temp , *for_ptr;

prev_ptr = head;
temp = for_ptr = head->link;

prev_ptr->link = NULL;

while(for_ptr->link != NULL)
{
temp = for_ptr;
for_ptr = for_ptr -> link;
temp ->link = prev_ptr;
prev_ptr = temp;
}

for_ptr->link = temp;
head = for_ptr;

traverse();

}

- raja roy August 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

note sure abt the question but you could always create a list of objects in one iteration (as space complexity is not an issue), then print the list in reverse.... not sure if we understand the question.

- akash.bhunchal January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why to take the pain of adding in a stack. simply store the values in an array , reverse it and put in back in the link list. ( it is better to use an array instead of stack , if we are using additional space(

- hajju February 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

one solution is, find the length of the linked list say n. then traverse the list through n/2, and push into stack from n/2 to n links... Now again start from beginning and swap first link with pop the stack element, and swap second link with pop the next element in stack, continue this till stack is empty

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

Using a stack is the obvious answer but this is pretty much equals to do-it-yourself-recursive.

- Selmeczy, P├ęter January 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create another double linked list with tail pointer.

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

using stack can do the reverse of linked list other than recursive or manipulating data/pointers

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

Maybe I'm missing something, but it's possible to create reversed copy of the list like this:

and

Node = namedtuple("Node", ["value", "next"])

def reverse(n):
cur = None
while n != None:
cur = Node(n.value, cur)
n = n.next
return cur

and

- filipovskii_off January 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, here is the code

Node = namedtuple("Node", ["value", "next"])

def reverse(n):
    cur = None
    while n != None:
        cur = Node(n.value, cur)
        n = n.next
    return cur

time and space O(n)

- Filipovskii.Off January 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can't modify the list.
Neither do we actually have to reverse the linked list. We just need to print in a reverse order.

- r.sachdeva9355 August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

printReversedLinkedList(Node node){

String reversedValue =  new String();
while(node !=null){

reversedValue =node.value+reversedValue;
node=node.next;
}
System.out.println(s);
}

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

You could also just use StringBuffer if coding in java. Similar to Sidhavratha's solution, but perhaps slightly more simple.

Also O(n) time!

Public void printReverseLinkedList(Node node) {
StringBuffer sb = new StringBuffer();
while (node != null ) {
sb.append(node.value);
node = node.next;

}
System.out.println(sb.reverse().toString());

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

or

void print_rev(list* head){

     if(head == NULL){
          return;
     }
     else{
          print_rev(head->next);
          cout << head->value << " ";
     }
}

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

we can take one more list and keep adding elemnts in the front, and then traverse the newly created linked list, and it will contain the objects in reverse order only

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

public String printReverse(LinkedListNode head)
	{
		int count = 0;
		LinkedListNode current = head;
		if(head == null)
			return null;
		while(current != null)
		{
			count++;
			current = current.next;
		}
		String str = "";
		while(count > 0)
		{
			int currCount = 0;
			current = head;
			while(current != null)
			{
				currCount++;
				if(currCount == count)
				{
					str += current.value;
					count--;
				}
				current = current.next;
			}
		}
		return str;
	}

- hello world January 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can add a break statement in the if loop ;) sorry missed that :D

- hello world January 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the questions says u can use an additional space , then the simplest ans is to store the contents of list in an array. Sort the array ( swap (a[0],a[n-1]), swap(a[1],a[n-2)...and so on). Once the array is sorted , put the value back in list. its O(n) solution.

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

declare a linked list
Linkedlist<Integer> l1 = new Linkedlist<Integer>();
int lsize;

l1.add("1");
l1.add("2");
l1.add("3");
l1.add("4");

lsize=l1.size();

for (i= lsize;i>=0;i--)
{
System.out.println(" the rev order" +l1.get(i));
}

- QC February 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just traverse the linked list and reverse the next links and once you get to the end of the list, traverse back and print.

- amshali March 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just traverse the linked list and reverse the next links and once you get to the end of the list, traverse back and print.

- amshali March 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think storing addresses of a list that is dynamic is not good. Its better to clone the data as well. Again if you use a fixed size stack you need to parse the list at least once to get the size, and a dynamic stack is just a list abstracted in a way that it looks like a stack.

#include <iostream>

struct Node
{
    int data;
    Node* next;
    Node():data(0),next(NULL){}
    Node(int x):data(x),next(NULL){}
    Node(Node& that):data(that.data),next(NULL){}
};
std::ostream& operator<<(std::ostream& cout, Node node){
    std::cout << node.data << ": ";
}

struct NodeAddr
{
    Node* addr;
    NodeAddr* next;
    NodeAddr(Node& node):next(NULL){
        addr = &node;
    }
};
std::ostream& operator<<(std::ostream& cout, NodeAddr node){
    if(node.addr)
        cout << *(node.addr);
}

template <class T>
class List
{
public:
    List():mHead(NULL) {}
    List(int count):mHead(NULL) { create(count); }

    ~List()
    {
        while(mHead){
            T* temp = mHead;
            mHead = mHead->next;
            delete temp;
        }
    }

    void prepend(T* node)
    {
        if(mHead == NULL)
            mHead = node;
        else{
            node->next = mHead;
            mHead = node;
        }
    }
    template <typename U>
    void cloneReverseFrom(List<U>& source)
    {
        U* headNode = source.getHeadPtr();
        while(headNode)
        {
            T* node = new T(*headNode);
            prepend(node);
            headNode = headNode->next;
        }
    }

    T* getHeadPtr() {return mHead;}
private:
    void create(int count)
    {
        T* temp = NULL;
        for(int i = 0 ; i < count; i++)
        {
            if(mHead == NULL)
            {
                mHead = new T(i);
                temp = mHead;
            }
            else
            {
                temp->next = new T(i);
                temp = temp->next;
            }
        }
    }
    T* mHead;
};

template <typename T>
std::ostream& operator<<(std::ostream& cout, List<T>& myList)
{
    T* obj = myList.getHeadPtr();
    while(obj){
        cout << *obj;
        obj = obj->next;
    }
    std::cout << std::endl;
}

template <typename T>
void printReverse(List<T>& source)
{
    //Holding Addresses: Not good if input list is dynamic
    List<NodeAddr> list2;
    list2.cloneReverseFrom(source);
    std::cout << list2;

    //Copying Data: works for a dynamic list
    List<Node> list3;
    list3.cloneReverseFrom(source);
    std::cout << list3;
}

int main()
{
    List<Node> list(10);
    std::cout << list;
    printReverse(list);
}

- Abhinav Tandon March 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;

public class PrintLLReverse {
	public static void print(ArrayList<Integer> list) {
		print_helper(list, 0);
	}

	private static void print_helper(ArrayList<Integer> list, int position) {
		if (position >= list.size() - 1) {
			System.out.print(list.get(position) + "\t");
			return;
		}
		print_helper(list, position + 1);
		System.out.print(list.get(position) + "\t");
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(4);
		list.add(5);
		list.add(6);
		list.add(7);
		list.add(6);
		list.add(2);
		list.add(1);
		list.add(9);
		list.add(0);
		print(list);
	}

}

- Kevin February 06, 2013 | 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