ITT: Interview Questions Thread

>>57717928
people here dont have enough IQ points to solve interview questions

also i would waifu her

>>57718148
No they'd rather make a thread about anime

>>57717928
No one even has jobs here

>>57718148
You'd waifu a hot ham and cheese you neckbearded faggot.

File: me.jpg (138KB, 625x400px) Image search: [Google]

138KB, 625x400px

>>57718244
Touche

(x1+x2)/2 = x'
(y1+y2)/2 = y'

Is (x',y') in both circles. Distance formula < radius

How is this an algorithm question?

>>57717928
put the circles equations in square matrix form
call said matrix M
if det(M) = 0, we have intersection
else, no intersections.

O(n)

bye

>>57717928
1. Simple. Make a grid.
2. Put circle anywhere and mark the squares on the grid the circle touches. Basically tell the circle and the square/cell about each other.
3 .Now when you need to check intersection for you check for other circles in the grid.

Now you can look up the circle, iterate over the list which contains the cells it touches then iterate over each cell and per cell iterate over the circles they touch and check for collision against your chosen circle excluding itself.
You could make a smaller and bigger grid.

Ehhh... just make a Quad-tree or something similar.

These are good for a lot of other things, general performance culling.

>>57718381
How do you solve the determinant in O(n)?


>>57718354
You need to check all the other circles for every every circle. OP wants an algo which is faster than O(n^2).

>>57717928
For each possible pair of circles, except a circle and itself and pairs we're already testing in the other order:
Let 1x 1y 1r be center xy coords and radius for nr 1
Let 2x 2y 2r be same for nr 2
If ((1x-2x)^2+(1y-2y)^2)>(1r+2r)^2 then they intersect

Better than O(n^2), yes?

>>57718354
Are you really that retarded?
You should apply this formula into a double for loop to satisfy initial request

So dumb

>>57718420
Quadtree is the right answer, I suppose
But I don't know its theoretical computational cost

>>57717928
qt

>>57717928
>Better than O(n^2) complexity
I don't think there is such a thing.

>>57718420
ah. Misread. Could do it the ESRI way. Bounding box for everything and then clean up the results. Requires two-pass, but polygons are a bitch.

>>57718439
Also, I am employed 6 figures and dumber than you. Enjoy your life shit sandwich.

>>57718427
>For each possible pair of circles, except a circle and itself and pairs we're already testing in the other order:
n*(n-1)/2 is still practically n^2. A constant addition/subtraction/division or multiplication doesn't really matter for very large n, cause n is going to dominate anyway.

>>57718558
>Also, I am employed 6 figures and dumber than you. Enjoy your life shit sandwich.

Yeah, sure, space cowboy

File: Brown Representability.png (1MB, 1344x1196px) Image search: [Google]

1MB, 1344x1196px

>>57718540

>>57717928
What kind of interview question is this?

>>57718604
your right. Clearly I am not dumber than you.

>>57718639
>your right
You prove my point twice

>>57718624
Given two pre-order traversal arrays of two binary search tree respectively, find first pair of non-matching leaves.

If they are general binary trees instead of BSTs, could you solve it? give out your reason.

>>57718766
You didn't answer my question. What kind of interview question is this?

>>57718789
Run of the mill software engineering interview questions

>>57718511
Yeah, it's good for cutting out the unnecessary stuff.
>But I don't know its theoretical computational cost
The cost is dependent on the underlying data structure, but you can certainly skip checking everything. That's the point.

You can probably add it up like this by adding up the cost of different parts.
1. Cost of looking up the cells.
2. Cost of iterating through the cells to get all the possible circles.
3. Checking the circles, which is still n^2 , but you do it on a much smaller scale, so this n is much smaller than the total number of circles.
However this greatly depends on the actual implementation.

You don't always need to reduce the complexity in a more straightforward way, it's enough if you can reduce the amount of data considerably.

Usually the point is a more costly (and memory intensive) creation, but a fast lookup .


Keep in mind though that for example a hash-table can have O(1) times doesn't mean it's faster than an array lookup for smaller values. Generating the hash, etc. can be slow for small data.

>>57718805
Interesting, are these question part of a daily work routine?

>>57718766
Yes. Because I'm good.

>>57718559
Still < O(n^2) though. How the fuck are you supposed to do it? Sort them by approximate location to cull more, like "if it doesn't intersect with B then not C either"? Do you need more math than what you learned in high school?

>>57717928
n^2 would simply be comparing every circle against every other circle in any ordered fashion. When you say better than n^2 do you mean that n^2 isnt good enough. Its a much more interesting problem then and I cant immediate think of one. Sorting as you go still has n^2 worst case.

>>57718910
You're supposed to use trees or something, see >>57718559

No one asking more questions
>alright anon, describe yourself

>>57718946
Check >>57718766

>>57718842
I would not assume so. More like to filter you out

>>57719122
Odd, wouldn't it be more normal to bring up work related questions?

worst case: O((n-1)*n/2) ~ O(n^2)
best case: O(n)

>>57718420
Hmmm
What about a tree. Like a BST but not really. Each tree has up to 4 children based on the root node as the origin. Im not about to make the actual program because its been too long since Ive done tree stuff, but its simple recursion.
Basically, the children as ++, -+, +-, -- (so based on if the x and/or y position is greater than or less than the root.
Then as you insert you just check for a collision.

>>57718766
Since the array represents a binary tree, it has (2^n)+1 dimension, said n is the height of the tree.

So we can check all the leaves at given k height, with 0<=k<=n.
Result is first mismatch.
Complexity is O(n) (both arrays should have same length).

Works for BST and binary trees.

>>57718895
See >>57718808

>Do you need more math than what you learned in high school?

You don't necessarily need more math. You need to know data structures and related math/thinking. The thinking is the important bit here. So yeah, you could say you need a bit more math.

Do Americans only learn a single mathematic? I thought mathematics was the most popular subject.

>>57718766
I dont understand. BST arrays are pretty straight forward with where the children are since nth child is always in mth array slot. So you could literally just iterate through the two arrays and if something doesnt match you found it. Its O(n)

>>57718766
When you say general trees. Are we talking trees with variable amounts of leaves?

>>57719264
Lets say variable

>>57717928
is this right?

var circles = [];
for(let i=0; i<circles.length; i++)
  for(let j=i; j<circles.length; j++) {
    var a = circles[i];
    var b = circles[j];
    var x = b.x - a.x;
    var y = b.y - a.y;
    if(x*x + y*y <= pow(a.radius+b.radius, 2) )
      return true;
  }
return false;

>>57719444
>let j=i+1
is what i meant

>>57718615
>>57717928
Topology isn't useful for anything.

>>57719519
This problem exist for collision detections. useful in programming physics simulators, games, robots.

>>57717928
Whats the answer to this? I would assume any binary search tree would work for this. Just make the sorting function take the x coordinate.

>>57719686
I was refering to the filenames. But I have to admit I wasn't aware of the concept of quadtrees and their use in image representation and collision detections.

File: get tomorrows date.png (77KB, 694x801px) Image search: [Google]

77KB, 694x801px

>Interview at company
>Had to ask one guy what "transposing a matrix" meant, solved the question after he told me the definition
>Waffled my way through some kind of tree search algorithm question
>Did pretty well when given a code sample and told to abstract the core functionality of it

I got the job, but I'm pretty sure I'm on the "least likely to break anything major" team. Oh well, I never even went to college.

>>57719768
It's just a basic quadtree. Better than O(n^2) is a big hint that narrows it down a lot, you can't use any naive solution that just directly compares each circle to every other one.

>>57720114
Why would you use a quad tree and not a bst?

>>57720138
You could use that too, but a quadtree is much more straightforward and easy to implement, since it doesn't involve sorting, while still satisfying the requirements. It's up to preference really.

> work as Software Engineer instead of Computer Scientist
> never get asked weird math questions about circles
whew

>>57718615
does she have a dick?

Business student here
So glad I don't have to deal with this shit

>>57717928
Check distance between 1 and 2. If they intersect then mark them. Check 3 with 1 and 2 and if they intersect then mark the pair that does. Then go on.

>>57720856
I meant continue algorithm until N circles

>ITT: we do anon's homework

>>57717928
>math question
>technology board

Smells like Social Contact DESPERATION

>>57718148

>also i would waifu her

she is a porn actress, anon

>>57721057
In her hearth she's still pure.

>>57719444
Not < n^2, and can be optimized further.

what kind of questions can i expect for a full stack engineer?

>>57721412
>full stack engineer?
https://www.sitepoint.com/full-stack-developer/

>mfw can't answer these questions
These aren't real things you'd be doing at work though right?

File: dUla8Vq.jpg (1MB, 2500x2500px) Image search: [Google]

1MB, 2500x2500px

>>57718895
>n*(n-1)/2
>Still < O(n^2) though.
No you fucking retard, it is LITERALLY O(n2)

Do you even big-O?

>>57720177
Isn't quad-tree collision detection O(n^2) unless you have unlimited levels to your quad tree, in which case you have a potential infinite loop (if all the circles are in the same spot)

>>57717928

Get a sheet of paper (O(1))
Get one of these (O(1))
https://www.walmart.com/ip/Compass-Cutter/17337979
Cut each circle (O(n))
    For each circle cut out, inspect the paper for roundness and return "true" if not round. (O(1))
return false

O(n) time, bitches.

>>57717928
1. Look at circles
2. If two intersect, say they intersect

Now hire me