Simple Code, High Performance [video]
youtube.com
Simple Code, High Performance [video]
1–10 of 86 posts
Re: Simple Code, High Performance [video]
#2So does he have a special reversed image printed on his shirt just for this lecture format?
Re: Simple Code, High Performance [video]
#3So does he have a special reversed image printed on his shirt just for this lecture format?
I looked into this a while back, yep.
Re: Simple Code, High Performance [video]
#4This was good. I like the presentation.
---------
This can be a good interview question for Google to screw people over.
I was asked to write a code to generate maze (100x100) with the constraints that it should neither be easy not it should be hard. This was for L6 position.
Re: Simple Code, High Performance [video]
#53 hour video with no timestamps, a minimal description, and comments turned off?
Re: Simple Code, High Performance [video]
#6"Simple code" -> very difficult to decipher use of SIMD intrinsics. Yikes.
He may have deleted 1000 lines of code, but he'll need a 2 hour inline video (with a 1000 line transcript) to explain how it works.
Re: Simple Code, High Performance [video]
#7"Simple code" -> very difficult to decipher use of SIMD intrinsics. Yikes. He may have deleted 1000 lines of code, but he'll need a 2 hour inline video (with a 1000 line transcript) to explain how it works.
Even if he had stopped before hand-rolling the SIMD, it'd still be a multiple order of magnitude improvement.
I do think it would have been useful to demonstrate that before going straight to hard mode.
Re: Simple Code, High Performance [video]
#8This was good. I like the presentation. --------- This can be a good interview question for Google to screw people over. I was asked to write a code to generate maze (100x100) with the constraints that it should neither be easy not it should be hard. This was for L6 position.
That's a very interesting. I am curious to hear what your answer was :D
Here's my thoughts on what a solution would need:
1. At least one path from source to target.
2. Some quantification of hardness. No of steps in optimal path? Number of turns in optimal path? Number of paths? Some weighted combination of all three?
Some preliminaries:
Finding optimal path, and finding number of paths can both be down in O(N^2) using DP. Finding number of turns is then trivial.
Now the Algos for 1:
Algo for 1: Naive backtracking, i.e., randomly generate paths until there are no paths. Evaluate each maze using the heuristic and output best one. Run for some fixed time t. This is exp time.
Another algo for 1. Generate a path as following: select K points on the grid, with the start and end being the first and last; then finding optimal paths in sequence (notice that this guarantees not cyclical path). Next, generate fresh path on an empty grid and overlay on the previous path. Keep repeating for some M paths. Now fill in non path pixels. Pick the best grid among these M steps. This is O(M*N^2).
Last Algo for 1: Throw the grid into an ILP solver and optimize the heuristic (exp time).
Re: Simple Code, High Performance [video]
#9This was good. I like the presentation. --------- This can be a good interview question for Google to screw people over. I was asked to write a code to generate maze (100x100) with the constraints that it should neither be easy not it should be hard. This was for L6 position.
That's a very interesting. I am curious to hear what your answer was :D Here's my thoughts on what a solution would need: 1. At least one path from source to target. 2. Some quantification of hardness. No of steps in optimal path? Number of turns in optimal path? Number of paths? Some weighted combination of all three? Some preliminaries: Finding optimal path, and finding number of paths can both be down in O(N^2) us…
Well, I addressed the "neither easy nor hard part" upfront. My take was there has to be a solution and that too 1 solution. In other words, it had to be fair.
Second was the degree of false paths (term I made-up). This essentially governs the branching of each false path. Higher the degree higher the branching and higher the backtracking. This would make the maze harder.
So my algo was
1. To generate a valid path from top-left to bottom-right. (this is simple bfs/dfs walk). This is illustrated as path 1-2-3-4-5-6-7..-10 below. This ensures we have a fair maze.
2. Now from each number below, generate path in an outward manner till it hits walls. These are false paths. The "degree" mentioned above will dictate if there are further branching out of these paths.
1 * * * * *
2 3 * * * *
* 4 5 6 * *
* * * 7 * *
* * * 8 9 10
In the step #1 we note the row,col in a dict/hashmap. We use these in step #2 to ensure the dfs walk dont step on these row,col.
This is all I could conjure-up in 45 min including a code in python. I was labelled lean-no hire.
Edit: fixed the rendering of the maze
Re: Simple Code, High Performance [video]
#10I really like this lecture format. What is he drawing on?