venkat325
BAN USERFor both left and right justification, first do usual step of trying to put the words in each line with single space. Then, if we end up with n spaces at end of line and the next word is larger than n-1, then we need to distribute the n spaces evenly across the line.
For this even distribution, if current spaces upto last word in the line = x, then do
intpart = n/x
remainderpart = n mod x.
Add intpart spaces to all spaces, then starting from first or last, add the reminderpart spaces until they are exhausted.
E.g., if there are 27 spaces at end, and next word is 30 characters, also suppose current line has 11 words or 10 spaces upto last word, then we need to distribute these 27 spaces over the 10 spaces. So 27/10 = 2 int part, 7 reminder part. So we ad 2 spaces to all 10 spaces, and then remaining 7 spaces, we add i space each to 7 spaces starting from beginning or end.
It can be done in O(N)
Keep indices track int last_W1, last_W2, last_W3 - where as we go through the doc from left to right, the last seen index of W1 is set to last_W1, last seen index of W2 is set to last_W2 so on.
Anytime W3 is seen, update last_W3 (similarly for last_W2, last_W1 cases). Then check
last_W3 minus min(last_W2,last_W1) and if it is lesser than global_min, update global_min and save the three indices last_W3, last_W2, last_W1.
Once you reach the end of the doc, the last_W1, last_W2 and last_W3 should give the needed substring from the doc. We can go to those locations and print the substring.
It can be done in two phases:
Step 1: Find if the string represents valid binary tree
Step 2: If valid tree, find depth
Step 1 Approach: Replace all (00) occurances with 0, At end, if you end up with a 0, then it is valid binary tree, else not. We can use simple stack to do this,
As we go from left to right in the string,
if element == '(' or '0', push element
if element == ')', then pop last three elements, check if the order of popped elements is
0, 0, ( and if yes, push 0
else return -1 (means not valid binary tree)
At end, check if the stack has only element 0, then return 1 (means valid binary tree), else return -1.
This is O(N)
Step 2 logic: - done only if step 1 return true or valid binary tree
Again go from left to right in string, and incement count when '(' and decrement when ')'.
When incrementing, always check if count is greater than max, and if yes, update max to new count.
After going thru all elements, the value of max -1 is depth. (max minus 1 needed since depth starts numbering from 0)
TreeSet
- venkat325 November 24, 2015- store set in a tree, sorted order of elements (increasing/decreasing) is preserved.
- insertion/removal/searching are O(log n)
HashSet
- store set in a hashmap, order of elements (whether sorted or insertion order) is lost
- insertion/removal/searching are O(1)
LinkedHashSet
- stores set in hashmap, plus a linked list to keep track of order of insertion
- insertion/removal/searching are O(1) , though extra space needed for the linked list
- order of insertion is preserved (due to linked list storing elements in order they are inerted)