给一个Mutex,里面有lock(),unlock() 实现一个ReadWriteLock, PRAM CREW (同步读, 读时lock写, 写时lock写). 需要实现的方法有, readLock(), readUnlock(), writeLock(), writeUnlock() 这个没什么好讲的…基础os操作… 这题好像软软经常出, 所以我就做一下, 保佑onsite面试成功. public class ReadWriteLock { interface Mutex {// given an mutex public void lock(); public void unlock(); } Mutex readLock; // read lock, in order to support PRAM CREW. it only lock when Mutex writeLock; // write lock. only lock […]
刚才刷题, Leetcode中, Reverse Integer 和 String to Integer (atoi), 都要对结果进行越界处理. 什么是越界处理? 越界处理就是当整形数据超过最大/最小值的时候, 需要对数据进行判断, 避免程序出错. 可以用以下code进行对Integer的越界处理: if(Math.abs(res) > (Integer.MAX_VALUE – Math.abs(update_value)) / 10) return 0; 这里的res就是以上两题中, 每次需要做 res = res*10 + update_value的结果值, 我们在更新res前判断下次更新会不会越界(超过Integer.MAX_VALUE).
算一个完全树的节点个数 答案是抄的 public class Solution { public int countNodes(TreeNode root) { int leftDepth = leftDepth(root); int rightDepth = rightDepth(root); if (leftDepth == rightDepth) return (1 << leftDepth) – 1; else return 1+countNodes(root.left) + countNodes(root.right); } private int rightDepth(TreeNode root) { // TODO Auto-generated method stub int dep = 0; while (root != null) { root […]
给一个二叉树, 问你path sum最大是多少, 返回最大值 遍历所有node, 如果当前的path sum小于0, 那么是对sum没帮助的, 只关心大于0的. 然后找到最大就行了 int max = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { if(root == null) return 0; helper(root); return max; } public int helper(TreeNode root) { if (root == null) return 0; int left = Math.max(helper(root.left), 0); int right = Math.max(helper(root.right), 0); max = Math.max(max, root.val + left […]
给一组string, 定义一下shift “abc” – >; “bcd” ->; … ->; “xyz” 让你找这组string中,能互相shift的几组. 可以看出, 当一个string的字符之间的距离决定了shift后的string. 所以对字符之间的距离进行记录, 当做key, 就可以找到. 这里先取一下string首字母当做offset, 然后算距离. 最后记录在一个key(string)中. public List<List<String>> groupStrings(String[] strings) { List<List<String>> res = new ArrayList<List<String>>(); HashMap<String, List<String>> maps = new HashMap<>(); for(int i = 0 ; i < strings.length; i++) { String key = “”; int offset = strings[i].charAt(0) – ‘a’; […]
给一个 bst和一个double, 问你能不能找到一个值,和target的值最相近. 很naive的解法.在二叉遍历的同时, 记录当前节点值合给的值的差. public int closestValue(TreeNode root, double target) { int res = root.val; while(root != null){ if(Math.abs(root.val – target) < Math.abs(res – target)) res = root.val; if(root.val < target) root = root.right; else root = root.left; } return res; }
For example, Given s = “the sky is blue“, return “blue is sky the“. 翻转一个string, 但是里面单词不翻转. 三步: 翻转整个string 用left记录每个单词开始的地方, 然后扫到空格就翻转一下. 最后记得翻转一下最后的string public void reverseWords(char[] s) { reverse(s,0,s.length-1); int left = 0; for(int i = 0 ; i < s.length; i++) { if(s[i] == ‘ ‘){ reverse(s, left, i-1); left = i+1; } } reverse(s, left, […]
给一个2d的grid, 上边有1也有0. 让你找一个点使得所有点到这点的Manhattan Distance 的合为最小. 这题考点很多: 首先,Manhattan Distance 的合为 sum(distance(p1, p2)) = sum(|p2.x – p1.x| + |p2.y – p1.y|)= sum(|p2.x – p1.x|)+sum(|p2.y – p1.y|). 也就是说, 可以分别计算x和y的合, 然后加起来. 其次, 我们需要把2d的grid变成1d, 这里的窍门是, 我们可以证明, 所求的点, 就在其中某点的x或者y的坐标轴上. 所以, 而这点, 必然是1d下的median. http://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations Suppose we have a set S of real numbers that ∑s∈S|s−x|is minimal if x is equal to themedian. 所以, 我们需要count一下x轴上有多少个1的投影, 和y轴上有多少个1的投影. […]