Find the location of the given string from a sorted array of string which is interspersed with empty strings
Problem
Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string
EXAMPLE
Input: find “ball” in {“at”, “”, “”, "ball”, "”, "”, "car”,“”, "”, "dad”, ”“, ”“}
Output:4
Solution
There are some points in problem sentence. One is a sorted array, and other one is that there are empty strings.
Sorted Array
When we search a object from sorted array, we can use binary search tree. So this problem can be solved by using binary search tree basically.
Array is interspersed with empty strings
But, this array is interspersed with empty string. So if the middle value is empty string, we have to check the left and right side until the string will be exist string.
Source Code
About HashTable in Java
What’s HashMap
HashTable is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array.
Structure Of HashMap in Java
HashMap class in java has array internally to save objects. The objects are Nodes that have key and value.
Hash Function
HashMap has a Hash Function. This function computes the index from inputted key.
Hash Collision
HashTable has a problem. When it computes the index by hash function, the results value of hash function can be identical. This phenomenon is called as Collision. In java, if collision occurs, the object is linked with a node has same index. Therefore, each node in array has Binary Search Tree.
Print all paths which sum to a given value in a Binary Tree
Problem
You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path dose not need to start or end at the root or leaf.
Solution
First, let’s approach this problem by using the Simplify approach.
Simplify Approach
What if the path had to start at the root, but could end anywhere? In this case, we can solve this problem easily by traversing from root node. By in-oder traversal, we add each node value to tmpSum. And when the tmpSum equals given sum, we print the path.
Generalize Solution
Well, What if the path can start from anywhere? In this case, this problem can be solved by checking from the deeper element.
Check if small binary tree T1 is a suibtree of large binary Tree T2
Problem
You have two large binary tree: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
A tree T2 is a subtree of T1 if there exists a node n in T1 such the the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
Solution
This problem can be solved by the following the steps.
- check first node if T1 and T2 if the two data are identical
- if above condition is true, check the left node and right node as well recursively.
- if above condition is false, start from left node or right node of T1.
Source Code
About LinkedList class in Java
What’s LinkedList
The LinkedList class implements the List interface. The structure is Doubly-linked list in java, each node has next node and previous node.
Time Complexity
add(E e) function
This function takes O(1) time. This is because, we only have to reconnect specific nodes.
E remove(int index) function
This function takes O(1) time as well as add(E e) function.
E get(int index) function
This function takes O(N). This is because, we have to traverse the list from first node or last node to target node. we cannot access the node with index.
About ArrayList class in Java
What’s ArrayList
The ArrayList class implements the List interface. ArrayList supports dynamic arrays that can grow as needed.
Standard Java arrays are of a fixed length. After arrays are created, they cannot grow or shrink, which means that you must know in advance how many elements an array will hold.
ArrayList are created with an initial size. When this size is exceeded the collection is automatically enlarged. When objects are removed, the array may be shrunk.
If we set the capacity of the ArrayList as a argument, the ArrayList is created with the capacity.
If the capacity is exceeded, this grow function is called. This method implements copying original array with new capacity.
Time Complexity
add(E e) function
The time complexity of the add(E e) function is 0(1) basically. This is because, ArrayList has internally standard array. But if the capacity of ArrayList is exceeded, it takes 0(N) time in order to copy original array with new capacity.
add(int index, E element) function
In this function case, we have to shift the elements in order to insert the element into middle of the ArrayList. So it takes O(N) time.
remove(int index) function
This method takes O(N) time in order to shift elements as well as add(int index, E element).
E get(int index) function
This method takes O(1) time because we can access the element by index
Find the next node (in-oder traversal) of a given node in a binary search tree
Problem
Write an algorithm to find the next node (i.e., in-oder successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.
Solution
This problem can be solved by thinking the two patterns. First pattern is in case the given node has right node, and second pattern is in case the given node dose not have right node.
the node has right node
In this case, the next node can be calculated by the following steps.
- traverse right node once.
- traverse left node until the left node is null
- when the loop is broken, the node is next node.
This traversal is to bottom.
the node dose not have right node
In this case, the next node can be calculated by the following steps.
- traverse the parent node until the left node of the parent node dose not coincide the current node.
- when the above loop is broken, the node is next node.
This traversal is to up.
