Teach me CS stuff for interviews

[reuben_tate]

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

[Reincarnate]

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

[reuben_tate]

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

[Reincarnate]

my OOP-fu is weak

I know the basics but lack exp

[dAnceguy117]

Originally Posted by Reincarnate

O(n^2) aka O(shit) time

lol'd

Originally Posted by reuben_tate

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.

Originally Posted by Reincarnate

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~

[Reincarnate]

Originally Posted by dAnceguy117

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?

[Shouka]

Originally Posted by Reincarnate

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();

[dAnceguy117]

Originally Posted by Shouka

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?

[Reincarnate]

Can anyone go over

-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]

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

[Kibblre]

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.

[Reincarnate]

thanks for the link, Kibblre - I'll definitely give those a watch

[Reincarnate]

hrrngg

[reuben_tate]

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

[FissionMailed1]

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.

[Reincarnate]

any more detail on polymorphism / interfaces / virtual functions?

[reuben_tate]

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)

[FissionMailed1]

Originally Posted by Reincarnate

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.

[Reincarnate]

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?

[FissionMailed1]

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.