leetCode Question: Bulls and Cows

Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

Secret number: "1807"
Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".

Please note that both secret number and friend's guess may contain duplicate digits, for example:

Secret number: "1123"
Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

Analysis:

It is not hard to discover that if we search the number and guess pair, a "bull" is straightforward to check and count, and also once we have a "bull", it can be viewed as "consumed". We don't have to store it anymore and it will not effect the counting for "cows".

Now the only problem is to handle the "cows". We could use hash map (hash table) to store the count numbers in secret and guess, respectively. It is OK to keep one hash table and search the sequence multiple times. Here, we want to search the whole sequence just once for better efficiency, two hash table are kept.

There are several cases when we go through the sequence and compare the number in secret (denoted as s[ ] ) and guess (denoted as g[ ] ), we also denote mp_s as the hash map for s[ ] and mp_g as the hash map for g[ ]:

• s [ i ] == g [ i ], then it is a "cow", just add the cow count.

• s [ i ] != g [ i ], the below 4 sub cases indicated that: We have the number g[ i ] at hand, check if it has occurred in secret. And then we have the number s[ i ] at hand, check if it has occurred in guess.

  • mp_s[ g[i] ] doesn't exist. It means currently g[i] is not a bull, but we are not sure if it is a bull in the future. E.g.,
    s = [1 2 0 3]
    g = [3 2 0 0]
    when i = 0, 1 != 3, 3 is not a bull for now, but 3 is a bull if we search until the end of sequence.
    Thus, we have to save the g[ i ] in mp_g for later.
  • mp_s[ g[i] ] exists and > 0. It means there is a char g[ i ] in the secret sequence, that is a "bull". So we subtract the value stored in mp_s[ g[i] ] and add the bull count. The reason of >0 condition is for the case of duplicates, if we have already consumed a "bull", the key is still there but value might be <= 0.
  • mp_g[ s[ i ] ] doesn't exist. Similarly, we also store the s[ i ] for later. E.g,
    s = [1 8 0 7]
    g = [5 8 1 6]
    when i = 0, s[i] = 1, which has no match, but later when i = 2, g[ 2 ]=1. g[ 2 ] and s[ 0 ] is a "bull".
  • mp_g[ s[i] ] exists and >0.

Code(C++):

class Solution {

public:

string getHint(string secret, string guess) {

int b = 0;

int c = 0;

int mp1[10] = {0,0,0,0,0,0,0,0,0,0};

int mp2[10] = {0,0,0,0,0,0,0,0,0,0};

for (int i=0;i<secret.size();i++){

if (secret[i] == guess[i]) {

b += 1;

}else{

if (mp1[guess[i]-'0']==0){

mp2[guess[i]-'0'] +=1;

}else{

mp1[guess[i]-'0'] -=1;

c += (mp1[guess[i]-'0']>=0);

}

if (mp2[secret[i]-'0']==0){

mp1[secret[i]-'0'] +=1;

}else{

mp2[secret[i]-'0'] -=1;

c += (mp2[secret[i]-'0']>=0);

}

}

}

return to_string(b) + "A" + to_string(c) + "B";

}

};

Code(Python):

class Solution(object):

def getHint(self, secret, guess):

"""

:type secret: str

:type guess: str

:rtype: str

"""

b = 0

c = 0

mp1 = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}

mp2 = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}

for i in range(len(secret)):

s = secret[i]

g = guess[i]

if s == g:

b += 1

else:

if mp1[g] == 0:

mp2[g] += 1

else:

mp1[g] -= 1

c += mp1[g]>=0

if mp2[s]==0:

mp1[s] += 1

else:

mp2[s] -= 1

c += (mp2[s]>=0)

return str(b) + "A" + str(c) + "B"

leetcode Question: Contains Duplicate II

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and jis at most k.

Analysis:

Same idea as previous question that Hash table is used. The only difference if the requirement of minimum distance between the same elements is at most k.

Remember that previous question, we set the value of hash table True/False, in this question, we change that to the index of element. Therefore we can keep tracking the distance between the two elements. A simple check can solve the problem.

Code(C++):

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if (nums.size() == 0 ){
            return false;
        }
        map<int,int> mp;
        for (int i=0;i<nums.size();i++){
            if (mp.find(nums[i])==mp.end()){
                mp[nums[i]] = i;
            }else{
                if (i - mp[nums[i]] <= k){
                    return true;
                }else{
                    mp[nums[i]] = i; //Update the position
                }
            }
        }
        return false;
    }
};

Code(Python):

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if len(nums) == 0:
            return False
        mp = {}
        for i in range(len(nums)):
            # Note: here you cannot use "if not "
            # because if mp[nums[i]] == 0, if not will also return True
            if mp.get(nums[i]) == None:
                mp[nums[i]] = i
            elif (i - mp[nums[i]]) <= k:
                return True
            else:
                mp[nums[i]] = i
        return False

leetcode Question: Contains Duplicate

Contains Dulplicate

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.

Analysis:

This is an easy question and there are many ways to do it.

One way is to firstly sort the array, and check each two elements to see if they are equal.

Another way is to utilize the hash map (map in C++ STL), create the map at the same time check if there exists any duplicates.

Code(C++):

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size()==0){
            return false;
        }
        map<int, bool> mp;
        for (int i=0;i<nums.size();i++){
            if (mp.find(nums[i])==mp.end()){
                mp[nums[i]] = true;
            } else{
                return true;
            }
        }
        return false;
    }
};

Code(Python):

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) == 0:
            return False
        mp = {}
        for num in nums:
            if not mp.get(num):
                mp[num] = True
            else:
                return True
        return False
            

leetcode Question: Majority Element

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Analysis:

This a simple question that hashmap (dict) is all we need.
Construct a hashmap that the key is each element in the num, the value is the occurrence of num.
Check the value while constructing the map can get the result.

Code(C++):

class Solution {
public:
    int majorityElement(vector<int> &num) {
        map<int,int> mp;
        for (int i=0;i<num.size();i++){
            if (mp.find(num[i]) == mp.end()){
                mp[num[i]] = 1;
            }else{
                mp[num[i]] += 1;
            }
            if (mp[num[i]] > num.size()/2){
                return num[i];
            }
        }
    }
};

Code(Python):

class Solution:
    # @param num, a list of integers
    # @return an integer
    def majorityElement(self, num):
        dict = {}
        for n in num:
            dict[n] = dict.get(n,0) +1
            if dict[n] > len(num)/2:
                return n

leetcode Question: Repeated DNA Sequences

Repeated DNA Sequences

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,

Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Analysis:

This problem is straightforward (no need to think about KMP algorithm), only dictionary (hashmap) can pass the OJ.
Since there are many restrictions in this problem, it becomes much easier. E.g., only four chars are occurred in the sequence (A,T,C,and G), only length-10 substr is needed.
So the algorithm goes as follows:
1. Search from the start of the string, get every substr with length 10.
2. Construct and look up a hashmap, add 1 to the value.
3. After the whole search, check every entry in the hashmap, if the value is greater than 1, output.

Note that in the C++ OJ, when using string as the map key, the will cause an memory exceeded error. So, I map the string to long int, which is used as the key. Results are mapped back to string and output.

Code(C++):

class Solution {
public:
    long str2long(string s){
        long res = 0;
        for (int i=0;i<10;i++){
            if (s[i] == 'A'){res = res*10 + 1;}
            if (s[i] == 'T'){res = res*10 + 2;}
            if (s[i] == 'C'){res = res*10 + 3;}
            if (s[i] == 'G'){res = res*10 + 4;}
        }
        return res;
    }
    string long2str(long s){
        string res = "";
        for (int i=0;i<10;i++){
            int d = s%10;
            if (d == 1) {res= "A" + res;}
            if (d == 2) {res= "T" + res;}
            if (d == 3) {res= "C" + res;}
            if (d == 4) {res= "G" + res;}
            s = s /10;
        }
        return res;
    }
    vector<string> findRepeatedDnaSequences(string s) {
        int n = s.size();
        map<long, int> d;
        vector<string> res;
        for (int i=0;i<n-9;i++){
            string sub = s.substr(i,10);
            long idx = str2long(sub);
            if (d.find(idx) == d.end()){
                d[idx] = 0;
            }else{
                d[idx] = d[idx] + 1;
            }
        }
        for (auto it= d.begin();it!=d.end();it++){
            if (it->second >= 1){
                res.push_back(long2str(it->first));
            }
        }
        return res;
        
    }
};

Code(Python):

class Solution:
    # @param s, a string
    # @return a list of strings
    def findRepeatedDnaSequences(self, s):
        n = len(s)
        d = {}
        res = []
        for i in range(n):
            substr = s[i:i+10]
            d[substr] = d.get(substr,0) + 1
        for key, val in d.items():
            if val > 1:
                res.append(key)
        return res
        

[Re-View]Hash Table (Basics)

Hash table Basics

Intro

The concept, usage and implementations of Hash table are always used in Software Engineer interviews. From the interview guidance of Google, there is an requirement of hash table. It is said "Hashtables: Arguably the single most important data structure known to mankind." There is indeed a bunch of knowledge and techniques for hashtables (hash function, collision, etc.), but from the interview perspective, it is not possible to test the thorough and complete skills of hashtables in a short interview. Take this advantage, in this post, I'd like to learn the basics of hash tables, and try to implement sample code.

What is Hash Table?

It is a very common but often occurred question in IT interviews. I generalize the concept in my own words: " Hash table, is a data structure, which stores key-value pairs, the access of value by key can be O(1) time, a hash function is used to map the key to the index of the value."

You can find many many definitions of hash table, generally speaking, you can imagine hash table is an array, originally we access an element in array by using index, e.g. A[1], A[2]. However in hash table, we access element by the key,  e.g. A["Monday"], D["Marry"].  The great advantage of it is the speed to look up an element (O(1) time). 

How does Hash table works

Firstly, hash tables can be implemented based on many data structures, e.g. Linked list, array and linked list, binary search tree, etc. The idea is to store the <key, value> pair and build a way to access it. For better understanding, just consider an array, we put the <key, value> in a specific order. The way to locate the <key, value> using the key is called hashing. We can consider a hash function takes the key as the input, and output the location of the <key, value> in the array. A simple hash function is to used "mod" operation.  Use the "key mod array size" to get the hash, the index of the desired value. 

An example

Let's see a simple example.

We have a storage of  size 5:

idx      key       value

0         -1           0

1         -1           0

2         -1           0

3         -1           0

4         -1           0

key=-1 means the slot is empty.

The hash function is   hash(key) = key % 5;

First we insert <12, 12>  (first is key, second is value)

Compute the hash(12) = 2;

Store the <key, value> into the storage of idx 2.

idx      key       value

0         -1           0

1         -1           0

2         12          12

3         -1           0

4         -1           0

Next we insert <29,29>, hash(29)=4;

idx      key       value

0         -1           0

1         -1           0

2         12          12

3         -1           0

4         29          29

Then we insert <27,27>, where the hash code is 2. When we check the location 2, it is already in use. 

It is called a collision, where different key are mapped into same hash code. To deal with the collision, there are many methods, such as, chaining (use a linked list for each location), and rehashing (second function is used to map to another location). Usually we need to know at least these two kinds of methods.

Here we use the rehashing.  

The rehashing function is:  rehash(key) = (key+1)%5;

So, continue the above step, rehash(2) = 3; location 3 is empty, then store the <27,27> to location 3.

idx      key       value

0         -1           0

1         -1           0

2         12          12

3         27          27

4         29          29

If we further insert <32,32>, hash(32) = 2; location 2 is in use, rehash(2) = 3, location 3 is also in use,

Then rehash again, rehash(3) = 4, no available, rehash(4) = 0, OK! Store <32, 32 > in 0th slot.

idx      key       value

0         32          32

1         -1           0

2         12          12

3         27          27

4         29          29

That is the basic way of insert operation for a hash table.

To retrieve the value, e.g. we want to find the value of key <27, ?>, hash(27) = 2, check the key stored in location 2 , which is 12 !=27, then rehashing is need, rehash(2) = 3,  the key is 27, then return the value 27.

A simple implementation (in C++)

#include <iostream>


using namespace std;

const int sz = 5;

struct data{
 int id;
 int val;
};

class Hashtable{
 data dt[sz];
 int numel;
public:
 Hashtable();
 int hash(int &id);
 int rehash(int &id);
 int insert(data &d);
 int remove(data &d);
 int retrieve(int &id); 
 void output();
};


Hashtable::Hashtable(){
 for (int i=0;i<sz;i++){
   dt[i].id = -1;
dt[i].val = 0;
 }
 numel = 0;
}

int Hashtable::hash(int &id){
 return id%sz;
}

int Hashtable::rehash(int &id){
 return (id+1)%sz;
}

int Hashtable::insert(data &d){
 if (numel<sz){
   int hashid = hash(d.id);
if (hashid>=0 && hashid < sz){
 if (dt[hashid].id==-1 || dt[hashid].id==-2){
   dt[hashid].id = d.id;
   dt[hashid].val = d.val;
           numel++;
   return 0;
 }else{
   cout << "collision! rehashing..." <<endl;
   int i=0;
   while (i<sz){
     hashid = rehash(hashid);
 if (dt[hashid].id==-1 || dt[hashid].id==-2){
   dt[hashid].id = d.id;
   dt[hashid].val = d.val;
   numel++;
   return 0;
     }
 if (i==sz){return -1;}
 i++;
}
 }
}
 }else{return -1;}
}

int Hashtable::remove(data &d){
 int hashid = hash(d.id);
if (hashid>=0 && hashid < sz){
 if (dt[hashid].id==d.id){
   dt[hashid].id = -2;
   dt[hashid].val = 0;
   numel--;
   return 0;
 }else{
   int i=0;
   while (i<sz){
     hashid = rehash(hashid);
 if (dt[hashid].id==d.id){
   dt[hashid].id = -2;
   dt[hashid].val = 0;
   numel--;
   return 0;
     }
 if (i==sz){return -1;}
 i++;
}
 }
}
}

int Hashtable::retrieve(int &id){
 int hashid = hash(id);
 if (hashid>=0 && hashid < sz){
   if (dt[hashid].id==id){
 return dt[hashid].val;
}else{
  int i=0;
   while (i<sz){
     hashid = rehash(hashid);
 if (dt[hashid].id==id){
   return dt[hashid].val;
 }
 if (i==sz){return 0;}
 i++;
}
}
 }
}

void Hashtable::output(){
 cout << "idx  id  val" << endl;
 for (int i=0;i<sz;i++){
   cout << i << "    " << dt[i].id << "    " << dt[i].val << endl; 
 }
}


int main(){
 Hashtable hashtable;
 data d;
 d.id = 27;
 d.val = 27;
 hashtable.insert(d);
 hashtable.output();
 
 
 d.id = 99;
 d.val = 99;
 hashtable.insert(d);
 hashtable.output();
 
 d.id = 32;
 d.val = 32;
 hashtable.insert(d);
 hashtable.output();
 
 d.id = 77;
 d.val = 77;
 hashtable.insert(d);
 hashtable.output();
 
 //retrieve data
 int id = 77;
 int val = hashtable.retrieve(id);
 cout << endl;
 cout << "Retrieving ... " << endl;
 cout << "hashtable[" << id<< "]=" << val << endl;
 cout << endl;
 
 
 //delete element
 d.id = 32;
 d.val = 32;
 hashtable.remove(d);
 hashtable.output();
 
 d.id = 77;
 d.val = 77;
 hashtable.remove(d);
 hashtable.output();
 
     
 return 0;
}

 

leetcode Question 129: Longest Consecutive Sequence

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Analysis:

At first glance, the "longest" requirement may lead us to DP. But this problem actually tests data structure rather than a certain algorithm.

If there is no O(n) requirement, we can just sort the array (O(n log n)), then find then longest sequence after a scan.

With the time limit O(n), first of all, what comes to my mind is HASH MAP! Because hash map searches value by key in O(1) time. Note that in C++ STL, the map<> data structure is implemented by BST, so the insert in O(log n), therefore we need to use the unordered_map<>, which has O(1) time complexity.

Firstly, we put all the element into a map.
Secondly, how to find the consecutive elements? Since the O(n) requirement, scan the array is a must.
For each element, we need to find its consecutive elements. Consecutive means +1 or -1, a while loop is enough to handle. Search two directions respectively (+1, -1),  during the search if the key is found, remove the current item in the map. This is because if two items are consecutive, the longest elements for this two are the same, no need to search again. In this way, the length of longest consecutive elements can be easily found.

Note that in C++ map<>, find(key) function will return  the end() iterator if key does not exist, But if we use (mp[key]==false), when key is not in the map, the program will insert the key into the map with a default value, so use find function is a safer way.

Code (C++):

class Solution {
public:

    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<int,bool>mp;
        for (int i=0;i<num.size();i++){
            mp[num[i]]=true;
        }
        
        int res=0;
        for (int i=0;i<num.size();i++){
            int mx=1;      
            int fd = num[i];
            
            mp.erase(num[i]);
            while (mp.find(fd+1)!=mp.end()){
                mx++;
                mp.erase(fd+1);
                fd++;
            }
            
            fd = num[i];
            while (mp.find(fd-1)!=mp.end()){
                mx++;
                mp.erase(fd-1);
                fd--;
            }
            
            if (mx>res){res=mx;}
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        dic = {}
        maxlen = 1
        for n in num:
            dic[n] = 1
        for n in num:
            if dic.has_key(n):
                tmp = n + 1
                l = 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp+=1
                tmp = n - 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp-=1
                maxlen = max(l, maxlen)
            else:
                continue
        return maxlen