[AC Question]

Suddenly, I find most of my contact (some random pattern) in my Samsung Note 4 are deleted. These are sync with Google Contacts and hence tried to sync, but sync seem to having issues. Deleted/ added my google account, restarted the phone several times, but the issue seems to still exist.

[Crashdamage]

If you have been saving your contacts to your Google account as you say you were, you should be OK. This will restore them to any point they were at in the last 30 days:

https://support.Google.com/mail/answer/1069522?hi=en

Because contacts apparently got fouled up on the phone, I recommend that before you go online and restore your contacts you should do the following so the phone doesn't scramble the contacts again:

Go to: Settings > Accounts > Google > Select account > Disable contacts sync.

Then remove contacts on the phone: Settings > Apps > All > Contacts > Force stop > Clear cache > Clear data.

Restore your contacts online. Then go back and enable contacts sync. They should sync to the phone and you should be good to go.

Android since v1.0. Linux since 2001.