Software Engineer

Concept of indexing can be used to solve this question.
Traverse the array. For every element at index i,visit a[i]. If a[i] is positive, then change it to negative. If a[i] is negative, it means the element has already been visited and thus it is repeated. Print that element.
Pseudocode :
findRepeating(arr[], n)
{
missingElement = 0

for (i = 0; i < n; i++){
element = arr[abs(arr[i])]

if(element < 0){
missingElement = arr[i]
break
}

arr[abs(arr[i])] = -arr[abs(arr[i])]
}
return abs(missingElement)
}

This can be solved using recursion. The basic idea is to subtract the value of current node from sum until it reaches a leaf node and the subtraction equals 0, then we know that we got a hit. Keep checking for left or right child path sum equal to target sum – value at current node.
Time Complexity : O(N)

The brute force approach would be to consider every possible subarray within the given array and count the number of zeros and ones in each subarray. Then, find out the maximum size subarray with equal no. of zeros and ones out of them.

Time Complexity: O(N^2)

To optimise the above approach, the concept of hashing can be used. If we consider 1 in array to be +1 and 0 to be -1, and while traversing the array maintain a variable called currSum that stores the sum of array elements upto i elements. A subarray can contains equal no. of 0 and 1 if its currSum is 0 or currSum in already encountered in the array before.

Algorithm:
Maintain a hahmap mp such that mp[currSum]=length of [0......i] whose sum=currSum
int sum=0
For 0 , do -1 from currSum and for 1, do +1 to currSum
Then there will be 3 cases:
case 1:
if(currSum==0){ //No of ones and zeroes in [0.....i] are equal so update the max length
case 2:
currSum already exist in map,
let for range [(0.....j)(......i)] sum of range[0....j] =sum of range [j+1....i]=> current range , it means No of zeroes and ones in the range [j+1.....i] are equal because total sum throughout this range didn't change
here mp[currSum]=length of interval [0.....j] so update the max length till now
case 3:
currSum did not exist earlier and neither equal to 0, so store this sum in map by its length

The idea here is to first, sort the critical POINTS with respect to their coordinate and height pairs. Make a pair of 'X1' and take a negative of the height for the building so that 'X1' pairs are sorted before 'X2' pairs. Create a dictionary keeping the heights as keys and as soon as a left edge of a building is encountered, we add that building to the dictionary with its height as the key. When we encounter the right edge of a building, we remove that from the dictionary. When you hit the left edge of a building you add it to the dictionary, and when you hit the right edge of a building you delete the key. Finally, any time we encounter a critical point, after updating the dictionary we find the height of that critical point with maximum height value from keys that we already have in the dictionary to the value peeked from the top of the heap.

The algorithm will be-

1. Store the coordinates and heights of the buildings paired up with each other with the first building coordinate paired after taking negative of the height and the second coordinate with positive height in a list ‘POINTS’.
2. Now, sort edges present in the ‘POINTS’ list (array) in ascending order.
3. The positions are now sorted from left to right, small to large. Now, initialise a dictionary named 'HEIGHTS' with zero as its first key, having a value of 1 since this would be the last height that would be added.
4. Now, for each pair of an edge in the ‘POINTS’ list (array) and check:
   1. Update the dictionary if the current edge is a start edge (with negative height) increment the value of the key by 1.
   2. Delete the invalid buildings from the dictionary if an end edge is encountered for a key after decrementing its value by 1.
   3. Now, In each iteration update the 'SKYLINE', which records the highest building from some position, and add it to the final list of our 'SKYLINE's if the current highest is no longer the tail of the 'SKYLINE' (previous highest).
5. We finally return the 'SKYLINE' list (array) that we have formed.

Hashing can be used to solve this question. Keep the count of words of the dictionary in a hash map. Iterate the string and for each word, check if is present in the map. If present, then decrease the count of that word in the map. If it is not present, then it is not possible to make the given string from the given dictionary of words.