# Resources for software engineers

This is a compilation of algorithms, interview questions and other resources. It is intended for students who want to become professional software engineers and a reference to professionals.

# Algorithms

## Techniques and classes of problems

(Taken from ZOJ)

• Dynamic Programming
• Greedy algorithms
• String management
• Simulation problems
• Abstract Struct Problems
• Search Problems
• Number Theory Problems
• Geometry Problems
• Tree Struct Problems
• Graph Problems
• Matching Problems
• Combination Problems
• Shortest Path Problems
• Game Theory Problems
• Maximum Flow Problems

# Software Engineering interviews

## Algorithm to solve any algorithmic problem

1. Understand the problem statement
2. Run through an example
3. Come up with the easiest solution
4. Explain the solution
5. Prove that it works
6. Is it the fastest that you can do? If not go to 3.
7. Watch-out for special cases

## Random problems

Few divide-and-conquer problems:

– nearest pair of points (2D) in O(nlogn)

– counting inversions in an array

– array shuffling

input : a1,….an,b1,…bn

output: a1,b1,….an,bn

A few dynamic programming problems by name:

– Max contiguous sum in array

– Max subset sum of non-adjacent elements in array

– longest increasing subsequence

– longest common subsequence

– shortest common supersequence

– longest oscillating subsequence (google interview question)

– longest accelerating subsequence

– longest Arithmetic Progression subsequence for unsorted array (google interview question)

– Matrix chain multiplication

– maximum value of expression consisting + and *

– minimum number of palindromic substring

– cutting stick (ACM UVA problem)

– 0/1 Knapsack

– counting ways of making a change

– Min. number of coins for a change

– 2-partitioning a set with/without repeations of items minimum sum difference

– Edit distance

– convert string to palindrome with minimum deletions /insertions

– Max. rectangle sum

– Max rectangle/square submatrix of 0 and 1

Do you know any other good algorithms resource? Leave it in the comments!