☕ Cracking The Coding Interview In Python?
Python Solutions and Explanations for CTCI. Plus, a cool blog post on the fundamentals of Rust. A beginner coding interview question this time and our solution to the last question on palindromes.
Hi Everyone!
Happy New Year!
Tech Dive
Our last tech dives were on Distributed Systems and Database Sharding!
Tech Snippets
Python Solutions and Explanations to all the questions in Cracking the Coding Interview - This is actually being done by yours truly 😉. If you like it, a github star on the repo would be much appreciated!
Cool blog post on learning the fundamental of Rust in a half hour.
The Best Software Every Reverse Engineer Should Have for Cracking Software
Interview Question
You are given an unsorted linked list as input. Write a function that removes duplicate items.
Input - 1 -> 2 -> 1 -> 5 -> 2 -> None
Output - 1 -> 2-> 5 -> None
We’ll send a detailed solution tomorrow, so make sure you move our emails to primary, so you don’t miss them!
Gmail users—move us to your primary inbox
On your phone? Hit the 3 dots at the top right corner, click "Move to" then "Primary"
On desktop? Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen
Apple mail users—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”
Previous Solution
As a refresher, here’s the previous question
You are given a string as input.
Write a function that checks 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.
Example
Input - “car race”
Output - True (the letters can be rearranged to “racecar”)
Solution
In order to solve this, we need to think about the properties of a palindrome. You should write a couple of palindromes down and see if you can notice any patterns.
They either
have an even number of characters
have an odd number of characters, where there’s only one character that appears an odd number of times
In other words, a palindrome is a string that can be reversed to produce the same string.
That means that either every character has a matching pair, or there is one character that appears an odd number of times (and that character must be placed in the middle of the string).
Therefore, we can solve this by counting the number of occurrences of each character with a dictionary.
Each there is at most 1 character that appears an odd number of times, then that means the string can be rearranged as a palindrome.