How to check if every element of an array has been visited

[ChPravin]

Hello All,

I recently came across this question asked in one of Google Tech Interviews.I am not able to think as to how to proceed on this.Any suggestions will be greatly appreciated.

Question-Write code to check whether every element of an array has been visited (you are given a starting position and each position stores a pointer to a subsequent position)

[Narue]

Start by thinking of the ways the linked list (because this is a linked list) could trip you up and thwart it. For example, what if there's a cycle where the pointer points back to a previous node? Come up with a dumb brute force solution first, just to understand what's involved sans any extra complexity due to cleverness. Then you'll be in a better position to think of something elegant.

[sangeet.ahuja]

Hello All,

I recently came across this question asked in one of Google Tech Interviews.I am not able to think as to how to proceed on this.Any suggestions will be greatly appreciated.

Question-Write code to check whether every element of an array has been visited (you are given a starting position and each position stores a pointer to a subsequent position)

Understanding the question
The question is really unique, involving linked list and array concepts both. The Nodes have memory allocated like an Array, so you can access the nodes like Arr . And each node has a ptr field , so that can be accessed with Arr.ptr .
All nodes are visited when each Node has 1 and Only 1 incoming link.

Solution
Now iterate over the array , and construct a hash map of ptr address a node contains to current address of the node, i.e. A.ptr (KEY) mapped to &(A) (VALUE).
If a key is already present, that means atleast 2 nodes point to same node and thus you know that all nodes are NOT visited. Just return false and exit.
At the end of this exercise, you have verified that each node is visited AT MAX once.

Now that you have a hash table, you have to verify that each node is visited AT LEAST once. start iterating over the Array again. Check that Each Node should have its address as key in the hash table.
For Loop
address = &(Arr)
If HashTable.ContainsKey(address)
continue
Else
return false and exit.

[arkoenig]

If every element points to a subsequent element, where does the last element point? By definition, no element can be subsequent to the last one.

So the problem as stated makes no sense. Once we have figured out exactly what the problem is, it may be possible to come up with a solution.

[TrustyTony]

I started to play little with Python and think and my thinking is this:

In array of n elements there exist one node which has None (say -1) as next, if all nodes are visited therefore all next fields have different value which is in range(len(array))

Therefore my algorithm Python style is (next_node is number indicating index of next visited array element):

def visitted_all(arraywithpointer):
    notvisited=set(range(len(arraywithpointer))+[None]) ## all indexes not visitted
    for item in arraywithpointer:
        if item.next_node not in notvisited :
            return False
        notvisited.remove(item.next_node) # take index oout as used
    else: return notvisited == set() ## notvisited is empty set, if everything was visited