jay
BAN USERHaving 'C++' does not prove we don't have a manageable finite dictionary, since the number of actual programming languages is quite low.
Regexs will be come unmanageable since you cannot assume ordering, as per the question, and building a regex of every possible permutation of alternating patterns could get inefficient as the search string gets large.
Idea:
Loop each string, adding the words into a hashmap on the word => string ID. For example:
java => 1, 3, 4
search => 0, 1, 2, 3, 4
To find "java search", look up each word in our map and intersect the results, i.e. we get 1, 3, 4 in this case.
Therefore the result is:
"java string search"
"java search code"
"c++ java code search"
I'm not sure how much more efficient we can make it - since we can now do the lookup in worst-case linear time, and we have the advantage that it's probably quite likely we could store this input in a database, and not have to recompute it constantly (and for each new string insertion, we just have to insert a couple more rows into the database).
Binary search. Suppose we have a list:
[1, 2, 3, 5, 6, 7, 8, 9] so length = 8
Divide the list into 2: [1, 2, 3, 5] and [6, 7, 8, 9], we know that the length is 8/2 = 4.
We can check to see which list is missing a number by checking 'first element' + length - 1 == 'last element', i.e. 6 + 4 - 1 = 9 but 1 + 4 - 1 == 4 != 5, so the left list contains the missing number.
Rinse an repeat, identify [3, 5] as having the missing element. Missing number is the average of the two.
Complexity: O(log n) (I think..)
Simpler solution at the cost of space:
- Create a hash set
- Loop the integers
-- If the element is in the hash set, remove it
-- Otherwise, add it (since it's not already present)
- The answer is the contents of the hash set (which scales to any number of odd numbers)
Complexity: O(n) (due to an O(1) get/put hash set).
Idea:
Take each element of the array, put it in a hash map: O(n)
Loop the array once more: check if (target - element) is in the hash map: O(n) for the loop, O(1) for the subtraction and existence check in the map.
Total: O(n)
Thoughts? FWIW, a Python set would do nicely for this, rather than a hash map.
The most efficient way is iterative, only keeping the last two numbers in the sequence.
def getNthFibonacci(i):
prev1 = 1
prev2 = 1
if i == 1:
return prev1
if i == 2:
return prev2
for _ in range(i - 2):
current = prev1 + prev2
# Push prev2 back to prev1, and add our latest one to the
# end of the 'sequence'.
prev2 = prev1
prev1 = current
return prev1
All you have managed to do is verify all the letters are in the word in O(n). You have *not* shown that there is a path (by traversing adjacent cells).
Your idea would say "TONE" is OK because all the letters are in the HashMap, which is incorrect, "TONE" is not a valid word (as given in the question).
Good point. It seems we can fix that by saying 'take K-1 coins from the current pile if the next pile has 2 or more coins on it, otherwise take all K' - therefore we are still in the situation where the person who goes first wins.
If the first pile has 1 coin, however, I think the person who goes first will lose.
Let's work backwards. In order to ensure there's precisely one coin left, we have to be the one to start the pile. That is, if a pile has K coins, and one person picks up K-1 of them, they will win since there is only 1 coin left.
So, we know that the winner of the game is the one who starts the last pile, therefore optimal plays says they will both want to start a pile.
How do you start a pile? Ensure there is just one coin left on the previous pile.
Seems to me, like we have an answer. The person who goes first will always win. They simply have to remove all but 1 coin on the first pile. Their opponent can only remove the final coin because that pile is the leftmost non-empty.
The person who goes first can now repeat this process. Eventually, their opponent will have to pick up the last coin, on the last pile.
I think this is the same idea as chenic626, but I couldn't understand their code very well, so I did it myself.
import collections
def pathExists(current_coordinate, coordinates_available, letters):
# This is our base case. If there are no letters left to check, then we
# have successfully matched all the ones we wanted.
if not letters:
return True
current_letter = letters[0]
if current_letter not in coordinates_available:
return False
(current_row, current_col) = current_coordinate
for (row_index, col_index) in coordinates_available[current_letter]:
# If the next letter has a co-ordinate within one cells radius, continue
# our search through it.
if ( abs(row_index - current_row) <= 1
and abs(col_index - current_col) <= 1 ):
if pathExists((row_index, col_index),
coordinates_available,
letters[1:]):
return True
return False
def isWordInMatrix(matrix, word):
# Create a map of letter => co-ordinate positions, noting that any given
# letter may be in more than one cell in our grid.
coordinates = collections.defaultdict(list)
for row_index, row in enumerate(matrix):
for col_index, letter in enumerate(row):
coordinates[letter].append( (row_index, col_index) )
# For each letter, pull up all the co-ordinates needed to construct it
# (they're the ones we have to work with, so we call them the available
# ones.)
coordinates_available = {}
for letter in word:
coordinates_available[letter] = coordinates[letter]
# We start our search with the first letter of the word.
startingCoordinates = coordinates_available[word[0]]
for coordinate in startingCoordinates:
if pathExists(coordinate, coordinates_available, word[1:]):
return True
return False
# Tests.
matrix = [ [ 'S', 'M', 'E', 'F' ],
[ 'R', 'A', 'T', 'D' ],
[ 'L', 'O', 'N', 'I' ],
[ 'K', 'A', 'F', 'S' ] ]
assert isWordInMatrix(matrix, 'SAND')
assert isWordInMatrix(matrix, 'NOTE')
assert not isWordInMatrix(matrix, 'STAR')
assert not isWordInMatrix(matrix, 'TONE')
assert isWordInMatrix(matrix, 'S')
assert isWordInMatrix(matrix, 'SRLKAFSIDFEMATNO')
assert not isWordInMatrix(matrix, 'SANSFAKFDI')
I'm wondering the same.
Your question essentially becomes: is there a data-structure where we can store k-elements, have the ability to remove one, add one, *and* find the min in O(1). I think the answer there is no: if you add or remove in O(1), the data cannot possible have any ordering/structure applied to it, so we can't get the min in O(1). If we want min in O(1), we're going to have to store it in some fashion that lets us extract that information quickly, and I think a min-heap is the best at just log(k) (as you said).
Suppose you have the string "34122151" and you want to see if it's a getEqualSumSubstring. First you would say, OK, we should consider length 4 substrings (since 4*2 = 8 <- length of "34122151"). So you compute:
3+4+1+2 and 2+1+5+1 - this results in an O(N) scan of the entire string.
You then say "nope", that didn't work. Let's try ones of length 3:
3+4+1 == 2+2+1? But wait, the LHS is simply the previous computation (3+4+1+2) but subtract 2. Similarly 2+2+1 = (2+1+5+1) - 5. Therefore, there is no point performing an (almost) complete scan of the entire string when you could have just cached this sum from before (an O(1) lookup with a single subtraction will still be O(1)).
This way, instead of having an O(N) scan on the innermost loop, you have an O(1) (amortised) lookup.
(The way showell implemented it the first time in "Python Solution with Cache" is that when you say sum(3, 4, 1, 2) you evaluate it recursively as 3 + sum(4, 1, 2) and each call to sum() is placed within a dict (which has an O(1) lookup)).
Please feel free to correct this if I am wrong, my complexity knowledge is not great.
- Empty string
- null string
- String that has all unique characters, and you want to remove one that's present
- String that has duplicate characters, and one that you want to remove that is present
- Remove from the beginning and the end of the string
- String that has only characters that are not in the 'to remove' set (i.e. so nothing happens)
- null given characters
- empty array of given characters
- duplicate given characters
- String that has all characters in the 'to remove' set (i.e. we get an empty string back)
"In the rare case that two objects have the same hash code" translates to "in the rare cases the accounts are the same" (assuming you have a good non-colliding hash). Swapping the balance from A to A makes no sense: if the objects have the same hash, then don't do any swapping, just return. That is why there is no need for a tieLock.
What did I miss?
(Don't worry, I won't 'just agree with your comment' ;-))
@Barry, Vekat is saying that you should only acquire locks in a predefined order (such as largest account number first).
For example, let A = 1 and B = 2. Then if you have transfer(A, B) and transfer (B, A) they will both attempt to lock B and then A (since 2 > 1) - not lock based on the order of the parameters which is the naive implementation. This way, they cannot deadlock.
def getFinalAmount(initialAmount, betResults):
finalAmount = initialAmount
# Betting starts at 1 dollar.
previousBet = 1
for result in betResults:
# As required, if we can't cover the last bet, return the balance.
if finalAmount < previousBet:
break
assert result in ('L', 'W')
if result == 'L':
# We lost. Deduct from our balance and double the next bet.
finalAmount -= previousBet
previousBet *= 2
elif result == 'W':
# We won. Add our winnings and reset our bet to 1 dollar.
finalAmount += previousBet
previousBet = 1
return finalAmount
# Tests:
assert getFinalAmount(12, 'WWWWWWWW') == 20
assert getFinalAmount(15, 'LLLWLLLL') == 1
Idea:
let n = 123456
Note that:
- There are ceil(log10 n) = 6 digits in '123456'
- floor(n / pow(10, ceil(log10 n) - 1)) = 1 (i.e. 123456 / 10000 = 1.23456 -> 1)
- n % 10 (i.e. 123456 % 10 = 6)
Putting this all together (Python):
Rinse and repeat for the rest of the digits, and you should be able to flip it in place.
- jay April 14, 2013(I sure hope there's a better way than this!)