4

I have been working on RTOS and Linux driver development for quite some time. Now I am interviewing at semiconductor companies and failing to answer questions about algorithms on strings, and time and space complexity. I have not studied discrete maths and algorithms during my as I have an electronics background.

How can I overcome this gap?

jammulak
  • 65
  • 4
  • 1
    There is a great introductory definition for time complexities in SO only http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o and http://stackoverflow.com/questions/107165/big-o-for-eight-year-olds – Rozuur Oct 19 '10 at 07:03

4 Answers4

5

Start with something simple like: Algorithms in a Nutshell (good starting point for interview like questions)

alt text

Or Algorithms For Interviews When you feel you know the above book, then you can think of diving into introduction to Algorithms.

zengr
  • 38,346
  • 37
  • 130
  • 192
  • Algorithms for Interviews is not a good way to get started with Algorithms and complexity. It's written for people who've had a couple lectures on this material, worked through the problems, and forgot it all a while ago. – Paul McMillan Oct 19 '10 at 07:15
  • 1
    As one of the authors of "Algorithms of For Interviews" I agree with Paul that this book is not a substitute for a textbook. But I also partially disagree. jammulak has already worked on complex software projects and AFI could be a fun way for him to teach the material to himself and get a quick interview prep. Of course (s)he may need a way to look things up on the net or in a textbook when he is stuck. – Amit Prakash Nov 08 '10 at 20:38
3

You need to review most of the course material for a Data Structures and Algorithms class. In order to answer those types of interview questions, you don't generally need the material covered in Discrete Math.

If you want to take the long way around (and actually understand the topic), I recommend you actually work through the class material and listen to the lectures. Since UC Berkeley posts some of their lectures online, you can watch just such a class (with an excellent instructor) here:

http://webcast.berkeley.edu/course_details.php?seriesid=1906978343

Pay particular attention to the lectures on Big O notation, and the sorting and searching algorithms. Those tend to be the bits that people ask about for job interviews.

If you can't be bothered to actually spend the 30 hours watching the lectures and many more working through the problems, you should at least consult the book that course uses:

Goodrich and Tamassia's Data Structures and Algorithms in Java

Paul McMillan
  • 19,693
  • 9
  • 57
  • 71
2

Introduction to Algorithms is a great algorithms book (and also happens to be listed 6th on the great influential book question)

Community
  • 1
  • 1
David Brown
  • 13,336
  • 4
  • 38
  • 55
1

I would suggest you Introduction to Algorithms(by CLRS) and Algorithm design manual for algorithms and complexity(by steven skienna) for understanding the Algorithms and complexity.Other than that there are quite a few good tutorials on algorithms and complexity at top coder ( site : topcoder.com/tc ) , you can check them out too.

deovrat singh
  • 1,220
  • 2
  • 17
  • 33