Bundle

 I've been busy for the past few days, so I've neglected the AlgoDaily problems. Here's a whole bundle. 

1. Single lonely number.

In a given array of numbers, one element will show up once and the others will each show up twice. Can you find the number that only appears once in O(n) linear time? Bonus points if you can do it in O(1) space as well.

 Solution: Because we're counting how many numbers there are in two's it seemed a bright idea to convert the numbers into binary. To do it in O(1) space you could sum the numbers. It turns out that the best way to do that is using the XOR e.g. a sum without a carry. An XOR of two numbers that are the same is just 0. So in the end when you XOR the binary representations of the numbers in the list, all the doubles will cancel out and you will only be left with the binary representation of the single number. 

 

2. Implement a hash map

 The instructions had an implementation of the hash function. You just take the ASCII representation of the characters in your string and add them together.

In order to hash into buckets you divide the hash function by the number of buckets and take the remainder. That gives you the index of the bucket where you store your data.

 The data in the buckets are tuples (key,value). 

The set method runs the key through the hash function and checks if the key is in the hash table. If it is it appends the key value pair to the list that is the bucket. This is called 'chaining'. Alternatively you could look for other empty buckets, which is called Open Addressing. Anyway, if the bucket is empty it adds the key value pair to the bucket. 

 The get method does the same as the set method, applies the hash function, looks for the key in the address and iterates over the list of key-value pairs if the bucket has more than one. 

For more details, this is a nice blog post: 

https://coderbook.com/@marcus/how-to-create-a-hash-table-from-scratch-in-python/ 

 

3. Binary in-order traversal

This blog post about tree traversal is just the best!

https://medium.com/@nhudinhtuan/binary-tree-traversals-cheat-sheet-for-coding-interviews-a71af9fe1dba

I'll leave this one empty for now. Just refer to the blog post. 

 

4. Sum strings until one

You have to repeatedly add digits in a number until the number has only one digit and you return it. I played around with converting ints into strings and looping over them. There was also a while loop to keep the algorithm running until the length of the sum was 1. 

 

5. Detect a substring in a string

I did this using a for loop and sub-indexing.

 

The code is here: https://github.com/mariakesa/Algorithms/blob/master/AlgoDaily/AlgorithmsPractice.ipynb