Teach me CS stuff for interviews

[benguino]

Re: Teach me CS stuff for interviews

sweet. Looks good to me.

http://programmers.stackexchange.com/questions/77529/why-isnt-radix-sort-used-more-often

Interestingly enough, Quicksort runs in O(n^2). Big-oh doesn't always tell the whole story.

I was just going to edit my post stating that quicksort was O(n^2) haha. Although, I didn't make any conjecture saying that quicksort was the best comparative based algorithm so its not like I lied :P although, quicksort does have an average run time of O(nlogn) (I forgot which Greek letter denotes average time, my bad). And I believe the coefficients/constants are also decent if you consider f(x) where f(x) "=" O(g(x)). Also, I'd say each of the popular sorting algorithms has its pros and cons compared to others, you can only say which one is best depending on the situation imho (ex: merge sort is simple and elegant but uses up a lot more space)

[benguino]

Re: Teach me CS stuff for interviews

Also, simply memorizing the time efficiencies of common algorithms may not be good enough, you should be able to look at the code yourself and do some analysis to determine the Big-O yourself. Your interviewer may hand you some code and ask you what the worst case time efficiency is.

These are from a simple review quiz I had on my first day of class. If you can do these you should be fine.

Find the Big-O of the following functions / code fragments

static long Fibonacci(int n) {
    if (n==1||n==2) return 1;
    return Fibonacci(n-2)+Fibonacci(n-1);
}

O(2^n)

for (int i=0,j=0; i<n; i++)
    for (double d=1; d<n; d*=2)
        j++;

O(n*logn)

int[] a=new int[n];
for (int i=4;i<n;i++) {
    for (int j=i-3,sum=a[i-4];j<=i;j++)
        sum+=a[j];
}

O(n)

private static long gcd(long n,long r) {
    if (r==0) return n;
    return gcd(r,n%r);
}

O(log(n))

[Reincarnate]

Re: Teach me CS stuff for interviews

static long Fibonacci(int n) {
    if (n==1||n==2) return 1;
    return Fibonacci(n-2)+Fibonacci(n-1);
}

Without memoization, I'd say O(2^n). I know there's something called the Master Theorem that can be used for linear recurrences but I haven't learned it yet.

With memoization, O(n)

for (int i=0,j=0; i<n; i++)
    for (double d=1; d<n; d*=2)
        j++;

O(n log n)

int[] a=new int[n];
for (int i=4;i<n;i++) {
    for (int j=i-3,sum=a[i-4];j<=i;j++)
        sum+=a[j];
}

what the fuck this code lol
uhh, O((n-4)*4) = O(4n-16) = O(4n) = O(n)?

private static long gcd(long n,long r) {
    if (r==0) return n;
    return gcd(r,n%r);
}

mofuggin euclidean algo ftw
and yet I have no idea its runtime. hmmm.
I don't know what the runtime contribution is like for the modulus operation, which in itself can be pretty expensive IME. I'll ignore it.
Overall though I'll just say log n, feels right but I don't know how to really prove that rigorously

[benguino]

Re: Teach me CS stuff for interviews

responses in bold

static long Fibonacci(int n) {
    if (n==1||n==2) return 1;
    return Fibonacci(n-2)+Fibonacci(n-1);
}

Without memoization, I'd say O(2^n). I know there's something called the Master Theorem that can be used for linear recurrences but I haven't learned it yet.

With memoization, O(n)

Yeah, O(2^n) is good. You can kind of figure out it by noticing that for each call of the function, you have to recursively call the same function twice.

So say fib(4) took n steps to complete. If you calculate fib(5), you'd have to call fib(4) (which is n steps) and fib(3) (which is about n/2 steps considering half the work for calling fib(4) is in calling fib(3).) So total, it'll take about 3n/2 steps to complete fib(5) compared to the n steps it took for fib(4). We see that it took about 1.5 more steps to complete the algorithm when we increased the data size by 1. This is analogous to about O((1.5)^n) which we can declare 2^n to be an upper bound. (If you go in depth with the fib(n) algorithm, you'll find that a tight bound is O((the golden ratio)^n) or about O(1.618^n) but this takes a lot more analysis to derive.)

for (int i=0,j=0; i<n; i++)
    for (double d=1; d<n; d*=2)
        j++;

O(n log n)

yup

int[] a=new int[n];
for (int i=4;i<n;i++) {
    for (int j=i-3,sum=a[i-4];j<=i;j++)
        sum+=a[j];
}

what the fuck this code lol
uhh, O((n-4)*4) = O(4n-16) = O(4n) = O(n)?

it's ok, that's what I thought when I saw that code too lmfao. Analysis is good though :)

private static long gcd(long n,long r) {
    if (r==0) return n;
    return gcd(r,n%r);
}

mofuggin euclidean algo ftw
and yet I have no idea its runtime. hmmm.
I don't know what the runtime contribution is like for the modulus operation, which in itself can be pretty expensive IME. I'll ignore it.
Overall though I'll just say log n, feels right but I don't know how to really prove that rigorously

This one is a bit tricky. For the sake of the quiz, I believe that is was assumed that % ran in constant time. Anyways, you can kinda derive this from the division algorithm. The division algorithm states that for any two numbers, a and b, there exists a unique q and r such that a = bq+r where 0<=r<b. Say a>b but b is at least one half of a. Then b can only go into a once and your remainder with be a = b*1+r -> r=a-b < a-(1/2)a = 1/2a so r will be less than (1/2)a if b is greater than 1/2 of a. Consider the case where b is less than 1/2 of a, well, r can only have values up to b so r will still be less than (1/2)a. You can then conclude that your remainder will always at most be (1/2)a. Thus you can kinda see how you are at least "halving" your work with each step of the recursion.

That was a sloppy, half-ass proof that I just came up with off the top of my head (I'm hoping I didn't slip up with some assumption I shouldn't have made.) There's a
more rigorous proof I can find in one of my textbooks but it's a bit confusing and convoluted.

Edit: mofuggin Euclidean algorithm ftw \o/

EDIT2:

ok, I found what I was looking for, for that gcd one.

So, by Euclidiean algorithm, you follow the procedure to find your gcd of (a,b): (assume a>b>0)

a = b*q_1+r_1, 0<r_1<|b|
b = r_1*q_2+r_2, 0<r_2<r_1
r_1 = r_2*q_3+r_3, 0<r_3<r_2
...
r_(n-2) = r_(n-1)*q_n+r_n, 0< r_n < r_(n-1)
r_(n-1) = r_n*q_(n+1), r_n = gcd(a,b)

It's obvious that the above process takes about n steps if you take each line as a step (or n+/- 1 or 2 or something, but for the sake of big-O, we can just say n for simplification.)

Note for the above process, q_i >= 1 for all i. Also, q_(n+1) >= 2 because r_n < r_(n-1). If q_(n+1) = 1, then that would imply that r_n = r_(n-1) which we can't let happen. We already established that all q_i >=1 so q_(n+1) can't be equal either. So it must be at least 2. From that we have the following:

r_(n-1) >= 2*r_n >= 2 = f_3 (the 3rd Fibonacci number)
r_(n-2) >= r_(n-1)+r_n >= (2)+(1) >= 3 = f_4
...
r_1 >= r_2+r_3 >= f_n+f_(n-1) = f_(n+1)
b >= r_1+r_2 >= f_(n+1)+f_n = f_(n+2)

So we have that b >= f_(n+2). If you know some of your properties of Fibonacci numbers, you'll find that:
f_n > [(1+sqrt(5))/2]^(n-2) (this would be a whole other proof to show this which I don't feel like going through atm >.<)

Therefore b > [(1+sqrt(5))/2]^(n-2).

You do some fancy manipulation and change of base crap and you end up with n < 5*log(b) (log is base 10)

Since n is the number of steps, we have that the big O is O(5*log(b))

EDIT3: The above proof is known as Lame's Theorem (with an accent mark over the e)

[Reincarnate]

Re: Teach me CS stuff for interviews

I probably would have failed that gcd question had I been asked in a live interview. I would have said log n just because it "felt that way" to me based on my experience, and how modular arithmetic generally cuts things down hardcore, but I think I would have screwed up trying to prove it.

I think I could only do it by talking about it in steps of 2, to go through a full cycle.

So if I am talking about gcd(a,b), after the first step I call gcd(b, a%b), and then once again, so I am really talking about the transformation from

a and b
to
b and a%b
to
a%b and b % (a%b)


So in other words, analyzing the effect of a, b to a%b, b % (a%b)

We know the modulus operation n % m = r is the same as n = mk + r

so a%b = R is the same as a = bK + R
R = a - bK
then b % (a%b) = r is b = (a%b)k + r = (a-bK)k + r
r = b - (a-bK)k = b - ak + bKk = b + bKk - ak = b(1 + Kk) - ak
Now let's say this isn't a trivial case, so K and k are at least 1 each
r = b(1+1) - a
r = 2b-a
a+r = 2b
b = (a+r)/2

and so around this point I would start braining myself with a car battery trying to make the argument that after two iterations of the GCD algorithm, b is of order magnitude of half of what a was or something, and therefore overall it's log a time or something. I have no idea if that math even checks out

[benguino]

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

[Reincarnate]

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

[benguino]

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

[Reincarnate]

Re: Teach me CS stuff for interviews

my OOP-fu is weak

I know the basics but lack exp

[dAnceguy117]

Re: Teach me CS stuff for interviews

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

lol'd

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.

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]

Re: Teach me CS stuff for interviews

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]

Re: Teach me CS stuff for interviews

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]

Re: Teach me CS stuff for interviews

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]

Re: Teach me CS stuff for interviews

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]

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