Indeed interview-Reverse string but let the html entity remain unchanged

One of the popular interview questions of Indeed

is to reverse the string but let the html entity remain unchanged.

For example :

The result of  "123&TWD;432&JPY;"should be &TWD;234&JPY;321


Solution: What we need to do is store the entities and insert them into the reversed string.

Read More

Leetcode--Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Solution:

This is a 26-ary system. However if we use 1-26. 26 can not be consistent with other numbers ahead.

For example: 25/26=0, but 26/26=1. So we need to apply 0-based policy in this problem.

Each number from 1-26 minuses 1 to conform A-Z. But new problems occur, AA should be 27

orginally, 27-1=26, 26%26=0. This is incorrect. So every number should minus 1 in each loop to

make sure it's 0-based.

1. class Solution {
2. public:
3.     string convertToTitle(int n) {
4.        
5.         string ans;
6.         while (n--!= 0) {
7.             ans = char(int('A') + n % 26) + ans;
8.             n /= 26;
9.         }
10.         return ans;
11.  
12.     }
13. };

Read More

Leetcode-Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

Solution : 

The idea to solve this problem is quite simple.  We can just move all the elements of nums1 to one

container then check every element in nums2 to derive the result. Noted that the result should not 

contain duplicate values. So we can use SET in STL to accomplish this work since the set will ignore

the duplicate values when adding new elements into it.

1. class Solution {
2. public:
3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
4.        
5.         set<int> SET (nums1.begin(),nums1.end());
6.         set<int> result;
7.        
8.         for(auto i:nums2)
9.             if(SET.count(i)) result.insert(i);
10.        
11.         return vector<int>(result.begin(), result.end());
12.        
13.     }
14. };

Read More

Leetcode--Summary Range

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Solution: 

We can use two pointers to record the start and the end of each range.

1. class Solution {
2. public:
3.     vector<string> summaryRanges(vector<int>& nums) {
4.        
5.        
6.         vector<string> result;
7.        
8.         int n = nums.size();
9.         if(n == 0)return result;
10.         if(n == 1){
11.              result.push_back(to_string(nums[0]));
12.              return result;
13.         }
14.        
15.         int start=nums[0];
16.         int end=nums[0];
17.  
18.        
19.        for(int i = 0; i < n;){
20.              
21.             while( i+1 < n && nums[i+1] == end + 1){
22.                 end++;
23.                 i++;
24.             }
25.             if(start != end){
26.                 result.push_back(to_string(start) + "->" + to_string(end));
27.             }
28.             else{
29.                 result.push_back(to_string(start));
30.             }
31.            
32.             i++;
33.             start = end = nums[i];
34.            
35.         }
36.        
37.         return result;
38.  
39.     }
40. };

Read More

Leetcode- Merge two sorted list

Merge two sorted linked lists and return it as a new list.

 The new list should be made by splicing together the nodes of the first two lists.

Solution： Make a temp node to point to the head pointer of result. 

Then we put each element into the list and return the head of the pointer at last.

class Solution {
public:
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *tmp = dummy;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                tmp->next = l1;
                l1 = l1->next;
            } else {
                tmp->next = l2;
                l2 = l2->next;
            }
            tmp = tmp->next;
        }
        if (l1 != NULL) tmp->next = l1;
        else tmp->next = l2;
        return dummy->next;
    }
};

Read More

Leetcode - Two sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution： Using Hashmap in C++

The core idea is to see where there is the value 「Target-nums[i]」in the hashmap.

For example : Now the index is in "0" and nums[0] is 2, if there is a solution pair with nums[0]

in the future, the other value should be Target-nums[0] =7. So we will search the Target-nums[i]

value before we insert new elements to the hashmap.

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& nums, int target) {
4.        
5.         vector<int> res;
6.         unordered_map<int,int> hashmap;
7.        
8.         for(int i=0;i<nums.size();i++){
9.             if(hashmap.find(target-nums[i])!=hashmap.end()){
10.                 res.push_back(hashmap[target-nums[i]]);
11.                 res.push_back(i);
12.                 return res;
13.             }
14.            
15.             hashmap[nums[i]]=i;
16.            
17.         }
18.         res.push_back(-1);
19.         res.push_back(-1);
20.         return res;
21.     }
22. };

Read More

Difference between overriding and overloading in Java

Method Overloading

deals with the notion of having two or more methods in the same class with the same name but different arguments.

1	static int binarySearch(byte[] a, byte key);

2	static int binarySearch(byte[] a, int fromIndex, int toIndex, byte key)

Method Overriding

means having two methods with the same arguments, but different implementations. One of them would exist in the parent class, while another will be in the derived, or child class. 

01	class Animal{

02	protected int legs = 1;

03	public int getLegs(){

04	return legs*4;

05

}

06

}

07	class Bird extends Animal{

08	public int getLegs(){

09	return legs*2;

10

}

11

}

Also the dynamic binding and static binding issues are related to this topic

Look at the examples below

We overload the eat method

public class Animal{}


public class Dog extends Animal{}

public class AnimalActivity{

    public void eat(Animal a){
       System.out.println("Animal is eating");
    }

    public void eat(Dog d){
       System.out.println("Dog is eating");
    }
}

then in the main class:

public static void main(String args[])
{
    Animal a=new Animal();
    Animal d=new Dog();
    AnimalActivity aa=new AnimalActivity();
    aa.eat(a);
    aa.eat(d);
}

the result in both two cases will be: Animal is eating

Then we try to override the eat mehod of Animal class

public class Animal{
    public void eat(){
System.out.println("Animal is eating");
}
}

then:

public Class Dog extends Animal{
public void eat(){
    System.out.println("Dog is eating");
    }
}

then in the main class:

public static void main(String args[]){
Animal d=new Dog();
Animal a=new Animal();
a.eat();
d.eat();
}

now the result should be:
Animal is eating
Dog is eating
So we can conclude here
Overloading binds at compile time "static binding"  while
Overriding binds at run time "dynamic binding"

Read More