## Google Interview Question for Software Engineer Interns

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
5
of 7 vote

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

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

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?

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

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!

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

how about inserting at the last and inserting at the beginning

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

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.

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

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.

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

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.

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

Most basic operation on a list is traversal. How would you do this in your case?

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

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

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

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

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

to complex, I will post my

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

``````/*
* 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
}
}``````

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

``````/*
* 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
}
}``````

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

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.

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

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.

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

typical google problem, building one DS from another.

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