Skip to content

Instantly share code, notes, and snippets.

View wayetan's full-sized avatar

Wei Tan wayetan

  • Microsoft
  • United States
View GitHub Profile
@wayetan
wayetan / ReverseWordsinaString.java
Created March 9, 2014 20:39
Reverse Words in a String
/**
* Given an input string, reverse the string word by word.
* For example,
* Given s = "the sky is blue",
* return "blue is sky the".
* Clarification:
* What constitutes a word?
***A sequence of non-space characters constitutes a word.
* Could the input string contain leading or trailing spaces?
***Yes. However, your reversed string should not contain leading or trailing spaces.
@wayetan
wayetan / DivideTwoIntegers.java
Last active October 18, 2015 06:46
Divide Two Integers
/**
* Divide two integers without using multiplication, division and mod operator.
*/
public class Solution {
public int divide(int dividend, int divisor) {
if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
int res = 0;
boolean isNeg = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);
// a / b
@wayetan
wayetan / SubstringwithConcatenationofAllWords.java
Last active October 16, 2019 18:55
Substring with Concatenation of All Words
/**
* You are given a string, S, and a list of words, L, that are all of the same length.
* Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
* For example, given:
* S: "barfoothefoobarman"
* L: ["foo", "bar"]
* You should return the indices: [0,9].
* (order does not matter).
*/
public class Solution {
@wayetan
wayetan / MultiplyStrings.java
Last active October 19, 2015 07:16
Multiply Strings
/**
* Given two numbers represented as strings, return multiplication of the numbers as a string.
* Note: The numbers can be arbitrarily large and are non-negative.
*/
public class Solution {
public String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0"))
return "0";
int l1 = num1.length(), l2 = num2.length();
@wayetan
wayetan / RegularExpression.java
Last active March 24, 2017 01:12
Regular Expression
/**
* Implement regular expression matching with support for '.' and '*'.
* '.' Matches any single character.
* '*' Matches zero or more of the preceding element.
* The matching should cover the entire input string (not partial).
* The function prototype should be:
* bool isMatch(const char *s, const char *p)
* Some examples:
* isMatch("aa","a") → false
* isMatch("aa","aa") → true
@wayetan
wayetan / WildcardMatching.java
Created March 6, 2014 21:16
Wildcard Matching
/**
* Implement wildcard pattern matching with support for '?' and '*'.
* '?' Matches any single character.
* '*' Matches any sequence of characters (including the empty sequence).
* The matching should cover the entire input string (not partial).
* The function prototype should be:
* bool isMatch(const char *s, const char *p)
* Some examples:
* isMatch("aa","a") → false
* isMatch("aa","aa") → true
@wayetan
wayetan / MergeIntervals.java
Created March 5, 2014 09:43
Merge Intervals
/**
* Given a collection of intervals, merge all overlapping intervals.
* For example,
* Given [1,3],[2,6],[8,10],[15,18],
* return [1,6],[8,10],[15,18].
*/
/**
* Definition for an interval.
* public class Interval {
@wayetan
wayetan / TextJustification.java
Created March 5, 2014 08:42
Text Justification
/**
* Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
* You should pack your words in a greedy approach; that is, pack as many words as you can in each line.
* Pad extra spaces ' ' when necessary so that each line has exactly L characters.
* Extra spaces between words should be distributed as evenly as possible.
* If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
* For the last line of text, it should be left justified and no extra space is inserted between words.
* For example,
* words: ["This", "is", "an", "example", "of", "text", "justification."]
* L: 16.
@wayetan
wayetan / SimplifyPath.java
Created March 3, 2014 02:30
Simplify Path
/**
* Given an absolute path for a file (Unix-style), simplify it.
* For example,
* path = "/home/", => "/home"
* path = "/a/./b/../../c/", => "/c"
* Corner Cases:
* Did you consider the case where path = "/../"?
* In this case, you should return "/".
* Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
* In this case, you should ignore redundant slashes and return "/home/foo".
@wayetan
wayetan / MinimumWindowSubstring.java
Created March 2, 2014 06:24
Minimum Window Substring
/**
* Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
* For example,
* S = "ADOBECODEBANC"
* T = "ABC"
* Minimum window is "BANC".
* Note:
* If there is no such window in S that covers all characters in T, return the emtpy string "".
* If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
*/