Showing posts with label Palantir. Show all posts
Showing posts with label Palantir. Show all posts

Saturday, June 17, 2017

303. Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.



Solution:

This is a prefix sum problem.

We define sum[i] = num[0] + num[1] + ... + num[i - 1].

A range sum sum(i, j) is

num[0] + num[1] + ... + num[j] - (num[0] + num[1] + ... + num[i - 1])

= sum[j + 1] - sum[i]



Code:


public class NumArray {

    public int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

Tuesday, May 23, 2017

325. Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.
Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
Example 1:
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)
Example 2:
Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)
Follow Up:
Can you do it in O(n) time?



Solution:

This is a range sum question. Whenever we see similar problem, we shall try prefixSum.

prefixSum[i] is the sum from 0 to i.

So prefixSum[j] - prefixSum[i - 1] is the range sum from i to j.

Now we go through the input array and calculate the prefixSum at index i.

At the same time, if we check and find a previous prefixSum with value prefixSum[i] - k in a HashMap, we know the range sum from map.get(prefixSum[i] - k) to i is k.

Therefore, we need O(n) time and O(n) space to solve the problem.



Code:


public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        int sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                maxLen = Math.max(maxLen, i - map.get(sum - k));
            }
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return maxLen;
    }
}

Monday, May 8, 2017

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.



Solution:

Use a HashSet to store the one we checked.

If the number is in the HashSet, we found the duplicate and return true.

The time complexity is O(n) and space complexity is O(n) as well.



Code:


public class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        HashSet<Integer> hash = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (hash.contains(nums[i])) {
                return true;
            }
            hash.add(nums[i]);
        }
        return false;
    }
}

Tuesday, May 2, 2017

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4



Solution:

The idea is to have a doubly linked list to cache elements. The most recent element will be put into the tail.

We also maintains a HashMap to mapping a key to each element.

In a get operation, we try to find the node in HashMap and put it to the tail.

In a put operation, if the node exists, we put it to the tail and update its value. If it does not exist, we create a new node and put it to the tail. In the meantime, we check if the cache is full.

If the cache is full, we need to remove the mapping of the head in the linked list.

We use a dummy head and a dummy tail for convenience.



Code:


public class LRUCache {
    
    class ListNode {
        int key;
        int value;
        ListNode prev;
        ListNode next;
        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
            ListNode prev = null;
            ListNode next = null;
        }
    }
    private int capacity;
    private HashMap<Integer, ListNode> map;
    private ListNode head;
    private ListNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.prev = head;
        map = new HashMap<>();
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        ListNode node = map.get(key);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        moveToTail(node);
        
        return node.value;
    }
    
    public void put(int key, int value) {
        if (get(key) != -1) {
            map.get(key).value = value;
            return;
        }
        
        if (map.size() == this.capacity) {
            map.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }
        
        ListNode node = new ListNode(key, value);
        map.put(key, node);
        moveToTail(node);
    }
    
    public void moveToTail(ListNode node) {
        node.prev = tail.prev;
        tail.prev.next = node;
        tail.prev = node;
        node.next = tail;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */