Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Optimisation Techniques

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

DIY Optimisation

If most people ask them to find an element in an ordered array - they are quite likely to implement a O(N) algorithm that will basically search for each element in the array iteratively, until it finds it and returns it.

Now, if a person asks you to find a student's exam in a pile of tests that are arranged alphabetically, quite likely by intuition they would apply a binary search algorithm O(Log N) in which you will start looking more or less for the medium, and will continue to pivot to the left or right of that medium - and will continue to split that half into another half until it eventually reaches the exam it needs.

For this reason it is very important to consider our intuition when designing an algorithm. Above all it is important to draw several examples on paper and try to solve it in this way, rather than trying to solve it in code. Think that in most scenarios, a process that is slow for a person will surely also be slow for a computer.

imagen

Try it with this example:

If we give you 2 Strings, the first shorter than the second. Design an algorithm that finds any permutation of String (A) within the second String (B) - which is longer.

String a = “abbc”;
String b = “cbabadcbbabbcbabaabccbabc”;

Try to think for a moment how would you solve it? Most programmers would try to solve it in code first. If you are like the majority of programmers I know, you would try to generate all the permutations of String A, which takes a very bad time of O(A!), And then you would compare linearly with the pieces of String B. To give you a sense - if the String A has 14 characters - this would entail an amount greater than 87 billion permutations. If you add one more character that would be multiplied by 15.

Look at this example that teaches all the permutations of A within B.

image

When you see it drawn it is much more obvious there are easier ways to find these permutations. You need 4 characters - 1 a, 2 b, 1 c. If you start from left to right you will notice that if you find one of these characters while traversing the String - you can see both sides to see if you also have the necessary amount of others to form a permutation.

Try this form of optimization when solving problems. Remember to use a large example and then manually solve it. If you have already solved the problem in code - try comparing it with your “manual” answer.

Last updated on 3/3/2020
← BUD optimisationLinked Lists →
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr