SimpleAlgos
This repo is a place for me to implement of some simple algorithms, as a way of learning about those algorithms. Part of the goal is to code the algorithms "from scratch", so avoiding standard libraries and Collections. So, for example, in order to code Dijkstra's, I created my own priority queue, backed by a binary heap. In order to represent graphs, I created my own linked list class.
Java
- Implement a LinkedList
- Implement a DoublyLinkedList
- Implement a HashTable
- Implement a Heap and a Priority Queue
- Implement a Graph (adjacency list)
- Implement a Binary search tree
- Implement Dijkstra's
- Implement an AVLTree
- Write the actual code to reverse a linked list
- Write a function to multiply two arbitrarily large integers.
- Given a matrix of numbers in which some may be zero. If a cell contains a zero, set all the cells in the corresponding column and row to zero
- You are given a set of numbers 0 - n. Given a k, print all subsets of size k. Give the time complexity of the algorithm
- Tree BFS: given a tree, print the elements in level order, i.e. level 1: root; level 2: a, b; level 3: c, d, e, f, etc..
- Find Kth smallest element in a BST.
- Find if a given tree is a BST
- same as above Write a method to verify that a binary search tree is well-formed (i.e. all left children are smaller than this node, all right children are larger).
- Given preorder and inorder traversal of a tree, construct the binary tree.
- Rotate as square matrix by 90 degrees clockwise
- Given a matrix print it clockwise from the first element to the very inner element
- Implement a function rotateArray(vector arr, int r) which rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives 4 5 1 2
- Divide without divide and multiply operator
- Same for addition.
- Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j].
- Implement atof function. eg., +3.5e-2, .03e1, 1e1, 0.0
- Parenthesizing a mathematical expression to find maximum value
- How can you merge two BST in-place so that preserving the BST property?
- Find the largest BST in a binary tree
Python
- Given a fraction how would you find length of the first cycle of decimals that repeats when repeating the division (e.g. 1/7).
- You have a skyline of buildings with the upper coordinates for each building. You have to output the coordinates of the outline made by all the buildings combined
- Find Kth smallest element in a BST.
- Compute whether a BST is balanced
- Given a timeseries of prices, find the max profit
- You have an array of english words {cat, then, hen, end, dog}. Can you make out if the given sentence is a concatenation of only words from the array?