Sigmoid Software Development Engineer II Interview Questions and Answers

Find max length of substring with equal 1s and 0s in a binary string.

• Use a hash table to store the difference between the count of 1s and 0s seen so far.

• If the difference is 0, update the max length seen so far.

• If the difference is already in the hash table, update the max length using the current index and the index where the difference was first seen.

• Return the max length.

• Example: '1100010110' -> 8

Sort an array of 0s and 1s in place without using extra space.

• Use two pointers approach - one for 0s and one for 1s.

• Swap elements at the two pointers until all 0s are on the left and 1s on the right.

Validate if a binary tree is a binary search tree

• In-order traversal should result in a sorted array

• Check if each node's value is within the correct range

• Recursively validate left and right subtrees

Reverse K group linked list

• Iterate through the linked list in groups of size K

• Reverse each group of K nodes

• Connect the reversed groups back together

Find the nearest element on the left side of an array that is greater than the current element.

• Iterate through the array from right to left.

• Use a stack to keep track of elements that are greater than the current element.

• Pop elements from the stack until finding a greater element or the stack is empty.

• If a greater element is found, that is the nearest left greater element.

• If the stack is empty, there is no nearest left greater element.