04-12-2013, 04:27 PM | #21 |
Kawaii Desu Ne?
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 30
Posts: 4,182
|
Re: Teach me CS stuff for interviews
I edited my post with a detailed argument for the big-O of the Euclid alg. Anyways, I don't think you have to worry too much about being able to give a detailed analysis like the one I posted, the interviewer would understand you are under some degree of pressure. As long as you can say the running time is about logarithmic and perhaps give a not-so-rigorous proof using some intuition and a couple examples, you should be fine :P
|
04-12-2013, 04:29 PM | #22 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: Teach me CS stuff for interviews
I think the mathy shit I am okay with (to some degree) -- PE has taught me a lot there and so I think if I had to get rigorous I could start using examples and blahblah make a better argument. I doubt I'll get asked about the gcd anyhow -- my concern is the CS stuff
|
04-12-2013, 04:37 PM | #23 |
Kawaii Desu Ne?
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 30
Posts: 4,182
|
Re: Teach me CS stuff for interviews
How comfortable are you with OOP (object-oriented programming?) I know solving the problems in PE, even the ones that are difficult, you still don't have to worry much about in terms of OOP like having classes with inheritance and stuff. When you are working on something on a larger scale, it's important to consider the structure of things and how things work together, etc.
For OOP, these are the main concepts that I can think of off the top of my head that you should have at least have some idea about. -classes -sub-classes -super classes -inheritance in general -polymorphism -interfaces -abstract classes -abstraction and encapsulation -public/private/protected/etc variables/functions/etc -static variables and functions |
04-12-2013, 05:10 PM | #24 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: Teach me CS stuff for interviews
my OOP-fu is weak
I know the basics but lack exp |
04-13-2013, 01:42 AM | #25 | |
new hand moves = dab
Join Date: Dec 2002
Location: he/they
Age: 33
Posts: 10,094
|
Re: Teach me CS stuff for interviews
lol'd
Quote:
itt: more practice. I feel like sample problems are really tough to invent though. ~to the internet~ |
|
04-13-2013, 10:04 AM | #26 | |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: Teach me CS stuff for interviews
Quote:
I just assumed instance method = some method that is localized to an object/its class, like myPuppy.pissOnFloor(); static method being something more 'global' in scope that doesn't require an underlying instantiation or w/e? |
|
04-13-2013, 10:39 AM | #27 |
FFR Veteran
Join Date: Nov 2006
Posts: 382
|
Re: Teach me CS stuff for interviews
I lol'd.
But yes you're right. Static methods can be called using the class name and do not require an actual instantiation of an object: Puppy.getNumPuppies(); Calling an instance method requires an instance of the object: myPuppy = new Puppy(); myPuppy.pissOnFloor(); Java allows you to call static methods by using an instance of the class but I think doing so is considered bad style: myPuppy = newPuppy(); myPuppy.getNumPuppies();
__________________
|
04-13-2013, 02:36 PM | #28 | |
new hand moves = dab
Join Date: Dec 2002
Location: he/they
Age: 33
Posts: 10,094
|
Re: Teach me CS stuff for interviews
Quote:
Rubix, it sounds like you learned all of these concepts well and just need a quick refresher on everything, which is awesome. when's the interview? |
|
04-13-2013, 02:47 PM | #29 | |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: Teach me CS stuff for interviews
Can anyone go over
Quote:
danceguy: No interview scheduled yet, but I just want to learn this stuff anyway so I feel less nervous going in. I only have a superficial understanding of it all. |
|
04-13-2013, 03:52 PM | #30 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: Teach me CS stuff for interviews
yeah I suck at CS. I'm not even good enough to figure out a good algorithm for part D on the google code jam
pure CS problem, you either know the right algo or you don't dynamic programming + memoization obv. not the way to go |
04-13-2013, 04:06 PM | #31 |
Caelondia Represent
Join Date: Jul 2004
Location: A place of hearts and ghosts
Age: 31
Posts: 1,984
|
Re: Teach me CS stuff for interviews
Rubix, my CS professor puts out videos all the time for us on new subjects including all the things you listed. Although it's in Java, you should be able to get something out of it in the very least. Here's the playlist: http://www.youtube.com/watch?v=LWyEN...bu2B5lvxrPuA3E . The videos start about basics of Java, but some of the videos are about topics you've asked for clarification on.
EDIT: Looked up a couple posts and you mentioned OOP. The class is literally called Object Oriented Programming. Most of the stuff he teaches us is through these videos, so you're basically taking the class I'm taking if you watch them.
__________________
Какой идиот придумал Бутерброд с дикобраза? Он хулиган и бездельник. Last edited by Kibblre; 04-13-2013 at 04:08 PM.. |
04-13-2013, 04:11 PM | #32 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: Teach me CS stuff for interviews
thanks for the link, Kibblre - I'll definitely give those a watch
|
04-14-2013, 01:48 PM | #33 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: Teach me CS stuff for interviews
hrrngg
|
04-14-2013, 02:43 PM | #34 |
Kawaii Desu Ne?
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 30
Posts: 4,182
|
Re: Teach me CS stuff for interviews
I can try to go over those last few topics later today (I'm on my phone atm and won't be on my lappy till a bit later.)
|
04-14-2013, 02:53 PM | #35 |
FFR Player
|
Re: Teach me CS stuff for interviews
These explanations will use C++. I will use method and function interchangeably.
Polymorphism: Suppose you have a base class that you have other classes inherit from. I will use a C++ snippet as an example. class Foo {}; class Bar1 : public Foo {}; class Bar2 : public Foo {}; Now, somewhere later in your program lets say you now want to declare a container of "Foo"s, as such: Foo bunch_of_Foos[100]; And then, after that, you want to now instantiate a bunch of objects in this container. This is the part that gets a little tricky. The following code segments are valid C++: bunch_of_Foos[0] = new Bar1(); bunch_of_Foos[1] = new Bar2(); Now, if you want access bunch_of_Foos[0] or bunch_of_Foos[1] anywhere in your program, your program uses a virtual table to resolve the address of the derived class. What this means is that if I were to use bunch_of_Foos[0], the type would resolve to be Bar1 because the program keeps a pointer in the virtual table to this class when you instantiated it. Why is this useful? Now lets say you want to iterate over the bunch_of_Foos container. What you could do is: for (int i = 0; i < bunch_of_Foos.size(); ++i) bunch_of_Foos[i]->doWork(); And this will work, assuming bunch_of_Foos is a pointer container and doWork() is in the base class. Now you can iterate over a bunch of different types of objects, as long as they share a common base class. Interfaces: Interfaces are classes that are not allowed to contain data or state. The purpose of interfaces is to make sure that classes that decide to implement an interface have a conformant set of functions. In C++, there is no interface construct. Interfaces only contain pure virtual functions, nothing else. To use the interface idiom in C++, you just inherit it much like you would any other class. Abstract classes: An abstract class in C++ is one that contains pure virtual functions. When you declare virtual functions inside of a class, you must have classes that inherit from it. Additionally, you can not instantiate abstract classes unless they are pointers. When you call a pure virtual function anywhere with a program, the program will look at the derived class' implementation of said pure virtual function and execute that. This lends itself well to using polymorphism, as explained above, as do interfaces. Abstraction and encapsulation: This is a very general term, so I will explain it the best I can. The main idea behind abstraction is hiding away lower level details. Suppose I have a Car class: class Car { private: void do_internal_stuff(); void do_more_internal_stuff(); void do_even_more_internal_stuff(); public: void drive(); void honk_horn(); void accelerate(); } The only thing that I need to worry about, as a driver, is being able to drive the car. I don't have to worry about the internals of the car, the drive() method and the accelerate() method will take car of all of the internals by calling do_internal_stuff(), do_more_internal_stuff() etc. The abstraction this idea of being able to drive(), honk_horn(), and accelerate(). The encapsulation is the private methods that are called as a result of calling drive(), honk_horn(), and accelerate() in order to maintain the Car object's state, but won't be called directly.
__________________
Last edited by FissionMailed1; 04-14-2013 at 03:31 PM.. |
04-15-2013, 12:51 PM | #36 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: Teach me CS stuff for interviews
any more detail on polymorphism / interfaces / virtual functions?
|
04-15-2013, 12:54 PM | #37 |
Kawaii Desu Ne?
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 30
Posts: 4,182
|
Re: Teach me CS stuff for interviews
I can give additional examples and clarification after classes today (I got class in 5 minutes so I don't have any time to type up anything right now)
|
04-15-2013, 01:00 PM | #38 | |
FFR Player
|
Re: Teach me CS stuff for interviews
Quote:
With that definition of pure virtual, interfaces should make more sense. As I explained before, interfaces only contain pure virtual functions, they do not contain any data members. Polymorphism is hard to wrap your head around at first, but I will try to give another example to explain it. Suppose you have a base class called "Animal". class Animal { public: virtual void make_sound {}; } Now suppose you have 3 more classes that inherit from animal. class Dog : public Animal { public: void make_sound {}; } class Cat : public Animal { public: void make_sound {}; } class Pig : public Animal { public: void make_sound {}; } Finally, I will create an array of 3 Animal pointers and instantiate a Dog, Cat, and Pig. Animal** animal_array = new Animal*[3]; animal_array[0] = new Dog(); animal_array[1] = new Cat(); animal_array[2] = new Pig(); And the following code segment will demonstrate polymorphism: for (int i = 0; i < 3; ++i) animal_array[i]->make_sound(); What happens here is that at run-time, your program will look at the virtual function table for your Animal class and then it will find out what the derived class types are in order to execute their implementations. In other words, your program will now cause an object of type Dog, Cat, and Pig to make a sound. The polymorphic behavior here is that instead of causing three Animal objects to make sounds, more specific types of animals make sounds instead.
__________________
Last edited by FissionMailed1; 04-15-2013 at 01:13 PM.. |
|
04-15-2013, 01:24 PM | #39 |
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,332
|
Re: Teach me CS stuff for interviews
I guess I am still a little lost.
Why bother having public: void make_sound {}; in the subclasses at all? They already inherit from Animal -- so couldn't calling make_sound just call the function from the Animal class? |
04-15-2013, 01:30 PM | #40 |
FFR Player
|
Re: Teach me CS stuff for interviews
If you just call make_sound() from the Animal class and you don't declare make_sound() in your subclasses, your program will execute Animal's make_sound() function. Sometimes this isn't the behavior you want. The make_sound() function isn't pure virtual, so I could do something like this:
Animal* animal_array_2 = new Animal[3]; animal_array_2[0] = new Dog(); animal_array_2[1] = new Cat(); animal_array_2[2] = new Pig(); for (int i = 0; i < 3; ++i) animal_array[i].make_sound(); And this code won't compile. The reason being is that you are trying to use Dog, Cat, and Pigs constructors for an Animal object, which isn't valid C++, unless animal_array_2 is a pointer array. I could, however, do this: animal_array_2[0] = new Animal(); animal_array_2[1] = new Animal(); animal_array_2[2] = new Animal(); and execute that same loop. This would be valid C++. But now, you aren't calling the subclasses make_sound() function, just Animal's.
__________________
Last edited by FissionMailed1; 04-15-2013 at 01:38 PM.. Reason: Oops, syntax. |
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
|
|