Documentation
¶
Overview ¶
Package arrays implements the solutions for the problem contained in chapter 5 in the book Elements of Programming Interviews.
Index ¶
- func Advance(x []uint) bool
- func Alternation(x []int)
- func ApplyPermutation(elems, permutation []int)
- func BuyAndSellStockOnce(prices []int) int
- func DeleteDuplicates(x []int) int
- func GeneratePrimes(upperBound int) []uint
- func Increment(digits []int) []int
- func LinearAlternation(x []int)
- func Partition(elems []int, i int) (int, int)
- func Rotate2DArray(matrix [][]int)
- func SpiralOrdering(matrix [][]int) []int
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Advance ¶
Advance advances through the array and returns if it is possible to advance to the last position. Time complexity O(N). Space Complexity O(1).
func Alternation ¶
func Alternation(x []int)
Alternation rearranges the slice such that the elements are in the order: x[0] <= x[1] >= x[2] <= x[3] >= x[4] ... Takes O(nlogn) time and O(1) space
func ApplyPermutation ¶
func ApplyPermutation(elems, permutation []int)
ApplyPermutation will apply the permutation in O(N) time and with additional O(N) space complexity.
func BuyAndSellStockOnce ¶
BuyAndSellStockOnce finds the maximum profit possible from the given stock prices in the slice returns the maximum profit. The time complexity is O(N) and the space complexity is O(1).
func DeleteDuplicates ¶
DeleteDuplicates deletes duplicate elements and returns the number of valid elements left in the slice. The time complexity is O(N), and the space complexity is O(1).
func GeneratePrimes ¶
GeneratePrimes generates all prime numbers from 2 all the way up but no including upperBound. Time complexity is O(n log(log(n))), space complexity O(n)
func Increment ¶
Increment increments the number passed in as a slice of digits by one, and returns the new number. Time complexity O(n).
func LinearAlternation ¶
func LinearAlternation(x []int)
LinearAlternation rearranges the slice such that the elements are in the order: x[0] <= x[1] >= x[2] <= x[3] >= x[4] ... Takes O(n) time and O(1) space
func Partition ¶
Partitions the slice in linear time, such that all elements less than the pivot appears before all elements equal to the pivot and elements which are greater than the pivot appears as last. The pivot is selected as elems[i].
func Rotate2DArray ¶
func Rotate2DArray(matrix [][]int)
Rotate2DArray takes as input an nxn 2D array, and rotates the array by 90 degrees clockwise. Takes O(N^2) time and O(1) space complexity.
func SpiralOrdering ¶
SpiralOrdering takes an nxn 2D array and returns the spral ordering of the array. Takes O(N^2) time and O(1) space complexity.
Types ¶
This section is empty.
Source Files