Teach me CS stuff for interviews

[Reincarnate]

So I may be interviewing at a place to make a jump to the realm of CS/analytics type stuff, but I also suck at CS interviews because I haven't ever bothered to use stuff like suffix trees / implementing my own linked lists / hashtables / basic sorts / etc. I pretty much just do what I need the program to do and look stuff up if I don't know it.

Sooo, any advice would be welcome. What sort of shit should I know how to do cold / can you explain the basics in a simple way / offer good resources / etc?

[dAnceguy117]

Re: Teach me CS stuff for interviews

disclaimer: I'm not actually a CS major

can you explain the basics in a simple way

I'd like to give it a shot. Any topics in particular? Here, I'll start off with something you listed.

A hash table stores data. More specifically, a hash table uses a hash function to map a key to a value. Giving a key to the function will always produce the same value. Thus, if we store each key at its proper location (value) in the table, then we can look stuff up in the table really fast.

Given a key to store, a hash function produces some place to stick it in (ha). A good hash function gives each key as unique a value as possible, because collisions suck. A hash collision occurs when more than one key maps to a single value.

We have to deal with collisions somehow. Replacing the old key would be dumb, because we're storing these values so we can look them up later. A better way to deal with collisions is probing (ha).

Linear probing checks slot S, then slot S+1, then slot S+2... until there's an empty spot. The performance of linear probing would be terribad with a weak hash function; if a bunch of keys hash to the same value, then we end up checking a lot of spots before finding an open one.

Quadratic probing checks slot S, then S+1, then S+4, then S+9, then S+16... until there's an empty spot. Pretty dope. The performance is extra dope if we use a prime number for the table size and grow the table if it becomes half full. That's because, uh, wikipedia says so.

Another alternative for handling collisions is "separate chaining hashing." That's a ridiculous name for such a simple concept. Upon a collision, add the new key to the list for that value. So if keys 'A' and 'B' both mapped to the value 37, then the lookup for value 37 will give us A -> B. Linked lists can be used here. Again, performance degrades if a bunch of keys map to the same value.

What sort of shit should I know how to do cold

Hearsay from professors and other students:

- reversing a linked list
- choosing and implementing a sorting algorithm (apparently Quicksort reigns supreme)

The types of questions would largely depend on where you're applying and what they're looking for, I would think.

offer good resources

Someone in my class posted this link, but I hadn't bothered to check the site out until now. (Stupid me.) Looks excellent.

http://teachingtree.co/

[Reincarnate]

Re: Teach me CS stuff for interviews

I'm not even sure what I should be studying -- I just figure stuff like home-rolled linklists, hashtables, suffix trees, SVL trees, binary search trees, red/black trees, insertion/selection/merge/bubble/shell/heap/quick/radix sort and their runtimes blahblah, graph theory, stacks and queues, priority queues, dijkstra/A*, breadth and depth-first search, blahblahblah I have no clue honestly. I'm just listing off a bunch of stuff I don't really know how to do from scratch without looking it up to see the general idea.

Basically I suck at the basics but I am good at solving problems / getting stuff working well in practice when I need to.


edit: Looks like an interesting site -- thanks

[dAnceguy117]

Re: Teach me CS stuff for interviews

yup. Just gotta get through the interview, and then looking stuff up as needed should be fine.

The fact that you can rattle off all of those topics should be encouraging. Are you looking for a refresher on the general ideas, or would translating the ideas into code be the bigger concern?


edit: leonid posted. /thread. mega helpful

[leonid]

Re: Teach me CS stuff for interviews

Read Introduction to Algorithms

You should know what data structures to use for certain problems right away, and the efficiencies of them in Big-O notation
Master basic sorting algorithms; know the efficiencies for best, average, and worst cases in Big-O

You should be able to write simple codes on a whiteboard
Know how to code in C (or C++), JAVA, and Python

Learn some OOP; Know how to plot starter classes to solve complex problems. Learn about inheritance, encapsulation etc etc

Read aloud anything that goes through your mind while solving a problem. If you are on the right track, interviewer will mark that positively. If you aren't, interviewer might add subtle hints to help you out

If in doubt, shout "HASH TABLES" and you will probably be right



If you have mentioned your previous works on your resume, interviewer might ask you about them.. Be prepared to briefly talk about it. If those are too old for you to be recalled, just get rid of them (interviewers hate long-ass resumes i.e. more than two pages)

[Wayward Vagabond]

Re: Teach me CS stuff for interviews

Why would you want to know about counterstrike if you're being interviewed

[Reincarnate]

Re: Teach me CS stuff for interviews

Read Introduction to Algorithms

You should know what data structures to use for certain problems right away, and the efficiencies of them in Big-O notation
Master basic sorting algorithms; know the efficiencies for best, average, and worst cases in Big-O

You should be able to write simple codes on a whiteboard
Know how to code in C (or C++), JAVA, and Python

Learn some OOP; Know how to plot starter classes to solve complex problems. Learn about inheritance, encapsulation etc etc

Read aloud anything that goes through your mind while solving a problem. If you are on the right track, interviewer will mark that positively. If you aren't, interviewer might add subtle hints to help you out

If in doubt, shout "HASH TABLES" and you will probably be right



If you have mentioned your previous works on your resume, interviewer might ask you about them.. Be prepared to briefly talk about it. If those are too old for you to be recalled, just get rid of them (interviewers hate long-ass resumes i.e. more than two pages)

Resume less than one page

I have intro to algs (third edition, nickname is CLRS iirc?) but it's so effing verbose and 10000x longer than it needs to be. Having a hard time figuring out how to study from it. Feels like it can be condensed to maybe 100 pages max.

Ask some random questions (tomorrow or sth) maybe, and I'll try to answer without using external sources

[Reincarnate]

Re: Teach me CS stuff for interviews

anyone?

[Herogashix]

Re: Teach me CS stuff for interviews

Resume less than one page

[loophole]fontsize 2[/loophole]
Sorry I'm not being useful, I'm not a CS major.

[dAnceguy117]

Re: Teach me CS stuff for interviews

A singly linked list has integer as data in each node. Write a function to delete a node from the list given an integer as the argument. (Assume all the nodes have unique integers.)

question blatantly stolen from here

[Reincarnate]

Re: Teach me CS stuff for interviews

Yeahhhh last time I wrote linked lists was in like, high school. exactly the sort of thing I'd just look up /copy/paste/edit to my needs if I needed to use such a thing

But I'd say something like

let LinkedList be the name of the class which implements the linked list


edit (removed earlier code for being stupid)

edit2: You know what I am going to start over. god damn it.

void LinkedList::delete(int value){
    LinkedList *traverser = head;
    LinkedList *prev;

    while (traverser != NULL){
        if (traverser->getData() == value){
            if (traverser == head){
                head = traverser->next;
                delete traverser;
                return;
            }
            else{
                prev->next = traverser->next;
                delete traverser;
                return;
            }
        }
        else{
            prev = traverser;
            traverser = traverser -> next;
        }

    } //end while
    
} //end delete function

[rushyrulz]

Re: Teach me CS stuff for interviews

Here's what I did for my 'linked list from scratch' when I had to do it last year. Pretty sure it's at least 90% correct, I haven't looked it over recently or anything, this is just a copypaste lol

http://puu.sh/2yI5D

[benguino]

Re: Teach me CS stuff for interviews

One way to impress: if they ask what is the best sorting algorithm is, tell them that the best comparison based sorting algorithms run in O(n*logn) but there exists non-comparison based sorting algorithms that run in linear time (the most popular being radix sort). There's also counting sort which is also O(n) but the coefficient on n and the constant that is dropped is kinda big to the point where its only more efficient than nlogn algorithms if the data set is extremely huge. These non-comparison based algorithms were only briefly acknowledge in my cs class (our professor just let us know of their existence) so someone can correct me if my details are wrong.

[dAnceguy117]

Re: Teach me CS stuff for interviews

void LinkedList::delete(int value){
    LinkedList *traverser = head;
    LinkedList *prev;

    while (traverser != NULL){
        if (traverser->getData() == value){
            if (traverser == head){
                head = traverser->next;
                delete traverser;
                return;
            }
            else{
                prev->next = traverser->next;
                delete traverser;
                return;
            }
        }
        else{
            prev = traverser;
            traverser = traverser -> next;
        }

    } //end while
    
} //end delete function

sweet. Looks good to me.

One way to impress: if they ask what is the best sorting algorithm is, tell them that the best comparison based sorting algorithms run in O(n*logn) but there exists non-comparison based sorting algorithms that run in linear time (the most popular being radix sort). There's also counting sort which is also O(n) but the coefficient on n and the constant that is dropped is kinda big to the point where its only more efficient than nlogn algorithms if the data set is extremely huge.

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.

[Reincarnate]

Re: Teach me CS stuff for interviews

My understanding is that the right sort depends on 1. the framework, 2. the size of the data, 3. other assumptions about that data

For example if you know your list will be close to being sorted, insertion sort or bubble sort may not be a bad idea because for a sorted list, they run in O(n) time. It's just that for randomized lists they tend to run in O(n^2) aka O(shit) time for average and worst cases.

If you know your dataset is massive, then clearly you wouldn't want something that runs in O(n^2) time

Also depends on memory -- some require n extra memory, others only constant memory, so if you're under constraints there, that matters too.

Or maybe if writes are more expensive speed-wise in your framework you wouldn't use insertion sort which is moving shit around all the time. Or if comparisons are more expensive you wouldn't bother with something like selection sort.

Quicksort and radix sort I don't know too much about yet.

EDIT: danceguy: I do know (IIRC) that quicksort's n^2 runtime is worst-case. On average and best case I believe it's n log n time. The n^2 runtime is extremely rare since it'd require that all your elements are pretty much in the exact random order needed to completely mess with the recursive pivoting at each substep -- although I guess this depends on how you choose your pivot?