uCertify Interview Questions and Answers

Compute the skyline of given rectangular buildings in a 2D city, eliminating hidden lines and forming the outer contour of the silhouette.

• Iterate through the buildings and create a list of critical points (x, y) where the height changes.

• Sort the critical points based on x-coordinate and process them to form the skyline.

• Merge consecutive horizontal segments of equal height to ensure no duplicates in the output.

Sort a string with alternate lowercase and uppercase letters in sorted order.

• Split the string into lowercase and uppercase letters.

• Sort the lowercase and uppercase letters separately.

• Merge the sorted lowercase and uppercase letters alternately.

Find coordinates from which water can flow to both the Pacific and Atlantic Oceans in a given matrix of water heights.

• Create a function that takes in the matrix 'A' and its dimensions 'N' and 'M'.

• Implement a depth-first search (DFS) algorithm to find all coordinates from which water can flow to both oceans.

• Keep track of visited cells and use two separate DFS calls to find coordinates for each ocean.

• Sort and return the coordinates in lexicographical order.

Check if a given graph can be colored using two colors without adjacent vertices sharing the same color.

• Use graph coloring algorithm like BFS or DFS to check if adjacent vertices can be colored with different colors.

• If there are odd cycles in the graph, it is not possible to color the graph with two colors.

• If the graph is bipartite, it is always possible to color the graph with two colors.

• Example: For the input 5 4, 1 2, 1 3, 2 4, 3 5, the output should be YES.

Check if given strings containing parentheses are balanced or not.

• Use a stack to keep track of opening parentheses

• Iterate through the string and push opening parentheses onto the stack

• When a closing parenthesis is encountered, pop from the stack and check if it matches the corresponding opening parenthesis

• If stack is empty at the end and all parentheses are matched, the string is balanced

• If stack is not empty or mismatched parentheses are encountered, the string is not balanc...read more

Semaphores are synchronization primitives used to control access to shared resources in a multi-threaded environment.

• Semaphores can be used to limit the number of threads accessing a resource simultaneously.

• They can be binary (mutex) or counting semaphores.

• Operations on semaphores include wait (P) and signal (V).

• Example: In a producer-consumer problem, semaphores can be used to control access to a shared buffer.