DOJ will file antitrust charges against...

Hey,

Hope you’re all having a fantastic day! Here’s your Interview Problem and Industry new for the day.

Interview Problem

Given an n-ary tree, return the level order traversal of it’s nodes values.

Industry News

• Department of Justice plans to file antitrust charges against Google as soon as this month - Attorney General William P. Barr is said to be keen to bring antitrust charges against Google. A DOJ lawsuit would have bipartisan support as a coalition of the 50 states and territories have already said they support antitrust action against Google. However, there is still disagreement on how exactly to move forward, with some lawyers in the DOJ arguing that the case is progressing too quickly.

• Uber expanding into new business lines - Uber announced they’re launching car rentals in the UK after trials in Australia and France. The company has also launched an on-demand grocery delivery service in Latin America and Canada and has even partnered with a commuter riverboat service in London to launch Uber Boat. In addition, the company acquired Postmates earlier this year in a bid to rapidly expand it’s food delivery services.

• Qualcomm-powered Chinese XR startup Nreal raises $40 million - Nreal is one of the most anticipated mixed-reality startups in China and it just secured $40 million in a Series B round. The headset they’re developing is extremely light at only 88 grams and it’s part of the “mixed reality” trend. It combines light from your outside environment with generated light to give you a view of reality interlaced with software-generated images.

Previous Solution

As a refresher, here’s the previous interview question

You are given a string as input. Write a function to check if the letters in the string can be rearranged to form a palindrome (or if the input is already a palindrome). You can ignore spaces in the string.

Input - “car race”

Output - True (the letters can be rearranged to form “racecar”)

Solution

The question is whether we can find a permutation of the string (ignoring the spaces) that is a palindrome.

The “naive” way of solving this is to find every possible permutation and check if there are any palindromes. That would take at least O(n!) time since there are n! possible permutations. Can we do better?

If we look at the properties of palindromes, we see that they can either have an even length or an odd length.

If they have an even length, then each character in the right side of the palindrome must have a matching character in the left side of the palindrome (that way it can be reversed). Therefore, each character must appear an even number of times.

For odd length palindromes, we have the same situation, except for one character that will appear an odd number of times. That character will be in the middle of the string.

Therefore, to solve this, we can just use a dictionary (hash table) to count the occurrences of each character in the string.

There should be at most one character that appears an odd number of times, and every other character should appear an even number of times. If this is the case, then this string can be rearranged to form a palindrome.

You can view a REPL with the code and testcases here.

The time and space complexities are both linear.