Screw SQL, let's just use english!
Hey Y’all,
Hope you’re having a terrific day. Here’s your interview problem and industry news for the day.
Daily Interview Problem
You are given a nonnegative integer as input. Write a function that returns the largest integer whose square is less than or equal to the given integer.
For example, if the input is 25, return 5. If the input is 300, return 17.
Industry News
Salesforce has integrated new research in NLP with SQL to build a database you can just talk to - Photon is a natural language interface to databases based on Salesforce’s research in neural semantic parsing. Most SQL operations (including table joins and query compositions) are supported. You can check it out here. NLIDBs (Natural Language Interface to DataBases) in general have been a very hot area of research over the past several years.
White House announces creation of AI and Quantum Research Institutes - The White House today announced the establishment of 12 new research institutes focused on AI and Quantum Information Science. This would be funded with an investment of $1 billion dollars.
Synthego raises $100 million for AI-driven gene editing - Synthego is using machine learning for engineering genomes, offering full-stack genome engineering via CRISPR. The company was founded by two SpaceX engineers who have no background in biotech. They have raised a total of $250 million up to date and are currently hiring full-stack Software Engineers and Data Engineers.
Yesterday’s Solution
As a refresher, here’s yesterday’s problem
You are given a character array containing a set of words separated by whitespace. Your task is to modify that character array so that the words all appear in reverse order. Do this without using any extra space.
Example
input - ['A', 'l', 'i', 'c', 'e', ' ', 'l', 'i', 'k', 'e', 's', ' ', 'B', 'o', 'b']
output - ['B', 'o', 'b', ' ', 'l', 'i', 'k', 'e', 's', ' ', 'A', 'l', 'i', 'c', 'e']
Solution
Let’s try and look at simpler version of this question.
What if every word in the sentence was just one letter? How could we solve it then?
Well, we could solve it by just reversing the character array. You can use the two pointer method to reverse it. One pointer goes at the start of the array and one pointer at the end. You swap the characters at both pointers and then increment the first pointer and decrement the last. You’ll terminate the loop when the two pointers cross.
Now, what about in the general case, where each word can be more than one letter?
In that scenario, reversing the character array gets the words in their correct position, but it causes the letters in the word to appear in reverse order (if that word is longer than 1 letter). We can fix that by reversing the individual words.
Use the two pointer method to reverse the entire character array. Then iterate through the character array and look for each individual word. Use the two pointer method again to reverse each word. That’ll give us the correct answer. It runs in O(n) time and uses O(1) space.