A Backbase assignment for Android engineering positions provided by Mohamed Nabil.
- User can search for a city by name.
- A map shows the city location.
- Info screen displays all data for a city.
- A dynamic UI that can adapt the screen orientation.
- Built with MVP (Model–view–presenter).
- Used Jackson for fast deserialization of the cities.json file.
- Used a Prefix Trie data structure (because it is has a very effective retrieval time).
Trie is an efficient information reTrieval data structure. Using Trie, search complexities can be brought to optimal limit (key length).
Every node of Trie consists of multiple branches. Each branch represents a possible character of keys. We need to mark the last node of every key as end of word node.
Inserting a key into Trie is a simple approach. Every character of the input key is inserted as an individual Trie node. If the input key is new or an extension of the existing key, we need to construct non-existing nodes of the key, and mark end of the word for the last node. If the input key is a prefix of the existing key in Trie, we simply mark the last node of the key as the end of a word. The key length determines Trie depth.
Searching for a key is similar to insert operation, however, we only compare the characters and move down. The search can terminate due to the end of a string or lack of key in the trie.
Insert and search costs O(key_length)
, however the memory requirements of Trie is O(ALPHABET_SIZE * key_length * N)
where N is number of keys in Trie.
Just import the project and hit run
button.
$ adb shell am start -n 'com.mohamedmenasy.backbasetask/com.mohamedmenasy.backbasetask.core.view.MainActivity'
There are many test cases covers the testing of Trie implementation, presenters and ui test of all activities using espresso.
./gradlew testDebugUnitTest --tests com.mohamedmenasy.backbasetask.data.TrieTest
./gradlew testDebugUnitTest --tests com.mohamedmenasy.backbasetask.presenter.*
$ adb shell am instrument -w -r -e debug false -e class 'com.mohamedmenasy.backbasetask.view.MainActivityTest' com.mohamedmenasy.backbasetask.test/androidx.test.runner.AndroidJUnitRunner
$ adb shell am instrument -w -r -e debug false -e class 'com.mohamedmenasy.backbasetask.view.InfoActivityTest' com.mohamedmenasy.backbasetask.test/androidx.test.runner.AndroidJUnitRunner
$ adb shell am instrument -w -r -e debug false -e class 'com.mohamedmenasy.backbasetask.view.AboutActivityTest' com.mohamedmenasy.backbasetask.test/androidx.test.runner.AndroidJUnitRunner
- Use Ternary Search Tree and test the performance.
- Mohamed Nabil - Initial work - linkedin