Q: Given an integer array find if there exists three integers that add up to zero.
A: This is another integer array problem where we are interested in a particular sum. Since we are looking for three integers the naiive solution looks O(n^3) but this is not the case. First we could just sort the elements, then for each element we encounter we know the complement that makes the sum zero.For each complement, we know the fractions has to be earlier than the number we have just encountered. Thus we can proceed better in this case if the elements are sorted.
Q: Given a set of login and logout pairs of users, find the number of users online at any given point of time.
A: From the start of the list of logins and logouts, populate a dictionary of users and their active logins by incrementing a counter for every login of that user and decrement for every logout of that user until the last entry. This gives the number of active logins for each user.
Q: Another integer array is given where there are repeating zeros. Compact the array by erasing the zeros.
A: The problem hints on using the same storage to get the resultant array. So we can lean on multiple passes on the array if we want. Hence, we could make one pass to find the index of all occurances of zero. Then for each occurance, shift all the elements following it. We could shift more than one at the same time if the occurances are consecutive. Another improvement could be to shift only the elements upto the next occurance and keep the zeros consecutive at the next occurance.
Q: Given a set of non-overlapping integer range and an input integer, now design a data structure to store them and have operations of insert, delete and search
A: A double dimensional array seems sufficient for the operations where the integer ranges could traverse one or more of the jagged array elements. For each element we keep track of the end of a range and the start of another.
Q:How can you tell if a given string is of the form aZb where a is the reverse of b ?
A: If a and b can be empty strings almost all strings can satisfy that form otherwise compare start and end index elements and update the indexes on a match.
A: This is another integer array problem where we are interested in a particular sum. Since we are looking for three integers the naiive solution looks O(n^3) but this is not the case. First we could just sort the elements, then for each element we encounter we know the complement that makes the sum zero.For each complement, we know the fractions has to be earlier than the number we have just encountered. Thus we can proceed better in this case if the elements are sorted.
Q: Given a set of login and logout pairs of users, find the number of users online at any given point of time.
A: From the start of the list of logins and logouts, populate a dictionary of users and their active logins by incrementing a counter for every login of that user and decrement for every logout of that user until the last entry. This gives the number of active logins for each user.
Q: Another integer array is given where there are repeating zeros. Compact the array by erasing the zeros.
A: The problem hints on using the same storage to get the resultant array. So we can lean on multiple passes on the array if we want. Hence, we could make one pass to find the index of all occurances of zero. Then for each occurance, shift all the elements following it. We could shift more than one at the same time if the occurances are consecutive. Another improvement could be to shift only the elements upto the next occurance and keep the zeros consecutive at the next occurance.
Q: Given a set of non-overlapping integer range and an input integer, now design a data structure to store them and have operations of insert, delete and search
A: A double dimensional array seems sufficient for the operations where the integer ranges could traverse one or more of the jagged array elements. For each element we keep track of the end of a range and the start of another.
Q:How can you tell if a given string is of the form aZb where a is the reverse of b ?
A: If a and b can be empty strings almost all strings can satisfy that form otherwise compare start and end index elements and update the indexes on a match.
No comments:
Post a Comment