LRU Cache

Q:

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.

T:
Store the data in a list. Move an item to the front of the list when that item is accessed. Use a hittable to store the mapping from the key to the iterator in the list;

A:

class LRUCache{
private:
    class entry {
        public:
        int key;
        int value;
    };
    int cap;
    list< entry > data;
    unordered_map< int, list< entry >::iterator > mp;
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if(mp.find(key) != mp.end()) {
            if(mp[key] != data.begin()) {
                entry item = *(mp[key]);
                data.erase(mp[key]);
                data.push_front(item);
                mp[key] = data.begin();
            }
            return data.front().value;
        }
        return -1;
    }
    
    void set(int key, int value) {
        if(mp.find(key) != mp.end()) {
            if(mp[key] != data.begin()) {
                entry item = *(mp[key]);
                data.erase(mp[key]);
                data.push_front(item);
                mp[key] = data.begin();
            }
            data.front().value = value;
            return;
        }
        if(data.size() >= cap) {
            mp.erase(data.back().key);
            data.pop_back();
        }
        entry item;
        item.key = key;
        item.value = value;
        data.push_front(item);
        mp[key] = data.begin();
    }
};

Sort Colors

Q:
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

T:
Keep two pointers. One points to the last index where red should occur. One points to the first index where blue should occur. Traverse the array, when meeting red, swap it with the first pointer, when meeting blue, swap it with the second pointer. Increase or decrease the pointers when needed.

A:

class Solution {
public:
    void sortColors(int A[], int n) {
        int red = 0;
        int blue = n-1;
        int i=red;
        while(i <= blue) {
            if(A[i]==0) {
                swap(A[i], A[red]);
                red++;
                i++;
                continue;
            }
            if(A[i]==2) {
                swap(A[i], A[blue]);
                blue--;
                continue;
            }
            i++;
        }
    }
};

Merge Intervals

Q:

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

T:
First sort the intervals by each start value. Then merge the intervals from the beginning. Once we cannot keep merging, push a new interval to the return vector, keep trying merging the following ones.

A:

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    static bool compare(const Interval & inter1, const Interval & inter2) {
        if(inter1.start < inter2.start) {
            return true;
        } else {
            return false;
        }
    }
    vector< Interval > merge(vector< Interval > &intervals) {
        vector< interval > ret;
        if(intervals.size() == 0) {
            return ret;
        }
        sort(intervals.begin(), intervals.end(), compare);
        
        Interval inter = intervals[0];
        for(int i=1; i < intervals.size(); i++) {
            if(inter.end >= intervals[i].start) {
                inter = Interval(inter.start, max(inter.end, intervals[i].end));
            } else {
                ret.push_back(inter);
                inter = intervals[i];
            }
        }
        ret.push_back(inter);
        return ret;
    }
};

Gas Station

Q:

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

T:
This problem is tricky to solve. Assume we start from station 0, then at some point, say station i, the gas may become negative. So we need to assume we start from the station i, and see whether when we reach station n there is enough gas left to continue the loop from station 0 to station i-1.

A:

class Solution {
public:
    int canCompleteCircuit(vector< int > &gas, vector< int > &cost) {
        int previous = 0;
        int rest = 0;
        int index = 0;
        for(int i=0; i < gas.size(); i++) {
            rest += gas[i] - cost[i];
            if (rest < 0) {
                previous += rest;
                rest = 0;
                index = i+1;
            }
        }
        if (previous + rest >= 0) {
            return index;
        } else {
            return -1;
        }
    }
};

Valid Number

Q:
Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

T:
The part before "e" should only contain numbers or "." with at least one number.
The part after "e" should only contain numbers. The "+"/"-" is an exception.

A:

class Solution {
public:
    bool isNumber(const char *s) {
        while(*s == ' ') {
            s++;
        }
        if(*s == '\0') {
            return false;
        }
        if(*s == '-' || *s == '+') {
            s++;
        }
        int dotseen = 0;
        int eseen = 0;
        int numseen = 0;
        while(*s != '\0') {
            if(*s >= '0' && *s <= '9') {
                if(numseen == 0) {
                    numseen = 1;
                }
            } else if(*s == '.') {
                if(!eseen && !dotseen) {
                    dotseen = 1;
                    if(!numseen && !(*(s+1) >= '0' && *(s+1) <= '9')) {
                        return false;
                    }
                } else {
                    return false;
                }
            } else if(*s == 'e') {
                if(numseen && !eseen){
                    eseen = 1;
                    if(!(*(s+1) >= '0' && *(s+1) <= '9') && !(*(s+1) == '-' || *(s+1) == '+')) {
                        return false;
                    }
                } else {
                    return false;
                }
            } else if(*s == '-' || *s == '+') {
                if(!(eseen && *(s-1) == 'e')) {
                    return false;
                }
                if(!(*(s+1) >= '0' && *(s+1) <= '9')) {
                        return false;
                }
            } else if(*s == ' ') {
                do {
                    s++;
                } while(*s == ' ');
                if(*s != '\0') {
                    return false;
                } else {
                    continue;
                }
            } else {
                return false;
            }
            s++;
        }
        return true;
    }
};

Text Justification

Q:
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

T:
Very tedious problem.

A:

class Solution {
public:
    vector fullJustify(vector &words, int L) {
        vector< string > ret;
        
        int n = words.size();
        int i=0;
        while(i < n) {
            int sz = 0;
            int start = i;
            while(i < n) {
                sz += words[i].size() + 1;
                if(sz > L+1) {
                    sz -= words[i].size() + 1;
                    break;
                }
                i++;
            }
            int end = i;
            int num = end - start;
            int extra = L + (num>1?1:0) - sz;
            num = (num>1?(num-1):1);
            int epw = extra/num;
            int left = extra%num;
            string line = "";
            for(int j=start; j start && j0?1:0);
                    if(end == n) {
                        ex = 0;
                    }
                    string spaces(words[j].size()==L?0:(1+ex), ' ');
                    line += spaces;
                }
                left--;
            }
            if(end == n) {
                int tail = L - line.size();
                string spaces(tail, ' ');
                line += spaces;
            }
            ret.push_back(line);
        }
        return ret;
    }
};

Coins in a Line

http://leetcode.com/2011/02/coins-in-line.html