You are creating an oracle function that takes in a 128x128 greyscale image. You have to find the direction of the darker parts of the image and make a new matrix that consists of "arrow" characters as the example shows. If should point towards the darkest pixel above, beside, or below it. If the pixel has no darker neighbours, use a o. A tie has either arrow as valid (if the pixel is 2, but it's surrounded on all sides by 3's, any direction is valid. An example of a 4x4 transformation would be an input image of:
1,2,3,4 2,3,5,7 4,7,9,9 9,5,3,2
And would give an output of:
>>vv vvvv v>oo o^^^
I iterated over each pixel and made a "get neighbour" function that called each neighbour so I could do a check. I made a program on the whiteboard that solved the issue but when they called me a few days later I was told that I should reapply after 6-12 months somewhere else when I've gone through more data-oriented learning. That makes me think even though I solved the problem and wrote a working program, I failed the interview on my code. Is there a way to do this without checking each each pixel and making a check?
>He didn't train artificial neural network and ask the network for the answer on the whiteboard while using his other hand to reverse binary tree Back to uni for you kiddo
Cameron Bennett
>Is there a way to do this without checking each each pixel and making a check? you don't need to call get_neighbor on a pixel if you already iterated over it
Liam Harris
hey op, I am not a data oriented expert. But I think the issues they might have had with your approach is that it wasn't very kind to your cache?
Since the image is probably saved in a long 128*128 array (masked as a 2d-array) the way you iterate over the pixels is important. Maybe you iterated from top to bottom (`for each x { for each y {}}`) instead from left to right (`for each y { for each x {}}`)? This would have destroyed the cache. Try benchmarking the difference.
I don't think there is a way to solve this without checking the neighbours, but I would love to be proven wrong.
Have you called the company to ask what you could have improved?
Daniel Diaz
Only obvious optimization I can think of is not checking pixels that are pointing into currently checked one but that could wreck your cache in most implementations. I don't really know what they were expecting you to conjure on a whiteboard other than what you did. Perhaps you made some simple mistake that recruiters were told to explicitly watch for.
Aaron Martinez
They wanted you to write a convolution filter which output the gradient. An iterative solution is awful, you want to be using some matrix primitives loaded onto gpus to parallelize the operations.
Is this real life in burgerland? I'm junior sysadmin in central europe and interviewers only asked my if I can install windows and linux. I do much more serious stuff now but when I was starting I wasn't required to have that much knowledge. I was also mechanical engineer btw.
Elijah Reyes
did you include edge cases in your get neighbour function? e.g. making sure you don't check for pixels to the left of the leftmost pixel?
Hunter Ortiz
In the US you have to be better at the job than the person you're replacing on day one so the interviews get pretty crazy.
After you get hired you don't actually do anything though.
Josiah Cox
This isn't even a difficult one. You should see the take home problems
Jackson Barnes
I guess your colleges must be a lot better then. I can't imagine how skilled a person would have to be to just graduate college and be immediately able to work unsupervised in any given company.
When I was applying for this job I didn't even remotely have idea about the things im doing now.
Jack Allen
>I guess your colleges must be a lot better then. I can't imagine how skilled a person would have to be to just graduate college and be immediately able to work unsupervised in any given company. Do you graduate without any work experience? You should have at the very least 2 years of professional experience by the time you graduate from a 4 year program if you're not a slacker.
Gabriel Kelly
What makes you think they simply didn't like you or that there wasn't really a job on offer.
David Rodriguez
OP here, I'm in Canada. I'm looking to make $7 USD/h.
Maybe they didn't like me, but this was the third (and they said final) interview, I made it to the last stage of the process so I doubt there was no offer.
What kind of mistakes are there to avoid here then?
"Entry level position" is just a codeword for "bad pay".
Josiah Stewart
I've been there before, several times. Often there's a friend of the employee getting nepotism-ed through. I was once outdone by a Chinese guy with none of the advertised skills, a poor grasp of the language and who would have necessarily flunked the behavioural and teamwork tests. Sometimes you get rejected because they asked you for a specific opinion on software, you gave one, and they state having the arrogance to answer as the reason for your rejection. Let alone if it was unprompted. And sometimes a mid level dev applies for your junior position part way through the application process and everyone gets dumped. Ironically I ended up getting hired as the sole developer of a software contracting company purely based off of my resume. Pays like shit and is insecure, but at least when I'm back on the market I won't have pretend to be a yes man (as much).
Leo Rivera
Why would an intermediate / senior look for $7/h jobs? Then again, it is Canada and I've seen 0 year / entry levels working for much cheaper comparatively.
The HR Manager walked me out and said "I actually had fun with that interview. I hope I get to see you around regardless of what the outcome of the teams decision is."
Now that I've applied to about 300~ places in my province (according to Gmail searches for "application" in the past 3 months) and having made it to final rounds of interviews a couple of times but still failing at jobs paying median wage around me ($10~/h USD) or lower I really wish Canadians weren't getting auto-banned from US-gig-work websites like Fiverr, Freelance, etc. Then at least I could sell my skills. Sorry for ranting a bit but damn it feels bad to be told "You're not worth $7-10/h". Now that it's been 3 months I'm really starting to feel the financial pain.
That seems like a really non-obvious solution for a junior level whiteboard interview. Maybe I am inexperienced but a working solution is a working solution.
Plus breadth first traversal on a 128 by 128 is not awful.
You never really know OP. Maybe you and one other guy both did it right, but he did it faster, and they only had one opening?
Eli Jenkins
this guy knows what he's talking about
Justin Stewart
didn't understand the problem 100% but from your description of solution i guess it's some sort of djikstra algorithm, retarded companies often ask that from juniors
Nolan Adams
should index [3][1] be < rather than ^?
Kayden Hall
Just do 3-5 years of tech support before trying to get a tech job :)
Landon Rodriguez
No minimum wage? It took me over a year to find something out of uni. GL.
Wyatt Howard
Canada minimum wage is like $10/h, IE $5 in freedom bucks.
Landon Torres
damn I would not even be able to finish reading that assignment complete waste of time. But if this is standard in US you should say fuck it and start building online income. It will be easier, more fun and with bigger potential
Luke Nelson
How does one build online income?
Wyatt Diaz
Jesus. I'm an IT pinhead straight out of college and I'm making $20/h, that's USD. I did work a lot while in school. Did a helldesk support thing for 11 months, and an internship for 3.
If you were tossed into small town Alberta you'd probably make $4-$5 per hour US (under minimum wage in Alberta of $11 USD/h). If you were in a city if you fought off enough people looking for those wages you'd be able to get $11 USD/h, but again you'd be in the city and paying city rent.
They cover gradients in multivariable calculus, so you should have been exposed to them as a concept even if you couldn't code what that other user said
Joshua Davis
Damn. I know nothing about Canada except that weed is legal. Can you even live by yourself on that wage?
I'm actually doing OK at $7/h intermittently. I have power and internet, pay my taxes, grow most of my own food and have enough mason jars of pickles to keep 100 people through winter. But if I want to start a family (I do) I need to move into higher wage positions, or at least $7/h consistently. If I move to the city, I would NEED $14-$20/h consistently to keep up with rent ($2000/mo in the city, vs $3000/yr in property taxes in the home I own). But I can easily pay $0 a year in food, water, etc if I choose not to take advantage of any luxurious options. I make about $4000/yr driving weed down to the city, which covers all the taxes on my house, but I actually like coding for a living. The problem is that there's 1 person hiring for every 100 applicants.
And now you know Canada!
Carson Jackson
Good luck man. I'm sure you'll find something good soon.
Luis Sanchez
imagine the smell
Levi Myers
Gradients are not a solution to this problem. Taking the gradient here offers no benefit.
Nathan Foster
>Not using recursion for the sake of recursion heh, I'd make the most confusing solution so they think i'm really smart.
Jaxson Nelson
noi
Aiden Parker
I've conducted hundreds of interviews. The thing that stands out to me is that you call your function "get nieghbour" which doesn't sound right, because your image should be some kind of an array so why do you need to define a function to get the value of a neighbour. You can just look it up in the array. The fact that they referred to "data oriented" programming confirms this. I guess that interviewer said "didn't understand how to use data structures effectively" and the recruiter translated this to "data oriented programming". Note that its' not about efficiency, e.g. in C the compiler would optimize away a function like "get neighbour", it's just that it's pointless to define functions like this and wastes time and mental energy. The right solution would be something like (using C here)
char get_arrow(uint8_t* grid, int i, int j, int M, int N) { char result = 'o'; uint8_t darkest_neighbour = 0; if (i > 0 && grid[i - 1][j] > darkest_neighbour) { darkest_neighbour = grid[i - 1][j]; result '
Nathan Flores
literally the only non retarded person here
Samuel Ross
I hope they weren't asking for recursion arbitrarily, but not telling me so, because I could do something like that. I wasn't told to though.
Sorry but I'm not sure why?
Ryder Bennett
The gradient will tell you the rate and direction of change, which seems to be exactly what OP needed.
Julian Cox
>That seems like a really non-obvious solution for a junior level whiteboard interview. If you are going into data oriented work like op appears to have then it should be obvious. This is some deep learning 101 tier stuff, you aren't worth considering if you can't recognize what the problem is.
Kayden Adams
I didn't take a picture but I came up with something like what I've attached. Only change was I passed the whole bitmap to the 'GetNeighbour' function which was unnecessary (in retrospect) but this is basically what ran.
Not sure why I'm sharing my failures, but idk, might as well make it a utilizable endeavour: Roast my code.
I got an $80k job just off of word of mouth and a github in Ottawa. My interview was largely non-technical. ie, I didn't have any whiteboard or coding exercises, but there was some discussion on what kind of complexity some algorithms on common data structures in c++'s STL were.
Keep applying, you can find places that don't interview the way you were interviewed. Usually with a technical interview, at least you can ask for feedback on what they expected in terms of the solution and all. I encourage you to apply to some companies in Ottawa and Toronto user. Yes the cost of living is stupid, but you'll come out ahead compensation wise.
Also you should name drop the company paying you $10/hr for C# development. That deserves naming and shaming.
This is Java right? You are on the right track but there's lots of little things wrong with the code. I'm guessing you were just too slow writing the solution, and with too many errors.
> you use nested if's instead of if(x > 0 && ...) >x-- mutates x so you shouln't use do this in input.data[x--][y], instead just write input.data[x - 1]][y]. >While the question has a square array, it's generally better to write for (int y = 0; y < int.data[0].length; y++) >You aren't actually doing the right thing with your series of if statements: your code will find a direction which points to a larger value, but not the direction that points to the largest direction. My code in was also wrong here, but my code would be correct if it started with uint8_t darkest_neighbour = grid[i][j].
You need to first learn to write correct code. Optimizations come after but you're just writing stuff that' wrong. Try running your code and see what happens.
Jordan Brown
This. My current internship was purely behavioral which was a nice change of pace compared to fizzbuzz nonsense
Anthony Moore
what the fuck is an oracle function
programming interviews should just be "prove to me you know the 'how' and 'why' of bread-and-butter data structures" and that's it, you are hired.
Camden Gomez
both x and y are counting up to image.data.Length, which can't be right
the post-decrement and post-increment of indices just results in comparisons of values with themselves
increment and decrement are wrong anyway and screw up the loop
troll exercise anyway, companies are awful these days because there's a huge surplus of labour
Jackson Ward
>troll exercise anyway Not a troll, it weeded out OP.
Logan Martinez
would have weeded me out the moment they asked me to program on a whiteboard
Bentley Collins
I'm happy to code on whiteboard if it means I get to work with competent people. The people most offended by whiteboard interviews are divas who think they are better than they are.
Noah Moore
For one, array access is expensive (relatively) so you should only mention image.data[x][y] once in the loop, same with arrowmap.data[x][y].
Jacob White
>>x-- mutates x so you shouln't use do this in input.data[x--][y], instead just write input.data[x - 1]][y]. Thing is that x doesn't even change before checking the condition, the post decrement operator means that what you're doing in the if statement is comparing data[x][y] with itself and only when the comparison is complete x will be decremented
Dominic Sullivan
This is 4 lookups per pixel in the image. I think it can be done with less.
Josiah Garcia
>name drop the company paying you $10/hr for C# development.
They also have "work from home" call sales, based on commission. If you order a pizza from Pizza hut in Canada, you're very likely talking to someone who is not in their main, full timer office. You're talking with a $2-$4/h call center support agent that only makes 3% of the sale. So if they get big orders and sell 20 $10 pizzas in an hour they make $6. It's legal in a different way its legal to pay me below minimum wage though. Here you can have no-base-wage and say "if they're good enough they could make tons of money, they make commission" and even though no one ever gets a $1000 order which would bump them to an amazing $30 for one hour, it's possible, so they can work that commission.
They explained the process as "incorporating". So I would be brought on if accepted, and given a named incorporation (So if I'm Bob Smith, I'd be made director and CEO of Bob Smith* (*Denotes incorporation) as it was shown to me). Then they pay the incorporation $X I would have to report as capital gains personally once I paid myself from the funds they paid my company.
I tried to be true to what I wrote on the whiteboard. On Visual Studio as soon as I got home I remembered GetLength() which I couldn't remember for the life of me on the whiteboard. It's not apparently relevant, but it just goes to show the different headspace I'm in when I don't use the regular environment. This is what I'd write if I was writing in Visual Studio - I didn't google anything, so I bet there's an algorithm I'd be able to look up easily that I could implement for efficiency. But this is what I would honestly write. If this post survives until tomorrow I'll actually see if google can help me find a better solution and then I'll try to write that too.
In the last line of the sample given there's a mistake. It should be o
Henry Moore
your code is still wrong. GetLength doesn't seem to do what you think it does (it doesn't accept an integer argument) and you are setting darkest to the pixel instead of the neighbor.
Adrian Ross
>You are creating an oracle function yeah i think i'm in the wrong interview bye
Leo Bell
So here's my attempt. It's designed specifically to minimize array lookups, doing two per pixel instead of 4 in your approach. pastebin.com/546u2UKd
GetLength does indeed work exactly like he thinks it does and it does accept an integer.
Nicholas Scott
Well not me personally, I have been working through college, but only to support myself. Only 1 year I worked in a field im emplyed in. And it's not mandatory, 80% people don't do that. Only people who need money to stay in school do it.
Dylan Brown
I missed that this is C#, thought it was Java from the syntax.
Brayden Hernandez
U being serious man? I'm the poster from central europe. My first job (part time job, when I was a student) paid 10euro/hour. And now after 1 year I wouldn't even consider for a second going under 20e/h. Damn I thought you guys were much richer.
Henry Thompson
That's my mistake, I'm sorry about that and will try to be more accurate (even though this is the internet) in the future.
Oh shit traversing over each dimension then setting the next check with a=b completely negates needing to put an if statement in all those sections. I bet this is the answer they were looking for.
Yikes I'm now facing mounting evidence that I am retarded. I mean, I never went in saying I'm hot shit, when asked my greatest strength I said I'm firm on forgiving people who try to redeem themselves even when it's hard. I never claimed I was able to operate a computer not connected to stackoverflow.com but if it is I think a business can make a profit off of my code when I get $56/day to make that code. That's fundamentally my claim - by my estimation, I am of the belief that my code is worth about $7/h. But God damnit it's hard to get someone to actually give me that.
Carter Morales
Where are you finding these cunts? I work for fucking bestbuy in the geeksquad, part time and refuse to accept any sort of responsibility and mostly just take closing shifts where I sit around on my phone and maybe press a few buttons on the mostly-automated software tools designed for the average monkey to be able to manage, and I still make 16 leafbucks an hour, and started at 13. They're trying to pay you less for shit that requires anything like the shit in the OP than the people I work with who's only qualifications are "slightly more tech savvy than the old ladies that call chrome 'the google'"
Caleb Perry
With modern CPUs, if you iterate through the first dim of the array in the outer loop, then the second dim in the inner loop, it will be fast because both the row, the row above, and the row below will stay in cache. But in your code you also iterate through the second dim of the array as the outer loop. This isn't cache friendly.
Iterating over the array in the wrong order will result in far worse performance than just doing the four lookups per iteration.
Luis Watson
You need to iterate both vertically and horizontally for this to work. I didn't say it will perform better, though I don't fully agree with you that it performs worse than naive approach.
Jordan Powell
If you don't care about performance why do you care about minimizing the number of array lookups?
Juan Carter
No ifs I specifically stated what it was optimized for.
Jose Adams
Jow Forums in a post
Mason Butler
>You should see the take home problems please no. I'm fucking sick of small startups that made me shit out a functional web app or implementing a server for a custom protocol over udp or something bullshit like this
Since you're Canadian, if you consider moving, apply to Amazon (they're Toronto and Vancouver), they're doing some massive hiring right now and pay much more than pretty much any other company in Canada.
Nathan Ortiz
apart from performance, is there some other reason one would want to minimize the number of array lookups?
Jackson Gutierrez
I've done 10~ hour projects for people back when I was naive. Or desperate. I didn't mind for a while, but when the amount of people that didn't even call me back to let me know I wasn't considered anymore, nor did they send me a thank you for applying message began to mount I had to stop. It was draining a significant amount of my time and I wasn't about to wait for it to suss out a 1/100th hire rate when I could work just fine under a 1/300th hire rate with the no-effort-required applications. A 10 hour project should get you right into the interview or pre-hire stage instantly.
Looks pretty good. You want a $7/h job?
rekt
Jaxson Bailey
Hey OP, I work at Google, this is a tougher problem than we'd usually give in our entry level interviews. The trick is to realize that you can never have a cycle between your pixels, and to use that fact to reduce the number of checks you need to make. Look into the BFS algorithm! The big-O runtime is the same, and it's still possible to achieve good cache behavior, especially when the entire image can fit in your cache.
Also, not sure if it's mentioned, but the example is wrong, around the bottom left corner.
Brody Hughes
I think you can avoid checking everything around the circles, since it’s a given that the neighbors will point at them, it’s the darkest pixel
Caleb Long
This code is extremely unfriendly to your branch predictor... And it's easy to f up your cache like this
Eli Kelly
(not op)
Josiah Reyes
Bumping to see if my assumption is correct
Chase Davis
brainlet here, I thought BFS is for trees, isn't an image just a matrix?
Charles Reed
I want to fuck a black IT college student
Blake Jackson
We effectively form a number of trees from the matrix. Each node is a pixel, each edge is a comparison between two pixels.
It doesn't have to be a tree structure, either. Trees work, but other DSs do fine as well
Jaxson Gonzalez
so you start at some pixel and always go down a child that is the darkest one out of them?
Andrew Ward
Start at 0,0. Check neighbours and mark it accordingly. If it's a one-way connection, proceed to that pixel. If it's a multiway connection, go to both pixels. Keep a log of which pixels you haven't visited, it's possible for directional graphs to miss some nodes in a traversal.
Eli Turner
>hurr you should know bfs from heart on the spot interviewers and hr cunts all deserve to be homeless
Blake Phillips
It's C# specifically, meaning no gpus and probably not even unsafe operations. They probably just want to avoid the boundary check and maybe also to split the 4 directions per pixel into 4 whole "runs" each only checking one direction of neighborhood.
