So anon I would like you to write some code that inverts a binary tree
>>54227710
>inverts a binary tree
please insert definition
>>54227710
Enjoy your botnet.
Nice trick.
But no, we won't do your homework.
>>54227710
Let me Google that.
>>54227747
According to new EU antitrust rules, we are only allowed to use Bing at Google campus.
>>54227710
I don't have a clue what you are talking about Sir, but I can install Google Ultron on all your PCs!
>>54227717
it's literally just flipping. so a tree like
4
/ \
2 7
becomes
4
/ \
7 2
it's not something magical. it's not super clear why google would ask this; it's not sufficiently high level that it would allow you to break the problem down into logical modules (the way fizzbuzz allowed, and was thus favored). inverting a binary tree is sort of something you learned in class or you didn't.
interviews are about trying to learn as much as possible in ~45-90 minutes. this seems to go in the opposite direction. maybe google knows something about interviewing that we don't, but it seems like a stupid question to ask.
>>54227762
Well fuck them amiright google for the win ;)
>>54227813
You mean that it's just inverting left and right child? No it's too trivial. It must be more complex.
>>54227710
Are you saying trees are binary you shitlord?
data Tree a = Leaf (Tree a) (Tree a) | Empty
invert (Leaf left right) = Leaf (invert right) (invert left)
invert Empty = Empty
>>54227862
No it's fucking too trivial. I don't believe it's that.
I'm a black native american transsexual lesbian female to male to female heterophobic wolfkin oppressed girl autistic and a Ruby artisan. We girls can code too :)
HIRE ME xD
>>54227914
Go to mozilla
>>54227914
Go to github
>>54227914
Go to Intell
>>54227710
> mfw i wrote software 90% of your employees use
> mfw cant invert binary tree
> mfw no job offer
>>54227710(invert-binary-tree *tree*)
lol so easy
>>54227862
You forgot to store values in your tree m8
>>54228168
Yeah I know. It's an extra 3 characters so w/e just pretend I did.
>>54227813
>it's not super clear why google would ask this
In technical interviews, you often either have a warmup question and a main question, or ~2-3 smaller questions. This could be the warm-up.
>inverting a binary tree is sort of something you learned in class or you didn't.
I actually don't think so. Reversing a tree is so contrived that you've probably never encountered it in academia or in the wild. I sure haven't.
However, it's also so trivial that anyone who has a working knowledge of trees should be able to do it.
It's basically, "can you implement a trivial recursive tree algorithm that you haven't memorized from a book?"
>>54228077
>require("invert-binary-tree.js")
>>54227710
>anon please write a program that inverts a binary tree
>Actually, I think you meant to say "please write an app", also what's a binary tree?
>Congratulations, welcome to Apple™!
>>54228498
But no one with experience in programming can fail such a task. It must be something else.
>>54228498
>I actually don't think so. Reversing a tree is so contrived that you've probably never encountered it in academia or in the wild. I sure haven't.
It's possible that inverting a binary tree is something you would just do in the process of doing something else fairly domain-specific. Like maybe you've never seen it in the wild, but it is something that gets done, but you're right that it's incredibly trivial, to the point of being infantile.
I'm not sure how to parse the homebrew guy not being able to do it, because it makes both parties in that story look incredibly incompetent in their own ways.
I think there's credibility to the argument that this is just a filter to see if you actually did a rigorous curriculum (university or otherwise), and I could actually defend a question *like* this on that principle.
the problem is that self-taught programmers often cut corners in their education, so you need to ask stupid, basic questions about recursion and whatnot to see which corners they opted to cut (if any). This is the basic issue with hiring self-taught programmers, and it's actually incredibly frustrating (as someone who has interviewed people for this kind of stuff) to deal with the amount of indignation they give when you probe this stuff a bit.
>>54228531
this is a surprisingly hapless, retarded attempt at humor. do everyone a favor and stop posting for a few days.
>>54228763
>I'm not sure how to parse the homebrew guy not being able to do it
That's why I'm sure that inverting tree means something more complex.
>>54228682
See >>54228763
it's basically asking whether you know recursion. a lot of self-taught programmers just elect not to learn some stuff that's hard to wrap their head around, so companies have to probe with these kinds of questions that seem infantilizing.
i mean, the guy who made homebrew couldn't do it. this is an excellent example of someone who's reasonably smart and self-taught who elected not to learn some fundamental component of programming because the effort/reward seemed misaligned. But everyone who works in software *should* know this stuff. Not because you'll use it every day, but because it's a foundational concept.
90% of high school graduates don't really need to use the pythagorean theorem in day to day life (please don't reply; i don't care about your story about how you use it all the time), but we all have to learn it.
>>54227710
A DAAAH WHAT'S A BINARY TREE?
>>54227710
What if I write the code backwards?
>>54228820
Nobody can't understand recursion. It's impossible. It's too easy to understand. I don't want to live on this planet.
But it would explain why people ask me stupid things when I postulate for a job (I succeed in one of the most difficult contest in programming in my country, and people ask me thing more trivial than fizzbuzz).
>>54228842
Eert yranib
>>54227717
I presume it's something with roots where there used to be leaves, and with all links going in the opposite direction.
>>54228018
>>54228498
I hate to say it, but counter to most replies you are getting, I see this as an expected outcome. Inverting a binary tree is not some trick interview question. It's a very basic data structure manipulation, and the ideas involved there are applicable to everything. I probably wouldn't hire someone who couldn't solve this, either. It most likely indicates lack of comfort with (or understanding of) recursion, which is kind of serious. This is not to say that the hiring process is good (I have never experienced it) or that they shouldn't have hired you (quite possibly they should have) but maybe instead of getting mad, take this as a cue that you could build up your data-structure-manipulation muscles a bit more and become better for it -- as that stuff applies everywhere.
>>54227811
>>54227747
>>54227732
Well, then you're not a very good programmer. Sorry but that's how it is.
>>54228782
I mean there's not that much room for interpretation in "invert a binary tree".
When i was an undergrad i went with a friend to a google information session and the recruiter told a room full of undergrads that one question they might ask in a technical interview was how you would sort 10k numbers.
some people asked if they were integers and/or floats, or if there were subsequences that were ordered already (a good way to probe to see if timsort is worth implementing), but the gist is that you're supposed to know not to use bubble sort and to use something like merge sort or something more efficient.
this isn't complicated. if you've never learned this stuff but you had been casually programming for a while, i'm willing to stake money on the claim that i could skype with you ("you" being a random person fitting the earlier criteria) and explain how mergesort works in ~20-30 minutes and you would be able to implement it. but the question in the context of the interview is whether you already know these concepts, or if you'll need to be explained all sorts (har har) of stuff for ~20-30 minutes at a time for the next several months/years.
Part of hiring a programmer is the hope that you don't need to catch them up on too much stuff.
>>54228845
I think recursion is one of those things that's conceptually very simple but framing problems to optimally use recursion can be somewhat challenging.
Every problem in the world is about framing, though. If you frame a simple problem the wrong way, you could spend hours or days or weeks trying to wrestle with it.
>>54228891
>optimally use recursion
I do it everyday when practicing my caml. I don't even know how to use a for loop or a while loop, I don't knoe the syntax.
>>54228866
FUCK U I AM BETTER PROGRAMMER THAN YOUR WHOLE FUCKING FAMILY AND SHITTY COMPANY INSTART MY OWN SEARCH ENGINE AND BUY YOURS WHEN U ARE SO POOR MARK MY WORD AND FUCK YOU TO YOU
derailing thread.
anyone remember those start-up animations that had incredibly small source codes yet created incredible landscapes?
one of them was called Everest if i recall correctly.
>>54228911
Fuck off.
>>54228870
Spot on. Sadly the uni crowd cranks out plenty of shit birds who can't into the basics like this either. I still rue the day I got promoted to senior and was put in charge of new talent acquisition. We aren't big 4, but close enough that I interview constantly. FML
>>54227710
Don't know if this is completely correct, but it's what I thought of in a couple of minutes.void invertTree(struct bnode* root) {
if (root == NULL)
return;
invertTree(left);
invertTree(right);
struct bnode *p = left;
left = right;
right = p;
}
>>54228991
Failed, you just fucked the stack. Find a better way without overflowing the stack anon.
>>54229002
can you explain? I also realized I messed up calling left and right.void invertTree(struct bnode* root) {
if (root == NULL)
return;
invertTree(left);
invertTree(right);
struct bnode *p = root->left;
root->left = root->right;
root->right = p;
}
>>54229028
With a big tree you'll overflow the stack.
https://en.wikipedia.org/wiki/Stack_overflow
>>54227710
>write some code that inverts a binary tree
Trees are non-linear, so that doesn't even make sense.
I know that they're looking for a recursive left-right swap, but that's not inversion. In fact, the only way "inversion" makes any sense with a tree is top-bottom inversion. In other words, print the tree growing bottom-to-top.
Incidentally, I think simply asking to print an ASCII art representation of a tree is a far more interesting question. Also, it actually makes sense without ambiguity, so there's that.
BTW anyone wanting to work at Google just needs to work through all of Cracking the Coding Interview. Google tests for culture (i.e. "have you seen the same set of concepts from the same set of respected schools I went to"), not actual intelligence, resourcefulness, and I've never even heard of them asking anything about your prior projects.
>>54229043
>I've never even heard of them asking anything about your prior projects
If one day I do interviews I will never ask about what people did. I would test what they can do.
It's magic manhocus.
pocus
alakazam
binary
tree
upside down
abra
Kadabra
}
ǝǝɹʇ ʎɹɐuiq
function invert (parent, current)
for child in current.children:
invert (current, child);
current.children = parent;
>>54229041
Damn, guess I've never worked with big enough data before. Thanks anon
>>54229073
And the second thing to understand is tail call optimization
https://en.wikipedia.org/wiki/Tail_call
and hwy you must not rely on it, except if you do OCaml.
>>54229055
Sorry man, but that's a neat way to lure in bullshitters. Always ask them what they did, even at home.
Would you like someone who dicks around with programming projects at home and at work, or some shmuck who just reads books?
>>54229002
Fuck off, it's a naturally recursive problem.
>>54229055
>If one day I do interviews I will never ask about what people did. I would test what they can do.
The entire reason you bring people in to interview is because of their resume.
The first thing you should be doing is discerning whether or not they're lying or misrepresenting their work history. The way you establish that is by asking questions about their approach, implementation decisions, what other approaches they discarded, etc.
If you don't recognize this, then you have no business working in the industry as far as I'm concerned. Then again, the majority of the industry seems to confuse culture for intelligence/knowledge/expertise, so whatever.
>>54229091
No, I will talk with them about coding. I know how to detect fraud or incompetents.
>I'm not sure how binary trees are represented in data, but if you could explain that to me or allow me to google it, I'm sure it'd be simple.
Would I get the job?
>>54229091
>Would you like someone who dicks around with programming projects at home and at work, or some shmuck who just reads books?
GGP here, I'd much rather work with the 'schmuck'. In my experience, people who "dick around with programming projects at home" tend to have an "everything is a nail" approach.
Getting the fuck away from the computer and engaging in unrelated hobbies and activities makes for much more well-rounded, interesting, insightful coworkers.
>>54229104
Found the person with no experience interviewing people.
Here's a story: our internal recruiter sent us a hot guy. He'd been working as a highly-paid contractor for years. We asked him questions about how he implemented some of the projects on his resume. He couldn't give ANY more technically detailed information than what was on his resume. Like, to the point that the guy must have had ZERO actual involvement in the implementation.
For example, one project was something like, "ported existing thin client application to a web-based interface". Basically, replacing old green-screened terminals with web forms. It required scraping the data stream from the mainframe, presenting a web form instead, and piping compatible commands back over the line to the mainframe. He couldn't explain ANYTHING about how the data was actually captured. Like, was it custom electronics? Was it just intercepting Ethernet packets? How did it work? His answers were just, "well... we intercepted the data from the mainframe, presented a web form, then sent compatible commands back to the mainframe."
And that, kids, is why you don't let HR or the general building manager get involved in the recruiting and initial selection game. Fucking retards.
>>54229158
>Like, to the point that the guy must have had ZERO actual involvement in the implementation.
If him and me were discussing about coding I would see it immediately. Because he won't be able to discuss with me about coding.
I don't care about a fake curriculum, I just care about coding skill. And discussing about coding is the best way to check.
>>54228902
I am tired of bad web programmers who think they are good. Sorry but my patience on this issue has been run out by others before you.
Sometimes the truth is unpleasant; allowing ourselves to see unpleasant truths, and responding appropriately, is how we get good.
>>54228866
Careful kid, you use my code daily.
>>54229202
You are completely misinterpreting my words and intent. I am not saying "you suck and will never be good". I am just saying that if someone is not comfortable doing all kinds of things to a tree, that person isn't very good *right now*. With work that changes, etc.
>>54229182
>If him and me were discussing about coding I would see it immediately. Because he won't be able to discuss with me about coding.
There are plenty of people who can do dumb, abstract, novelty programming challenges who can't get shit done to save their life. In fact, it's flat out amazing how few people can actually complete a full project from beginning to end. Most people just get excited for a day or two, then lose focus and end up adrift with no progress.
>I don't care about a fake curriculum, I just care about coding skill
Because you have no idea what you're talking about.
>>54229158
It's not a clear division between the shmuck and the "everything is a nail" guy. We're all a bit of both. I've had a friend who could nail any test related to programming, but when it came to actually creating something useful - nada. He played WoW at home and thought of himself as a good developer... can't change the PSU in his own PC, can't code his way out of a cardboard box. He made a website once, and it was awful... but it was xhtml transitional valid, so there's that.
Also, Pajeets are really good at doing interviews. They will know the shit you're asking them, but they'll fail to do anything useful.
>>54229230
Uh.
>>54229202
>Careful kid, you use my code daily.
was a reference to the original screencap where the guy complained about being rejected by Google because he couldn't "invert a binary tree". To this day, as far as I know, nobody knows if that's literally what was asked or if that was his poor recollection.
>>54229233
>Most people just get excited for a day or two, then lose focus and end up adrift with no progress.
There is a test period to check that.
>Because you have no idea what you're talking about.
What do you mean?
invert(01110100011100100110010101100101);
>>54229246
>It's not a clear division between the shmuck and the "everything is a nail" guy.
Well, there is. For any given programming skill level, I'd rather work with people who have interesting and varied lives outside work than the guy who overloads himself on too much of the same experience.
Not only are they more pleasant to *work* with, but their solutions tend to be pragmatic and simply get the job done. The "code at home guy" will be more likely to demand some ridiculously over-engineered thing that reinvents a bunch of wheels and is mostly designed for some bizarre future requirement that's unlikely to ever occur.
>>54229256
>There is a test period to check that.
Sorry, what?
>What do you mean?
You have no idea what you're talking about. It's blatantly obvious, right there in what you wrote.
>I don't care about a fake curriculum, I just care about coding skill
You sound like a kid with very little actual work experience, and no meaningful experience in interviewing and hiring people, then seeing the results long-term.
There is much, much more to being an effective software engineer than whatever your criteria for "coding skill".
>>54228911
intros/demos/etc they were procedurally generated
>>54229253
This post >>54229202 (along with several others) was a Jon Blow quote from that twitter conversation.
>>54229041
Is this even a concern for log(n) function calls?
>>54229310
Sorry, I meant this post >>54229230, to which you Uh'd.
Next question:
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
>>54229317
You'd have to have one hell of a large, unbalanced tree to overflow the stack, unless you're doing something like embedded work, where you *really* shouldn't be working with unbalanced trees...
>>54229296
>For any given programming skill level, I'd rather work with people who have interesting and varied lives outside work than the guy who overloads himself on too much of the same experience.
This is quite a difference from plenty of other jobs which require you to post your GitHub account.
>>54227710
/**
Invert a binary tree.
Parameters: Binary Tree
Returns: Inverted Binary Tree
*/
func invertBinaryTree(binaryTree: BinaryTree) -> BinaryTree {
return binaryTree.reverse()
}
>>54229296
>>There is a test period to check that.
>Sorry, what?
In my country there is a test period. You can fire an employee as you want during that period. The period for a skilled dev (cadre) is 7 months.
>You have no idea what you're talking about. It's blatantly obvious, right there in what you wrote.
You mean that I'm not capable of distinguish a non geek from a geek?
>You sound like a kid with very little actual work experience
7 professional years, and 25 if I count my amateur experience. And I'm fucking respected developers. I always impress people when I code.
I see that today industry apply your method, and I see that a lot of incompetent developers are recruited and promoted. Don't deny it I use computer everyday, people use computer everyday and we all see the "quality" of software.
Maybe when recruiter will focus on skill and not of ability to speak (blathering) about things.
>>54229317
>log(n) function calls
What's that? You're talking about function calls? The real danger is recursive.
>>54229345
>This is quite a difference from plenty of other jobs which require you to post your GitHub account.
So? They're selecting specifically for people who are easily exploited.
You'll find that probably 5% of those jobs actually need anyone with substantial programming and algorithmic chops. Don't kid yourself: they want someone they can whip.
>>54229367
>You're talking about function calls? The real danger is recursive.
Recursion is accomplished through function calls.
>>54229367
>In my country there is a test period. You can fire an employee as you want during that period. The period for a skilled dev (cadre) is 7 months.
Ah, so great, you admit that your hiring methodology is weak and you rely on this "test period" to weed out what you missed in the interview.
Kbye.
>7 professional years
LOL okay kid.
>I see that today industry apply your method
Really? Because you just said they want GitHub accounts.
>I see that a lot of incompetent developers are recruited and promoted.
That happens in any high-demand field, you idiot.
>people use computer everyday and we all see the "quality" of software.
Maybe when recruiter
No idea what point you're trying to make. If it's that software is somehow terrible. Uh. There is more software doing MORE COMPLEX TASKS now than anytime in history, by far.
>>54229462
Yes, but there are function calls that are not recursive. Like any function of the "stdlib".
What mut be avoid is recursion, except in language who handle tail call optimization (or at least tail rec optimization) like OCaml.
If you want to play with recursion, give a try to OCaml.
>>54229481
>Ah, so great, you admit that your hiring methodology is weak and you rely on this "test period" to weed out what you missed in the interview.
How do you check motivation of people? You have a safe method? I'm interested? Really. For me the test period is just to test commitment, I would already know the skill of the person, I know how to check that.
>LOL okay kid.
Here we are. You're hiding behind your experience because you're uncomfortable. I know your kind. Right now, I know that you're unskilled. I met and work with people with 40 years of experience, worldwide respected, and they never dare to play the biggest dick with me. But you you try, like all the incompetents.
>you just said they want they want GitHub accounts
Not me, another anon.
>That happens in any high-demand field, you idiot.
With my method, I will check quickly. It's one of my specialties to test skill of people by talking with them (I must be skilled in the domain, otherwise I can check nothing).
>No idea what point you're trying to make
Just saying that your method is applied today, and responsibilities is given to incompetent persons.
>>54229548
Yes, what he was saying was that since the algorithm is only O(log n), it's unlikely to require enough (recursive) function calls to overflow the stack.
>>54228870
>Part of hiring a programmer is the hope that you don't need to catch them up on too much stuff.
this is taken to an extreme that is retarded, though
every fucking job application looks like:
>required: 5 years in JSON/XML/MS-SQL/C#/ASP.NET/jQuery
and everyone wants someone who already has programming experience with their special software stack. as if someone who knows java isn't going to be able to pick up c# or vis versa.
>>54229548
>How do you check motivation of people? You have a safe method? I'm interested?
Are you paying any attention at all?
You discuss PAST PROJECTS WITH THEM. This is how you discern the people who get shit done from the people who get on the flashy teams and contribute nothing.
>Here we are. You're hiding behind your experience because you're uncomfortable.
No. You're literally a kid with seven years of industry experience, who wants to count his kiddie school days for some reason. You don't know what you're talking about.
>With my method, I will check quickly.
So, I assume that you're ESL and just have poor reading comprehension?
As I've already stated, your method will select for people who can do purely academic programming, with ZERO test of ability to actually get things done, or even basic honesty.
>Just saying that your method is applied today
No it isn't, and no, you didn't say that. In fact, you said the exact OPPOSITE.
Anyway, I've got things to do. Ignore me at your own peril. kiddo.
>>54229606
It's log(n), yes, but it's O(n) is n is the depth of the tree, and with a big tree the stack will explode. So that code must be avoid, even in OCaml, because there is non tail rec call.
>>54229618
>No. You're literally a kid with seven years of industry experience
Okay, you have a bigger cock, you're awesome, I shouldn't dare to argue with you, I don't know my place.
>>54228870
>I mean there's not that much room for interpretation in "invert a binary tree".
Given that it doesn't actually mean anything, there is.
>this isn't complicated.
It's irrelevant. The fact is, 99.9% of the people in that room will never run into 10k numbers outside of a database.
Domain knowledge is more important than algorithmic/CS knowledge.
Currently, companies like to obsess on this sort of CS bullshit. Not because it's relevant, but because 1) it boosts their ego, 2) they don't actually realize how butthole-simple their company's software is, 3) it's handily ageist, since you're unlikely to remember this stuff well enough to speak intelligently, and 4) thusly it supports their claims that there are too few qualified candidates and they need more H1-B's to exploit.
Literally everything about the industry hiring practices revolves around culture and prestige, followed by exploitability.
>>54229336nums = [2, 7, 11, 15]
target = 9
def trivs(remain, used, target):
if sum(used) == target:
return used
for n, r in enumerate(remain):
solution = trivs(remain[:n] + remain[n + 1:], used + [r], target)
if solution:
return solution
solution = trivs(nums, [], target)
solution = [nums.index(s) for s in solution]
print(solution)
>>54229336
fuck that looks like a computational nightmare
>>54229667
>they need more H1-B's to exploit.
Idiot detected
>>54228891
>using recursion in place of for and while loops
You hardcore bastard. I get how it's done but it's still an annoying way to think about those loops
>>54229336
Testing every pair is only O(n^2), do you want something better than that?
>>54230671
the constraints make it pretty easy.
- you can only add
- you can only add 2 of the elements together
- ostensibly, you know there's only one pair (so you can return quickly)def summer(sequence,target):
results=list()
for i in range(len(sequence)):
if target-sequence[i] in sequence[:i]+sequence[i+1:]:
return (i,sequence.index(target-sequence[i]))
return results
print(summer([2,7,11,15],9)) # returns (0,1)
>>54229336for(var i = 0; i < nums.length - 1; i++) {
for(var j = i + 1; j < nums.length; j++) {
if(nums[i] + nums[j] == target) {
return [i, j];
}
}
}
>>54227710
The trick to these questions is to try and establish the problem parameters beyond what the interviewer specifies. So, my answer would be, like, "OH, well obviously this is a binary tree object right?"
"s-sure..."
"OK! so it probably has left and right attributes right?"
"fine"
"And we implemented it in python right? I'm just going to write this as if we have a reasonable python implementation of a tree!"
And then you just write this in 3 seconds:def invert(tree):
if tree:
invert(node.l)
invert(node.r)
tmp = node.l
tree.l = node.r
tree.r = tmp
>>54232074
do the tuple flip to be extra fancy
>>54232074
>And we implemented it in python right
In the trash your resume goes!
Seriously, you're not wrong in defining the parameters of the program like that, but they are very fucking obviously not asking you if you know how to abuse an object with parameters you made up on the spot.
Inverting a b-tree as an object is the pinnacle of pajeet code.
>>54229336
Sort list, target - list, binary search to find matching element from original list
>>54229336
If the data is sorted as per the example given, it has a really simple solution.#include <stdio.h>
int get_sum(int *a, int n, unsigned long long bv);
void print_solution(int *a, int n, unsigned long long bv);
int main(void)
{
int target_value = 9;
int data[] = {2, 7, 11, 15};
int data_size = sizeof(data)/sizeof(int);
int temp_sum;
unsigned long long bit_vector = 1;
// trim data
while(data[data_size-1] > target_value) data_size--;
// test remaining data
bit_vector <<= data_size;
while(--bit_vector > 0) {
temp_sum = get_sum(data, data_size, bit_vector);
if(temp_sum == target_value) {
print_solution(data, data_size, bit_vector);
printf("\n");
}
}
getchar();
return 0;
}
int get_sum(int *a, int n, unsigned long long bv) {
unsigned long long i = 1;
int sum = 0;
i <<= n;
while(i > 0) {
if(bv & i) {
sum += a[n];
}
i >>= 1;
n--;
}
return sum;
}
void print_solution(int *a, int n, unsigned long long bv) {
unsigned long long i = 1;
int m = -1;
i <<= n;
while(i > 0) {
if(bv & i) {
printf("%d ", m);
}
i >>= 1;
m++;
}
}
>>54232141
>Seriously, you're not wrong in defining the parameters of the program like that, but they are very fucking obviously not asking you if you know how to abuse an object with parameters you made up on the spot.
this. you guys are grossly misjudging how amusing you are. you'd be lucky to get more than an exasperated sigh out of them from this kind of childish non-answer.
>>54232157
Fails with negative values
>>54232157
And if the answer is [0, 1] as per the example given it has a really simple solution, but that wasn't part of the statement of the problem. What's your point?
>>54229336
The thing to miss in this problem is that you should just ignore list items that are greater than the target entirely. The question doesn't explicitly say that a solution can't be a pair of the same indices, so I didn't include it but that would just be another check added to the end of the generator.def two_sum(lst, target):
for (s, indexes) in ((s, (xi,yi))
for xi, x in enumerate(lst)
for yi, y in enumerate(lst)
if x <= target and y <= target):
if s == target:
return indexes
>>54232178
Isn't that a proper answer, though? I thought that was what the problem was actually asking - just a simple question to makes sure you can use recursion.
If it was written in C, each node would probably have pointers to the left and right nodes, and swapping them or calling an invert function on them should be trivial.
>>54232275
>The thing to miss in this problem is that you should just ignore list items that are greater than the target entirely.
You can't do that because some entries could be negative.
>>54232275
Wrong. It's an obvious optimization idea, but an incorrect one, since integers can be negative.
e.g. [-2, 7, 11, 15], target = 9.
Welp, thanks for reminding me that software development companies are full of douches.
>>54232240
What are target_value and data set to?
Also try using the latest version of C in order to allow defining arrays without a length.
i.e. a[] = {1, 2} instead of a[2] = {1, 2}
http://ideone.com/Jh3tdQ
>>54232141
>>54232178
You are deluded. I have both done this in interviews and been given positions from those interviews. The point of the question is most obviously how well you can abstract a computer structure that is defined recursively. Writing a function that worries about a binary tree implemented in an array or something else just shows someone that you know how to shuffle around indexes, and thats not very hard anyways.
Write a function that prints a formatted representation of a binary tree.struct node
{
node *left, *right;
int value;
};
void PrintTree(node *head)
{
// Your implementation
}
Example output:9
/ \
5 11
/ \ \
3 7 12
>>54232387
Oops, stupidly formatted the output with a proportional font like a retard:9
/ \
5 11
/ \ \
3 7 12
>>54232301
>>54232310
Ah, I see my mistake. Thankfully a mistake like that wouldn't reflect very poorly on an interview. And its likely you could catch it when running an example in your head before telling your interviewer that you're done. You guys didn't catch that I didn't actually sum the x and y values:def two_sum(lst, target):
for (s, indexes) in ((x + y, (xi,yi))
for xi, x in enumerate(lst)
for yi, y in enumerate(lst)):
if s == target:
return indexes
>>54232413
I must have missed it because I didn't bother reading your code.
>>54232284
the point is clearly that you need to implement the binary tree. Just like if someone asked you to sort a collection of numbers (as in a previous post), you wouldn't say "No problem! sorted(sequence)" and then chortle at how clever you are.
It's clever if you're in the real world and there's a complex (maybe even NP hard) problem that defies simplification or optimization, but you realize a key insight that allows you to trivialize the problem, but that's not the basis of technical interviews at this level. If someone is asking you to invert a binary tree or write fizzbuzz or sort a collection of numbers, they're asking you to prove that you can do basic, fundamental things that all CS graduates should be capable of doing.
This is the equivalent of a P.E. teacher telling you to run a mile. If you're going to unlock your bike or grab your car keys, you're not being clever - you're being a jackass.
>>54232467
>you wouldn't say "No problem! sorted(sequence)" and then chortle at how clever you are.
But that's not a good analogy - he actually wrote out all the logic required to invert the tree.
Maybe you missed the fact that he's not calling any built-in functions? The only function call is recursive, to the function he wrote himself.
I agree that people with solutions like "Hurr, I can reverse the string by calling string.reverse," are annoying, but that's much different than this case. If they wanted you to write the whole binary tree yourself, they would include it in the problem definition.
In fact, the original problem was for a whiteboard test. I would assume pseudocode is permissible in such a situation, because it's a test of algorithmic reasoning, not concrete coding of a standard data structure that everyone knows.
>>54232467
I think this guy doesn't understand the solution that was provided.
>the point is clearly that you need to implement the binary tree.
Eh? If someone asks about "inverting" (not a real thing) a binary tree, they're clearly asking for a recursive left-right swap. Everyone understands a binary tree is composed of nodes with left/right node pointers.
I mean, it's one of the most basic data structures. I'm not sure what you THINK they could be wanting, beyond any old object.left/object.right type of syntax.
>This is the equivalent of a P.E. teacher telling you to run a mile. If you're going to unlock your bike or grab your car keys, you're not being clever - you're being a jackass.
What the actual fuck? Let's look at the original code that you SEEM to be commenting on:def invert(tree):
if tree:
invert(node.l)
invert(node.r)
tmp = node.l
tree.l = node.r
tree.r = tmp
That's pretty much standard binary tree left-right swapping. Are you somehow under the impression that he's calling a magical 'invert' function? I mean, that really SEEMS to be what you think he's doing, but he defined 'invert' right there.
Where's the magic you're criticizing?
>>54232467
I guarantee you if you ever get this question in an interview and you start implementing the binary tree, the interviewer is going to tell you to assume that its already implemented. If they wanted you to implement a binary tree, they would tell you to implement it.
btw if a problem can be trivialized with a "key insight" then cannot be NP-Complete (I'm guessing what you meant by NP hard) unless if it proves P=NP. If you prove P=NP in an interview let me know k?
>>54232517
This exactly
This thread is triggering me. The questions are very similar to a weekly homework programs I get in class. I suffer from Post dramatic stress disorder. Fuck off with the homework questions it's the end of the semester ok? Fuck off. I had enough of your shit all semester.
>>54232556
You should honestly just drop out now.
Just save your time and money.
>>54232387
C'mon, ladies, let's see those tree-printing functions.
>>54230671
>>54232413
There it is in 4 lines.
>>54232606
A brute-force n^2 solution (over a potentially significant subset of the data) that assumes the data is pre-sorted for you, sure.
>>54227914
HIRED!
>>54232683
O(n^2) is just fine. Also you don't have to assume the data is presorted.
Best I believe would be O(nlog(n)) and that would involve sorting the list first.
No thanks. I don't wanna go through some dumb interview. There are many other well paying jobs.
>>54227914
I think Google generally prefers Python over Ruby
>>54232683
Pretty sure it doesn't assume the data is pre-sorted but whatever you say man.
I guess the data could be sorted. That would be 1 more line since showing you know how to sort is not the point of the problem.
But lets talk about sorting. Sorting is O(nlogn)
I admit I don't see any tricks beyond brute forcing the answer, so maybe you could enlighten me. Otherwise you have to deal with the cartesian product of the list and itself, which is O(n^2) like you said, but consider the values [1, 2, ..., n] with a target = 2n. That also will have a runtime proportional to n^2 giving even a sorted list a worst case running time of Θ(n^2). Sorting it doesn't provably win you anything.
Unless of course you're interpreting the solution as actually not working if the data isn't sorted, in which case I ask that you try running it.
>>54232741
>O(n^2) is just fine.
What if you have a million entries?
You're right about not assuming presorted, my mistake.
>I'm a black native american transsexual lesbian female to male to female heterophobic wolfkin oppressed girl autistic
Say no more. I don't care if you can type, let alone code. You're hired.
>>54232741
see:
>>54232833
Sorting still has a big theta bound proportional to n^2
>>54232851
*sorting before brute-forcing solves the problem in a running time with a big theta bound proportional to n^2
>>54232841
>What if you have a million entries?
This is a good question. How can there be a better runtime, I'm assuming you know. I'm genuinely curious about the solution, I'm usually really bad at these problems that have clever a math trick or optimization (the real problems).
>>54232851
Create new sorted list: O(nlogn)
Create new list, elements are target - sorted list: O(n)
Test whether each element of original list is in new list of target - list: O(logn) for each test because the list is sorted, n comparisons: O(nlogn) for all comparisons
Find location of the two numbers in original list: O(n)
It's O(nlogn)
>>54232925
Shitty python example to show what I mean
This is O(n log(n)), isn't it?def find_sum(nums, target):
numset = set(nums)
for x in numset:
if(target - x in numset):
return nums.index(x), nums.index(target - x)
>>54232925
Cool I see.
I think BST's are one of my blindspots
>>54233078
My issue with this is that it relies on python's sets "probably" being implemented with some lookup that's O(logn), which kind of doesn't feel so good to me. I think as long as you say that you create a BST out of the sorted values in the list, then the last 3 lines are exactly what the correct answer would be.
>>54229548
>and they never dare to play the biggest dick with me
I've worked with plenty idiots and I never told them they're idiots. Enjoy mediocrity
>>54233134
>My issue with this is that it relies on python's sets "probably" being implemented with some lookup that's O(logn)
They are. But regardless yeah you could just use a sorted list instead.
>>54233145
I don't doubt you either. I was just saying that in an interview I would wave my hands and say "Binary search tree", but that's just my style. Good solution.
>>54232519
The key insight point is referencing the fact that mathematical problems are contrived; when you're trying to do something like TSP in real life you find that there are other factors that actually help arrive at an optimal solution more quickly. For example, buses that ship goods want to deliver those goods in the most optimal way every day, and it seems like a classic TSP problem.
Except, you factor in that taking a right turn is much easier in countries where the car drives on the right, and you find an incentive to navigate a small area in a way that has the car making mostly right turns (especially versus unprotected left turns).
This kind of stuff happens a lot - the mathematical problem is more abstracted and generalizable, but organizations in the real world operate under much more constrained requirements making many of the other potential solutions easier to reject at the outset.
In the context of finding a key insight (back to the original point and not wanting to follow your red herring), there are lots of domains where simpler heuristics can be applied and accurately classify or otherwise decide on something like 80-90% of the heuristics. the more advanced, complex models might get you another 5-10%, but the question becomes whether it's necessary to achieve that level of accuracy for your purposes (in many cases you need >90%, but in *many* cases you don't, and wasting your time achieving it is just that - wasteful).
>>54233145
Sets are implemented as a hashtable - this might actually be O(n)
>>54232683
>>54232741
the problem never says the integers are positive...
>>54233283
Sounds like you're talking about approximating np-complete problems or just dealing with np-completeness in general when you say trivialize.
I was responding in the sense that trivialize meant "solve"
