Cómo aprendí a dejar de preocuparme y amar la entrevista

MIs apuntes, como reconocer patrones de algoritmos (tipicos).

Algorithms and Data Structures

https://www.topcoder.com/community/competitive-programming/tutorials/how-to-find-a-solution/
Breadth First Search (BFS):

• Ask to find the fewest number of steps (or the shortest path) needed to reach a certain end point (state) from the starting one.

• Often there is given a N x M table (formed of N lines and M columns) where certain cells are passable and others are impassable, and the target of the problem is to find the shortest time/path needed to reach the end point from the start one. (mazes, maps, cities, and other similar things.)

• Pattern:

  • A table is given

  • Entity can make a step to move

  • Cost of 1 for any step

  • Find minimum steps

Flood Fill:

• A technique that uses BFS to find all reachable points. The thing that makes them different from BFS problems described above is that a minimum path/cost is not needed.
• Note that in most cases a DFS (Depth First Search) will not work for such problems due to stack overflows.

Brute Force and Backtracking:

• Try all possible cases(situations) and choose the best one, or count only those that are needed. Backtracking is just more advanced and optimized than Brute Force.

• It usually uses recursion and is applied to problems having low constraints (for example N<=20).

• Pattern:
  -You need to find all possible situations that satisfy a rule
  -The limits are very low (space/memory)

Backtracking:

• Usually problems of this kind ask you to find (similarly to Brute Force):
• Every possible configuration (subset) of items. These configurations should respect some given rules.
• The "best" configuration (subset) that respects some given rules.

Dynamic Programming:

• Besides that there should exist states and one or more ways (rules) to reach one greater state from another lower one.

• In addition, greater states should depend only upon lower states.

• What is a so-called state? It’s just a certain configuration or situation.

• Pattern:

  • N isn’t too small nor too big
  • A state depends only on lower states
  • By adding an element to the state, another bigger state is created.

Maximum Flow

• Often you have to create/define graphs with capacities based on the problem statement.

• Pattern:

  • Take a look at the constraints, they have to be appropriate for a O(N³) or O(N⁴) solution, i.e. N shouldn’t be greater than 500 in extreme cases (usually it’s less than 100).
  • There should be a graph with edges having capacities given, or you should be able to define/create it from data given in the statement.
  • You should be finding a maximum value of something.

Optimal Pair Matching:

• These problems usually have a list of items (from a set A ) for which other items (from a set B ) should be assigned under some rules, so that all (or a maximum possible number of) items from set A have to each be assigned to a certain item from set B.

Linear Programming:

• Pattern:
  • You are given collection of items having different costs/weights. There is a certain quantity of each item that must be achieved.
  • A list of sets is given. These sets are composed of some of the available items, having certain quantities of each of them. Each set has a certain cost.
  • The goal of the problem is to find an optimal combination (the cheapest one) of these sets so that the sum of quantities of each of the items they have is exactly the one needed to achieve.