Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: In-Person
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.
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.
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
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?'.
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;
}
}
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 .
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.
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;
}
looks correct, the values of the HashMap dont matter right? It can be whatever, we are only testing for keys?
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
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--;
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.
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);
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
}
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;
}
}
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 :-)
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;
}
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);
}
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.
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.
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);
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.
- WearyMonkey June 03, 2013