[Java] Find longest increasing or decreasing subsequence

 As second question from the last exercise, there was this. Given an input such as:

[
   [true, true, true, false],
   [true, false, false, false, false],
   [true, true, true, true, true, true, false, false]

]
 

Where each internal array ALWAYS has at least 2 elements and starts with a "true". Also, after the first "false" there can ONLY be "false" until the end of the array.

We calculate for each of these arrays the percentage of false elements over all elements, call it pct.

We then look for the longest strictly increasing pct sequence.

An empty input list or a list of only one element should return 0, in all other cases, the sequence starts counting AFTER the starting element.

[Java] Binary search find first and last occurrence

We saw how to implement binary search both recursively and iteratively, however if the input has duplicates, the result we get is just one possible occurrence of the item.

If we want to find the very first or very last occurrence of the item, we need to tweak the search a bit.

Specifically, we use a temporary variable initialized to -1 and if we find the item in the mid position, we do NOT return yet; instead, we store the matching position in this variable and continue the search as if we hadn't found the element yet.

We do NOT simply walk left or right from there, otherwise we go back to O(N) time.

If we are looking for the first occurrence, we continue the search on the left of the middle, since any prior duplicate must be there. Otherwise we continue on the right, since the last occurrence must be after the current item.

The important part is that at each new step, IF we find the element, we update our temporary result since we're getting closer to the first or last occurrence we want.

At the end, we either did not find the element, so return our default -1 from the temporary result, or we have the exact first or last location of the element there.

This logic is easily implemented iteratively, otherwise in the recursive case we would need to pass an additional variable as input to track the last found occurrence. Up to you whatever road you prefer.

You can check my implementations of binarySearchFirstOccurrence and binarySearchLastOccurrence on my Gist alongside tests in BinarySearchFirstOccurrenceJTests and BinarySearchLastOccurrenceJTests

For the recursive version check out instead binarySearchFirstOccurrenceRecursive and binarySearchLastOccurrenceRecursive on my Gist alongside tests in BinarySearchFirstOccurrenceRecursiveJTests and BinarySearchLastOccurrenceRecursiveJTests

 

Note that the code has been tweaked to make it generic, and can be further improved by accepting a Comparator in input, which would allow the search to work correctly also for elements that are not following natural ordering.

[Java] Binary search on array

While doing another exercise, I needed to use binary search on an array and I realised I never published any code for that.

Let's remedy this. Important things to remember: array MUST be sorted, if not the logic makes no sense, finally the magic formula:

int mid = floor + ((ceil - floor) / 2);

Burn it in your mind and you'll forever be good to go. 

That's necessary because we alternate between sections of the array, so we won't always start from floor at position 0 and therefore need to offset our starting position everytime to the new floor.

Also I was checking how to make it generic, the change would simply be to modify the declaration of the method to:

 public static <T> int binarySearch(T[] elements, T element)  

And then invoke as:

 ArrayUtils.<TYPE>binarySearch(collection, element)  

However, since you are comparing elements in the collection, your generic type MUST offer the compareTo method to be used in place of integer comparison.

You can find my implementation of binarySearch for integer arrays on my Gist along with some tests in BinarySearchJTests.
An iterative version is proposed in binarySearchIterative along with some tests in BinarySearchIterativeJTests.

[Java] Find minimum highest calculated value in ordered collection

I was searching from some problems online and found a video that poses an interesting one.

We handle Apartment objects that look like this:

Apartment:{

  "gym": false,

  "school": true,

  "store": false

} 

The values true/false indicate that the specific facility is present (true) or not (false) at that apartment. If a facility is present at an apartment, the travel distance from the apartment to the facility is 0.

If a facility is not present at an apartment, it might be present at a farther apartment. In that case, the travel distance is equal to the number of apartments you must cross to reach that facility.

An array of Apartments is given in input as well as a collection of facilities that are relevant for us, for example:

["gym","school"]

The goal of the exercise is to find which apartment minimizes the maximum travel distance to any relevant facility (return its index in the input array).

If an apartment has two facilities at distances N and M, the maximum travel distance is the max(N,M), NOT the sum.

If multiple apartments satisfy the requirement, return any of them.

I also added an additional requirement, if NO apartment satisfies the requirements (eg a relevant facility is NOT present at any apartment), return -1.

[Python] Sentiment analysis with NLTK

NLTK is an interesting and powerful Python library to perform text analysis. A common use case is to perform sentiment analysis of some text.

While the configuration can go very deep, here is a sample application to analyse the sentiment of online posts written in English. The first time you execute your program, you will be prompted to download data for NLTK, choose the one that best fits your use case.

 import nltk  
 from nltk.sentiment import SentimentIntensityAnalyzer  
   
 #common words that have no impact on the overall analysis  
 stopwords = nltk.corpus.stopwords.words("english")  
 sia = SentimentIntensityAnalyzer()  
   
 #strip the STRING text only to relevant words  
 text = ""  
 for word in STRING.split():  
  #stopwords are all provided to us in lowercase  
  if word.lower() not in stopwords:  
   text += word + " "  
   
 #get overall sentiment in this post  
 sentiment = sia.polarity_scores(text)["compound"]  

An honorable mention goes to the pyenchant library, which uses Enchant spellchecker dictionaries and allows to check whether a string is a word in a given language. Additionally, it will match ignoring weird casing:

 import enchant  
   
 english_words = enchant.Dict("en_US")  
 if english_words.check(STRING):  
  #this is an english word  

[Python] Access Twitter tweets with Tweepy

To programmatically access Twitter tweets, you can use Python's Tweepy library.

You must login to Twitter, then apply for developer access. The process is a bit delayed since you will need to wait for Twitter to approve your request (maybe even reply to their emails with additional info), but in general for academic/testing purposes, the approval process takes about 1 week.

Once you're set it is simply a matter of:

 import tweepy  
   
 twitter_auth = tweepy.AppAuthHandler(TWITTER_KEY, TWITTER_SECRET)  
 #twitter limits frequency of polls, we need to slow down automatically. You have about 900 requests/15 minutes  
 twitter_api = tweepy.API(twitter_auth, wait_on_rate_limit=True, wait_on_rate_limit_notify=True)  
   
 #default is 2 weeks of data, the optional input variable since_id is the ID of the last tweet since you want to start polling  
 #we are preparing the request here, but not yet executing it  
 cur = None  
 if since_id is not None:  
  cur = tweepy.Cursor(twitter_api.search, count=TWEET_POLL_LIMIT, include_entities=False, result_type="recent", q=YOUR_HASHTAGS)  
 else:  
  cur = tweepy.Cursor(twitter_api.search, count=TWEET_POLL_LIMIT, include_entities=False, result_type="recent", q=YOUR_HASHTAGS, since_id=since_id)  
   
 #we retrieve the tweets here, we can optionally limit the total we retrieve. If we do not limit ourselves and go over our quota, we are stalled until the next window is available to us  
 #the config we did on the twitter_api object will handle this automatically for us (wait_on_rate_limit) and notify us as well (wait_on_rate_limit_notify)  
 tweets = None  
 if TWITTER_POST_LIMIT == 0:  
  tweets = cur.items()  
 else:  
  tweets = cur.items(TWEET_LIMIT)  
    
 for tweet in tweets:  
  #do something  

 

Some things to note:

Your query rate will likely be limited, currently the free tier has a 900 requests/15 minutes quota. If you go over that quota, your app will stall and can only resume after the quota is reset.

 

The output of the poll is a set of tweets which are simply JSON, some notable fields:

• id: unique ID of this tweet
• created_at: a string representation of the datetime when this tweet was created
• text: the body of the tweet

 

Strangely, the created_at value is NOT an epoch but a human readable string, to convert it to date you can:

 parsed = datetime.strftime(datetime.strptime(date,'%a %b %d %H:%M:%S +0000 %Y'), '%Y-%m-%d %H:%M:%S')  

And to convert that to epoch you can:

import ciso8601
return int(ciso8601.parse_datetime(parsed).timestamp()) 

To verify if a tweet is a retweet you can check if it starts with RT @:

tweet._json["text"].startswith("RT @")

[Python] Access Reddit posts and comments with PRAW

To programmatically access posts and comments from a Reddit subreddit, you can use Python's PRAW library.

You must login to Reddit, then register your application to get a client ID and secret.

Once you're set is it simply a matter of:

 import praw  
   
 reddit = praw.Reddit(  
   client_id="CLIENT_ID",  
   client_secret="CLIENT_SECRET",  
   user_agent="WHATEVER"  
 )  
   
 submissions = reddit.subreddit("SUBREDDIT_NAME").new(limit=POST_LIMIT)  
   
 for submission in submissions:  
  submission.comments.replace_more(limit=None)  
    
  for comment in submission.comments:  
   #do something  

Some things to note:

A post is represented by a submission object, some interesting attributes are:

• created_utc: the UTC epoch when this post was created
• author
• score: all posts start with score 1 and it changes based on user votes
• title
• selftext: the body of the post

 

To verify if a post was deleted there is unfortunately not a simple way but in general you can consider this rule to be valid:

submission.author is None or not submission.is_robot_indexable or submission.selftext == "[deleted]" or submission.selftext == "[removed]"

Remember however that the [deleted] and [removed] strings are language dependent, therefore based on your settings you might not get them in English.

A comment is represented by a comment object, its body is in the body attribute.

To verify if a comment was posted by a moderator (or a moderator bot), you can check:

comment.distinguished == "moderator"