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

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

this is the efficient solution! :)

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

this is the efficient solution! :)

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

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

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

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.

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

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.. :-)

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

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

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

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

Good Solution!!!

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

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

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

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

Better yet would be to use some kind of auto_ptr.

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"?

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

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.

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

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.

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)

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

private static void reverse(LinkedList<Integer> lList) {
lList2 = lList;
int len = lList.size();
int t;
for (int i = 0; i < len; i++) {
t = lList2.getLast();
lList2.removeLast();
}

}

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

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

{
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.
}

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

Good one Arvind!

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

my soln:

{
return;
}

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

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

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.

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

struct node
{
int a;
};

{

struct node* prev_ptr , *temp , *for_ptr;

{
temp = for_ptr;
prev_ptr = temp;
}

traverse();

}

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.

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

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(

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

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.

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

Create another double linked list with tail pointer.

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

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

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

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)

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

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.

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

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!

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

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

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

or

``````void print_rev(list* head){

return;
}
else{
cout << head->value << " ";
}
}``````

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

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

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

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

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

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.

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

int lsize;

lsize=l1.size();

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

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.

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.

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

{
}
};
}

template <class T>
class List
{
public:

~List()
{
delete temp;
}
}

void prepend(T* node)
{
else{
}
}
template <typename U>
void cloneReverseFrom(List<U>& source)
{
{
prepend(node);
}
}

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

template <typename T>
std::ostream& operator<<(std::ostream& cout, List<T>& myList)
{
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
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);
}``````

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>();
print(list);
}

}``````

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.