9 weeks ago

John 910

Hyderabad

Question 1

Smart Dictionary

Ellie is working on an e dictionary. The dictionary contains an infinite number of words! in chronological order. The main purpose of writing this smart dictionary is to detect! any amount of similarity in words. This similarity is further to be used for syntax analysis in Ellie's machine learning project.

Joffery who is a data scientist inputs into Ellie's dictionary a series of words and expects an output of a particular kind.

If the series of words is {"This", "That", "There"}, the dictionary should return the smart sub-string. A smart sub-string is a common prefixing sub-string occurring in all the words. For example, in the given series of words, the common prefixing sub-string is 'Th'.

Given a list of words, your task is to return the length of the longest smart sub-string.

Input Specification:

input1: N, number of words in the series.
input2: An Array containing a list of N words from Ellie's dictionary.

Output Specification:

Your function should return the length of the smart substring that has the maximum length.

Example 1:

input1: 5 
input2: {"That","This", "There", "Their","Therefore"}

Output: 2

Explanation: 'Th' is the smart sub-string which is similar in series of Ellie's dictionary. Its length is 2.

Example 2:

input1: 4 
input2: {"Data","Database""Datapower", "Space"}

Output: 0

Explanation: There is no similarity among all the words in the series. Hence, 0.

Question 2

Big Prime Number

Dylan has N prime numbers. He wants to make a new number by multiplying these numbers with each other. He can use any prime number infinite number of times.

Your task is to help Dylan find and return the Kth number that he can make with his set of prime numbers.

Input Specification:

input1: An integer denoting the number of prime numbers with Dylan.
input2: An integer array representing the prime numbers which Dylan has.
input3: An integer K

Output Specification:

Return the Kth number Dylan can make from his set of prime numbers.

Example:

input1: 3
input2: {2,3,5}
input3: 3

Output: 4

Question 3

Modify Variable Names

Variables in any programming language should be named in such a way that the name itself clarifies its purpose. However, we cannot have a variable name having multiple words separated by space. Therefore, we use different approaches of defining variable names as given below:

In C++: this_is_a_variable In Java: thisisAVariable

Your task is to convert a C++ variable name into a Java variable name and vice versa and then return the converted variable name.

*Note: Assume that a Java variable name never contains '_' before any alphabet. In other words, if the given variable name contains '_' before any alphabet, treat the given variable name as a C++ variable name and generate the output as a Java variable name and vice versa.*

Input Specification:

input1: A string value representing the variable name

Output Specification:

Output: Return a string value containing the transformed variable name.

Example 1:

input1: modify_variableName

Output: modifyVariableName

Explanation: While traversing the input string, an "_" is encountered first as compared to the "N". So, the input string is treated as a C++ variable and hence "modifyVariableName" is returned as the output string after removing the "_" and converting the next alphabet i.e., v to its uppercase.

Example 2:

input1: thisIsAVariable

Output: this_is_a_variable

Explanation: The input string is treated as a Java variable and hence "this_is_a_variable" is returned as the output string after placing an underscore before all uppercase alphabets and finally converting the uppercase alphabets to lower case.

2.2 years ago

Maddela Sai Karthik 100

Problem 1

Since we want to find the longest prefix which is common to all the strings, let us compute the longest common prefix of the first two strings, the output of this will be checked with the third string and so on. In this way at the end we will be left with a single string which is the longest common prefix.

Sample code would look something like this

longest_common_prefix_till_now = compute_common_prefix( word[0], word[1] )

for i in range(2, len(word)-1): 
        longest_common_prefix_till_now = compute_common_prefix( word[i], longest_common_prefix_till_now )
ans = longest_common_prefix_till_now

Now How do you compute the longest common prefix between two strings ?

def compute_common_prefix( a, b):
    i=0
    n=min(len(a), len(b))
    while i<n:
       if a[i]==b[i]:
          i+=1
      else:
          break 
    return a[:i-1]

//Note that we infact don't even need the string we just need the length, this would save memory too

Overall the time complexity would be O(N time_taken_by_compute_common_prefix ) => O(N min_word_length_in_word_array)
as we can see in the compute_common_prefix function the while loop would run n times where n is the minimum length out of the two strings

Problem 2

For the sake of simplicity let's assume N=3 and the primes are [2,3,5] let's list down the first 10 smallest numbers that we can make out from them in ascending order. [2, 3, 4(2*2), 5, 6 (2*3), 8(2*2*2), 9 (3*3), 10 (2*5), 15(3*5), 16(2*2*2*2), ... ] since we only deal with numbers of the form 2^x*3^y*5^z , let's denote each number as a triplet of 3 numbers (x,y,z) now let's rewrite the list in terms of triplets [(1,0,0), (0,1,0), (2,0,0), (0,0,1), (1,1,0), (3,0,0), (0,2,0), ..]

the reason behind visualizing the numbers like these will be explained below.

let's consider the triplet (a,b,c) now what could be the next nearest/smallest number greater than this?

could of be (a+1,b,c) or (a, b+1, c) or (a, b, c+1)

this is an important observation.

Now comes the next idea of using a min_priority_queue, we would insert (0,0,0) into the min_priority_queue and keep on polling the queue until we reach the Kth element,

enter code here
cnt=0
    while min_pq is not empty:

        a,b,c = min_pq.pop() 

        if cnt==K:
            print(2**a * 3**b * 5**c )
            break 

        cnt+=1

        min_pq.push((a+1, b, c))
        min_pq.push((a, b+1, c))
        min_pq.push((a, b, c+1))

Even though the code is written assuming there are three prime numbers, we can generalize it to N numbers. Note that this is one of the common tricks to find Kth smallest type questions.

let's analyze the time complexity.

Code would terminate after K iterations and in each iteration we are doing some computations.

push_cost and pop_cost would be of order O(log(size_of_min_priority_queue)) . since in each iteration we are inserting at most 3 new elements and deleting one old element we are increasing the queue size by 2 per iteration. So the queue size can be atmax 2K. the time complexity in each iteration is of the order `NlogK`. Hence overall time complexity would be O(K N log(K))

Problem 3

This is a typical implementation problem. Try to think of any edge cases that you might miss by dry running your code.

enter code here
    # s is the input string given to us 
def solve(s):
    if s.contains('_'): # this is a c++ variable name
        words = s.split('_') # split s by '_'
        n=len(words)
        ans=[]
        ans.append(word[0])
        for i in range(1, n):
            ans.append(capitalize(word[i]))

        return ''.join(ans)#stich back the words                 

    else: # this is a java variable name
        words=[]
        # split s whenever we see a capital letter
        # eg: helloWorld should be split into 'hello' & 'World'

        cur_word = []

        for ch in s:
            if isUpper(ch):
                ans.append(''.join(cur_word))
                cur_word=[ch]
            else:
                cur_word.append(ch)

        if cur_word:
            # in case we have constructed cur_word but it's not added to ans 
            ans.append(''.join(cur_word))

        # once we have split the string it's easy to compute the ans

        n=len(words)
        ans=[word[0]]
        for i in range(1, n):
            ans.append('_'+ tolower(word[i]))

        return ''.join(ans)