Arrays

Meeting Slides

self-check: What's the difference between normal array and resizable array? answer

First we need to know the difference between Array Resizable Array. In the interveiw problems we recommand you to use resizable array when solving array problem, they are as fast as native array, and you don't have to worry about memory management.

• C++ vector vs. array
• Java Array vs. List

Basic Operations:

• Look up by index O(1)
• Update O(1)
  • Swap O(1)
• Insert O(n)
  • Insert from the back O(1)
• Deletion O(n)
  • Delete from the back O(1)

self-check: Why is it so expensive to perform insertion and deletion?

Tricks:

Be really careful with off by one error

self-check: What's the result of the following code?

    int i, counter = 0, n = 10;
    for (i = 0; i < n; ++i) {
        ++counter;
    }
    print(counter);
    print(i);


    int j, n = 10, counter2 = n;
    for (j = n; j <= 0; --j) {
        --counter2;
    }
    print(counter2);
    print(j);

• EPI 6.16. The Sudoku Checker Problem
• EPI 6.4. Advancing Through an array

Solving a problem using constant space, when using extra storage makes the problem trival

• Marking on the input: (How to preserve the integrity of your markers?)
  • CTCI 1.8 Zero Matrix (lecture)
  • Leetcode Game of Life (hands on)
  • Leetcode 442. Find All Duplicates in an Array (lecture)
  • Leetcode 448. Find All Numbers Disappeared in an Array (hands on)
• Multiple Pointers:
  • Geeks for Geeks Segregate 0s and 1s in an array

Learn to use multiple pointers

• Geeks for Geeks Segregate 0s and 1s in an array
• EPI 6.1. The Dutch National Flag Problem (homework)

If it is sorted, take advantage of it.

• Leetcode 1. Two Sum (sorted) (lecture)

Instead of deleting an element from an array, try to overwrite it

• EPI: 6.5. Delete Duplicates From a Sorted Array (lecture)

Greedy Algorithm

• EPI 6.6. Buy and sell a stock once (lecture)
• EPI 6.7. Buy and sell a stock twice (lecture)

Using extra space to reduce time complexity

• Leetcode 1. Two Sum (not sorted) (lecture)
• EPI 6.8. Enumerate All Primes to n (lecture)
• Leetcode 454. 4Sum II (hands on)

Problem set

Check box indicate if a solution is availible

Elements of Programming Interviews 2015

• 6.1. The Dutch National Flag Problem
• 6.2. Increment An Arbitrary Precision Interger
• 6.3. Multiply Two Arbitrary Precision Intergers
• 6.4. Advancing Through an array
• 6.5. Delete Duplicates From a Sorted Array
• 6.6. Buy and sell a strock once
• 6.7. Buy and sell a strock Twice
• 6.8. Enumerate All Primes to n
• 6.9. Permute The Elements of An Array Hard
• 6.10. Compute the next permutation
• 6.11. Sample Offline data
• 6.12. Sample Online data
• 6.16. The Sudoku Checker Problem
• 6.17. Compute the spiral ordering of a 2D array
• 6.18. Rotate a 2D array
• 6.19. Compute rows in Pascal's triangle

Cracking the code interviews 6e

• 1.8 Zero Matrix

Leetcode

• 228. Summary Ranges
• 169. Majority Element Moore Voting Algorithm
• 442. Find All Duplicates in an Array

• 448. Find All Numbers Disappeared in an Array

• 80. Remove Duplicates from Sorted Array II
• 238. Product of Array Except itself
• 59. Spiral Matrix II
• 1. Two Sum
• 167. Two Sum II
• 15. 3Sum
• 16. 3Sum Closest
• 18. 4Sum
• 454. 4Sum II
• 122. Best Time to Buy and Sell Stock II
• 11. Container With Most Water
• 55. Jump Game
• 289. Game of Life Question
• 283. Move Zeros

Geeks for Geeks

• Find Maximum Sum Strictly Increasing Subarray
• Sum of maximum elements of all subsets
• Rearrange positive and negative numbers

Others

• How to Find Top Two Maximum Number from Integer array in Java
• Cound Negative Intergers in Sorted Matrix

Hard

• LeetCode: 128. Longest Consecutive Sequence