一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
把贵司信息放这里
查看: 2424|回复: 141
收起左侧

[打卡] 多伦多在职每日刷题打卡也欢迎组队

[复制链接] |试试Instant~ |打卡, 打卡组队
我的人缘0

分享帖子到朋友圈
zhangrz2 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
坐标多伦多,每日刷题打卡,争取工作日每日3道,周末5道,欢迎大家来讨论系统设计题和OOP

--另外跪求大米

上一篇:behavior question和简历问题、算法 mock求组队
下一篇:DS Analytics向 每日打卡
我的人缘0
 楼主| zhangrz2 2019-5-27 02:25:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
1052. Grumpy Bookstore Owner-- sliding window

[Java] 纯文本查看 复制代码
class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int satis = 0;
        for (int i = 0; i < customers.length; i++) {
            satis += grumpy[i] == 0 ? customers[i] : 0;
        }
        int window = 0;
        int ans = 0;
        int start = 0;
        for (int i = 0; i < customers.length; i++) {
            window += grumpy[i] * customers[i];
            if (i >= X) {
                window -= grumpy[start] * customers[start];
                start++;
            }
            ans = Math.max(ans, window);
        }
        
        return ans + satis;
    }
}
回复

使用道具 举报

我的人缘0
 楼主| zhangrz2 2019-5-27 02:50:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
1054. Distant Barcodes -- Heap(PriorityQueue)
[Java] 纯文本查看 复制代码
class Solution {
    public int[] rearrangeBarcodes(int[] barcodes) {
        int[] ans = new int[barcodes.length];
        Map<Integer, Integer> count = new HashMap<>();
        for (int barcode : barcodes) {
            count.put(barcode, count.getOrDefault(barcode, 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int[] unit = {entry.getKey(), entry.getValue()};
            queue.add(unit);
        }
        int start = 0;
        while(queue.size() > 2) {
            int[] front = queue.poll();
            int[] sec = queue.poll();
            ans[start++] = front[0];
            ans[start++] = sec[0];
            if (front[1] > 1) {
                front[1]--;
                queue.add(front);
            }
            if (sec[1] > 1) {
                sec[1]--;
                queue.add(sec);
            }
        }
        while(queue.size() > 0) {
            int[] front = queue.poll();
            ans[start++] = front[0];
            if (front[1] > 1) {
                front[1]--;
                queue.add(front);
            }
        }
        return ans;
    }
}
回复

使用道具 举报

我的人缘0
14417335 2019-5-27 02:53:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (457)
 
 
0% (4)    👎
欢迎来系统设计题专版讨论系统设计问题: System Design

回复

使用道具 举报

我的人缘0
 楼主| zhangrz2 2019-5-27 04:21:46 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
284. Peeking Iterator -- you can define your own LinkedList and apply generics to solve this too

[Java] 纯文本查看 复制代码
// Java Iterator interface reference:
// [url]https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html[/url]
class PeekingIterator implements Iterator<Integer> {
    boolean hasMore;
    Iterator<Integer> it;
    Integer next;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    it = iterator;
        updateNext();
	}

    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return this.next;
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
        Integer ans = this.next;
        updateNext();
	    return ans;
	}

	@Override
	public boolean hasNext() {
	    return hasMore;
	}
    
    private void updateNext() {
        if (it.hasNext()) {
            next = it.next();
            hasMore = true;
        }else {
            hasMore = false;
        }
    }
}
回复

使用道具 举报

我的人缘0
 楼主| zhangrz2 2019-5-27 06:40:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
本帖最后由 zhangrz2 于 2019-5-27 06:43 编辑

93. Restore IP Addresses -- family with valid IP format

-- must smaller or equal than 255
-- if the first char is '0', then the length must be 1
more optimal solution--using StringBuilder instead of creating new string at each recursion call

[Java] 纯文本查看 复制代码
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        buildList(ans, "", 0, s, 0);
        return ans;
    }
    
    private void buildList(List<String> ans, String str, int curIndex, String s, int count) {
        if (str.length() == s.length() + 4 && count == 4) {
            ans.add(str.substring(1, str.length()));
            return;
        }
        if (count >= 4) {
            return;
        }
        int last = Math.min(curIndex + 3, s.length());
        for (int i = curIndex; i < last; i++) {
            String cur = s.substring(curIndex, i + 1);
            if (isValid(cur)) {
                buildList(ans, str + "." +  cur, i + 1, s, count + 1);
            }
        }
        return;
    }
    
    private boolean isValid(String str) {
        if (str == null || str.length() == 0) {
            return false;
        }
        int len = str.length();
        if (len > 3) {
            return false;
        }
        if (len != 1 && str.charAt(0) == '0') {
            return false;
        }
        return Integer.parseInt(str) <= 255;
    }
}

回复

使用道具 举报

我的人缘0
 楼主| zhangrz2 2019-5-27 08:55:34 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
本帖最后由 zhangrz2 于 2019-5-27 08:58 编辑

362. Design Hit Counter-- using AtomicIntegerArray to scale(multithreading)

[Java] 纯文本查看 复制代码
class HitCounter {
    int[] times;
    int[] hits;
    /** Initialize your data structure here. */
    public HitCounter() {
        times = new int[300];
        hits = new int[300];
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        int index = timestamp % 300;
        if (times[index] != timestamp) {
            times[index] = timestamp;
            hits[index] = 1;
        }else {
            hits[index]++;
        }
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        int ans = 0;
        for (int i = 0; i < times.length; i++) {
            if (times[i] > timestamp - 300) {
                ans += hits[i];
            }
        }
        return ans;
    }
}

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */
回复

使用道具 举报

我的人缘0
 楼主| zhangrz2 2019-5-28 09:41:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
706. Design HashMap -- linear probing

[Java] 纯文本查看 复制代码
class Node {
    int key;
    int val;
    Node next;
    Node prev;
    
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
    
    public void setNext(Node next) {
        this.next = next;
    }
    
    public Node getNext() {
        return this.next;
    }
    
    public int getKey() {
        return this.key;
    }
    
    public int getVal() {
        return this.val;
    }
    
    public void setVal(int val) {
        this.val = val;
    }
    
    public void setPrev(Node prev) {
        this.prev = prev;
    }
    
    public Node getPrev() {
        return this.prev;
    }
}
//linear probing
class MyHashMap {
    Node[] nodes;
    /** Initialize your data structure here. */
    public MyHashMap() {
        nodes = new Node[100000];
    }
    
    /** value will always be non-negative. */
    public void put(int key, int value) {
        //create head node
        int index = getIndex(key);
        if (nodes[index] == null) {
            nodes[index] = new Node(-1, -1);
        }
        Node target = findNode(key);
        if (target == null) {
            Node newNode = new Node(key, value);
            Node next = nodes[index].getNext();
            nodes[index].setNext(newNode);
            newNode.setPrev(nodes[index]);
            if (next != null) {
                next.setPrev(newNode);
                newNode.setNext(next);
            }
        }else {
            target.setVal(value);
        }
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        Node target = findNode(key);
        return target == null ? -1 : target.getVal();
    }
    
    
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        Node target = findNode(key);
        if (target != null) {
            Node prev = target.getPrev();
            Node next = target.getNext();
            prev.setNext(target.getNext());
            if (next != null) {
                next.setPrev(prev);
            }            
        }
        return;
    }
    
    private int getIndex(int key) {
        return Integer.hashCode(key) % nodes.length;
    }
    
    private Node findNode(int key) {
        int index = getIndex(key);
        Node leadNode = nodes[index];
        if (leadNode == null) {
            return null;
        }
        while(leadNode != null) {
            if (leadNode.getKey() == key) {
                return leadNode;
            }
            leadNode = leadNode.getNext();
        }
        return null;
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */
回复

使用道具 举报

我的人缘0
 楼主| zhangrz2 2019-5-28 10:20:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
295. Find Median from Data Stream -- so many solutions(any ideas for the follow ups?)

[Java] 纯文本查看 复制代码
class MedianFinder {
    PriorityQueue<Integer> maxLowHeap;
    PriorityQueue<Integer> minHighHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        minHighHeap = new PriorityQueue<Integer>();
        maxLowHeap = new PriorityQueue<Integer>((a , b) -> b - a);
    }
    
    public void addNum(int num) {
        maxLowHeap.add(num);
        minHighHeap.add(maxLowHeap.peek());
        maxLowHeap.poll();
        if(maxLowHeap.size() < minHighHeap.size()) {
            maxLowHeap.add(minHighHeap.poll());
        }
    }
    
    public double findMedian() {
        if (maxLowHeap.size() == minHighHeap.size()) {
            return (maxLowHeap.peek() + minHighHeap.peek()) * 0.5;
        }else {
            return maxLowHeap.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
回复

使用道具 举报

我的人缘0
 楼主| zhangrz2 2019-5-28 10:21:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (16)
 
 
0% (0)    👎
zhangrz2 发表于 2019-5-28 10:20
295. Find Median from Data Stream -- so many solutions(any ideas for the follow ups?)

[mw_shl_cod ...

TODO: look up implementing AVL Tree using Java
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-11-22 05:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表