Google Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

I think we could implement the stack as doubly linked list. Each version keeps a pointer to the top of stack. As it has backward pointer, we can print the stack elements (from top to bottom). In this approach, push/pop is O(1), and print is O(n). Per version's space requirement is O(1).
For above example,

V1: 11 <-> null
V2: 8 <-> 11 <-> null
V3: 11 <-> null
V4: 15 <-> 11 <-> null

- lol September 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In your case the version requirement is O(1) if and only if say between V2 and V4. The 11'Node is shared. If it is shared either the prev of 11 is 8 or 15. It cannot be both

- Anonymous September 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you didn't get it quite properly.

At V1, 11.next = NULL.
At V2, 11.next = 8 (8.prev = 11).
At V3, 11.next = NULL.
At V4, 11.next got updated and set to 15 (15.prev = 11).

- lol September 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't see it causes any problem, if multiple nodes point to 11 here. Say, we've 2 more versions:

V5: pop -> points to stack-top (11)
V6: pop -> points to NULL

At this stage, node 11 must exist in the memory, i.e. you can't free up 11's space (otherwise there is no point of maintaining version controlling).

- lol September 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@lol
So how will your print work after V6 let say, if you want to print version 2?

- gadhacoder September 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

V2 points to top-of-stack for V2, which is 8. Follow the prev pointer of 8 which points to 11, then follow 11's prev that points to NULL.
So V2 prints: 8 11

- lol September 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Btw, it's sufficient to implement stack as singly LL. Doubly LL seems overkill just to print stack in either order.

- lol September 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@lol
Gr8 solution.
Just to confirm, in this case there will be multiple node can have same next pointer? Also, do we still call this structure as linked list?

- temp September 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Interesting would be to implement a total delete/free of this structure.

- Anonymous September 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Can you please elaborate with an example?

- Victor September 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include<stdio.h>
#include<stdlib.h>
struct node{
	int data;
	struct node *next;
};
struct node *version_array[10] = {0};
int version = 0;

void push(int ele)
{
	struct node *new_node =(struct node *)malloc(sizeof(struct node));
	new_node->data = ele;
	new_node->next = version_array[version];
	version_array[++version] = new_node;
}

int pop(void)
{
	struct node *temp = version_array[version];
	if(temp){
		int v = temp->data;		
		temp = temp->next;
		version_array[++version]= temp;
		return v;
	}else{
		puts("UnderFlow");
		exit(1);
	}
}

void print(int n)
{
	if(n > version || n < 0)
		puts("Version Not Exist");
	else{
		struct node *top = version_array[n];
		while(top){
			printf("%d\t",top->data);
			top = top->next;
		}
	}
}

int main()
{
	int v;	
	push(11);
	push(8);
	v = pop(); printf("%d ",v);
	push(5);
	v = pop(); printf("%d ",v);
	v = pop(); printf("%d ",v);
	puts("");
	print(3);
	puts("");
	print(2);
	puts("");
	print(5);
	return 0;
}

- venkat September 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is easier and faster way

You create one class : versionstack. Take stack and map as data member.
stack for push,pop operation
map to trace and store operations. <int,string>
check code below.

#include <iostream>
#include <stack>
#include <map>
#include <string>
#include <sstream>
using namespace std;
class versionstack{
    public:
        versionstack()
        {
            cnt =1; //it is key not array index
        }
        void Push(int n)
        {
            data.push(n);
            std::stringstream ss;
            ss << "pushed:" << n  ;
            trace[cnt++]= ss.str();
        }
        int Pop( )
        {
            if (!data.empty())
            {
                int n = data.top();
                data.pop();
                std::stringstream ss;
                ss << "popped:" << n  << " remaining:" << data.size();
                trace[cnt++]= ss.str();
                return n;
            }
        }
        void Print(int n)
        {
            cout << "Print:" << n << "  ->  " << trace[n] << endl;
        }
    private:
    stack<int> data;
    map<int,string> trace;
    int cnt;
};

int main()
{
    versionstack s1;

    s1.Push(12);
    s1.Push(1);
    int n = s1.Pop();
    s1.Print(3);


}

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

It will have complexity of O(1). Please correct me if i am wrong. I only posted this solution.

- miteshkoradia November 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.HashMap;
import java.util.Map;
import java.util.Random;
 
class VersionedStack {
  
 private static Node head = null;
 private static Map<Integer, Node> versionMap = new HashMap<Integer, Node>();
 private static int version = 0;
  
 public static void main(String[] args) {
  versionMap.put(version, head);
  head = push(head, 9);
  head = push(head, 10);
  head = push(head, 11);
  Node node = pop();
  head = push(head, 12);
  node = pop();
  node = pop();
  node = pop();
  node = pop();
  
  //print versions
  for (int i=0; i<=version; i++) { printVersionedStack(i); }
 }
  
 public static void printVersionedStack(int n) { 
  System.out.println("Version::" + n);
  if (n > version) {
   System.out.println("ERROR: version: " + n + " is out of range!");
   System.out.println("Latest version is: " + version);
  }
  Node node = versionMap.get(n);
  printSinglyList(node);
 }
  
 public static Node push(Node node, int value) {
  Node vnode = versionMap.get(version);
  Node head = new Node(value);
  head.next = vnode;
   
  //increase the version.
  versionMap.put(++version, head);
  return head;
 }
  
 public static Node pop() {
  Node node = versionMap.get(version);
  // if the stack is already null, we are not changing the version upon POP call on the stack.
  if (node == null) {
   return null;
  }
   
  //increase the version
  versionMap.put(++version, node.next);
  return node.next;  
 }
  
 public static void printSinglyList(Node node) {
  for (Node curr=node; curr != null; curr=curr.next) {
   System.out.print(curr.data + " -> ");
  }
  System.out.println("null");
 }
}
 
class Node {
 int data;
 Node next;
 
 public Node(int data) {
  this.data = data;
  this.next = null;
 }
}

}

- Rockstar July 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Have a hastable to keep track of corresponding element version value. Before you push check the hashtable and if you find the element ignore pushing and increment hashtable value. Similarly for pop when you pop the an element and the corresponding hashtable value is 1 then you remove the element from hashtable.

- Mat September 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am not sure how hash table helps here.

I guess giving an example would be better:
-> initially stack is empty.
-> Version 1: 11 is pushed
-> Version 2: 8 is pushed
-> version 3: pop. only 11 left
-> Version 4: 15 is pushed
....
And so on.

Print(n) should print state at version 'n'. Here 1 should print 11, 2 should print 8, 11...

Hope I made it clear.

My solutions:
1. Copy complete stack at each version and keep in an array or something. Huge space complexity & push/pop both are O(n) as you need to copy state at each step.

2. Keep a log of operations at states. As in, for the above example I would keep:
[0] push 11
[1] push 8
[2] pop
[3] push 15
...
Since on one extra step is required during push/pop, they are still O(1). Print is expensive. Basically I need to rerun all operations start from 1 till 'n' to get the state of version 'n'.

He wasn't very satisfied with my solutions and wanted me to improve. During my telephonic interview, I couldn't.

However now I can think of one trick. Basically a middle ground of both solutions. After 'm' steps, I'll copy the stack state. Say after every 10 operations. I mean:
-> keep log of operations from 1 to 9.
-> keep copy of stack state for version 10.
-> keep log of operations from 11 to 19.
-> keep copy of stack state for version 20.
....
Larger 'm' will tend to reduce the space but will make print expensive.

Can anybody do better?

- gadhacoder September 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry Mat. Because of my typo, description of print method became confusing. I should have said:
"print which would print stack STATE corresponding to stack version"

- gadhacoder September 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

push version no. along with it's value.
when there is a pop do the following.
(1) do pop
(2) again do pop
(3) now push the popped value along with the present version no. and already present version no. as a linked list in it.

Then whenever print(n) is required.
traverse the stack until you get that version . Once found, start printing the values of the remaining stack elements one by one.

- Anonymous September 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the best implementation will be if we extend Stack class and add 2 new variables to the class, one to keep a track of version and a hash table. At every push/ pop operation, we will add the element pushed/popped along with the vision into the hash table and increment the vision. Now at print(n) all we need to do is look up into the hash table for the vision. The time complexity for all the operation will be O(1). Memory will be O(n).

- Goooooooooogle October 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey97870" class="run-this">

import java.util.LinkedList;

/**
* Created by IntelliJ IDEA.
* User: user
* Date: 10/22/11
* Time: 9:42 PM
* To change this template use File | Settings | File Templates.
*/
public class VersionedStack {

private volatile int changeSetNumber;

private LinkedList<Integer> stack = new LinkedList<Integer>();
private LinkedList<ChangeElement> versionTracker = new LinkedList<ChangeElement>();

public synchronized void push (int elem) {
versionTracker.add(new ChangeElement(Operation.push, elem));
stack.push(elem);
}

public synchronized int pop() {
int elem = stack.pop();
versionTracker.add(new ChangeElement(Operation.pop, elem));
return elem;
}

public LinkedList<Integer> getVersion (int n) {
int changeSetNumber = versionTracker.size();
if (n < 0 || n > changeSetNumber) {
throw new IllegalArgumentException("No version " + n + " exists. ");
}
if (n==0) {
return new LinkedList<Integer>();
}
LinkedList<Integer> result = (LinkedList<Integer>) stack.clone() ;
for (int i = changeSetNumber-1; i> n-1; i--) {
ChangeElement changeElement = versionTracker.get(i);
if (changeElement.op.equals(Operation.push)) {
result.pop();
} else {
result.push(changeElement.element);
}
}
return result;
}

class ChangeElement {
Operation op;
int element;

ChangeElement(Operation op, int elem) {
this.op = op;
this.element = elem;
}
}

enum Operation {
push, pop
}

}
</pre><pre title="CodeMonkey97870" input="yes">
JUnit test case -


import junit.framework.Assert;
import org.junit.Test;

import java.util.List;

/**
* Created by IntelliJ IDEA.
* User: user
* Date: 10/22/11
* Time: 10:27 PM
* To change this template use File | Settings | File Templates.
*/
public class VersionedTaskTest {

@Test
public void testVersionedStack() {
VersionedStack versionedStack = new VersionedStack();
versionedStack.push(1);
versionedStack.push(2);
versionedStack.push(3);
Assert.assertEquals(versionedStack.pop(), 3);
versionedStack.push(4);
Assert.assertEquals(versionedStack.pop(), 4);
Assert.assertEquals(versionedStack.pop(), 2);
versionedStack.push(5);
versionedStack.getVersion(0);
Assert.assertTrue(compare(versionedStack.getVersion(5), new int[] {4, 2, 1}));
Assert.assertTrue(compare(versionedStack.getVersion(7), new int[] {1}));
}


private boolean compare (List<Integer> actualResult, int[] expectedResult) {
if (actualResult.size() != expectedResult.length) {
return false;
}
int counter = 0;
for (int elem : actualResult)
{
if (elem != expectedResult[counter]) {
return false;
}
counter++;
}
return true;
}

}
</pre>

- Anonymous October 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why not use check point?

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

By idea we can implemet this stack using tree. This tree has a root - beggining state. All leafs in tree connected in linked list. Each time we do push/pop - new branch is made and this new node added to linked list os states.

- gstepanov@griddynamics.com October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

class VersionedStack {

private static Node head = null;
private static Map<Integer, Node> versionMap = new HashMap<Integer, Node>();
private static int version = 0;

public static void main(String[] args) {
versionMap.put(version, head);
head = push(head, 9);
head = push(head, 10);
head = push(head, 11);
Node node = pop();
head = push(head, 12);
node = pop();
node = pop();
node = pop();
node = pop();

//print versions
for (int i=0; i<=version; i++) { printVersionedStack(i); }
}

public static void printVersionedStack(int n) {
System.out.println("Version::" + n);
if (n > version) {
System.out.println("ERROR: version: " + n + " is out of range!");
System.out.println("Latest version is: " + version);
}
Node node = versionMap.get(n);
printSinglyList(node);
}

public static Node push(Node node, int value) {
Node vnode = versionMap.get(version);
Node head = new Node(value);
head.next = vnode;

//increase the version.
versionMap.put(++version, head);
return head;
}

public static Node pop() {
Node node = versionMap.get(version);
// if the stack is already null, we are not changing the version upon POP call on the stack.
if (node == null) {
return null;
}

//increase the version
versionMap.put(++version, node.next);
return node.next;
}

public static void printSinglyList(Node node) {
for (Node curr=node; curr != null; curr=curr.next) {
System.out.print(curr.data + " -> ");
}
System.out.println("null");
}
}

class Node {
int data;
Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

- Rockstar July 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.Map;
import java.util.Random;
 
class VersionedStack {
  
 private static Node head = null;
 private static Map<Integer, Node> versionMap = new HashMap<Integer, Node>();
 private static int version = 0;
  
 public static void main(String[] args) {
  versionMap.put(version, head);
  head = push(head, 9);
  head = push(head, 10);
  head = push(head, 11);
  Node node = pop();
  head = push(head, 12);
  node = pop();
  node = pop();
  node = pop();
  node = pop();
  
  //print versions
  for (int i=0; i<=version; i++) { printVersionedStack(i); }
 }
  
 public static void printVersionedStack(int n) { 
  System.out.println("Version::" + n);
  if (n > version) {
   System.out.println("ERROR: version: " + n + " is out of range!");
   System.out.println("Latest version is: " + version);
  }
  Node node = versionMap.get(n);
  printSinglyList(node);
 }
  
 public static Node push(Node node, int value) {
  Node vnode = versionMap.get(version);
  Node head = new Node(value);
  head.next = vnode;
   
  //increase the version.
  versionMap.put(++version, head);
  return head;
 }
  
 public static Node pop() {
  Node node = versionMap.get(version);
  // if the stack is already null, we are not changing the version upon POP call on the stack.
  if (node == null) {
   return null;
  }
   
  //increase the version
  versionMap.put(++version, node.next);
  return node.next;  
 }
  
 public static void printSinglyList(Node node) {
  for (Node curr=node; curr != null; curr=curr.next) {
   System.out.print(curr.data + " -> ");
  }
  System.out.println("null");
 }
}
 
class Node {
 int data;
 Node next;
 
 public Node(int data) {
  this.data = data;
  this.next = null;
 }
}

- Rockstar July 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create nary tree where each child has link to its parent. We will use array to store versions. Version-array will have last node for that version and traversing to the top will give all nodes. We will store top-node so adding/removing node in nary tree is O(1). Printing version is O(n) where n is number of nodes in that version.

- dishant.shahani July 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

<pre lang="" line="1" title="CodeMonkey14414" class="run-this">import java.util.EmptyStackException;
import java.util.HashMap;
import java.util.Random;
import java.util.Stack;

/**
* @author jk
*
* @param <T>
* You need to implement a versioned stack, i.e. version of stack
* will increment after each push/pop. Apart from push/pop, implement
* a method print which would print corresponding stack version. All
* methods should be as efficient as possible.
*/
public class VersionedStack<T> {

/**
* This is the main data structure which stores the state of the version stack
*/
private HashMap<Integer, Stack<T>> verMap = new HashMap<Integer, Stack<T>>();

/**
* This is the main stack
*/
private Stack<T> st = new Stack<T>();

int currentVersion = -1;

/**
* @param value adds to the stack
* Stores the cloned stack in the hash map used for printing
*/
@SuppressWarnings("unchecked")
public void push(T value) {
this.currentVersion++;
st.push(value);
verMap.put(currentVersion, (Stack<T>)st.clone());
}

/**
* @return the last insert element (LIFO)
* Stores the cloned stack in the hash map for printing
*/
@SuppressWarnings("unchecked")
public T pop() {
if (st == null || st.isEmpty())
throw new EmptyStackException();
this.currentVersion++;
T value = st.pop();
verMap.put(currentVersion, (Stack<T>)st.clone());
return value;

}

public void printTheStack(int version) {
Stack<T> st1 = verMap.get(version);
@SuppressWarnings("unchecked")
Stack<T> st2 = (Stack<T>) st1.clone();
while (!st2.isEmpty()) {
System.out.printf("%s ", st2.pop());
}
System.out.println();
}

public static void main(String[] args) {
VersionedStack<Integer> versionedStack = new VersionedStack<Integer>();
Random r1 = new Random();
for (int i = 0; i < 15; i++) {
versionedStack.push(r1.nextInt(8));
if (i % 6 == 0)
versionedStack.pop();
}
versionedStack.printTheStack(5);
versionedStack.printTheStack(5);
versionedStack.printTheStack(4);
}

}

</pre><pre title="CodeMonkey14414" input="yes">
</pre>

- Anonymous September 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its funny your write every method should be as efficient as possible and yet do a O(N) stack clone in both push and pop.

- Anonymous September 17, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

or else you can keep a hash table instead of a linked list.

- Anonymous September 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Here's one solution.

Use a prefix tree. Have a pointer to the root denoting the current node.

When you push an element to the stack at step number s, check if the children of the current node contains that element. If not, add a node pointing to that element and set two integer values representing the steps at which the node was first reached and when it was returned to to (s, infinity). Update the pointer to the current node. If a node containing the element is already present, change the second number at that node to infinity.

When you pop an element at step s, change the upper value at the current node to s-1 and change the pointer to the current node to point to the current node's parent.

Thus push and pop are both O(1).

To print the status of the stack at step n, start at the root and traverse downward along the path at which the integer range at each node includes n and print the element that each node traversed points to.

The running time of print is dependent on the total number of elements that have been added at any point to the stack, k. If l is the length of the stack at time n, the print runs in O(l*k), since at each depth 1 through l, at most k comparisons are needed to find the correct child node.

Can anyone think of a way to improve the runtime of print using this method?

- Anonymous September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This actually won't work, the ranges are wrong if you pop an element and re-add it later. An alternative would be to use a dynamic array to point to the current position at each time. At each call to push/pop, the pointer to the current position on the prefix tree is added to the dynamic array in O(1) amortized time. Then, when print(n) is called, you only have to traverse up the prefix tree, printing out the element at each node. This can be done in O(l) where l is the size of the stack at time n.

- Anonymous September 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The versioning can be done with either a linked list or a hash table. Every time a pop/push is performed a new entry is added to the LL or hash table and the ID of the entry is the version number. When print(n) is called, we just iterate through the LL or hash table from 1 to n and print out the entries. Both solutions will be O(n).

- Anonymous September 23, 2011 | 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