td.abinesh
BAN USER[Edit based on Alex's comment: The solution assumes that diagonal points of a square are enough to form squares. This does not work for the problem stated originally]
Maintain N series buckets and P series buckets.
N0 will contain all points(x,y) such that x-y=0
N1 will contain all points(x,y) such that x-y=1
Ni will contain all points(x,y) such that x-y=i
P0 will contain all points(x,y) such that x+y=0
P1 will contain all points(x,y) such that x+y=1
Pi will contain all points(x,y) such that x+y=i
For each bucket with size b, there are bC2(b choose 2) combinations of points that can combine to form a square.
Add these numbers for each bucket to get final number of squares possible.
O(n) time complexity. O(3n) space complexity as each point will be in both N and P buckets.
Nodes we are interested in are: kth level grand parent and kth level grand children
To find kth level grand parent:
1. Get BFS trace till you encounter N in the tree.
2. In this trace array, parent node's index=floor(a node's index/2). Use this to go up k levels terminating if you hit zero before kth grand parent.
To find kth level grand children: BFS or DFS till level k
Python:
Can be improved though
def split_into_four(a):
sub_parts = []
for (left, right) in [(0, len(a) / 2), (len(a) / 2, len(a))]:
sub_parts.append([v[0:len(v) / 2] for v in a[left:right]])
sub_parts.append([v[len(v) / 2:len(v)] for v in a[left:right]])
return sub_parts
Maintain a Trie structure for dictionary of words.
Traverse the tree from root node as you parse and print each character in the string.
When trie tells you that you have successfully traversed a word, print space and start over from root for remaining characters.
Oh, sorry, looks like I misinterpreted the question. I now wonder why I assumed diagonal points of a square are enough to form one. My solution works only for such scenarios. Sorry for the confusion.
- td.abinesh February 04, 2013