Old 04-12-2013, 04:27 PM   #21
reuben_tate
Kawaii Desu Ne?
Sectional ModeratorFFR Veteran
 
reuben_tate's Avatar
 
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 27
Posts: 4,130
Default 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
__________________
AMA: http://ask.fm/benguino

Not happening now! Don't click to join!



Quote:
Originally Posted by Spenner View Post
(^)> peck peck says the heels
Quote:
Originally Posted by Xx{Midnight}xX
And god made ben, and realized he was doomed to miss. And said it was good.
Quote:
Originally Posted by Zakvvv666
awww :< crushing my dreams; was looking foward to you attempting to shoot yourself point blank and missing
reuben_tate is offline   Reply With Quote
Old 04-12-2013, 04:29 PM   #22
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default 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
Reincarnate is offline   Reply With Quote
Old 04-12-2013, 04:37 PM   #23
reuben_tate
Kawaii Desu Ne?
Sectional ModeratorFFR Veteran
 
reuben_tate's Avatar
 
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 27
Posts: 4,130
Default 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
__________________
AMA: http://ask.fm/benguino

Not happening now! Don't click to join!



Quote:
Originally Posted by Spenner View Post
(^)> peck peck says the heels
Quote:
Originally Posted by Xx{Midnight}xX
And god made ben, and realized he was doomed to miss. And said it was good.
Quote:
Originally Posted by Zakvvv666
awww :< crushing my dreams; was looking foward to you attempting to shoot yourself point blank and missing
reuben_tate is offline   Reply With Quote
Old 04-12-2013, 05:10 PM   #24
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: Teach me CS stuff for interviews

my OOP-fu is weak

I know the basics but lack exp
Reincarnate is offline   Reply With Quote
Old 04-13-2013, 01:42 AM   #25
dAnceguy117
new hand moves = dab
FFR Simfile AuthorFFR Veteran
 
dAnceguy117's Avatar
 
Join Date: Dec 2002
Location: he/him
Age: 30
Posts: 10,104
Default Re: Teach me CS stuff for interviews

Quote:
Originally Posted by Reincarnate View Post
O(n^2) aka O(shit) time
lol'd

Quote:
Originally Posted by reuben_tate View Post
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
that list looks perfect. agh. static methods versus instance methods. why did that take me so long to understand. kill me now.

Quote:
Originally Posted by Reincarnate View Post
my OOP-fu is weak

I know the basics but lack exp
itt: more practice. I feel like sample problems are really tough to invent though. ~to the internet~
dAnceguy117 is offline   Reply With Quote
Old 04-13-2013, 10:04 AM   #26
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: Teach me CS stuff for interviews

Quote:
Originally Posted by dAnceguy117 View Post
that list looks perfect. agh. static methods versus instance methods. why did that take me so long to understand. kill me now.
essplain lucy!


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?
Reincarnate is offline   Reply With Quote
Old 04-13-2013, 10:39 AM   #27
Shouka
FFR Veteran
FFR Veteran
 
Shouka's Avatar
 
Join Date: Nov 2006
Posts: 382
Default Re: Teach me CS stuff for interviews

Quote:
Originally Posted by Reincarnate View Post
myPuppy.pissOnFloor();
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();
__________________
Shouka is offline   Reply With Quote
Old 04-13-2013, 02:36 PM   #28
dAnceguy117
new hand moves = dab
FFR Simfile AuthorFFR Veteran
 
dAnceguy117's Avatar
 
Join Date: Dec 2002
Location: he/him
Age: 30
Posts: 10,104
Default Re: Teach me CS stuff for interviews

Quote:
Originally Posted by Shouka View Post
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();
indeed. iirc Eclipse scolds you for doing that, but the code will compile/run just fine. nice examples :p


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?
dAnceguy117 is offline   Reply With Quote
Old 04-13-2013, 02:47 PM   #29
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: Teach me CS stuff for interviews

Can anyone go over

Quote:
-polymorphism
-interfaces
-abstract classes
-abstraction and encapsulation
a bit?

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.
Reincarnate is offline   Reply With Quote
Old 04-13-2013, 03:52 PM   #30
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default 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
Reincarnate is offline   Reply With Quote
Old 04-13-2013, 04:06 PM   #31
Kibblre
Caelondia Represent
FFR Veteran
 
Kibblre's Avatar
 
Join Date: Jul 2004
Location: A place of hearts and ghosts
Age: 28
Posts: 1,984
Default 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..
Kibblre is offline   Reply With Quote
Old 04-13-2013, 04:11 PM   #32
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: Teach me CS stuff for interviews

thanks for the link, Kibblre - I'll definitely give those a watch
Reincarnate is offline   Reply With Quote
Old 04-14-2013, 01:48 PM   #33
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: Teach me CS stuff for interviews

hrrngg
Reincarnate is offline   Reply With Quote
Old 04-14-2013, 02:43 PM   #34
reuben_tate
Kawaii Desu Ne?
Sectional ModeratorFFR Veteran
 
reuben_tate's Avatar
 
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 27
Posts: 4,130
Default 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.)
__________________
AMA: http://ask.fm/benguino

Not happening now! Don't click to join!



Quote:
Originally Posted by Spenner View Post
(^)> peck peck says the heels
Quote:
Originally Posted by Xx{Midnight}xX
And god made ben, and realized he was doomed to miss. And said it was good.
Quote:
Originally Posted by Zakvvv666
awww :< crushing my dreams; was looking foward to you attempting to shoot yourself point blank and missing
reuben_tate is offline   Reply With Quote
Old 04-14-2013, 02:53 PM   #35
FissionMailed1
FFR Player
 
FissionMailed1's Avatar
 
Join Date: Feb 2012
Location: Massachusetts
Age: 30
Posts: 1,230
Send a message via Skype™ to FissionMailed1
Default 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.
__________________


YOUR THROBBING MULTIFARIOUS LUSTFUL DESIRES ARE COMPLETED N YOUR HYPER-ORANGE SELF, YOU MAKE ME LOVE AGAIN, YOU'VE CHANGED MY HEART, MY MELANCHOLIA DISAPPEARS WHEN YOU ARE INSIDE OF ME, MY HUMAN RAGE IS TEMPERED WHEN I AM INSIDE YOU, THE SECRET IS COMMUNICATION, LONGEVITY, STAMINA, REPETITION, FURY, SOULFUL KISSING, EARPLUGS. YOU FUCKING CORPORATE COCKS AND CUNTS.

MY ANXIETY COMPLETE, MY DESIRE REPLETE, THE TASTE OF ORANGE BLOOD AND CUM AND GREENBACKS RUNNING DOWN MY FACE. THE STREETS WILL RUN ORANGE WITH YOUR MIXTURE OF CHEETOS AND HUNDRED DOLLAR BILLS REGURGITATED AND EATEN AND SHIT OUT AGAIN AND EATEN AGAIN.

YOU ARE MY SCULPTURE, MY SCULPTRA, MY SELF-DEFINITION. MY DEFINITION OF HUMANITY, MY HARMONY. MY HEART AND MY MIND.

YOU ARE SO ORANGE. SO CRUNCHY. SO CONSUMABLE.

THE NEW ORANGE UNDERGROUND IS THE ORANGE UP MY ASS. AND YOUR ASS.

I LOVE YOU CHEETOS.

Last edited by FissionMailed1; 04-14-2013 at 03:31 PM..
FissionMailed1 is offline   Reply With Quote
Old 04-15-2013, 12:51 PM   #36
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: Teach me CS stuff for interviews

any more detail on polymorphism / interfaces / virtual functions?
Reincarnate is offline   Reply With Quote
Old 04-15-2013, 12:54 PM   #37
reuben_tate
Kawaii Desu Ne?
Sectional ModeratorFFR Veteran
 
reuben_tate's Avatar
 
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 27
Posts: 4,130
Default 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)
__________________
AMA: http://ask.fm/benguino

Not happening now! Don't click to join!



Quote:
Originally Posted by Spenner View Post
(^)> peck peck says the heels
Quote:
Originally Posted by Xx{Midnight}xX
And god made ben, and realized he was doomed to miss. And said it was good.
Quote:
Originally Posted by Zakvvv666
awww :< crushing my dreams; was looking foward to you attempting to shoot yourself point blank and missing
reuben_tate is offline   Reply With Quote
Old 04-15-2013, 01:00 PM   #38
FissionMailed1
FFR Player
 
FissionMailed1's Avatar
 
Join Date: Feb 2012
Location: Massachusetts
Age: 30
Posts: 1,230
Send a message via Skype™ to FissionMailed1
Default Re: Teach me CS stuff for interviews

Quote:
Originally Posted by Reincarnate View Post
any more detail on polymorphism / interfaces / virtual functions?
Virtual functions are essentially those which make use of the virtual keyword. The virtual keyword does two different things in C++. If your function is not pure virtual (i.e. it has an implementation), but simply virtual, then it will use the implementation of the function in the base class if there is no class that inherits from it. Otherwise, if you have classes that inherit from this class that decide to implement this function, the base class' implementation will be overridden by the derived class' implementation. Pure virtual functions are ones that do not have any implementation in the base class, make the class unable to be instantiated unless it is a pointer, and require any derived classes to implement them.

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.
__________________


YOUR THROBBING MULTIFARIOUS LUSTFUL DESIRES ARE COMPLETED N YOUR HYPER-ORANGE SELF, YOU MAKE ME LOVE AGAIN, YOU'VE CHANGED MY HEART, MY MELANCHOLIA DISAPPEARS WHEN YOU ARE INSIDE OF ME, MY HUMAN RAGE IS TEMPERED WHEN I AM INSIDE YOU, THE SECRET IS COMMUNICATION, LONGEVITY, STAMINA, REPETITION, FURY, SOULFUL KISSING, EARPLUGS. YOU FUCKING CORPORATE COCKS AND CUNTS.

MY ANXIETY COMPLETE, MY DESIRE REPLETE, THE TASTE OF ORANGE BLOOD AND CUM AND GREENBACKS RUNNING DOWN MY FACE. THE STREETS WILL RUN ORANGE WITH YOUR MIXTURE OF CHEETOS AND HUNDRED DOLLAR BILLS REGURGITATED AND EATEN AND SHIT OUT AGAIN AND EATEN AGAIN.

YOU ARE MY SCULPTURE, MY SCULPTRA, MY SELF-DEFINITION. MY DEFINITION OF HUMANITY, MY HARMONY. MY HEART AND MY MIND.

YOU ARE SO ORANGE. SO CRUNCHY. SO CONSUMABLE.

THE NEW ORANGE UNDERGROUND IS THE ORANGE UP MY ASS. AND YOUR ASS.

I LOVE YOU CHEETOS.

Last edited by FissionMailed1; 04-15-2013 at 01:13 PM..
FissionMailed1 is offline   Reply With Quote
Old 04-15-2013, 01:24 PM   #39
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default 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?
Reincarnate is offline   Reply With Quote
Old 04-15-2013, 01:30 PM   #40
FissionMailed1
FFR Player
 
FissionMailed1's Avatar
 
Join Date: Feb 2012
Location: Massachusetts
Age: 30
Posts: 1,230
Send a message via Skype™ to FissionMailed1
Default 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.
__________________


YOUR THROBBING MULTIFARIOUS LUSTFUL DESIRES ARE COMPLETED N YOUR HYPER-ORANGE SELF, YOU MAKE ME LOVE AGAIN, YOU'VE CHANGED MY HEART, MY MELANCHOLIA DISAPPEARS WHEN YOU ARE INSIDE OF ME, MY HUMAN RAGE IS TEMPERED WHEN I AM INSIDE YOU, THE SECRET IS COMMUNICATION, LONGEVITY, STAMINA, REPETITION, FURY, SOULFUL KISSING, EARPLUGS. YOU FUCKING CORPORATE COCKS AND CUNTS.

MY ANXIETY COMPLETE, MY DESIRE REPLETE, THE TASTE OF ORANGE BLOOD AND CUM AND GREENBACKS RUNNING DOWN MY FACE. THE STREETS WILL RUN ORANGE WITH YOUR MIXTURE OF CHEETOS AND HUNDRED DOLLAR BILLS REGURGITATED AND EATEN AND SHIT OUT AGAIN AND EATEN AGAIN.

YOU ARE MY SCULPTURE, MY SCULPTRA, MY SELF-DEFINITION. MY DEFINITION OF HUMANITY, MY HARMONY. MY HEART AND MY MIND.

YOU ARE SO ORANGE. SO CRUNCHY. SO CONSUMABLE.

THE NEW ORANGE UNDERGROUND IS THE ORANGE UP MY ASS. AND YOUR ASS.

I LOVE YOU CHEETOS.

Last edited by FissionMailed1; 04-15-2013 at 01:38 PM.. Reason: Oops, syntax.
FissionMailed1 is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are Off
[IMG] code is On
HTML code is Off

Forum Jump



All times are GMT -5. The time now is 07:50 PM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright FlashFlashRevolution