Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: Written Test
This solution is brilliant. Though, I do have a question. Since a doubly linked list usually has both head and tail pointers, how do we keep the ability of traversing via tail? It seems that we can traverse via head by keeping only one element in the left stack and all of the rest in the right stack, correct?
This solution is really good. But I think you need another two stacks so that you can traverse via the tail:
1,2,3,4 -> <-5,6,7,8 first pair of stacks
8,7,6,5 -> <-4,3,2,1 second pair of stacks kept in reverse order
once current stack runs out
empty-><-1,2,3,4,5,6,7,8 first pair of stacks is currently being traversed
empty-><-8,7,6,5,4,3,2,1 second pair of stacks
simply switch to the second pair of stacks!
next() and previous() ca be easily done with two stacks as shown above. But addLast() can be achieved in O(1) only if the last element is always at the top of the stack(which comes with a cost of popping elements back to the first stack). Using a pair of two stacks for maintaining the head and tail of the list is not a good idea because if we add element to one pair of stacks the same should be added to the second pair of stacks too. And that will cost O(n) which is not good. Two pair of stacks solution is feasible but not efficient.
a double linked list should have these operation
go_pre
go_next
insert
delete
so we can use two stack to simulate a double linked list
stack1 store the data before the pointer now ,stack2 store the data after the pointer.
insert : push this element to s1
delete: pop element from s1
go_pre operation we can pop the top element from s1, and push to s2.
go_next : pop the element from s2 and push to s1.
this is the basic solution every operation is O(1)
these is some specific part need to be pay attention to.
I would ask what are the EXACT operations to support on the new DS. I will assume the required DS is a double linked list the same as that of java (LinkedList<>) so, here are the main ops:
1- Add/Remove first
2- Add/Remove last
Use first stack to add to the head, and the second stack for adding to the tail. Removing is simply popping from the corresponding stack. So far, everything O(1).
Problem is when one stack is empty, i.e., you pop from stack 2 until it is empty. The next tail is indeed the last element of stack 1 now.
To avoid this situation and keep stacks balanced, whenever size of one stack becomes much larger than the other, we can use some external memory to rearrange and balance the stacks. The amortized cost is O(N), e.g.,
say stack 1 has size N and stack 2 size 3xN. In 4N operations we can make them
of size 2N and 2N. Now we need at least 4N inserts or 4/3N consecutive removes from one stack to get into unbalanced state. Either way, the amortized cost is between 1-3 basic operations per DS function.
Implementation
import java.util.Stack;
class DoubleLinkedList{
Stack<Integer> s;
Stack<Integer> t;
int count;
DoubleLinkedList(){
s = new Stack<Integer>();
t = new Stack<Integer>();
count = 0;
}
public void insertInBeginning(int data){
while(!s.isEmpty()){
t.push(s.pop());
}
s.push(data);
count++;
}
public void insertAtEnd(int data){
while(!t.isEmpty()){
s.push(t.pop());
}
t.push(data);
count++;
}
public void moveForward(){
while(!t.isEmpty()){
int temp = t.pop();
System.out.println(temp);
s.push(temp);
}
}
public void moveBackward(){
while(!s.isEmpty()){
int temp = s.pop();
System.out.println(temp);
t.push(temp);
}
}
public void delete(int data){
while(!s.isEmpty()){
t.push(s.pop());
}
while(!t.isEmpty()){
if(t.peek() == data){
t.pop();
return;
}
else{
s.push(t.pop());
}
}
}
public void deleteFirst(){
while(!s.isEmpty()){
int temp = s.pop();
if(s.peek() == null){
return;
}
t.push(temp);
}
}
public void deleteLast(){
while(!t.isEmpty()){
int temp = t.pop();
if(t.peek() == null){
return;
}
s.push(temp);
}
}
}
class P2{
public static void main(String args[]){
DoubleLinkedList list = new DoubleLinkedList();
list.insertInBeginning(4);
list.insertInBeginning(3);
list.insertInBeginning(2);
list.insertInBeginning(1);
list.insertAtEnd(5);
list.insertAtEnd(6);
list.insertAtEnd(7);
list.moveBackward();
list.moveForward();
list.delete(5);
list.moveBackward();
list.moveForward();
}
}
/*Logic
Imagine all items are organized into two stacks, draw them facing each other where face is where you put and peek:
1,2,3,4-><-5,6,7,8
now you can move 4 to 5:
1,2,3-><-4,5,6,7,8
and 3 to 4:
1,2-><-3,4,5,6,7,8
and you can go backwards
So we can imagine two stacks, storing data as follows
S T
4 5
3 6
2 7
1*/
double linked list means should be able to traverse from both ends.
stack 1: which will be traversed from end to start
stack 2 reverse: which will be traversed from start to end
implement reverse stack optimally
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package ds1;
import java.util.Scanner;
/**
*
* @author brian
*/
class stack
{
static int top=-1;
static int top1=-1;
node[] put=new node[30];
node put1[]=new node[30];
void pushh(node temp)
{
top++;
put[top]=new node();
put[top]=temp;
}
void pusht(node temp)
{
top1++;
put1[top1]=new node();
put1[top1]=temp;
}
}
class node
{
int data ;
node left;
node right;
}
class link
{
static stack obj1=new stack();
node obj;
node head;
node tail;
void insertfromhead(int data1)
{
if(head==null)
{
obj=new node();
obj.left=null;
obj.data=data1;
if(obj1.top1==-1)
obj.right=null;
else{
obj.right=obj1.put1[obj1.top1];
}
obj1.pushh(obj);
if(obj1.top1!=-1)
obj1.put1[obj1.top1].left=obj;
head=obj;
}
else
{
node temp,prev;
temp=head;
while(temp.right!=null)
{
prev=temp;
temp=temp.right;
}
obj=new node();
temp.right=obj;
obj.left=temp;
obj.data=data1;
if(obj1.top1==-1)
obj.right=null;
else
obj.right=obj1.put1[obj1.top1];
obj1.pushh(obj);
if(obj1.top1!=-1)
obj1.put1[obj1.top1].left=obj;
}
}
public void disp()
{
node temp=head;
if(temp==null)
{
System.out.println("no element at start");
}
while(temp!=null){
System.out.println(temp.data);
temp=temp.right;
}
}
void deletebeg()
{
node temp;
temp=head;
if(head==null)
{
if(tail==null)
return;}
else
{
if(head.right==null)
{
System.out.println("Last element of head deleted");
if(tail==head)
{
tail=null;
head=null;
}
}
else{
head=head.right;
head.left=null;}
temp=null;
}
}
void deleteatend()
{
node temp;
temp=tail;
if(tail==null)
{
if(head==null)
return;}
else
{
if(tail.left==null)
{
if(tail==head)
{
tail=null;
head=null;
}
System.out.println("Last element Delleted");
}
else{
tail=tail.left;
tail.right=null;
}temp=null;
}}
void insertfromtail(int data1)
{
if(tail==null)
{
obj=new node();
if(obj1.top==-1)
obj.left=null;
else
{
obj.left=obj1.put[obj1.top];
}
obj.data=data1;
obj.right=null;
tail=obj;
obj1.pusht(obj);
if(obj1.top!=-1)
obj1.put[obj1.top].right=obj;
}
else
{
node temp,prev;
temp=head;
while(temp.right!=null)
{
prev=temp;
temp=temp.right;
}
obj=new node();
temp.right=obj;
obj.left=temp;
obj.data=data1;
obj.right=null;
tail=obj;
obj1.pushh(obj);
}
}
public void disp1()
{
node temp=tail;
if(temp==null)
{
System.out.println("no element at end");
}
while(temp!=null){
System.out.println(temp.data);
temp=temp.left;
}
}
}
public class Ds1 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
link obj=new link();
int d=1;
int data;
while(true){
System.out.println("1]ENter elements from head");
System.out.println("2]Enter elements from tail");
System.out.println("3]Display elements from start to end");
System.out.println("4]Display elements from end to start");
System.out.println("5]Delete elements from head");
System.out.println("6]Delete elements from tail");
System.out.println("7]Exit");
int choice=s.nextInt();
switch(choice)
{
case 1:
System.out.println("Enter a number to be inserted");
data=s.nextInt();
obj.insertfromhead(data);
break;
case 2:
System.out.println("Enter a number to be inserted from tail");
data=s.nextInt();
obj.insertfromtail(data);
break;
case 3:
System.out.println("Display elements from start to end");
obj.disp();
break;
case 4:
System.out.println("Display elements from end to start");
obj.disp1();
break;
case 5:
obj.deletebeg();
break;
case 6:
obj.deleteatend();
break;
case 7:
System.exit(0);
}
}
// TODO code application logic here
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package ds1;
import java.util.Scanner;
/**
*
* @author brian
*/
class stack
{
static int top=-1;
static int top1=-1;
node[] put=new node[30];
node put1[]=new node[30];
void pushh(node temp)
{
top++;
put[top]=new node();
put[top]=temp;
}
void pusht(node temp)
{
top1++;
put1[top1]=new node();
put1[top1]=temp;
}
}
class node
{
int data ;
node left;
node right;
}
class link
{
static stack obj1=new stack();
node obj;
node head;
node tail;
void insertfromhead(int data1)
{
if(head==null)
{
obj=new node();
obj.left=null;
obj.data=data1;
if(obj1.top1==-1)
obj.right=null;
else{
obj.right=obj1.put1[obj1.top1];
}
obj1.pushh(obj);
if(obj1.top1!=-1)
obj1.put1[obj1.top1].left=obj;
head=obj;
}
else
{
node temp,prev;
temp=head;
while(temp.right!=null)
{
prev=temp;
temp=temp.right;
}
obj=new node();
temp.right=obj;
obj.left=temp;
obj.data=data1;
if(obj1.top1==-1)
obj.right=null;
else
obj.right=obj1.put1[obj1.top1];
obj1.pushh(obj);
if(obj1.top1!=-1)
obj1.put1[obj1.top1].left=obj;
}
}
public void disp()
{
node temp=head;
if(temp==null)
{
System.out.println("no element at start");
}
while(temp!=null){
System.out.println(temp.data);
temp=temp.right;
}
}
void deletebeg()
{
node temp;
temp=head;
if(head==null)
{
if(tail==null)
return;}
else
{
if(head.right==null)
{
System.out.println("Last element of head deleted");
if(tail==head)
{
tail=null;
head=null;
}
}
else{
head=head.right;
head.left=null;}
temp=null;
}
}
void deleteatend()
{
node temp;
temp=tail;
if(tail==null)
{
if(head==null)
return;}
else
{
if(tail.left==null)
{
if(tail==head)
{
tail=null;
head=null;
}
System.out.println("Last element Delleted");
}
else{
tail=tail.left;
tail.right=null;
}temp=null;
}}
void insertfromtail(int data1)
{
if(tail==null)
{
obj=new node();
if(obj1.top==-1)
obj.left=null;
else
{
obj.left=obj1.put[obj1.top];
}
obj.data=data1;
obj.right=null;
tail=obj;
obj1.pusht(obj);
if(obj1.top!=-1)
obj1.put[obj1.top].right=obj;
}
else
{
node temp,prev;
temp=head;
while(temp.right!=null)
{
prev=temp;
temp=temp.right;
}
obj=new node();
temp.right=obj;
obj.left=temp;
obj.data=data1;
obj.right=null;
tail=obj;
obj1.pushh(obj);
}
}
public void disp1()
{
node temp=tail;
if(temp==null)
{
System.out.println("no element at end");
}
while(temp!=null){
System.out.println(temp.data);
temp=temp.left;
}
}
}
public class Ds1 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
link obj=new link();
int d=1;
int data;
while(true){
System.out.println("1]ENter elements from head");
System.out.println("2]Enter elements from tail");
System.out.println("3]Display elements from start to end");
System.out.println("4]Display elements from end to start");
System.out.println("5]Delete elements from head");
System.out.println("6]Delete elements from tail");
System.out.println("7]Exit");
int choice=s.nextInt();
switch(choice)
{
case 1:
System.out.println("Enter a number to be inserted");
data=s.nextInt();
obj.insertfromhead(data);
break;
case 2:
System.out.println("Enter a number to be inserted from tail");
data=s.nextInt();
obj.insertfromtail(data);
break;
case 3:
System.out.println("Display elements from start to end");
obj.disp();
break;
case 4:
System.out.println("Display elements from end to start");
obj.disp1();
break;
case 5:
obj.deletebeg();
break;
case 6:
obj.deleteatend();
break;
case 7:
System.exit(0);
}
}
// TODO code application logic here
}
}
Have a solution, to have 2 stacks, one keeping the data as given and other keeping the same data in reverse order,
When needs to be added from back, add to second stack and viceversa.
In needs to be added or deleted from between, check the number of pop() operation required if traversed from front or back and choose the smaller, thus making it optimal.
Based upon the approach mentioned by CT in the first comment this is a class in Java
public class DoubleLinkListUsingStack<E> {
private Stack<E> h = new Stack<E>();
private Stack<E> t = new Stack<E>();
private int size = 0;
/*
* Returns number of elements in the list
*/
public int size(){
return size;
}
/*
* Inserts the specified element at the beginning of this list.
*/
public void addFirst(E element){
if(h.empty()){
h.push(element);
}else{
while(!h.empty()){
t.push(h.pop());
}
h.push(element);
}
size++;
}
/*
* Inserts the specified element at the end of this list.
*/
public void addLast(E element){
if(t.empty()){
t.push(element);
}else{
while(!t.empty()){
h.push(t.pop());
}
t.push(element);
}
size++;
}
/*
* Inserts the specified element at the specified index
*/
public void add(int index, E element){
if(index > size){
// Can't insert
System.out.println("Index out of bounds");
}else{
if(h.size() > index){
while(h.size()>index){
t.push(h.pop());
}
h.push(element);
size++;
}else{
while(h.size()<= index){
h.push(t.pop());
}
h.push(element);
size++;
}
}
}
/*
* Returns the index of the first occurrence of the specified element in this list,
* or -1 if this list does not contain the element.
*/
public int indexOf(E element){
while(!h.empty()){
t.push(h.pop());
}
while(t.peek()!= element){
h.push(t.pop());
}
if(t.empty()){
return -1;
}else{
return h.size();
}
}
/*
* Returns true if this list contains the specified element.
*/
public boolean contains(E element){
return indexOf(element) >= 0;
}
/*
* Replaces the element at the specified position in this list with the specified element.
*/
public void set(int index,E element){
if(index > size){
// Can't insert
System.out.println("Index out of bounds");
}else{
if(h.size() > index+1){
while(h.size() > index){
t.push(h.pop());
}
h.pop();
h.push(element);
}else{
while(h.size()<= index){
h.push(t.pop());
}
t.pop();
h.push(element);
}
}
}
/*
* Removes first occurrence of element in the list
*/
public void removeFirst(E element){
if(size == 0){
System.out.println("Stack Empty. Nothing to remove");
}else{
while(!h.empty()){
t.push(h.pop());
}
while(t.peek() != element){
h.push(t.pop());
}
if(!t.empty()){
t.pop();
}
size--;
}
}
/*
* Removes last occurrence of the element in the list
*/
public void removeLast(E element){
if(size == 0){
System.out.println("Stack Empty. Nothing to remove");
}else{
while(!t.empty()){
h.push(t.pop());
}
while(h.peek() != element){
t.push(h.pop());
}
if(!h.empty()){
h.pop();
}
size--;
}
}
/*
* Gets the first value in the List
*/
public E getFirst(){
while(h.size() > 1){
t.push(h.pop());
}
return h.peek();
}
/*
* Returns the last value in the list
*/
public E getLast(){
while(t.size() > 1){
h.push(t.pop());
}
return t.peek();
}
/*
* Returns the value at the specified index
*/
public E get(int index){
E val = null;
if(index > size-1){
return null; // index out of bounds
}else{
if(h.empty()){
// pop index number of times from t to h and then peek()
while(h.size() < index){
h.push(t.pop());
}
val = t.peek();
}else if(t.empty()){
// pop from h to t till index comes to top
while(h.size() > index+1){
t.push(h.pop());
}
val = h.peek();
}else if(index < h.size()){
// element is in stack h
while(h.size() > index+1){
t.push(h.pop());
}
val = h.peek();
}else{
// element is in stack t
while(h.size() < index){
h.push(t.pop());
}
val = t.peek();
}
}
return val;
}
}
Note: This might contain bugs as this has not been tested much.
Imagine all items are organized into two stacks, draw them facing each other where face is where you put and peek:
- CT October 21, 20141,2,3,4-><-5,6,7,8
now you can move 4 to 5:
1,2,3-><-4,5,6,7,8
and 3 to 4:
1,2-><-3,4,5,6,7,8
and you can go backwards