Some advice from when I studied for these no more than two months ago:
1. Cracking the Code - get ahold of it and read through it. It 'll give you all the topics that you should study through and some tricks that are helpful in implementations. You'll still need to use other resources in order to know the topics in depth, like I don't think it goes too in depth into dynamic programming, but the book does have a large amount of questions and solutions.
2. oj.leetcode.com - This is just a website kind of like how interviewstreet was, and something around 180 problems that are interview style problems. You should be fine if you can do the almost all of the medium or easy level problems and maybe some of the hard ones. For these, I'd definitely get out a notebook and write out solutions and then throw type them up, to get a feel for how whiteboarding is going to be.
3. If you've got friends who are in the same position, actual mock interviews in person are an enormous help. I had a couple friends get together, and one of us would do one problem at a time while the rest evaluated them - basically acted like the interviewer.
With regards to timeline, I think I started preparing for my first phone interview a week early. The first couple of days were definitely slow, but with 3 days left, I studied for a couple hours each day before. For my first onsite, I found out about oj.leetcode.com about two weeks before and just did those problems almost non-stop for the two weeks leading up. Five days before the onsite, I rounded up some friends and we started doing whiteboard problems for a couple hours each day.
I guess preparation time varies by person. I did a little bit of competitive programming before this, so I would say I had a little bit of a head start. However, before this, I probably couldn't program a binary search off the top of my head, or approach dynamic programming problems, but now, I can probably handle a decent amount of algorithmimc interview problems. I can't say I'm pro, but I'm apparently good enough.
This. To be honest, I don't think it really accomplishes that much for you. For the most part, it seems like you're just making the interviewer feel awkward, and you're not really learning anything about the company. I agree with asking them about what they're working on. As a soon to be new grad, my experience is limited to only like 2 interviews, but I usually try to ask my interviewers questions pertaining to the specific project they're working on. Hopefully, you can find something about their work that interests you and ask them about it.
Aside from that, I don't think it's a good idea to look at an interview as a power struggle. It's not a you vs. them situation, but rather you're both kind of gauging if you want to work together. The first part is kind of where they determine if they want to work with you (gauging your skill) while the second part (your questions and beyond) is kind of where you determine if you want to work with them.
As far as things go, unless you're well proven, people are probably going to need to gauge your skill in some way. Don't get too nervous about the algorithmic questions. Just think of them as a type of puzzle just with much higher stakes. For some practice, if you're not familiar with this website: oj.leetcode.com.
Disclosure: I don't have much experience interviewing. That's just my take on how to look at it.
With regards to timeline, I think I started preparing for my first phone interview a week early. The first couple of days were definitely slow, but with 3 days left, I studied for a couple hours each day before. For my first onsite, I found out about oj.leetcode.com about two weeks before and just did those problems almost non-stop for the two weeks leading up. Five days before the onsite, I rounded up some friends and we started doing whiteboard problems for a couple hours each day.
I guess preparation time varies by person. I did a little bit of competitive programming before this, so I would say I had a little bit of a head start. However, before this, I probably couldn't program a binary search off the top of my head, or approach dynamic programming problems, but now, I can probably handle a decent amount of algorithmimc interview problems. I can't say I'm pro, but I'm apparently good enough.