Google Interview Question for Software Engineer Interns


Country: United States
Interview Type: In-Person




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

Assumptions:
* No duplicates in the references array
* References array is NOT ordered
* array.length <= list.length, as the array contains no duplicates. So ideally we only want to loop over the array if possible. E.g. if there are a billion items in the list, but only two references in the array, looping over the entire away is a total waist of time!

For each node:
1. Add node to a HashSet
2. increment the block count by one.
3. If the nodes previous or next siblings are already in the set, that means we have closed a gap between two blocks, so we must decrement the incorrectly counted blocks.

{
int countNodes(Node[] references) { // who cares about the actual list, we don't need it
	int blocks = 0;
	Set<Node> set = new HashSet<Node>();

	for (int i = 0; i < references.length; ++i) {
		Node current = references[i];
		count++;
		if (set.contains(current.prev)) --blocks;
		if (set.contains(current.next)) --blocks;
		set.add(current);
	}

	return blocks;
}

- WearyMonkey June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

count++ should be blocks++, don't know how to edit sorry.

Also if we are able to mark (e.g. add seen variables to them) the nodes, we don't need the set.

- WearyMonkey June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Is if (set.contains(current.next)) --blocks; needed? That's the only part that seems iffy to me, everything else looks great, blows all the other answers away. Also, what if the references array was ordered, how would this be more effecient?

Thanks.

- Aasen June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If the array is ordered, then you don't need the 'if (set.contains(current.next))' check. So it would be more efficient that way.

When it is not ordered, imagine the scenario:

list: A-B-C-D
array: B, A
So the block count is 1.

Loop over B, add 1 to count
Neither A or C (prev/next) are in the set so don't decrement count.
Count is now 1

Loop over A, add 1 to count (now 2)
A.next (B) is in the set, so decrement count
Count is now 1 again

Another example which closes a gap:

list: A-B-C-D
array: A, C, B
So the block count is 1.

Loop over A, add 1 to count
A.next (B) is not in the set so don't decrement
count is now 1

Loop over C, add 1 to count (now 2)
Niether B or D (prev/next) are in the set, so dont decrement
count is now 2

Loop over B, add 1 to count (now 3)
B.prev (A) is in the set, so decrement count (now 2)
B.next (C) is in the set, so decremetnt count (now 1)
count is now 1

- WearyMonkey June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Impressive, your solution is THE optimal one I believe!

- Aasen June 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Thanks Lucas :)

Just one more thing. I realised if the array IS ordered, this simple solution requires no Set:

int countBlocks(Node[] references) {
	int blocks = 0;
	
	for (int i = 0; i < references.length; ++i) {
		Node current =references[i];
		if (i == 0 || references[i-1] != current.prev) { // start of a new block
			blocks++;
		}	
	}

	return blocks;
}

Because the block parts will be stored next to each other in the array as well.

But if I was asking this interview question, the array would be unsorted ;) Or another interesting follow on question would be, 'How do you sort an array of linked list nodes?'.

- WearyMonkey June 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the referenced array is empty, in that case the number of blocks should be the length of the list

- zjzzjz September 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following is the code for a working solution, it definitely is not a very efficient one, better solutions are welcome :)

package com.vaibhav.cc;

public class FindNumberOfBlocks {

	public int getNumberOfBlocks(DoubleListNode root, DoubleListNode[] refArray)
	{
		int numberOfBlocks=0;
		DoubleListNode current=root;
		while(current!=null)
		{
		  if(isContained(current,refArray))
		  {
			  while(current!=null)
			  {
				  if(!isContained(current,refArray))
					  break;
				  current=current.right;
			  }
			  numberOfBlocks++;			  
		  }
		  if(current!=null)
		  current=current.right;
		}
		return numberOfBlocks;
	}

	private boolean isContained(DoubleListNode current,
			DoubleListNode[] refArray) {
		for(DoubleListNode d: refArray)
		{
			if(current.equals(d))
				return true;
		}
		return false;
	}
	
	public static void main(String[] args)
	{
		DoubleListNode root;
		DoubleListNode dll0=new DoubleListNode(1);
		DoubleListNode dll1=new DoubleListNode(1);
		DoubleListNode dll2=new DoubleListNode(1);
		DoubleListNode dll3=new DoubleListNode(1);
		dll0.right=dll1;
		dll1.left=dll0;
		dll1.right=dll2;
		dll2.left=dll1;
		dll2.right=dll3;
		dll3.left=dll2;
		root=dll0;
		DoubleListNode[] refArray={dll0,dll2,dll3};
		FindNumberOfBlocks fnob=new FindNumberOfBlocks();
		System.out.println(fnob.getNumberOfBlocks(root, refArray));
	}
}

class DoubleListNode implements Comparable
{
	int value;
	DoubleListNode left;
	DoubleListNode right;
	
	DoubleListNode(int value)
	{
		this.value=value;
	}
	
	public int compareTo(Object arg0) {
		DoubleListNode otherNode=(DoubleListNode) arg0;
		return this.value-otherNode.value;
	}
}

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

It works, I think we can do better though, the guy hinted that the good soln was "like a few lines of code" and "used a HashMap"

- Aasen May 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Can you explain question with more example.
Few questions are
1. Can array contain references of node which are not present in linked list,
2. {ref#0 , ref#2 , ref#4, ref#1} with this example you want output as 2 blokcs of 4 blocks?
here we have 0,1,2 adjacent in linkedlist but are not adjacent in array .

- Varun Jain May 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1. No it can not
2. 2 blocks:
[0, 1, 2] 3 [4]

0, 1, 2 are adjacent, counts as one block.

- Aasen May 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I may have figured it out just now with help from "anonymous", not sure though.

1. Put all the node refs into a hashtable.
2. Iterate through the linkedlist:

int blocks = 0;
while ( cur != null ) {
       if ( cur.inHashTable() ) {
           while ( cur != null && cur.inHashTable() ) {
                  cur = cur.next;
           blocks++;
       }
       cur = cur.next;
}

return blocks;

O(n) runtime with n being the number of nodes.

- Aasen May 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Basically you put the nodes refs as keys and array index as value, then iterate through list, every time there is no value for key you increment blocks. I haven't tested out the following code:

public int BlockNum(Object [] array, LinkedList<Object> list){
		int Blocks = 1;
		HashMap<Object,Integer> ht = new HashMap<Object,Integer>();
		//assuming array does not have duplicates
		if(array.length == list.size())return Blocks;
		
		for(int i = 0; i < array.length; i++){
			ht.put(array[i], i);
		}
		for(Iterator<Object> i = list.iterator(); i.hasNext(); ){
			if(ht.get(i) == null)Blocks++;
			
		}
		return Blocks;
	}

- Raminder May 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

looks correct, the values of the HashMap dont matter right? It can be whatever, we are only testing for keys?

- Aasen May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

that's right..all we looking for is null value which means no ref in array

- Raminder May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The blocks will be over counted if the missing nodes are adjacent. e.g, {ref0, ref3},
correct answer is 2
your output will be 3

- Anonymous May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Anon is right, might wanna edit the code Rami

- Aasen May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats a good point...as i said I did not tested the code..but I think it can be fixed by setting a Boolean flag in the loop..so if you get more than one null together..it wont increment the block counter..the following loop part of the code also take care of special cases like first and last node..

flag = false;
		int counter = 0;
		for(Iterator<Object> i = list.iterator(); i.hasNext(); ){
			if(ht.get(i) == null && !flag){
				if(counter != 0 && counter != list.size() - 1){
				flag = true;
				Blocks++;
				}
			}
			if(ht.get(i) != null && flag){
				flag = false;
			}
			counter++;
		}
		if(flag)Blocks--;

- Raminder May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if extra memory is allowed, we could define an array(call it B, call the original array as A) of the same size of the list, initialize to all null.
then iterate thru the list, if an element exists in A, insert into array B in the corresponding position as the list.
The resulted array B would be like
node1ref null node2refe null null node3ref node4ref
then it becomes easy to find the no. of blocks.

- Jackie May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In C++:

typedef LinkedList<int*> LinkedIntPtrList;

	//arr = array of references (ints here)
	//list = linked list

	std::hash_set<int*> refs;
	for(auto iter = arr.begin(); iter != arr.end(); iter++)
	{
		refs.insert(*iter);
	}
	LinkedIntPtrList *node = &list;

	int numBlocks = 0;

	while(node)
	{
		while(node && refs.find(node->data) != refs.end())
		{
			node = node && node->next ? node->next : 0;
		}
		numBlocks++;
		node = node && node->next ? node->next : 0;
	}

	printf("%d", numBlocks);

- Anonymous May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a c# solution in O(array.Length)

public static int FindNumberofBlocks(LinkedList<int> list, LinkedListNode<int>[] array)
        {
            if((list==null)||(array.Length==0)) return 0;
            LinkedListNode<int> node1, node2;
            int i = 0;
            int noofGaps = 0;
            List<LinkedListNode<int>> temp = new List<LinkedListNode<int>>();
            while (i < array.Length - 1)
            {
                node1 = array[i];
                node2 = array[i + 1];                
                if (!(node1.Next == node2))                
                    noofGaps++;
                i++;
            } ;
            return noofGaps+1;//No of blocks = no of gaps + 1
        }

- Pradeep May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is no need to create the list(temp variable)..that's a mistake

- Pradeep May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my version of code... Thought of using HashSet instead of HashMap

public static int blockCount(Object[] array, LinkedList<Object> list)
    {
        int blockCount = 0;
        boolean isBlockStarted = false;
        Set<Object> set = new HashSet<Object>();
        Collections.addAll(set, array);
        for(Object item : list)
        {
            if(set.contains(item))
            {
                if(!isBlockStarted)
                {
                    blockCount++;
                    isBlockStarted = true;
                }
            }
            else
            {
                isBlockStarted = false;
            }
        }
        return blockCount;
    }

}

- Code Warrior May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think your solutions so far don't use the fact it is a double-linked list.
Tell me what do you think about this:

1. You go over the array from the beginning to the end:
- for every object the array points to, you add to the linked list two DUMMY objects - one before and one after the pointed object

2. You go over the list from the beginning and delete the dummies:
- While deleting - you count the number of dummies
- You don't include in your count a dummy that had a dummy connected to him (before or after)
- Therefore, what you counted is the number of block starts + number of block ends.
- you divide this number in 2 and get the number of blocks!

Am I stupid?
Please explain :-)

- A simple solution outline WITHOUT hash (where am I wrong?) May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I believe below function will give the desired result in O(n). Please suggest if any improvement can be done in below code.

public static int countBlocks(DLLNode head, DLLNode[] input){
		HashSet<DLLNode> s = new HashSet<DLLNode>(Arrays.asList(input));
		DLLNode temp = head;
		int blockCount = 0;
		while(temp != null){
			if(temp.getLeft()== null && s.contains(temp))
				blockCount++;
			if(temp.getLeft() !=null && s.contains(temp) && !s.contains(temp.getLeft()))
				blockCount++;

			temp = temp.getRight();
		}
		return blockCount;
	}

- Rahul Khanna May 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recording the left boundaries and right boundaries of each potential block

public void blockCount(LinkedList[] node_refs){
		HashSet<LinkedList> left_bound=new HashSet<LinkedList>();
		HashSet<LinkedList> right_bound=new HashSet<LinkedList>();
		int block_counter=0;
		for(int node_index=0; node_index<node_refs.length; node_index++){
			LinkedList temp=node_refs[node_index];
			if(left_bound.contains(temp) && right_bound.contains(temp)){ //two block merges to one
				block_counter--;
				left_bound.remove(temp);
				right_bound.remove(temp);
			}
			else if(left_bound.contains(temp)){ //some block's left boundary extended
				left_bound.remove(temp);
				if(temp.ancerstor!=null)
					left_bound.add(temp.ancerstor);
			}
			else if(right_bound.contains(temp)){ //some block's right boundary extended
				right_bound.remove(temp);
				if(temp.descent!=null)
					right_bound.add(temp.descent);
			}
			else{ // a new block
				block_counter++;
				if(temp.ancerstor!=null)
					left_bound.add(temp.ancerstor);
				if(temp.descent!=null)
					right_bound.add(temp.descent);
			}
		}
		System.out.println(block_counter);
	}

- txbb May 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Logic (Assuming 1st element ref of the doubly linked list is present in the node[] array somewhere)
1. Build the hashmap <key,value> pair with "key" as nodes from node[] array provided (not the doubly linked list) and value as position of the node in the same array.
2. Create a new block array[] int of the same size as node[] array.
3. Iterate through the doubly linked list, for each node starting from beginning check if the key is present in the hashmap. 2 cases
3.1 If present : get the value which is the position in the node array. and do ++block[position]. This step is to ensure we have block size of 1 for all elements. We can avoid this case by assigning 1 to the block when the block was created initially. Either way it is good.
3.2 If NOT present : Go to the doublylinked list. Copy the current ref that is not present in a temp and go backwards in the doublylinked list until you find a ref which is present in the hashmap. Get the value of the reference in the hashmap which is the position, do ++block[position].
4. Continue until the end of the doublylinked list [note : you have used a temp here, so you still retain your iterating position].
5. Return the block array which is of size position.

- Time Pass June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I thought a solution would just be:

Put each node* in a hash
If head node is in hash, start blockcounter as 1, otherwise 0
Start iterating through the linked list. If the following case is detected:
node -> prev is not in hash and node is in hash. Increment blockcounter;
//All we need is the number of blocks and every signal for a begin of a block we increment
Runtime: O(n)

Also possible without a doubly linked list if we keep 2 node pointers while iterating one following the lead.

- Anon June 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a TreeSet.
1. no duplicates, and sorted.

Check for broken links in reference array and update block count on each such encounter.

Set<Node> blockCheck = new TreeSet<Node>();

// add all nodes from node array.
for(Node n : node){
blockCheck.add(n);
}

// find broken links
for(Node s : blockCheck){
if(s.next==null || !blockCheck.contains(s.next))
++blockCount;
}

System.out.println(blockCount);

- AlgoAlgae June 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

just suppose at the begining that the solution is the size of the double linked list. Now you go through the array, and if value at pos i and value at pos i+1 are adjacent , then you subside 1 from the solution.

- Andrew October 02, 2013 | 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