Site Color

Text Color

Text Color

Evergreen

Duotone

Mysterious

Classic

or

Algorithms and Data Structures Interview Preparation & Walkthrough — Part 2, Array and String by@victor-lin

# Algorithms and Data Structures Interview Preparation & Walkthrough — Part 2, Array and String

### @victor-linVictor Lin

In my previous post: Algorithms and Data Structures Interview Preparation & Walkthrough — Part 1, we talked about how to do Complexity Time and Space analysis, and also see the common Big-O factors with examples.

In this post, I will start talking about Array in depth, and cover some interview questions and hopefully by the end of the reading, you would have a good glance about Array. Once we are familiar with Array, I will talk about String and how to use Array to solve String problems.

Array is a data structure that contains a group of elements. The most basic implementation of an array is a static array. The reason it’s called static is the size is fixed. The read/write access to a certain position is O(1).

#### Implementation of Static Array

`class StaticArray  def initialize(length)    self.store = Array.new(length)  end`
`# O(1)  def [](index)    self.store[index]  end`
`# O(1)  def []=(index, value)    self.store[index] = value  end`
`protected  attr_accessor :storeend`

We create a Dynamic Array from Static Array as follow. The read/write access is also O(1). Let’s implement some general methods i.e. pop(), push(), shift() and unshift() for it. The key here is, when we reach the array size, we want to resize it and double its space, in order to push() or unshift() new elements to the array.

#### Implementation of Dynamic Array

`require_relative "static_array"`
`class DynamicArray  attr_reader :length`
`def initialize    @length = 0    @capacity = 8    @store = StaticArray.new(8)  end`
`# O(1)  def [](index)    check_index(index)    @store[index]  end`
`# O(1)  def []=(index, value)    check_index(index)    @store[index] = value  end`
`# O(1)  def pop    check_index(0)    @length -= 1    @store[length + 1]  end`
`# O(1) amortized; O(n) worst case.  def push(val)    resize! if @length == @capacity    @store[@length + 1] = val    @length += 1  end`
`# O(n): has to shift over all the elements.  def shift    check_index(0)    idx = 0    first_el = @store[0]    while idx < @length - 1      @store[idx] = @store[idx + 1]      idx += 1    end    @length -= 1    first_el  end`
`# O(n): has to shift over all the elements.  def unshift(val)    resize! if @length == @capacity    idx = @length    while idx > 0      @store[idx] = @store[idx - 1]      idx -= 1    end    @store[0] = val    @length += 1    @store  end`
`protected  attr_accessor :capacity, :store  attr_writer :length`
`def check_index(index)    raise "out of bounds" if (@length < index + 1 || index < 0)  end`
`# O(n): has to copy over all the elements to the new store.  def resize!    new_store = StaticArray.new(@capacity * 2)    idx = 0    while idx < @length      new_store[idx] = @store[idx]      idx += 1    end    @store = new_store    @capacity *= 2  endend`

#### What is amortization?

If you read carefully enough, you would notice there is a keyword “amortized” in the code snippet. What does that mean? When we want to append (or push) a new element to the Array and it reaches its size limit, we want to double the size. However, `resize!` method allocates a larger region, moves the whole array, and deletes the previous. This is a `O(n)` operation. But if we're only doing it every `O(1/n)` times, then on average it can still come out to `O(n * 1/n) = O(1)`. That’s called amortized cost.

#### Time Complexity and Space Complexity for Dynamic Array

In average and worst cases,

`Access O(1)`

`Search O(n)`

`Insertion O(n)`(at the end of Array is O(1) amortized, at the beginning or middle of Array is O(n)

`Deletion O(n)`

`Space O(n)`

We now know accessing an element in Array is fast (`O(1)`), whereas searching/adding/removing is relatively slow (`O(n)`), which sometimes requires looping through the whole array.

#### Ring Buffer

It is a data structure that uses a Static Array as if it were connected end-to-end.

`require_relative "static_array"`
`class RingBuffer  attr_reader :length`
`def initialize    @length = 0    @capacity = 8    @start_idx = 0    @store = StaticArray.new(@capacity)  end`
`# O(1)  def [](index)    check_index(index)    ring_index = (index + @start_idx) % @capacity    @store[ring_index]  end`
`# O(1)  def []=(index, val)    check_index(index)    ring_index = (index + @start_idx) % @capacity    @store[ring_index] = val  end`
`# O(1)  def pop    check_index(0)    @length -= 1;    val = @store[(@length + @start_idx) % @capacity]    @store[(@length + @start_idx) % @capacity] = nil    val  end`
`# O(1) amortized  def push(val)    resize! if @length == @capacity    @store[(@length + @start_idx) % @capacity] = val    @length += 1  end`
`# O(1)  def shift    check_index(0)    val = @store[@start_idx]    @store[@start_idx] = nil    @start_idx = (@start_idx + 1) % @capacity    @length -= 1    val  end`
`# O(1) amortized  def unshift(val)    resize! if @length == @capacity    @start_idx = (@start_idx - 1) % @capacity    @store[@start_idx] = val    @length += 1    val  end`
`protected  attr_accessor :capacity, :start_idx, :store  attr_writer :length`
`def check_index(index)    raise "index out of bounds" if (index < 0 || index > @length - 1)  end`
`def resize!    new_store = StaticArray.new(@capacity * 2)    idx = 0    while idx < @length      new_store[idx] = @store[(@start_idx + idx) % @capacity]      idx += 1    end    @store = new_store    @start_idx = 0    @capacity *= 2  endend`

To master Array data structure and questions, we at least need to be very familiar with:

1. Loop operation.
2. Sense of using pointer(s) to record location(s).
3. Swap technique.
4. Basic Math.
5. Common array methods and the time complexity of them, i.e. pop(), push(), shift(), unshift(), forEach(), sort(), slice(), splice(), reverse(), concat(), filter(), map() … etc.

● Constant time access and allows random access

● Grouping like items

● Insertion and deletion can be expensive for large arrays

● Dynamic arrays have cost to resize, and limited by the size allocated

Enough said, here are some popular interview questions for your practice:

1. Move Zeros — Given an array of numbers, write a function to move all `0`'s to the end of it while maintaining the relative order of the non-zero elements. (thought process and solution)
2. Stocks 101 — When to buy/sell the stock? Given an array contains the daily price for a stock. Try to find the maximum profit. (thought process and solution)
3. Find Duplicates — Given an array of numbers, return true if any number appears more than once in the array, otherwise return false. (thought process and solution)

#### String

Now we know about Array, let’s talk about String — which is nothing but a Character-based Array. You just need to learn techniques to solve Array questions, and you are a String Master by nature!

Before diving into String related questions, we need to get familiar with:

1. String related methods, i.e. charAt(), includes(), trim(), concat(), slice(), split(), substring(), toUpperCase(), toLowerCase(), toString()…etc.
2. Two pointers.
3. Swap elements within Array.
4. Recursion.

In my next post, I will talk about Data Structures for Queue, Stack and Linked List.

#### Before You Go —

There’s no better way to support me than to give me a follow on Medium (Victor Lin). Let me know that I should write more!

Did you know that you can give up to 50 👏’s by pressing down on the 👏 button? Give it a try if you reeeeeeally liked this article!