Question

Suppose you are developing part of a social media website.

For the following, write down an algorithm that you would use to accomplish each one of these tasks. Your choice of search algorithm should be selected to complete each task as efficiently as possible

1. A search algorithm to determine the post with the highest number of positive votes (e.g likes)
2. A search algorithm to find all the posts made by a user on a specific date.
3. A search algorithm to determine the first post made by a specific user AFTER a specific date.
4. A search algorithm to find all the posts made by a user between two dates.
5. A search algorithm to find all posts containing a specific pattern of text.

Answer 1

1. For searching a post with highest number of likes

Each post will be having an associated number of likes on that post so first we will start traversing the array/any data structure used to contain the number of likes of the post and have a maximum and compare the next post likes with the current max number of likes. This way space complexity will be O(n). Linear searching is used here.

algorithm:

int max=0,i,maxind=0

int[] likes // likes for each post saved sequentially on timestamp basis

for(i=0;i<likes.length;i++)

if(max<likes[i])

max=likes[i]

maxind=i // save the index to refer the post

else

//do nothing

return max

2. Assuming all the posts made by a user are stored in a sorted order on the basis of their timestamp in an array.

Binary search can be used here.

Algorithm:

dates[] // array of dates

binsearch( dates[] , n, sdate)

left=0,right=0,mid=0

while( left<right)

mid=(right+left)/2

if(dates[mid]==sdate)

while(mid+1<n && dates[mid+1] == key)

mid++

break;

else if (dates[mid]>key)

right=mid

else

left=mid+1

while)mid>-1 && dates[mid]>key)

mid--

return mid+1 // returning mid+1 because of 0 based indexing of array

3. Assuming all the posts made by a user are stored in a sorted order on the basis of their timestamp in an array.(most recent would be the right most element)

Binary search can be used here.It will be almost same as the previous one just the

Algorithm:

dates[] // array of dates

binsearch( dates[] , n, sdate)

left=0,right=0,mid=0

while( left<right)

mid=(right+left)/2

if(dates[mid]==sdate)

while(mid+1<n && dates[mid+1] == key)

mid++

break;

else if (dates[mid]>key)

right=mid

else

left=mid+1

while)mid>-1 && dates[mid]>key)

mid--

return mid+2 // returning mid+1 because of 0 based indexing of array and +1 for the immediate next post

4.   Assuming all the posts made by a user are stored in a sorted order on the basis of their timestamp in an array.(most recent would be the right most element)

ds--> start date de--> end date

Algorithm:

dates[] // array of dates

binsearch( dates[] , n, sdate)

left=0,right=0,mid=0

while( left<right)

mid=(right+left)/2

if(dates[mid]==sdate)

while(mid+1<n && dates[mid+1] == key)

mid++

break;

else if (dates[mid]>key)

right=mid

else

left=mid+1

while)mid>-1 && dates[mid]>key)

mid--

return mid+1 // returning mid+1 because of 0 based indexing of array

// ds is found then de can be found from ds to the end of the array dates using the same algorithm and return all the indexes from ds to de.