Support NeoGAF

[Mister Zimbu]

I'd just like to say I don't like this way of thinking. I really don't see the use of someone saying it's the same thing, period, when the entire practical use is different. This also means you can't make an extended, advanced, customized reverse function, since string usage and array usage are completely different. Yes, I can't argue the basic function is the same thing. If you think that's the end of the story, then so be it, but I respectfully disagree.

One of the core tenets of being a good programmer is taking a larger task and splitting it down into smaller, manageable, reusable chunks that will work properly regardless of context.

One of the biggest advantages of basic object oriented, and even procedural design, is that you write smaller, bite-size methods that are reusable in multiple places in code with minimal modification should bugs occur or the method need to be optimized, and also easily testable.

You guys aren't web (ASP/VB/PHP/JSP/Flash/Silverlight) programmers, are you?

I'm an ASP.NET web developer with experience in C# and VB.NET, Javascript, and TSQL. Previously have experience with the horrific ASP 3.0 predecessor before it. I wouldn't touch Silverlight or WPF with a 10 foot pole.

Also did some PHP/Flash work in college but don't really remember any of it.

 

[Proelite]

Question that I got asked on my Amazon onsite:

Implement read and write locks in Java. A read locks allows only threads with read locks to access the critical section of code, a write lock blocks all threads from accessing the critical section of code.

Question that I got asked on my Google onsite:

Given a circular integer array A, i.e. {1, 5 , 3, 4, 2, 1, 6, 7}, tell if this array is complete circular loop.

Explanation: a[0] = 1, a[1] = 5, a[5] = 1, a[1] = 5, infinite loop discovered that's not completely circular, meaning that it doesn't visit all the indexes of the array before looping.

I had to do this on the white board with 15-20 min.

There are standards, and then there are standards.

 

[ShinNL]

One of the core tenets of being a good programmer is taking a larger task and splitting it down into smaller, manageable, reusable chunks that will work properly regardless of context.

One of the biggest advantages of basic object oriented, and even procedural design, is that you write smaller, bite-size methods that are reusable in multiple places in code with minimal modification should bugs occur or the method need to be optimized, and also easily testable.

NP, I know this. I also have my own custom PHP framework that lets me create custom website in 1 day. But it seems what I'm saying makes people assume I don't know OOP and MVP.

Question that I got asked on my Amazon onsite:

Implement read and write locks in Java. A read locks allows only threads with read locks to access the critical section of code, a write lock blocks all threads from accessing the critical section of code.

Question that I got asked on my Google onsite:

Given a circular integer array A, i.e. {1, 5 , 3, 4, 2, 1, 6, 7}, tell if this array is complete circular loop.

Explanation: a[0] = 1, a[1] = 5, a[5] = 1, a[1] = 5, infinite loop discovered that's not completely circular, meaning that it doesn't visit all the indexes of the array before looping.

I had to do this on the white board with 15-20 min.

There are standards, and then there are standards.

I am not worthy.

 

[TheExodu5]

The lock question makes sense...but I don't understand that Google question one bit. It seems like it's missing information.

To me, circular arrays don't exist...they're just implemented using a modulus when retrieving a value at a given position.

 

[AlimNassor]

I have no experience with coding, and can do the reverse thing with ease. Can I have a job too? I wanna learn to code.

 

[Proelite]

The lock question makes sense...but I don't understand that Google question one bit. It seems like it's missing information.

To me, circular arrays don't exist...they're just implemented using a modulus when retrieving a value at a given position.

It means that if the index is out of bounds, they're modded with the length of the array. You use the remainder as the new index.

 

[Zoe]

You guys aren't web (ASP/VB/PHP/JSP/Flash/Silverlight) programmers, are you?

For my current job I wasn't really asked any technical teaser questions or really anything about coding. There was one SQL question that I bombed (never formally learned SQL so I don't know the terminology), but that's about it.

They had me complete a small project (basically web form) before coming in though.

 

[Mister Zimbu]

Question that I got asked on my Amazon onsite:

Implement read and write locks in Java. A read locks allows only threads with read locks to access the critical section of code, a write lock blocks all threads from accessing the critical section of code.

Question that I got asked on my Google onsite:

Given a circular integer array A, i.e. {1, 5 , 3, 4, 2, 1, 6, 7}, tell if this array is complete circular loop.

Explanation: a[0] = 1, a[1] = 5, a[5] = 1, a[1] = 5, infinite loop discovered that's not completely circular, meaning that it doesn't visit all the indexes of the array before looping.

I had to do this on the white board with 15-20 min.

There are standards, and then there are standards.

I hate threading and locking. Parallel processing was my worst course in college (and the only one I dropped because I was doing so poorly), though I've since gotten better at it just from doing it from a practical standpoint.

I could probably do the Google one but not do it the best/fastest, which is what Google would be looking for. I could probably do it iteratively, but I'm assuming there's a good DP approach as well (CS theory was my 2nd worst course in college. Probably have gotten worse at this stuff since then because theoretical CS isn't really used for any web development except at the highest levels). I graduated with a CS degree but I consider myself to be more of a Software Engineer than a Computer Scientist).

 

[TheExodu5]

It means that if the index is out of bounds, they're modded with the length of the array. You use the remainder as the new index.

Yeah, that's fine with me. What I'm not understanding is the question:

Given a circular integer array A, i.e. {1, 5 , 3, 4, 2, 1, 6, 7}, tell if this array is complete circular loop.

Do you mean to ask whether there's a repeating pattern? Any array can be made circular if using a custom implemented wrapper class.

I hate threading and locking. Parallel processing was my worst course in college (and the only one I dropped because I was doing so poorly), though I've since gotten better at it just from doing it from a practical standpoint.

I could probably do the Google one but not do it the best/fastest, which is what Google would be looking for. I could probably do it iteratively, but I'm assuming there's a good DP approach as well (CS theory was my 2nd worse course in college. I graduated with a CS degree but I consider myself to be more of a Software Engineer than a Computer Scientist).

I swear I learned semaphores 5 different times throughout University. Learned it for Java 2, Software Engineering 1, Operating Systems, Distributed Programming, Computer Architecure III (implementing multicore CPUs on FPGA boards).

 

[cpp_is_king]

I'd just like to say I don't like this way of thinking. I really don't see the use of someone saying it's the same thing, period, when the entire practical use is different. This also means you can't make an extended, advanced, customized reverse function, since string usage and array usage are completely different. Yes, I can't argue the basic function is the same thing. If you think that's the end of the story, then so be it, but I respectfully disagree.

Everything about this post is wrong.

1) It is the same thing. In fact it's identical
2) The "entire practical use" is not different. It's only different in your head, because you personally have apparently never had a reason to reverse a string, index individual characters in a string, or maintain information about each character in a string.
3) It doesn't mean you can't make whatever functions you want that are customized however you like.

 

[Proelite]

Yeah, that's fine with me. What I'm not understanding is the question:

Given a circular integer array A, i.e. {1, 5 , 3, 4, 2, 1, 6, 7}, tell if this array is complete circular loop.

Do you mean to ask whether there's a repeating pattern? Any array can be made circular if using a custom implemented wrapper class.

It means that you've visited all nodes before hitting your first already visited node.

 

[cpp_is_king]

Yeah, that's fine with me. What I'm not understanding is the question:

Given a circular integer array A, i.e. {1, 5 , 3, 4, 2, 1, 6, 7}, tell if this array is complete circular loop.

Do you mean to ask whether there's a repeating pattern? Any array can be made circular if using a custom implemented wrapper class.

They give the definition of "complete circular loop" immediately following.

You start with a[0] and use the VALUE at a[0] to index into the array. You keep repeating this over and over until you revisit an index you previously visited. It's a complete circular loop if a) You end up at a[0], and b) you have visited every element of the array exactly once.

Example:
{0} is a complete circular loop
{1, 0} is a complete circular loop
{1, 3, 5, 4, 2, 0} is a complete circular loop
{1, 4, 2, 0, 3} is a circular loop, but it is not complete (you never visit the element at index 2)

 

[ShinNL]

For my current job I wasn't really asked any technical teaser questions or really anything about coding. There was one SQL question that I bombed (never formally learned SQL so I don't know the terminology), but that's about it.

They had me complete a small project (basically web form) before coming in though.

Pretty much all my friends get hired because they performed well as an intern. I'm one of the only few who decided to stop working despite how fun it is because I wanted to explore more of what the world has to offer. I think seeing 1st hand how you perform is the best way to be screened.

 

[TheExodu5]

Oooooh.

Out of curiosity, is this an actual data structure, or just a theoretical one? In Java you'd need a wrapper class to implement such an array.

 

[Celine]

I came to learn, of course, the the Convert.ToXXX methods are documented to return the default value for the type XXX when the input is null for all types except System.String. So the above example is going to return 0. If you want 0, just write 0!

Laughed at your anecdotes.
Are you sure about the bold part?
Convert.ToString(string) will return null if the string is null.
Convert.ToString(object) is another matter though.
In that case it would return empty.

 

[Proelite]

Oooooh.

Out of curiosity, is this an actual data structure, or just a theoretical one? In Java you'd need a wrapper class to implement such an array.

Theoretical. The behavior is added through your code that you will be using to solve the problem.

 

[Mister Zimbu]

Actually, I'm overthinking the Google question. I think it's pretty simple. From a lazy standpoint this would work, but probably wouldn't be optimal from a memory standpoint:

bool[] blah = new bool[arr.Length];
Array.Fill(blah, false);
for( int i = 0; i < arr.Length; i++ ) {
 if ( arr[i] >= 0 && arr[i] < blah.Length && !blah[arr[i]] )
   blah[arr[i]]=true;
 else
   return false;
}
return true;

That should work, shouldn't it?

Spoiler

Actually, it doesn't- {0, 2, 1} will fail that miserably.

 

[TheExodu5]

Yeah sorry, I understand the complete circular loop thing now. I was thinking we were just talking about a circular array in the following sense:

a = {1, 4, 3}

Where:

a[0] = 1
a[1] = 4
a[2] = 3
a[3] = 1
a[4] = 4
a[5] = 3

etc...

 

[barkers crest]

Question that I got asked on my Google onsite:

Given a circular integer array A, i.e. {1, 5 , 3, 4, 2, 1, 6, 7}, tell if this array is complete circular loop.

Explanation: a[0] = 1, a[1] = 5, a[5] = 1, a[1] = 5, infinite loop discovered that's not completely circular, meaning that it doesn't visit all the indexes of the array before looping.

Do you get the bolded explanation before or while you at the whiteboard?...First thing I would have done is asked what do you mean by complete circular loop?

This is exactly a prime example of why I hate these riddle questions. The asker tries to be so cryptic as to not give away the answer to the point where it is practically impossible to decipher what they are asking for. Most of the time the answer is needed to even understand what the question is.

 

[cpp_is_king]

Actually, I'm overthinking the Google question. I think it's pretty simple. From a lazy standpoint this would work, but probably wouldn't be optimal from a memory standpoint:

bool[] blah = new bool[arr.Length];
Array.Fill(blah, false);
for( int i = 0; i < arr.Length; i++ ) {
 if ( arr[i] >= 0 && arr[i] < blah.Length && !blah[arr[i]] )
   blah[arr[i]]=true;
 else
   return false;
}
return true;

That should work, shouldn't it?

Spoiler

Actually, it doesn't- {0, 2, 1} will fail that miserably.

You are not verifying that you visited every node once. So your conditions are necessary, but not sufficient.

BTW: Any time you encounter a question like this, you should immediately think "bitfield".

This is exactly a prime example of why I hate these riddle questions. The asker tries to be so cryptic as to not give away the answer to the point where it is practically impossible to decipher what they are asking for. Most of the time the answer is needed to even understand what the question is.

When you have problems in the real world, you usually don't have people coming and giving you a fully speced document on how to solve the problem. At least 30% of what the interview is trying to find out is how well you try to understand the requirements and the problem definition.

In any case, in this particular example, of course they are going to give you the definition of a complete circular loop. And if they don't, why would you be upset about having to ask? furthermore, this is not even close to a riddle. It's a simple test of your ability to understand a generic problem and create a solution. Anyone with basic coding skill can do this question. This question is entirely about seeing if you can solve problems. Which, incidentally, is usually what the actual job entails and what they're paying you for.

 

[Proelite]

Yeah sorry, I understand the complete circular loop thing now. I was thinking we were just talking about a circular array in the following sense:

a = {1, 4, 3}

Where:

a[0] = 1
a[1] = 4
a[2] = 3
a[3] = 1
a[4] = 4
a[5] = 3

etc...

a[0] = 1;
a[1] = 4;
a[4] = 4;
a[4] = 4;

 

[TheExodu5]

a[0] = 1;
a[1] = 4;
a[4] = 4;
a[4] = 4;

a[4] = ArrayOutOfBoundsException

Anyways the problem sounds pretty straightforward to me. There are only a few conditions to check:

1) Is every position in the array visited only once?
2) Is there a return to 0?

There are a ton of ways to accomplish this. You could even do it mathematically.

 

[Proelite]

a[4] = ArrayOutOfBoundsException

Anyways the problem sounds pretty straightforward to me. There are only a few conditions to check:

1) Is every position in the array visited only once?
2) Is there a return to 0?

There are a ton of ways to accomplish this. You could even do it mathematically.

a[4] = a[1], a[8] = 1, hence circular.

 

[Mister Zimbu]

a[4] = ArrayOutOfBoundsException

Anyways the problem sounds pretty straightforward to me. There are only a few conditions to check:

1) Is every position in the array visited only once?
2) Is there a return to 0?

There are a ton of ways to accomplish this. You could even do it mathematically.

My guess is that Google would throw you out for doing it any way but the mathematical way. I'd imagine Google would want candidates who can do something faster than the O or O(n^2) that someone would have done using a strictly iterative approach where they walk the array normally.

Fun link for people interested in doing this sort of thing better, by the way:
http://projecteuler.net/ has a ton of problems like this.

 

[cpp_is_king]

My guess is that Google would throw you out for doing it any way but the mathematical way. I'd imagine Google would want candidates who can do something faster than the O or O(n^2) that someone would have done using a strictly iterative approach where they walk the array normally.

Not even sure what you mean by mathematically. O looks like the best possible solution for this problem. But they might throw you out for using an array of bools instead of a bitfield (Not trying to call out your solution as being bad. It wasn't bad, but they do look for things like this, and bitfields are a classic gotcha, especially somewhere like google)

 

[Proelite]

Do you get the bolded explanation before or while you at the whiteboard?...First thing I would have done is asked what do you mean by complete circular loop?

This is exactly a prime example of why I hate these riddle questions. The asker tries to be so cryptic as to not give away the answer to the point where it is practically impossible to decipher what they are asking for. Most of the time the answer is needed to even understand what the question is.

I asked for an explanation. They expect you to ask. The worst thing you can possibly do is not clarifying your confusion, or trucking on ahead without fully understanding the problem.

 

[TheExodu5]

a[4] = a[1], a[8] = 1, hence circular.

You guys are throwing in two definitions. You're describing a circular array, and cpp_is_king is describing a circular index pattern in an array.

I'm confused.

 

[ShinNL]

Complete circular loop in an array is not common terminology, right?

 

[TheExodu5]

Complete circular loop in an array is not common terminology, right?

I've certainly never heard of it. I'm guessing not, as they supply the definition following the question.

 

[Proelite]

You guys are throwing in two definitions. You're describing a circular array, and cpp_is_king is describing a circular index pattern in an array.

I'm confused.

You can call the array whatever you want, as long as you understand how Google want you to traverse the array and how to handle the out of bounds exception.

 

[ShinNL]

I've certainly never heard of it. I'm guessing not, as they supply the definition following the question.

You mean the "explanation" part is part of the question? Cause of that's true, isn't that the answer already?
Edit: oh wait, barkers crest already questioned this.

 

[TheExodu5]

You mean the "explanation" part is part of the question? Cause of that's true, isn't that the answer already?

No, they still want you to write the code. The reason they have that question is undoubtedly because there are many ways to solve it.

So, given the question again, there has to be a trick to it. Circular loop and circular array are two separate concepts. There must be a reason they specified circular array, as the question is easily solvable in O time given a regular array.

Keep in mind this is Google we're talking about...I'm sure they're looking for a completely out of the box solution on this one. And yeah, I can pretty much assure you it involves some mathematics. Given the array of a certain size, we know exactly what numbers must be in the array. For example, if we have an array of size 7, the following numbers must be in the array: 0, 1, 2, 3, 4, 5, 6 (the order doesn't matter). It's obviously easy to iterate over the full array and check to see if all of these values are there, but otherwise I can't think of how to speed it up, and I'm assuming that's where the circular array comes into play.

 

[Proelite]

You mean the "explanation" part is part of the question? Cause of that's true, isn't that the answer already?

I might have confused people. The explanation was about how the array is supposed to behave for the context of the problem. There still needs to be a function written that identifies a "completely traversable" array for you.

 

[Hari Seldon]

I swear I learned semaphores 5 different times throughout University. Learned it for Java 2, Software Engineering 1, Operating Systems, Distributed Programming, Computer Architecure III (implementing multicore CPUs on FPGA boards).

Holy shit what school did you go to that you took enough computer architecture that you were screwing around with FPGAs? We can't hire CS majors who know HDL. That is why I am trying to get into CS, because I am already an HDL dev and need software to be truly versatile.

 

[barkers crest]

When you have problems in the real world, you usually don't have people coming and giving you a fully speced document on how to solve the problem. At least 30% of what the interview is trying to find out is how well you try to understand the requirements and the problem definition.

In any case, in this particular example, of course they are going to give you the definition of a complete circular loop. And if they don't, why would you be upset about having to ask? furthermore, this is not even close to a riddle. It's a simple test of your ability to understand a generic problem and create a solution. Anyone with basic coding skill can do this question. This question is entirely about seeing if you can solve problems. Which, incidentally, is usually what the actual job entails and what they're paying you for.

Did you read my entire post? I did say the first thing I would have done is ask for clarification on such matter.

And yes, it is a riddle, which isn't necessarily a bad thing. As a matter of personal preference when I want to to know if people can solve real world problems I give them real world problems to solve. I've found that you get more bang for the buck that way but that is just my experience.

 

[ShinNL]

I might have confused people. The explanation was about how the array is supposed to behave for the context of the problem. There still needs to be a function written that identifies a "completely traversable" array for you.

Ohhhhhhhhhhhhhhhhhhhhhhhhhhhh

That actually sounds like fun.

Edit: Wait, isn't that actually easy? You just reverse the key with the values, then check if there are any duplicate keys and if there are any out of bound keys?
Edit2: Wait, nvm, I have to think this through.
Edit3: Array {1,4,3,2,0}
array[0] = 1 / loop
array[1] = 4 / loop
array[2] = 3
array[3] = 2
array[4] = 0 / loop
Edit4: Nope, won't work with my original concept, some parts are not visited. But meh, reaaaally don't wanna loop it, there has to be a better solution.
1 0
4 1
3 2 = not unique
2 3 = not unique
0 4

I sorted the reversed key array..

0 4
1 0
2 3 = WTF, it's the same as the original
3 2 = WTF, it's the same as the original
4 1

Array {10,10,10,10,10,10,10,10, 10, 10} false
Array {1,5,8,6,7,4,9,0,2,3} false
Array {1,2,3,4,5,6,7,8,9,0} true
Array {9,0,3,4,5,6,7,8,1,2} true

0 10 1 1 9
1 10 5 2 0
2 10 8 3 3
3 10 6 4 4
4 10 7 5 5
5 10 4 6 6
6 10 9 7 7
7 10 0 8 8
8 10 2 9 1
9 10 3 0 2


4th example
0 1
1 8
2 9
3 2
4 3
5 4
6 5
7 6
8 7
9 0

2nd example
0 7
1 0
2 8 = WTF, it's the same as the original
3 9
4 5
5 1
6 3
7 4
8 2 = WTF, it's the same as the original
9 6

Ah I give up, I can't see the formula fast enough (if there is one). After a certain amount of time, just writing the loop would be more cost efficient. Though in Google's case I guess it's more worth it to spend more time thinking on it, given the amount of users. I'm almost sure there's a way to check without a loop.

Edit 5: I might be on to something.

 

[TheExodu5]

Holy shit what school did you go to that you took enough computer architecture that you were screwing around with FPGAs? We can't hire CS majors who know HDL. That is why I am trying to get into CS, because I am already an HDL dev and need software to be truly versatile.

University of Ottawa. I'm studied Computer Engineering though, not Computer Science.

I worked on FPGAs in 4 or 5 different classes. The most interesting one was High Level Systems, where we designed and coded a MIPS processor using HDL. Did plenty of microcontroller and robotics programming (through MATLAB) as well.

It's a shame my talents are wasted on Java development.

HDL coding is an exceptional skill, as it requires a very, very different way of thinking than procedural or object oriented programming. It would definitely take me a while to get me back into the mindset.

 

[cpp_is_king]

No, they still want you to write the code. The reason they have that question is undoubtedly because there are many ways to solve it.

So, given the question again, there has to be a trick to it. Circular loop and circular array are two separate concepts. There must be a reason they specified circular array, as the question is easily solvable in O time given a regular array.

Keep in mind this is Google we're talking about...I'm sure they're looking for a completely out of the box solution on this one. And yeah, I can pretty much assure you it involves some mathematics. Given the array of a certain size, we know exactly what numbers must be in the array. For example, if we have an array of size 7, the following numbers must be in the array: 0, 1, 2, 3, 4, 5, 6 (the order doesn't matter). It's obviously easy to iterate over the full array and check to see if all of these values are there, but otherwise I can't think of how to speed it up, and I'm assuming that's where the circular array comes into play.

That's not all you have to check for. That condition is necessary, but not sufficient.

 

[TheExodu5]

That's not all you have to check for. That condition is necessary, but not sufficient.

Actually, you're right. I think the only other necessary condition would be that a certain value cannot point to its own position. So, a[0] != 0. I think that as long as those two conditions are satisfied, you've got your circular loop.

edit: no, I'm an idiot.

a[2] = 4
a[4] = 2

results in a non fully circular loop.

I guess you really do have to iterate through the entire thing and follow the chain...I can't personally think of any other way to do it.

 

[Mister Zimbu]

Not even sure what you mean by mathematically. O looks like the best possible solution for this problem. But they might throw you out for using an array of bools instead of a bitfield (Not trying to call out your solution as being bad. It wasn't bad, but they do look for things like this, and bitfields are a classic gotcha, especially somewhere like google)

I'd imagine that there's some sort of DP O(log n) solution out there. Though, like I said, the mathematical theory portions of my CS courses were never one of my strong points.

Just out of curiosity, why is a bitfield preferred over a bool array in this case?

 

[cpp_is_king]

Did you read my entire post? I did say the first thing I would have done is ask for clarification on such matter.

And yes, it is a riddle, which isn't necessarily a bad thing. As a matter of personal preference when I want to to know if people can solve real world problems I give them real world problems to solve. I've found that you get more bang for the buck that way but that is just my experience.

I don't see how it's a riddle. It says "Here's a problem, please write a function to produce correct output given the problem requirements".

A riddle is asking, for example, if you place 1 ant on each of the 3 vertices of an equilateral triangle, and they all simultaneously choose one of their two adjacent edges to walk along until they reach the next vertex, what is the probability that no two ants will collide.

I'd imagine that there's some sort of DP O(log n) solution out there. Though, like I said, the mathematical theory portions of my CS courses were never one of my strong points.

Just out of curiosity, why is a bitfield preferred over a bool array in this case?

Speed and size. A bool takes up an entire byte even though it only contains two values (true or false). You only need 1 bit to represent true/false. Suppose you're working on something like google's search backend where you have to maintain some kind of information for every single search request that comes through. If you choose an array of bools instead of a bitfield, for whatever reason, then it's possible this could be allocated on a per-request basis, which would be unacceptable given they handle potentially hundreds of millions of requests a day.

So you find out that the array has, say, N elements in it (probably N is passed as an argument to the function, or you can call array.length() or whatever). You compute ceil(N/8). You allocate a buffer of that many bytes to store your bitfield. Instead of looking at a[n], you look at the n'th bit in your buffer, which you can do some integer division to find out which byte it is, and then use a bitmask to test the value of the bit.

 

[TheExodu5]

I'd imagine that there's some sort of DP O(log n) solution out there. Though, like I said, the mathematical theory portions of my CS courses were never one of my strong points.

That's my thinking. It just doesn't seem like a complex enough problem for Google, because doing it O is pretty trivial. Google is really about innovation and outside the box thinking...at least that's the impression I get.

Or maybe it was just a tier 1 idiot test or something.

 

[cpp_is_king]

That's my thinking. It just doesn't seem like a complex enough problem for Google, because doing it O is pretty trivial. Google is really about innovation and outside the box thinking...at least that's the impression I get.

Or maybe it was just a tier 1 idiot test or something.

It is easy to prove that there is no solution better than O, because EVERY element in the array must be in the range [0, length). There is absolutely no way to determine that for every single element unless you visit every single element.

 

[TheExodu5]

It is easy to prove that there is no solution better than O, because EVERY element in the array must be in the range [0, length). There is absolutely no way to determine that for every single element unless you visit every single element.

I suppose you're right.

 

[Zilch]

Though I'm not a programmer I've found this thread to be a very interesting read.

Also a bit surprised that people here are not familiar with IAC, is that because this a nerd forum where everyone wants to work on videogamez or something?

 

[Proelite]

public static boolean isComplete(int[] array) {
boolean[] visited = new boolean[array.length]; //Can also use a bit vector but it's not necessary according to Google
for (int i = 0; i < array.length; i++) {
int value = array;
if (value >= array.length) {
value = value % array.length;
}
if (visited[value] && i == array.length - 1) {
return true;
} else if (visited[value]) {
return false;
}
visited = true;
}
return false;
}

Didn't check.

 

[Mister Zimbu]

I don't see how it's a riddle. It says "Here's a problem, please write a function to produce correct output given the problem requirements".

A riddle is asking, for example, if you place 1 ant on each of the 3 vertices of an equilateral triangle, and they all simultaneously choose one of their two adjacent edges to walk along until they reach the next vertex, what is the probability that no two ants will collide.




Speed and size. A bool takes up an entire byte even though it only contains two values (true or false). You only need 1 bit to represent true/false. Suppose you're working on something like google's search backend where you have to maintain some kind of information for every single search request that comes through. If you choose an array of bools instead of a bitfield, for whatever reason, then it's possible this could be allocated on a per-request basis, which would be unacceptable given they handle potentially hundreds of millions of requests a day.

So you find out that the array has, say, N elements in it (probably N is passed as an argument to the function, or you can call array.length() or whatever). You compute ceil(N/8). You allocate a buffer of that many bytes to store your bitfield. Instead of looking at a[n], you look at the n'th bit in your buffer, which you can do some integer division to find out which byte it is, and then use a bitmask to test the value of the bit.

Interesting. That's a thing I'd expect a C compiler or the C# runtime to abstract away nowadays. My impression was that the compiler would be smart enough to arrange bools themselves into single bytes.

edit: Thinking about a bit more, I guess that makes sense in C at least. If that were the case in C then:

bool bob, steve; if (&bob == &steve) { /* oh crap */ }

Forgive my horrific C. Haven't written C in years and forget the whole pointer syntax by now.

 

[cpp_is_king]

<snip>

Here's mine. Also didn't check.

bool is_complete_circular(int* arr, int len)
{
     bitfield bits(len);    //For brevity, but I could implement the members of this if necessary

     int visited=0;
     int cur = 0;
     do
     {
          int next = arr[cur];
          if (bits.is_set(next) && next != 0) 
               return false;     //Been to the next node before

          bits.set(cur);
          cur = next;
          ++visited;
     } while (cur != 0);

     return (visited==len) ? true : false;
}

Edit: I looked over yours again, it doesn't "chain" elements together. I mean it doesn't take the value at the current index and use it to index into the next location. So all you're checking is that every number in the range [0, len) appears exactly once, but not that it's also a cycle. Or did I misunderstand something?

 

[cpp_is_king]

Interesting. That's a thing I'd expect a C compiler or the C# runtime to abstract away nowadays. My impression was that the compiler would be smart enough to arrange bools themselves into single bytes.

In a language like C / C++, it *might* be possible if the compiler is able to prove at compile-time that the address of the array is not passed around and that it is never aliased or anything. Because the standard is supposed to guarantee that elements of array are uniquely addressable. In other words, &a[n] == &a[m] if and only if n == m. In practice I would be pretty surprised if this optimization were ever actually possible (In any case, I'm no compiler writer)

In C# / Java / etc it's even more unlikely, because of things like reflection / managed code / etc it is much harder to change out the generated code and be able to get away with it.

 

[wolfmat]

Question that I got asked on my Google onsite:

Given a circular integer array A, i.e. {1, 5 , 3, 4, 2, 1, 6, 7}, tell if this array is complete circular loop.

Well.

1. Values can't repeat themselves because otherwise, it would shorten the loop.
2. Keys can't repeat themselves because it's an array.

Therefore, this is a bijective mapping.

So all you have to do is go through the array, starting at any field, and check whether the number of steps until repetition of the value equals the number of elements in the array.

Array A = 1, 5, 3, 4, 2, 1, 6, 7
int r = Random.int(from:0 to:A.size) or exit moaning "Well, of course this is a complete circular loop since there is only one element, you wanker" provided A.size equals 1
int start = A.valueAt(r)
int current = A.valueAt(start)
int steps = 1

while not start equals current
  steps++
  current = A.valueAt(current)
end

in the unlikely event that not steps equals A.size then fart something like "Not a complete circular loop" in Aramaic
otherwise utter witty nonsense about success regarding finding a complete circular loop in this very array and say goodbye.

(Also, there's some pseudocode for ya. It's not that hard!)