146. LRU Cache

Difficulty: Hard

Frequency: N/A

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class LRUCache{
public:
    LRUCache(int capacity) : cap(capacity) { }
    
    int get(int key) {
        auto iter = map.find(key);
        if (iter == map.end()) return -1;
        touch(iter);
        return iter->second.first;
    }
    
    void set(int key, int value) {
        auto iter = map.find(key);
        if (iter != map.end()) touch(iter);
        else {
            if (map.size() == cap) {
                map.erase(lru.back());
                lru.pop_back();
            }
            lru.push_front(key);
        }
        map[key] = {value, lru.begin()};
    }
private:

    typedef list<int> IntList;
    typedef pair<int, IntList::iterator> IntIntList;
    typedef unordered_map<int, IntIntList> Map;
    
    int cap;
    IntList lru;
    Map map;
    void touch(Map::iterator iter) {
        int key = iter->first;
        lru.erase(iter->second.second);
        lru.push_front(key);
        iter->second.second = lru.begin();
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

295. Find Median from Data Stream

Difficulty: Hard

Frequency: N/A

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

  • void addNum(int num) – Add a integer number from the data stream to the data structure.
  • double findMedian() – Return the median of all elements so far.

For example:

add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class MedianFinder {
private:
    priority_queue<int> small, large;
public:

    // Adds a number into the data structure.
    void addNum(int num) {
        small.push(num);
        large.push(-small.top());
        small.pop();
        if (small.size() < large.size()) {
            small.push(-large.top());
            large.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        if (small.size() > large.size()) return small.top();
        else return (small.top() - large.top()) / 2.0;
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

284. Peeking Iterator

Difficulty: Medium

Frequency: N/A

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation — it essentially peek() at the element that will be returned by the next call to next().


Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Hint:

  1. Think of “looking ahead”. You want to cache the next element.
  2. Is one variable sufficient? Why or why not?
  3. Test your design with call order of peek() before next() vs next() before peek().
  4. For a clean implementation, check out Google’s guava library source code.

Follow up: How would you extend your design to be generic and work with all types, not just integer?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
// Below is the interface for Iterator, which is already defined for you.
// **DO NOT** modify the interface for Iterator.
class Iterator {
    struct Data;
	Data* data;
public:
	Iterator(const vector<int>& nums);
	Iterator(const Iterator& iter);
	virtual ~Iterator();
	// Returns the next element in the iteration.
	int next();
	// Returns true if the iteration has more elements.
	bool hasNext() const;
};


class PeekingIterator : public Iterator {
public:
	PeekingIterator(const vector<int>& nums) : Iterator(nums) {
	    // Initialize any member here.
	    // **DO NOT** save a copy of nums and manipulate it directly.
	    // You should only use the Iterator interface methods.
	    
	}

    // Returns the next element in the iteration without advancing the iterator.
	int peek() {
        return Iterator(*this).next();
	}

	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	int next() {
	    return Iterator::next();
	}

	bool hasNext() const {
	    return Iterator::hasNext();
	}
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

244. (Locked)Shortest Word Distance II

Difficulty: Medium

Frequency: N/A

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = "coding”word2 = "practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.

Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
class WordDistance {
    unordered_map<string, vector<int>> dict;
public:
    WordDistance(vector<string> words) {
        int n = words.size();
        for (int i = 0; i < n; i++) {
            dict[words[i]].push_back(i);
        }
    }
    int shortest(string word1, string word2) {
        vector<int> pos1 = hash[word1];
        vector<int> pos2 = hash[word2];
        int dist = INT_MAX;
        for(auto p1:pos1){
            for(auto p2:pos2){
                dist = min(dist, abs(p1-p2));
            }
        }
        return dist;
    }
};

Things to learn:

251. (Locked)Flatten 2D Vector

Difficulty: Medium

Frequency: N/A

Implement an iterator to flatten a 2d vector.

For example,
Given 2d vector =

[
  [1,2],
  [3],
  [4,5,6]
]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:[1,2,3,4,5,6].

Hint:

  1. How many variables do you need to keep track?
  2. Two variables is all you need. Try with x and y.
  3. Beware of empty rows. It could be the first few rows.
  4. To write correct code, think about the invariant to maintain. What is it?
  5. The invariant is x and y must always point to a valid point in the 2d vector. Should you maintain your invariant ahead of time or right when you need it?
  6. Not sure? Think about how you would implement hasNext(). Which is more complex?
  7. Common logic in two different places should be refactored into a common method.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Vector2D {
    vector<vector<int>>::iterator iter, iEnd;
    int j = 0;
public:
    Vector2D(vector<vector<int>>& vec2d) {
        iter = vec2d[0].begin();
        iEnd = vec2d[0].end();
    }

    int next() {
        if (iter != iEnd) {
            return *iter++;
        } else {
            j++;
            iter = vec2d[j].begin();
            iEnd = vec2d[j].end();
            return next();
        }
    }

    bool hasNext() {
        return j < vec2d.size() - 1 || iter != iEnd;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

281. (Locked)Zigzag Iterator

Difficulty:  Easy

Frequency: N/A

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class ZigzagIterator {
    public:
        ZigzagIterator(vector<int>& v1, vector<int>& v2) {
            cur = -1;
            counts.push_back(0);
            counts.push_back(0);
            this->v1 = v1;
            this->v2 = v2;
        }

        int next() {
            cur = (cur + 1) % 2;
            if (cur == 0 && counts[0] < v1.size()) return v1[counts[0]++];
            else if (cur == 1 && counts[1] < v2.size()) return v2[counts[1]++];
            return next();
        }

        bool hasNext() {
            return counts[0] < v1.size() || counts[1] < v2.size();
        }
    private:
        int cur;
        vector<int> counts;
        vector<int> v1, v2;
    };

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

288. (Locked)Unique Word Abbreviation

Difficulty: Easy

Frequency: N/A

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word’s abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example:

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
private:
    unordered_map<string, vector<string>> dict;
public:
    ValidWordAbbr(vector<string> &dictionary) {
        for (string s : dictionary) {
            int n = s.size();
            string key = s[0] + to_string(n - 2) + s[n - 1];
            if (dict.find(key) == dict.end()) {
                vector<string> val;
                val.push_back(s);
                dict.insert(make_pair<string, vector<string>>(key, val));
            } else dict[key].push_back(s);
        }
    }
    bool isUnique(string word) {
        int n = word.size();
        string key = word[0] + to_string(n - 2) + word[n - 1];
        if (dict.find(key) == dict.end()) return true;
        else if (dict[key].size() == 1 && word == dict[key][0]) return true;
        return false;
    }
}

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: