What's IAC ?
-
Hey Guest. Check out your NeoGAF Wrapped 2025 results here!
My company is trying to hire competent developers
- Thread starter Proelite
- Start date
- Status
ShinNL
Member
Okay, guys, check this out. I'm not sure if it's a coincidence but:
1. You flip the keys and values.
2. You sort all the keys. (so it's in order)
3. You check if there no duplicate keys and/or are out of bounds.
Now the freaky part:
4. You check if any of the keys have the same value as the original array.
If not, it should be a circular loop.
Not tested.
Edit: Don't think this is foolproof, the original array check probably only checks mini loops of 2 entries.
1. You flip the keys and values.
2. You sort all the keys. (so it's in order)
3. You check if there no duplicate keys and/or are out of bounds.
Now the freaky part:
4. You check if any of the keys have the same value as the original array.
If not, it should be a circular loop.
Not tested.
Edit: Don't think this is foolproof, the original array check probably only checks mini loops of 2 entries.
wolfmat
Confirmed Asshole
It's not a coincidence and sorting is costly.
cpp_is_king
Member
It's also 3 passes through the array AND a sort. It can be done with a single pass through the array (untested code posted no previous page)
ShinNL
Member
Sorting part can be skipped, as long as you follow the keys.
wolfmat
Confirmed Asshole
Yeah. Dude, we're going to Google! Drinks on me.
Being that this is Google, I wonder if they'd like you to approach the circular array problem like as if it were a spanning tree that ultimately has to end up back at the beginning.
Think of an airplane on a roundtrip. You start at destination A (vertex 0 or the 0th index of your array) which takes you to some other airport. This airport then takes you to another and so on and so on until you get to an airport that takes you back to the beginning airport. Of course the caveat here is that you had to visit every single possible airport before your return, hence the minimum spanning tree aspect of the problem (every vertex is connected).
If so, it's a pretty easy algorithm to solve for.
Think of an airplane on a roundtrip. You start at destination A (vertex 0 or the 0th index of your array) which takes you to some other airport. This airport then takes you to another and so on and so on until you get to an airport that takes you back to the beginning airport. Of course the caveat here is that you had to visit every single possible airport before your return, hence the minimum spanning tree aspect of the problem (every vertex is connected).
If so, it's a pretty easy algorithm to solve for.
wolfmat
Confirmed Asshole
Yes, it's easy. I think it's a weeding-out question.
Think about it: You have to go through the array at least once, even if you're doing magic like, I don't know, assemble a number from the values and check whether it meets some mathematical criterium that fits.
Exception handling aside, as soon as you're doing more than that, your chances getting hired are drastically lowered.
After that, they ask you to paint a petri net of torrent networking in action from the perspective of a tracker or something.
Think about it: You have to go through the array at least once, even if you're doing magic like, I don't know, assemble a number from the values and check whether it meets some mathematical criterium that fits.
Exception handling aside, as soon as you're doing more than that, your chances getting hired are drastically lowered.
After that, they ask you to paint a petri net of torrent networking in action from the perspective of a tracker or something.
ShinNL
Member
Ah nvm this post, I think it will reduce performance.
barkers crest
Member
You know that ant thing kinda sounds like a problem that someone could solve by writing a function to produce the correct output given the problem requirements.
Now that the thread has mentioned the processes for hiring managers and stuff, I want to ask, what are the possible career paths for a developer? I don't want to get stuck making web pages forever, but also I don't want to stop coding, or at least doing technical stuff, I would hate to end up in manager positions, but is all my coworkers (and everyone I know) seem to be aiming for, what are your thoughts?
Software architect.
As you move up the technical career ladder, you basically start distancing yourself away from low level code.
wolfmat
Confirmed Asshole
Well, if the company you're in doesn't provide other, more demanding / rewarding opportunities for a developer, you could of course switch the company and end up in another subfield at any point. And so forth. Until you're going into retirement. But it's basically a question of what the company you're employed at does.
Anyhow, as a programmer, you're really always down in the guts of things. So as long as you want to actually produce code, that's the way your career is limited.
Meaning that it's rather rare that you are in a leading position and at the same time writing code. Companies that can support that kind of position tend to be small.
It's not impossible though; look at Carmack as an extreme example. That guy builds teams (to an extent), directs programming, does PR and outreach stuff, and programs as well.
But I'd expect that kind of acceptance of a jack-of-all-trades position only towards a guy who's got a tremendous influence in the company. Otherwise, he'd have a hard time arguing for, let's say, not finishing the shader pipeline refactoring because it's time to go to E3 and talk to journos, to stay with the Carmack example.
The best chances for this kind of opportunity are to be found in unique companies that can support it. You'll rarely find those though; the general trend points towards a utilitarian approach, where you're a dedicated part of a clockwork of sorts, and climbing up one step on the career ladder means taking the position of another dedicated part of that clockwork. Of course, with that philosophy, responsibility overlap is to be avoided by principle.
I mean, think up a hypothetical position that exemplifies where you'd want to end up with your caveats in mind. Then hold that against companies you know.
I see there are three paths:
Project/Program Manager: You largely forsake the coding and run a dev team.
Technical Architect: You dive deep into the tech and set a detailed technical vision and move that forward
Solution Architect: a mix of Project/Program manager and the technical architect. Is more interested in business/use problems and setting an overall technical direction than either managing the developers or the deep technical architecture.
I'm a Sr. Solution Arch and I think it's the best of both worlds.
Randolph Freelander
Member
We interviewed a couple of applicants today.
Neither was a complete idiot.
Progress.
Neither was a complete idiot.
Progress.
butzopower
proud of his butz
Reading through the last couple of pages, and specifically Soneet's confusion on strings being arrays has enlightened me a bit to part of the problem I think that is going on. A lot of modern languages treat strings as objects, and developers could very well not have had any exposure to how a string works on a lower level. I imagine a lot of CS courses will touch on these things, but not everyone has a CS background, and I think you'd be foolish to only hire CS grads. I myself have a CS degree, and could tell you how to reverse a string in something like C or Java, but couldn't tell you how a string is being stored in Ruby, which is a language I've used on a daily basis for the last 4 years.
While I still don't think asking someone to reverse an array is a great interview question, it might at least be a bit clearer.
EDIT:
To be clear, if you are hiring for a position that is going to be more low level, and require that someone understands how a string is stored, then yes, you should ask those kinds of questions. If you are trying to hire a web developer using anything modern, then you are either kidding yourself on how low level you need to get on a day to day basis, or you are totally over-engineering.
While I still don't think asking someone to reverse an array is a great interview question, it might at least be a bit clearer.
EDIT:
To be clear, if you are hiring for a position that is going to be more low level, and require that someone understands how a string is stored, then yes, you should ask those kinds of questions. If you are trying to hire a web developer using anything modern, then you are either kidding yourself on how low level you need to get on a day to day basis, or you are totally over-engineering.
Randolph Freelander
Member
All I got from that whole episode was a (stubborn?) inability to see the proper abstraction, or to separate the commonality of the algorithm from the usage of the result, as that's just noise. It came across as somewhat Mort-ish.
butzopower
proud of his butz
Using the roles in that article, for a lot of modern languages, someone like 'Elvis' might not even know how a string is being stored in the language. As we move forward, and classes are taught with these languages, 'reversing a string' becomes the same as 'bit-twiddling'.
I use Ruby pretty frequently and I'm not sure how reversing a string in Ruby is really any different from reversing it in any other language.
Code:
def reverse str
reversed_str = ""
str.chars.each do |ch|
reversed_str = ch + reversed_str
end
reversed_str
endYou could also do it with a reduce or use indices or do it a myriad of other ways, but the basic premise is the same. It's not something where choice of language should trip you up. Like at all.
If you really never have the need to iterate through an array and do anything out of sequence, you're probably not doing "modern" development of any sort.
wolfmat
Confirmed Asshole
Nono, he talked about how strings are stored in Ruby.
It's a sequence of bytes with an Object wrapper and appropriate methods, if you care to know.
Everything has an Object wrapper in Ruby. And to be honest, I don't care how Ruby stores strings internally (except regarding how it handles different character sets). Ruby's a horribly inefficient language and nobody using it is doing so because the underlying implementation is amazing. Unless I'm streaming exceptionally large amounts of data the implementation of String is the last thing on my mind. But the core concept here--that reversing a string and reversing an array are the same--has absolutely nothing to do with how strings are stored internally or your choice of language.
butzopower
proud of his butz
Yes, reversing an array is going to be the same, no matter your language.
Asking someone to reverse a string is going to require that they understand a string is stored as an array. If you've never had to treat a string as an array, and I don't really see why you would in a modern language, it's sort of bunk to expect that someone is going to know that.
You implementation even turns the string into an enumerable. You know it's an array. You are reversing an array. If you didn't know that you could represent the string as an array, you might not realize someone was asking you to show how you'd implement reversing an array.
Completely off-topic, and unrelated, but you actually wouldn't be able to reverse it with indicies straight up in Ruby 1.8.7, due to the fact that the [] method on strings returns the char byte code, ie 'abc'[0] returns 97.
wolfmat
Confirmed Asshole
It's very efficient! It's efficient in terms of actual programming. You get shit done in Ruby real fast. And the library landscape is great, which gives a lot of extra efficiency.
But you're of course right in terms of computing efficiency, although that only has impact when the solutions actually demand highly efficient processing of code.
And it's really not that bad. I have a recent (healthy) MacBook here with applications on it from Apple themselves, written in pure ObjC, and sometimes, the beachballs drive me crazy. That is real-world inefficiency.
I still wouldn't want to write a superprecise realtime flight simulation in Ruby, of course. Whatever, not sure what we're talking about anymore. Jurassic Park.
Re: your spoiler, you can always do str[index..index]. Which is dumb but works.
Re: the first part, that's total bullshit. You don't need to understand how a string is stored internally to recognize that it's an array, you just have to think for two seconds about what reversing a string really means--reversing its characters. At that point you've already arrived at the solution. If you don't, of course, you'll remain stuck. If you can never get to that point--and it's completely one of definition, not programming at all--then I doubt you will get hired, and that's completely okay.
butzopower
proud of his butz
How do I know a string has characters?
I don't think you and I are speaking the same language. Forget programming for a moment.
I ask you to reverse a string. What does that mean to you? To me, it means "reverse its letters." There. We're done. I now know I have to be able to isolate the string's letters and reverse them. So a string in this context has to be thought of as a list of letters. An ordered list. An array. Okay, we're reversing an array. Nowhere did we need to even touch a computer to figure this out, and yet you're trying to convince me that you need to know the "underlying implementation" for this to make sense. Even if your interviewee doesn't actually know the function to extract the characters, that's fine as long as he can coherently explain where to go from there.
butzopower
proud of his butz
In your train of thought you are making the connection that you can somehow represent a string as it's letters. I don't think that's a crazy connection to make by any means, but I think that if you've never had to make that connection before, if you've never had to treat a string as anything more than just a string, that it also wouldn't be crazy for someone to not realize that they could somehow deconstruct the string down to the characters that make it up.
I'm not even saying the person has to know how to GET the letters, they might not even know that they CAN.
But that leap is probably the most interesting part of the question. If a person really cannot wrap his or her mind around the idea that a string is made up of letters--if, effectively, a person can't even understand the request "reverse this string"--then do you really want him or her working on your project?
Even if a person somehow doesn't know that a string is an array of characters, they have to at least understand that the ability to isolate each character on its own has to be part of the language. If you can deduce that much, you can solve the problem.
Still, I would find it hard to believe that someone who is applying for an experienced programmer job has never had to use a string.charAt(int) method before.
Still, I would find it hard to believe that someone who is applying for an experienced programmer job has never had to use a string.charAt(int) method before.
butzopower
proud of his butz
It's not a leap in understanding the problem any better, though, it's having known something beforehand or not, through having had a need to mutate or manipulate a string in some way. I think it'd be pretty uncommon to not have had a need to do that, but I don't think it's totally out there either.
I wouldn't use the question in an interview, because of the above, and because I don't think it's an interesting question. I said this earlier, but if I wanted to know if I wanted them to work on my project or not, I'd have them work on my project with me for a few hours, which is how I interview people for the company I work at right now.
No, but you sound like some misplaced alleged prodigy. Talent in programming context is really just independence, how fast you learn, and your understanding of code. You certainly don't get understanding of code from nothing, so programming talent is very much connected to having done a lot of programming. You seem to be hung up on this narcissistic notion that you just know programming, and that you somehow are above the programming tasks first in this thread. If I were an employer, and you did an interview where you boasted about your genius, fast learning, but tried to talk yourself out of not knowing the basic, basic question asked, I'd just think you were full of shit, and even if you'd actually do a good programming job, you wouldn't be beneficial to the work-space, since your arrogance would probably be detrimental to workspace atmosphere (partially which has been proven by some of your responses to criticism in this thread).
But I guess (hope) that you'll grow out of it with time.
There are no dedicated software architects where I work. Intermediate and senior developers are the major contributors to the overall design of a feature, but everybody on the technical side is involved in the implementation.
I don't think I'd have it any other way, either. Even if a person who wasn't involved in the details of the implementation could do an equally good job at designing the system, he'd have to clearly communicate more information to a lot more people than if the responsibility were just distributed more widely. Even if the overall design of a project is huge, you can almost certainly modularise it and apply a similar strategy.
NullPointer
Member
I'd agree. I do the systems and architecture work at my job, but I'd feel out of the loop if I wasn't doing low level code as well. So I tend to design the overall system and subsystem interfaces and then lay the groundwork for others by doing the hardest parts of the lower level stuff. It also helps in presenting example code, style, conventions, etc.
Abstraction is all well and good, but being able to see your designs at work from every angle can keep you grounded. But I've been lucky to stay working at a small company over the years where roles aren't so well defined.
Here is what I think is a good algorithm to test for complete circular arrays:
1. Starting at index 0, iterate through the array using the given method (next index is the element at the current index). Keep track of the number of iterations.
2. For each iteration do the following in order:
>a. Check that the next index is within the array's bounds. If not, it's not a circular array.
>b. If the next index is 0, and the number of iterations is not equal to the size of the array, then it is not a complete circular array.
>c. If the number of iterations is the same size as the array, and the next element is 0, then the array IS a complete circular array.
>d. Check that the next index is not the same as the current index. If it is, it's not a complete circular array.
Basically, it checks if you hit every element if you try to traverse through it. If it's a complete circular array, you MUST end up at the element you started at after going through exactly n elements (n being the size of the array), and NEVER before that point.
It runs in O
time (it's simply a traversal through the array), and uses O(1) space. There might be an optimization I'm missing but this should cover all cases fairly well, unless I'm really misunderstanding something.
1. Starting at index 0, iterate through the array using the given method (next index is the element at the current index). Keep track of the number of iterations.
2. For each iteration do the following in order:
>a. Check that the next index is within the array's bounds. If not, it's not a circular array.
>b. If the next index is 0, and the number of iterations is not equal to the size of the array, then it is not a complete circular array.
>c. If the number of iterations is the same size as the array, and the next element is 0, then the array IS a complete circular array.
>d. Check that the next index is not the same as the current index. If it is, it's not a complete circular array.
Basically, it checks if you hit every element if you try to traverse through it. If it's a complete circular array, you MUST end up at the element you started at after going through exactly n elements (n being the size of the array), and NEVER before that point.
It runs in O
time (it's simply a traversal through the array), and uses O(1) space. There might be an optimization I'm missing but this should cover all cases fairly well, unless I'm really misunderstanding something.butzopower
proud of his butz
I've thought of a way that might help generate interview questions that could give insight on someone's coding ability and comprehension, while hopefully keeping your questions relevant.
Come up with one of these generalized code questions, let's use the 'Write a function that reverses a string'. Now, find in your codebase where you have code that does this. Present this snippet to the interviewee, and ask them if they can tell you what it does, answering any questions they might have. If they can't, explain what it does to them. Have them explain how they would implement whatever the snippet does, or if they are more comfortable with it, have them whiteboard it. Have them explain their reasoning.
Try and come up with three of these, and don't spend more than 15 to 20 minutes on any of them.
Come up with one of these generalized code questions, let's use the 'Write a function that reverses a string'. Now, find in your codebase where you have code that does this. Present this snippet to the interviewee, and ask them if they can tell you what it does, answering any questions they might have. If they can't, explain what it does to them. Have them explain how they would implement whatever the snippet does, or if they are more comfortable with it, have them whiteboard it. Have them explain their reasoning.
Try and come up with three of these, and don't spend more than 15 to 20 minutes on any of them.
First of all... what? Manipulating strings is a fucking huge amount of programming (yes, even modern programming, since for you apparently anything that happened five or more years ago is ancient history). Any network transactions are probably going to involve tons of parsing, as does validation on both the server and client side. I'm really sort of baffled that you'd even say something like this. If someone's applying to your job and isn't that familiar with manipulating strings, they might well be brilliant but you're still going to have to spend a fair amount of time ramping them up--so you'd at least want to make sure they understand the core concepts. Which leads to the next point...
Last time I respond to this. It has nothing to do with having had to mutate or manipulate a string before. In order to even define reversing a string you have to understand that the string is made up of letters. You are getting so hung up on this point about what you've been exposed to and what the computer's doing internally that I almost think we're not talking about the same thing.
Fundamentally, programming is about being able to understand a problem posed to you in English, break down what it really is, and then rewrite it in a language even an idiot (a.k.a a computer) can understand. What you have just told me is that it's okay to not even understand the question "how do I reverse this string" and that not being able to understand that question says nothing about how effective of a programmer you'll be. I can't agree with that, and I don't care how effective a person is at working on a project with me--if that person can't think independently enough to come up with a solution to a basic problem like that, he or she probably isn't going to be able to solve any novel problems that occur when working on my project, either.
Here is what I think is a good algorithm to test for complete circular arrays:
1. Starting at index 0, iterate through the array using the given method (next index is the element at the current index). Keep track of the number of iterations.
2. For each iteration do the following in order:
>a. Check that the next index is within the array's bounds. If not, it's not a circular array.
>b. If the next index is 0, and the number of iterations is not equal to the size of the array, then it is not a complete circular array.
>c. If the number of iterations is the same size as the array, and the next element is 0, then the array IS a complete circular array.
>d. Check that the next index is not the same as the current index. If it is, it's not a complete circular array.
Basically, it checks if you hit every element if you try to traverse through it. If it's a complete circular array, you MUST end up at the element you started at after going through exactly n elements (n being the size of the array), and NEVER before that point.
It runs in O
That's pretty much right. Depending on the average size of the arrays sent to this method, you could also try to catch errors earlier. You could create a boolean array of equal length to the array passed down so that you can mark each array cell as read as you're going through the chain. If you encounter a cell you've already read before, you know it's not a complete circular array. Obviously that adds a bit of overhead though, and should probably only be used if the array is a certain size.
You might not have a dedicated software architect, but someone should be assuming that role, or a commitee of people, at the very least. Our current project started out without anyone assuming the role, and as a result, our application is a mish-mash of different (some very bad) design philosophies. We've had to do a ton of refactoring because there was no consistent direction and no one was really aware of the big picture during development.
- Status