As per some website-
I can think of below solution & one can see the sample to print data of each level in the tree. And printing the tree data can further have vaious flavors.
As per one website this question from LeetCode problem#85 is asked in Google & it is tagged as 'Medium', though it is 'Hard' on LeetCode.
Again, if you get the approach, then it can be medium, else it is damn difficult.
Below question content has been taken from :
Though below question is tagged as Easy one, but it is not that easy also.
It can be easy for Googlers, but not for me.
Below I have used bottom-up approach, even the same is also suggested on above website.
Below I am giving Java code as per my current understanding, & below caode may be wrong
as I tested it for above given examples only.
It will really helpful if one can provide the correct code, in case of any concern, so that others
can also learn. The problem asked around this concept on LeetCode, I can say easy & you can see its solution here, 965. Univalued Binary Tree
On above website C++ code is given which one can refer.
Given a stack of N elements, interleave the first half of the stack with the second half reversed using only one other queue. This should be done in-place.
Recall that you can only push or pop from a stack, and enqueue or dequeue from a queue.
For example, if the stack is [1, 2, 3, 4, 5], it should become [1, 5, 2, 4, 3]. If the stack is [1, 2, 3, 4], it should become [1, 4, 2, 3].
Hint: Try working backwards from the end state.
Solution : I just thought about below solution, please suggest better solution -
Find the maximum rectangle or square in the given array of integers where each value denotes the height of the towers or find the maximum length of subarray in the given array having a single minimum number in the subarray.
Not giving any specific question but such questions have similar approach & if you know how to code for that approach then can code.
Given an array of integers where every integer occurs three times except for one integer, which only occurs once, find and return the non-duplicated integer.
For example, given [6, 1, 3, 3, 3, 6, 6], return 1. Given [13, 19, 13, 13], return 19.
Do this in O(N) time and O(1) space.
One solution which I can think is as below, please comment your thoughts -
Few other ideas one can see at -
One brilliant solution from above page is -
I will try to post my solutions to Google Interview Questions as & when I get those & if I can solve those. Request you also to keep posting the questions & suggestions here so that all can benefit.
Given an array of integers, return a new array where each element in the new array is the number of smaller elements to the right of that element in the original input array.
For example, given the array [3, 4, 9, 6, 1], return [1, 1, 2, 1, 0], since:
Solution which I can think is as below using Binary Tree & I feel that it can further be
improved such that count is found during Tree creation itself.
I think above buildTree() can be modified like shown below to reduce the traversing-
Please provide your comments if we can solve it in better way & please keep posting the questions you get.
I got the concern about the performance of the above solution, so just did a little tweak to improve its performance as shown below -
Well above can be one one way but better will be to have 2 other arrays-
one array keeps the count of smaller elements in the right to the current index.
second array keeps the index of next smaller element in the right to current index.
So this way also we can hop to have log n comparison like we have above.