Skip to content

Instantly share code, notes, and snippets.

View shailrshah's full-sized avatar
🖥️
Available

Shail Shah shailrshah

🖥️
Available
9 followers · 0 following
View GitHub Profile
@shailrshah
shailrshah / StackFromQueue.java
Created October 22, 2017 18:46
Implement the stack operations (push(), pop(), peek(), isEmpty()) using queues.
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
queue = new java.util.LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
@shailrshah
shailrshah / QueueFromStack.java
Created October 22, 2017 19:09
Implement the queue operations (push(), pop(), peek(), isEmpty()) using 2 stacks
class QueueFromStack {
/** Initialize your data structure here. */
Stack<Integer> stack1;
Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
@shailrshah
shailrshah / SerializeTree.java
Last active November 7, 2022 21:27
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work.
// 1
// / \
// 2 3
// / \
// 4 5
// "1 2 3 * * 4 5 * * * *"
public String serialize(TreeNode root) {
if(root == null)
return "";
@shailrshah
shailrshah / sortedArrayToBST.java
Created October 22, 2017 22:35
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
public TreeNode sortedArrayToBST(int[] nums) {
return getBalancedTree(nums, 0, nums.length-1);
}
private TreeNode getBalancedTree(int[] a, int start, int end) {
if(end < start)
return null;
int mid = (start + end) / 2;
TreeNode root = new TreeNode(a[mid]);
root.left = getBalancedTree(a, start, mid-1);
@shailrshah
shailrshah / LongestPalindrome.java
Last active November 13, 2017 19:42
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
int low, max;
public String longestPalindrome(String s) {
int n = s.length();
if(n < 2)
return s;
for(int i = 0; i < n-1; i++) {
extendPal(s, i, i);
extendPal(s, i, i+1);
}
@shailrshah
shailrshah / CountAndSay.java
Last active October 24, 2017 20:04
1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth term of the count-and-say sequence.
private static String computeNext(String seed) {
StringBuilder next = new StringBuilder();
for(int i = 0; i < seed.length(); i++) {
char ch = seed.charAt(i);
int count = 1;
while(i+1 < seed.length() && seed.charAt(i+1) == ch) {
i++;
count++;
}
next.append(count);
@shailrshah
shailrshah / MaxDiameter.java
Created October 23, 2017 02:28
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
static int max;
public int diameterOfBinaryTree(TreeNode root) {
max = 0;
maxDepth(root);
return max;
}
private static int maxDepth(TreeNode root) {
if(root == null)
return 0;
@shailrshah
shailrshah / PowerSet.java
Last active October 28, 2017 03:47
Given a set of distinct integers, return all possible subsets (the power set). The solution set must not contain duplicate subsets.
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> answer = new ArrayList<>();
int n = nums.length;
long ansSize = (long)Math.pow(2, n);
for(long i = 0; i < ansSize; i++) {
List<Integer> element= new ArrayList<>();
for(int j = 0; j < n; j++) {
// add jth number if jth bit in i is set
@shailrshah
shailrshah / CalcSetBits.java
Last active November 13, 2017 20:47
Return the number of set bits for a non-negative number n.
//Brian Kernighan’s Algorithm
// For 1011
// 1011 & 1010 = 1010
// 1010 & 1001 = 1000
// 1000 & 0111 = 0000
// Number of &s till zero = 3
private int calcSetBits(int n) {
int count = 0;
@shailrshah
shailrshah / IsSymmetricTree.java
Created October 23, 2017 20:11
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
public boolean isSymmetric(TreeNode root) {
return isSymmetricHelper(root, root);
}
private static boolean isSymmetricHelper(TreeNode root1, TreeNode root2) {
if(root1 == null && root2 == null)
return true;
if(root1 == null || root2 == null)
return false;