Kodr

Kodr

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

›Problems: Dynamic Programming

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

Magic Index

A magic index in an array A[0... n-1] is defined to be an index such that A[i] = i. Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.

input = {-40, -20, -1, 1, 2, 3, 5, 7, 9, 12, 13};
output = 7; // as the index in position 7, is 7.

👉 Link here to the repo to solve the problem

imagen

👌 Tips

Start with a brute force algorithm.

Your brute force algorithm probably ran in O(N) time. If you're trying to beat that runtime, what runtime do you think you will get to? What sorts of algorithms have that runtime?

Can you solve the problem in O(log N)?

Binary Search has a runtime of O(Log N)

Given a specific index and value, can you identify if the magic index would be before or after it?

👊 Brute Force Solution

This algorithm is really easy to solve in a O(N) fashion, no shame in starting here, but we can do much better.

int iterativeSolution(int[] n) {
    for (int i = 0; i < n.length; i++) {
        if (n[i] == i) return i;
    }
    return -1;
}

👊 Better Solution

If we want to solve this problem in Log(N), we need to implement something similar to a binary search. This is plausible, as we know the array is sorted from smaller to bigger.

First we need to get the middle value of the array, if this value is bigger than its index, that means that the value we are after must be in the right. Same applies for the opposite direction.

Then we can recursively calculate with the other half of the array, all we need is the start, and the ending indexes.

Take the array from the example:

int[] numbers = new int[]{-40, -20, -1, 1, 2, 3, 5, 7, 9, 12, 13};
// start = 0
// end = 10
// middleIndex = 5
// value = 3
// we need to move right, as the index is bigger


// start = 6
// end = 10
// middleIndex = 8
// value = 9
// we need to move left, as the index is smaller

// start = 6
// end = 9
// middleIndex = 7
// value = 7
// We've found the magic index! :)

The code would look like this:

public int recursively(int[] n) {
    return recursively(n, 0, n.length -1);
}

private int recursively(int[] array, int start, int end) {
    if (end < start) return  -1;

    int mid = (start + end) / 2;

    if (mid == array[mid]) return mid;
    else if (array[mid] > mid) {
        return recursively(array, start, mid - 1); // we need to go left
    }
    else  return recursively(array, mid + 1, end); // we need to go right
}

Question borrowed from “Cracking the coding interview”

Last updated on 3/26/2020
← Triple Step(Hard) Towers Of Hanoi →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Brute Force Solution
  • 👊 Better Solution
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr