-
Hey, guest user. Hope you're enjoying NeoGAF! Have you considered registering for an account? Come join us and add your take to the daily discourse.
Programming |OT| C is better than C++! No, C++ is better than C
- Thread starter Kikarian
- Start date
out0v0rder
Member
browsing for a driver or package on ibm's website is frustrating.
In other words, you are asking how to render shadows. It is a high level problem that has no direct hardware support, so there's no simple OpenGL switch you can flick to do it. There are many techniques for it, eg. using shadowmaps or shadow volumes. Here's a starting point for you:
https://en.wikipedia.org/wiki/Shadow_mapping
https://en.wikipedia.org/wiki/Shadow_volume
Chainsawkitten
Member
That sounds crazy. My professor also sticks pretty tightly to that book (though I think the book uses red-black trees and we had AVL) but he's doing it in 3 months, and with one final test.
Hang in there
Interviewed a candidate today for a JavaScript Entry Level position and I had to tell him what global/scoped variables are and how to define them.
That literally was the first thing and originally I hesitated to ask that cause why else would someone apply to a position like that. Far too basic, well guess not.
That literally was the first thing and originally I hesitated to ask that cause why else would someone apply to a position like that. Far too basic, well guess not.
I wonder if he was super nervous or something and that caused him to answer improperly. Did he have any sort of idea or absolutely none? He might have applied to the position because he felt it would be good practice or that he would have been a good candidate otherwise who could learn on the job. Sometimes I wonder about applying to jobs outside my range to see responses.
I was actually called in for an interview for a position that I was unqualified for. Only reason the chance to interview came up was because it was a special circumstance where someone else in the company really wanted me to be given a chance because he couldn't hire me himself. It was a bad interview (way too many things that I didn't have any experience with and some stuff I just couldn't remember). However it was a great learning experience and I took notes on some of the stuff I couldn't remember, like singletons, so I could study them in the future.
Okay so I just got a new MBP from my company. First time owning an OSX machine. What are some must have developer apps or even general utility apps? Just looking for ways to improve my workflow. I already have iTerm2, homebrew, and a couple IDEs but that's it. Mostly Android development.
Android Tool is pretty neat. Yeah, you can capture screenshots and videos from Android Studio, but Android Tool is a nice dedicated app for grabbing a quick capture.
As far as just OS tools go, Better Touch Tool will give you Windows Snap-like features. This is coming in the next OSX update natively, but BTT is so customizable and you need to get it now. You can customize other things too, like multitouch gestures, but I haven't messed with that.
Caffeine is a nice little utility that just acts as a quick toggle to keep the screen/computer from sleeping.
I think BTT and Caffeine are both on the Mac App Store if you'd rather get them from there.
If it helps, Youtube was my best friend so far for this course. Almost everything in the book has a nice and intuitive video that explains/shows what's going on in a couple of minutes.
The problems I had the hardest time with though are those that treat the algorithms/structures as a black box and ask you to write another algorithm that uses them, so understanding the material doesn't really help there.
As in "design an algorithm to solve this problem"?
On the algorithm courses I've taken, there haven't really been many applied/creative exercises like that unfortunately. It's pretty much been about analysing and following well-known algorithms. I would think carefully before putting that sort of problem on an exam though, it has the same sort of issue as using a brainteaser question in a job interview - some will have a flash of inspiration on that day and some won't.
Forklift is a brilliant file manager. I wish there was an equally good one for Windows, but there I have to settle for FreeCommander. The stock Finder is not as bad as Windows Explorer, if you put it permanently in column mode and get used to it, but Forklift is easily worth the cost.
Skim is a PDF reader, handier than Preview for reading books and the like. Has a proper fullscreen (fullscreen borderless window) mode so you can instantly cmd-tab into it and back from other apps, as opposed to using OS X' built-in fullscreen functionality which is garbage.
Yeah it's basically a riddle or a brainteaser and that's why it's such a wildcard. Each homework assignment had on average one or two such questions. Still, they usually give us the expected time and space complexity to shoot for, which more than once was a big enough hint to give me the answer outright.
For example (of course having to write the algorithms too)
Suggest a data structure that can contain m groups, each group containing n keys, with the algorithms:
Insert(i, k) - Insert k to group no. i - O(logm+logn)
Remove(i, k) - same
MinMax() - get the minimum value among {x | x is maximum of a group} O(1)
GlobalMax() - same except the maximum value from the group - O(1)
My answer was
an array of AVL trees + an array of {x} + an AVL tree of {x}, updating MinMax and GlobalMax inside the other functions
Using a maximum heap of size n, can you give an algorithm to get the k largest values in less than O(klogn)?
My answer
yes, using another heap to get O(klogk)
Suggest a structure of space complexity O
withInit() - get empty instance
Insert(i, k) - enter k into index i, pushing everything above i one index forward O(logn)
Get(i) - O(logn)
Multiply(a, b) - get the multiplication of all values except for those between indexes a and b (not including) - O(logn)
My answer
using a skiplist, each node saves how many nodes (on the ground level) there are between it and the next node on its own level, and the multiplication of those nodes
As long as the exam stays at around that level I'll hopefully be ok. It's hard but doable
Those are pretty tough. I have to read up on heaps because I've pretty much forgotten about them.
Here's a fun brainteaser. Multiple people I've given it to have insisted it can't have a solution, but it does. There's no funny business, no assumption made about the data, and it doesn't require knowledge of any complex data structure. The implementation is actually dead simple. Still took me a good while to find the answer.
Give a data structure that behaves like a fixed size array of size n (that is to say, O(1) to read and write any index) but additionally allows resetting all of the data to arbitrary value k in O(1).
A bit of a cop out but how an array + an int and a flag, if the flag is set to true then use the int instead of the array, and reset the flag back to false every time something in the array is changed after a reset.
It's not that easy. With your proposed solution, if you have the array full of value A, reset to value B, and then assign value C into index 0, the data in the other indices that should now all be B would incorrectly read as A.
Put a spoiler on further solution attempts, someone else might be working on it as well.
Chainsawkitten
Member
Code:
blah.set(1, 1)
blah.reset(0)
blah.set(0, 1)
print blah.get(1)Either print blah.get(1) is going to print wrong (1 rather than 0), or blah.set(0, 1) is going to take O
, with that solution.Though one can build on that solution.
Instead of just having a flag, we could create an array of structs.
Rather than just storing whether the data structure has been reset, we store when each value was stored and when we reset it, and only default to the reset value when accessing a value that hasn't been updated since the last reset.
Rather than just storing whether the data structure has been reset, we store when each value was stored and when we reset it, and only default to the reset value when accessing a value that hasn't been updated since the last reset.
Bro, spoilers!
One of my students actually came up with this same attempt before. It's clever, but incorrect. The iteration will, at least theoretically, overflow and I doubt you can come up with a way to handle the overflow situation in O(1).
Chainsawkitten
Member
How do I spoiler code tags?
If you're doing it for something like a char, it'll also multiply memory consumption by 5. (Or more if you're going for longs if you're really that afraid of overflow.) (On the plus side, it doesn't have to be fixed size, though resize will obviously take longer than O(1).)
If you're doing it for something like a char, it'll also multiply memory consumption by 5. (Or more if you're going for longs if you're really that afraid of overflow.) (On the plus side, it doesn't have to be fixed size, though resize will obviously take longer than O(1).)
Oh, they don't work on code tags? Then I guess paste your code into a gist and link to it from your post. https://gist.github.com/
This probably isn't what you're after but I think I have a working solution at least. Totally got nerd sniped by that challenge :'(
http://ideone.com/wyR43I
http://ideone.com/wyR43I
Just a bit more on the problem and the problem-solving process. If I remember correctly it took me hours of on-and-off thinking over 2-3 days to come up with the solution, but many others can probably come up with the solution much quicker. The performance constraints are so severe that there really aren't many things you can do. If you eliminate all other options, then whatever remains must be a part of the correct solution, even if it feels silly. There is a bit of a crazy idea you have to get at the end to simultaneously reach all the requirements, but up to that point you can just grind out the problem.
As you can probably guess from the fact that you haven't heard about this structure (and AFAIK it doesn't even have a name), it is not likely to be genuinely useful. It is however easy to actually implement, and not theoretical in that sense.
As you can probably guess from the fact that you haven't heard about this structure (and AFAIK it doesn't even have a name), it is not likely to be genuinely useful. It is however easy to actually implement, and not theoretical in that sense.
All the operations are O(1), so it'd be a solution, but it doesn't work. You thought it works because the structure's Get() modifies the structure, and your test code printed the full contents of the structure after every operation, in fact performing a O
cleanup sweep into the structure. If you remove the prints from the test code:
Code:
SpecialArray<int> test = new SpecialArray<int> (0, 4);
test.Set (0, 999);
test.SetAll (14);
test.SetAll (16);
test.Print (); // 999, 16, 16, 16 - oops.When you get the idea for the correct solution, you won't need an implementation to know it works. I warmly recommend working it out on paper. I never manage to think about structures correctly otherwise.
Okay, so instead of using one boolean flag like I tried before, use an "array" of booleans in the form of a binary string. You can turn all of them off in O(1) using &&0 and also turn a single bit on in O(1) with ||(<<shift^x 1)
Though I guess this isn't possible with n that's too big..
Though I guess this isn't possible with n that's too big..
Edit: oh wait a hint huh. well dang. i ain't looking.
Yep, micro-optimization tricks do not turn O
into O(1).Regarding the hint, it's the weakest I can possibly give, to focus someone who feels they can't find any traction to get started with the problem. Doesn't spoil any of the solution. I can later give away the full first half of the solution, and that still leaves the funniest and most challenging part.
All the operations are O(1), so it'd be a solution, but it doesn't work. You thought it works because the structure's Get() modifies the structure, and your test code printed the full contents of the structure after every operation, in fact performing a O
Code:SpecialArray<int> test = new SpecialArray<int> (0, 4); test.Set (0, 999); test.SetAll (14); test.SetAll (16); test.Print (); // 999, 16, 16, 16 - oops.
When you get the idea for the correct solution, you won't need an implementation to know it works. I warmly recommend working it out on paper. I never manage to think about structures correctly otherwise.
Dang it! I thought I had it
Thanks for taking a look at my code though.
Ok I thought about it some more and I think I have another solution (not that the last one was a solution
).It's just a slight variation on what upandaway originally proposed. Instead of the flag you have a timestamp and each value in the array also has a timestamp.
- Start the global timestamp at 0
- If you set a value in the array, you set its timestamp to the same value as the global timestamp's value.
- If you set the global value you also incremement the global timestamp by one.
- To read, if the timestamps match you use the local value, if not you use the global value as you can tell that the global value is newer.
The only problem is if your timestamp is a 64 bit unsigned int you can only do the set all values thing 18 quintillion times before you run out of timestamps. But it's not bad since the more space you use for the timestamp you acquire exponentially more of them. 2^128 is a very, very big number.
- Start the global timestamp at 0
- If you set a value in the array, you set its timestamp to the same value as the global timestamp's value.
- If you set the global value you also incremement the global timestamp by one.
- To read, if the timestamps match you use the local value, if not you use the global value as you can tell that the global value is newer.
The only problem is if your timestamp is a 64 bit unsigned int you can only do the set all values thing 18 quintillion times before you run out of timestamps. But it's not bad since the more space you use for the timestamp you acquire exponentially more of them. 2^128 is a very, very big number.
That's what chainsawkitten proposed earlier (in a now edited post), and I responded:
http://www.neogaf.com/forum/showpost.php?p=170046422&postcount=12927
It's actually a good idea, reasonable and would work in practically all circumstances, but theoretically doesn't satisfy the conditions unless you were to figure out some way to handle the overflow situation in O(1).
Hmm I'm tempted to read the hint now but I'll think about it some more first.
I can do that by itself but my solution does not lend itself to the second as it relies on propogating information through a tree.
So there must be another solution. Very slight additional hint:I can do that by itself but my solution does not lend itself to the second as it relies on propogating information through a tree.
There's only one type of data structure that has any hope of (later) achieving the second part with arbitrary data, therefore the solution to the first part must be based on those data structures.
Thanks!
Also, is there a reason I can't alt-tab to minimized windows? They show up in the alt-tab popup screen, but they won't open. It's frustrating having to mouse over to reveal the dock, just to open it back up. I don't think I've ever encountered this behavior in a Linux distro or Windows.
To be effective with OS X' UI, you have to have substantially different habits than in Windows (but I find it's somewhat nicer when you do develop those habits). OS X' minimize does not interact well with the rest of the windowing system. My suggestion for a power user is to never use it; it might be okay for casual users who don't use the more powerful windowing features. The thing to do is to leave everything open and visible (apps and windows) and then just switch to the one you want using cmd-tab, cmd-' and Mission Control features. Hide (cmd-H) is nice for putting an entire app out of sight and it doesn't take the app off the cmd-tab stack. In Mission Control preference panel -> Hot Corners, assign "Mission Control", "Application Windows" and "Desktop" to three corners of the screen that are easiest to swing the mouse at. This lets you do combos like cmd-tab into an app while throwing the mouse cursor into a corner to get all that app's windows to pick from. You can also drag files while activating the hot corners or cmd-tabbing, which is all kinds of useful.
Like minimize, I also essentially never use the Dock, and hide it to one side of the screen.
That would assume I have Windows habits haha. I haven't used it in years but I remember that this behavior didn't exist. I'm gonna try out these new tricks, thanks!
How about
storing the data in a hash map, keys being the indices. Also store a "default" value, which will be used if a key is looked up that doesn't exist. This way, the reset is simply to set the map to an empty map and update the default value.
So it's something like this in practice:
Code:
a = [1, 7, 2, 4, 1] // some data storage/structure
// 1-index ordering
a.get(3) // returns 2
a.reset(5) // a should be perceived as [5, 5, 5, 5, 5]
a.get(4) // returns 5If that's so . . . I have an idea.
Basically, I guess I was thinking like poweld, but before looking at that response.
My take: Just create a new hash map upon a reset.
My take: Just create a new hash map upon a reset.
https://gist.github.com/anonymous/adba867c0b6db00fc910
http://jsbin.com/vipuxilibu/edit?js,console
I had a similar idea as you can see, but no OThat has an O
. I think.edit: Links work.
Yes, while keeping every operation in constant time.
Sorry, but not initializing the data structure would only move the work to individual writes which would then be OIf that's so . . . I have an idea.
...
I had a similar idea as you can see, but no O
.An additional observation about hashmaps: perfect hashing is required for O(1) accesses. When the keys are indices to a virtual array, perfect hashing is trivial to accomplish (identity function!), but then your "hashmap" is actually just an array.
Wait, I just now read some other posts and I think that's the solution with the overflow problem.
This nerdsniped me hard, but I think I got it now:
http://pastebin.com/eTfWUFi1
http://pastebin.com/eTfWUFi1
Yep, that's it. Fun, right?
It's not every day that you get to use arbitrary/random data to drive program logic and get a correct result at the end.
That was what I had meant. AFAICT this solution is, in fact, constant time. The only work to be done during the reset is
the garbage collection on the hashmap, the creation of a new one, and setting the new default, which are constant time operations.
http://pastebin.com/TjJae4nk
Yep. Was fun indeed.
I read the hints after my first iteration. I was already pretty sure that it had to be constructed in some way out of static arrays but they probably saved me from quite some sidetracking nevertheless. I think the first version (with the overflow problem) took me like 10 minutes and the second maybe about an hour.
Like I said to hateradio, in a hashmap implementation where the structure initialization is O(1), the individual writes are inevitably O
so it's still no good as a solution to the original problem. https://wiki.python.org/moin/TimeComplexity
Like I said to hateradio, in a hashmap implementation where the structure initialization is O(1), the individual writes are inevitably O
https://wiki.python.org/moin/TimeComplexity
I guess I'm looking at this more from an engineering perspective than a CS one. It is reasonable to say that your chosen hashing algorithm will not place all elements into the same index of the backing array. The solution I proposed is concise and eliminates the fixed length hindrance.
But of course, this was a CS thought exercise, and a fairly neat one at that, so my solution is flawed from that perspective.
Thanks for sharing, gave me something to think about on a rainy Sunday.
Like I said to hateradio, in a hashmap implementation where the structure initialization is O(1), the individual writes are inevitably O
https://wiki.python.org/moin/TimeComplexity
I was actually going with two arrays, one for the established indexes and one for the values, but I decided that hash map was easier to implement.
The only difference was going to be a length attribute in the constructor for the fixed length.
The only difference was going to be a length attribute in the constructor for the fixed length.
Didn't know that hash maps are O
to set. I could have sworn they were O(1).