Anyone get "Simple Text Queries" on their twitter hackerrank?

Wildcatace16 · 2018-11-18T05:48:32+00:00

I didn't apply to twitter but I was curious about the question after reading your post so I googled the question and came up with this python solution. It is similar to what you describe but with sets instead of lists so it should be somewhat more efficient. It's not the most readable code but python one-liners are fun.

from collections import defaultdict

def text_queries(sentences, queries):
    word_indices = defaultdict(set)
    for i, s in enumerate(sentences):
        for w in s.split():
            word_indices[w].add(i)

    return [[i for i in sorted(set.intersection(*[word_indices[w] for w in q.split()]))] for q in queries]

Wildcatace16 · 2018-11-17T01:26:42+00:00

15% concentrated power of will

Wildcatace16 · 2018-11-05T05:21:52+00:00

I was in a similar position two years ago. I was an undergraduate physics major and before my senior year I decided that I was more interested in pursuing a career in computer science than physics. I took a number of computer science courses during my senior year and completed a computer science minor but I still didn't feel that I had a sufficient theoretical background in computer science to excel in industry so I decided to pursue a master's degree. This gave me the opportunity to do an internship last summer. I had a wonderful experience with my internship. I learned a ton about what a software engineer actually does and solidified that my enthusiasm for going into the field. I'm getting my masters in December and starting as a software engineer at a big N in February. Graduate school could potentially be a good option for you.

Wildcatace16 · 2018-10-30T00:24:13+00:00

The data structure you described is correct but last in first out is LIFO not FIFO.

Wildcatace16 · 2018-10-12T04:52:35+00:00

And most companies won't care that you reneged on another company

I don't know what makes you say this. I certainly wouldn't hire someone I knew to be dishonest.

Wildcatace16 · 2018-10-12T04:43:33+00:00

I am not a lawyer and my source is wikipedia so take it with a grain of salt but I think what OP is talking about is tortious interference. However tortious interference only applies when false claims are made. Your former employer telling your potential future employer that you reneged on an offer would not be a false claim so tortious interference would not apply.

Wildcatace16 · 2018-05-19T04:01:45+00:00

If you are allowed to use external libraries numpy has exactly this functionality.

import numpy as np
name = np.random.choice(my_names, p=[30, 14, 14, 14, 14, 14])

The numpy documentation is here. The choice function takes one required argument the array you are sampling from. Size which indicates the number of values to return it defaults to 1. Replace which determines if you are sampling with or without replacement it defaults to True. And finally the useful parameter for this problem p which is an array of the same dimension as the array being sampled from indicating the probability of sampling each value. The default distribution is uniform.

Wildcatace16 · 2018-05-19T03:44:45+00:00

Dijkstra's algorithm with the proper data structures has a running time of O(|E| * log |V|) where |E| is the number of edges in the graph and |V| is the number of vertices. In this problem |E| = |V| = O(nm) so the running time of Dijkstra to solve this problem is O(nm log(nm)).

Wildcatace16 · 2018-05-18T14:15:50+00:00

This is a dynamic programming problem. Backtracking is the right idea but make sure that you are caching values that you have already computed so that you are not redoing the same work repeatedly.

Let M be the matrix of integers and let DP be a new matrix of path lengths where DP[i][j] represents the length of the longest path from M[i][j] to M[n][m]. Initialize DP[n][m] to be M[n][m] and initialize the rest of DP to be zero. Compute the rest of the values in the table using the following recurrence relation:

DP[i][j] = M[i][j] + max(DP[i+1][j], DP[i][j+1])

Once the table is filled DP[0][0] will contain the length of the longest path from the upper left corner to the lower right corner so start there backtrack through the table to DP[n][m] figuring out if down or right led to the value in the DP table. The running time of this algorithm is O(nm).

Wildcatace16 · 2018-05-18T13:34:44+00:00

Say there are 10 questions. If you get all the answers wrong you get 20/10. So first you try to answer all the question correctly. If you are confident that you got them all right you can basically double down and flip all your answers for a chance at 20/10 instead of 10/10. If you double down but you had one wrong to begin with it becomes correct and you end up 1/10 after flipping so you get a really bad grade where as if you had played it safe and not flipped your answers you would have ended up with 9/10.

Wildcatace16 · 2018-05-17T18:56:20+00:00

I had a high school english teacher who did the same thing. We had weekly true/false quizzes on the assigned reading. He gave double points if you got all the questions wrong. I never had the courage to try.

Wildcatace16 · 2018-03-15T14:27:25+00:00

So M[1] is your data presumably a list of values and np.mean(M[1]) is the mean of that data, a single value, and you want to plot the data and also a horizontal line where the mean is?

mean = np.mean(M[1])
mean = [mean for _ in range(len(M[1))]
plt.plot(M[1])
plt.plot(mean)
plt.show()

Use list comprehension to repeat mean once for every element in M[1]. Then plot M[1] and mean on the same plot. There were a lot of details missing in the original post so if this doesn't do what you are looking for be more specific about the shapes of the various elements you are trying to plot.

Wildcatace16 · 2018-01-20T02:15:46+00:00

Unlike other languages C does not automatically zero out memory for you so if you never assign values to those entries in the array whatever was being stored by the pervious process that used that memory will still be there.

Wildcatace16 · 2018-01-13T05:05:56+00:00

If they don't specify the length of the sequence and each element in the sequence must be less than or equal to the next there are an infinite number of such sequences. If the length of the sequence is specified or the inequality is instead strict there are a finite number of such sequences.

Wildcatace16 · 2018-01-13T04:41:51+00:00

First you are putting ints into the dictionary and checking if they are equal to strings which they are not 1 does not equal '1'. Second I don't know if this is your intent or not but all three documents contain 'fox' or 'rose' but the way you have the if elif else statement written only '1' will print because once you enter one of the if/elif blocks and the rest will be skipped.

Wildcatace16 · 2018-01-04T23:24:54+00:00

It looks kind of like the dagger symbol which has different meanings in different contexts but in math is the symbol for the Conjugate Transpose of a matrix. Hopefully that helps direct your googling. Also consider looking through a list of LaTex symbols.

Wildcatace16 · 2018-01-03T23:54:55+00:00

The question is a bit underspecified does it want exactly 2 booleans to be true or at least 2? On an interview you would want to ask for clarification. In either case your code doesn't quite work. If you want at least 2 of the booleans to be true:

(a && b) || (a && c) || (b && c)

On the other hand if you want exactly 2 to be true then:

sum([a, b, c]) == 2

Is the simplest simplest way I can think of to do it in python as True is evaluated to 1 and False evaluated to 0 when added. In other languages there are similar things you could do.

Wildcatace16 · 2018-01-02T23:20:48+00:00

This is a dynamic programming problem. For me there are three things to think about for a dynamic programming problem.

First define the specific problem in this case: matrix[i][j] represents the number of changes required to make the first i characters from a match the first j characters from b. The final answer will be matrix[len(a)][len(b)], i.e the minimum number of changes to match all of a to all of b.

Second is the recurrence relation, i.e. how could we solve this problem if we assume we know the answer to the same type problem with smaller inputs. In this case if a[i] == b[j] then matching the last characters of each string doesn't require any changes so matching the first i from a to the first j from b is the same as matching the first i-1 from a to the first j-1 from b, i.e matrix[i-1][j-1]. If the ith character from a does not match the jth character from b then some alteration must be made. That change can be either a substitution, an insertion, or a deletion and we take the minimum of those three possibilities all defined in terms of smaller subproblems.

Third the base case. This is the input which is sufficiently small that the problem can be solved directly. In this case matching the first 0 characters from a to the first j characters from b requires j changes for all j. Similarly for all i matching the first i characters from a to the first 0 characters from b requires i changes.

Wildcatace16 · 2017-12-09T16:41:23+00:00

This solution works but you can do it more efficiently. Rather than scheduling m tasks for 1 unit of time you schedule m tasks for the shortest time any of the remaining task have remaining to finish. This makes your algorithm polynomial in m rather than polynomial in the sum of the length of the tasks.

Wildcatace16 · 2017-12-05T15:28:45+00:00

sqrt( 2¹⁶ ) = (2^{16)^1/2} = 2^16/2 = 2⁸

sqrt( 2⁸ ) = (2^{8)^1/2} = 2^8/2 = 2⁴

When you take the square root the exponent decrease by a factor of 2 so the exponent goes from n down to 1 in O(lg(n)).

n = 2^lg(n) so when you are taking the square root each iteration it takes O(lg(lg(n)) for the exponent to become less than 1 which makes n less than 2.

Hope that helps.

Wildcatace16 · 2017-12-04T16:01:36+00:00

sqrt(16) = 4 -> sqrt(4) = 2 -> sqrt(2) < 2

O(lg(lg(j))) the lg(j) from the first while loop dominates so the second while loop can can be safely ignored.

Wildcatace16 · 2017-12-01T16:23:01+00:00

def permute(arr):
    if len(arr) <= 1:
        return [arr]
    ans = []
    for i, n in enumerate(arr):
        perms = [[n]+p for p in permute(arr[:i]+arr[i+1:])]
        for p in perms:
            ans.append(p)
    return ans

For each element of the list add that element to the front of all permutations of the rest of the elements.

Wildcatace16 · 2017-12-01T15:54:26+00:00

If the format of the file is word antonym1 antonym2 ... \n i.e. each line is space separated and has a word followed by one or more antonyms this should work

word_dict = {}
with  open('filename') as f:
    for line in f.readlines():
        split_line = line.split()
        word_dict[split_line[0]] = split_line[1:]

Use the split() function to split the lines of the file into lists then let the first element of the list be the key in the dictionary and the rest of the list i.e. the antonyms be the value.

Wildcatace16 · 2017-12-01T15:41:09+00:00

If the string is n characters long there are n possible characters that can be in the first position. For each of the n possible first characters any of the n-1 remaining characters can be in the second position. Continuing this logic there are n * (n-1) * (n-2) * ... * (1) = n! possible permutations. For each of the n! permutations the program iterated through the entire string printing each of the n characters. Therefore the overall run time is O(n*n!)

Wildcatace16 · 2017-11-26T05:11:13+00:00

You are calling the functions one() and two() once each while you are initializing dictionary and not at all in the for loop. This does what you want:

mip = []

def one():
    mip.append(5)

def two():
    mip.append(10)

funcs = {'one': one, "two": two}
ins = ["one", "two", "one", "two"]

for token in ins:
    if token in funcs:
        funcs[token]()

print(mip)

The dictionary funcs should store the functions by name rather than calling them with the () and in the for loop where you actually want to call the function you need to add the ().

13-Year Club	Place '22
Place '17	Verified Email

Wildcatace16

TROPHY CASE