Validate a string if it is almost palindrome (remove at most one char to make it palindrome)
Two-pointer, time O(n), space O(1)
public class Solution {
public boolean isAlmostPalindrome(String s) {
return isAlmostPalindrome(s, 0, s.length() - 1, true);
}
public boolean isAlmostPalindrome(String s, int left, int right, boolean canSkip) {
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
++left;
--right;
} else if (!canSkip) {
return false;
} else {
return isAlmostPalindrome(s, left + 1, right, false)
|| isAlmostPalindrome(s, left, right - 1, false);
}
}
return true;
}
}
Implement an iterator API with only next() function to get node from BT with preorder traversal.
要求尽量on-the-fly，即支持多次访问。
Stack
Leetcode 173原题。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
Stack<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new Stack<>();
pushAllLeft(stack, root);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.empty();
}
/** @return the next smallest number */
public int next() {
TreeNode curr = stack.pop();
pushAllLeft(stack, curr.right);
return curr.val;
}
private void pushAllLeft(Stack<TreeNode> stack, TreeNode root) {
while (root != null) {
stack.push(root);
root = root.left;
}
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
decode ways I, 唯一和LC不同是要考虑到任何input string所以有很多error/edge case要想到
621. Task Scheduler
略
543. Diameter of Binary Tree
略
KNN
各种follow up，数据量太大怎么办，KNN service的QPS很高怎么办，input是data stream怎么办
Trie
写了几个trie的基本操作，add word，search word, search word with '?' matching any single char + output all matches。最后剩不到10分钟面试官灵机一动说，你给我做个trie compression吧，就是给一个一般的trie，怎么compress trie里面可以share的path以节省存储空间，注意他不要ternary trie，也不要对unicode的volcabulary做bit level的huffman encoding，只能在原来的trie里collapse shared paths。完全没有头绪，支支吾吾说了几个idea之后只剩3分钟，下一轮面试官已经站在门口了，他居然说，sounds good，你把你的idea写出来吧。。。瞎写几行时间就到了
283. Move Zeroes
简单题，略。
76. Minimum Window Substring
TODO
binary tree inorder traversal (Iterator)
subarray sum to K
15. 3Sum变型题，数组中的每个数字可以重复使用
在原题基础上稍作改变即可，指针j从i开始，到k结束。
也可以用combination sum的思路做，k = 3。
91. Decode Ways，input可能不规范
LintCode 819. Word Sorting
25. Reverse Nodes in k-Group
34. Search for a Range
Minesweeper
Given a height and a width and number of mines, return a minesweeper
field with mines in random positions
input: 2, 3, 3
return:
- X -
- X - X - -
我用loop，每次random一个0~width*height的数，然后转化为x和y，给mine二位数组赋值
follow up question：
- what if input: 100, 100, 9999. 雷太多怎么办
- what if input: 10000, 10000, 10000*10000/2. 上一题我答的用雷过半就算没雷的地方，保证不过半。然后他就问如果刚好一半怎么办，如何检测conflict
88. Merge Sorted Array
略
138. Copy List with Random Pointer
TODO
658. Find K Closest Elements
TODO
269. Alien Dictionary变型题
知道字典排序 判定字符串是不是按顺序排 就是反过来
