Bloomberg LP Amazon Interview Question
Financial Software Developers Software Engineer / DevelopersHow stack is different from Recursion ...Please try to understand the intention of interviewers and also intention of questions ..
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.
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.. :-)
void printRev(const node* node) {
if (node) {
printRev(node->next);
cout << node->value << endl;
}
}
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;
}
}
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"?
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.
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.
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)
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);
}
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 ;
}
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();
}
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.
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
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
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)
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());
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;
}
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);
}
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);
}
}
Since space is not a restriction, a simple solution would be to use a stack...
- Rahul Arakeri January 10, 2012Start 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)