Google Interview Question Software Engineers
Country: United States
Interview Type: Written Test
Algorithm:
String longestSubstring = "";
Create two collections:
Distinct characters collection
Duplicate characters collection
Create two pointers:
Start index
End index
Loop
While end index does not reach the end of string( increment end index)
if(distinct_collection.size() < k)
Read character at end index
If(char is in distinct)
Remove char from distinct collection + Add to duplicate collection
else if (char in duplicate )
Do nothing
// This means the char has come up the first time
else
Add to distinct collection
// This will happen when the number of distinct characters == k
else
If substring(startIndex, endIndex).length() > longestSubstring.length()
longestSubstring = substring(startIndex, endIndex)
Loop (distinct collection.size() == k)
If character at startPtr in distinct collection
startPtr++
Remove character from distinct collection
Else
continue;
}
Print longestSubstring
String longestSubstring = "";
Create two collections:
Distinct characters collection
Duplicate characters collection
Create two pointers:
Start index
End index
Loop
While end index does not reach the end of string( increment end index)
if(distinct_collection.size() < k)
Read character at end index
If(char is in distinct)
Remove char from distinct collection + Add to duplicate collection
else if (char in duplicate )
Do nothing
// This means the char has come up the first time
else
Add to distinct collection
// This will happen when the number of distinct characters == k
else
If substring(startIndex, endIndex).length() > longestSubstring.length()
longestSubstring = substring(startIndex, endIndex)
Loop (distinct collection.size() == k)
If character at startPtr in distinct collection
startPtr++
Remove character from distinct collection
Else
continue;
}
Print longestSubstring
Solution in python for the round 1
from random import choice
from string import ascii_lowercase
def stream_of_chars():
while True:
yield choice(ascii_lowercase)
def longest_unique_str(k, max_rounds=1000):
unique_str, max_unique_str = list(), list()
repeated = set()
for round, char in enumerate(stream_of_chars()):
# Maximum number of characters that we can consume from the stream
if round == max_rounds:
break
# If it is a unique character just add it to the list
if char not in repeated:
repeated.add(char)
unique_str.append(char)
if len(unique_str) == k:
return unique_str
else:
# Check if it is a maximal string
if len(unique_str) > len(max_unique_str):
max_unique_str = unique_str
# Find where the repeated character appears on the string
index = unique_str.index(char)
# Update the repeated values and the list of values removing
# the characters that appear before the repeated character
for c in unique_str[:index+1]:
repeated.remove(c)
unique_str = unique_str[index+1:]
return max_unique_str
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution to Round 4
- aonecoding July 23, 2017//input a 4X13 matrix with 4 suits and 13 ranks of cards. set cards[suit][rank] to 1 if this card in hand. public static boolean handClear(int[][] cards, int hand) { if(hand == 0) return true; for(int rank = 12; rank >= 0; rank--) { for(int suit = 0; suit < 4; suit++) { if(cards[suit][rank] == 1) { //if cards[suit][rank] in hand cards[suit][rank] = 0; hand--; int smallerRank = rank == 0 ? 12: rank - 1; // look for straight flush that end with this card // watch for Ace as a special case that ***QKA and A23*** both valid if(cards[suit][smallerRank] == 1) { cards[suit][smallerRank] = 0; hand--; int r = smallerRank - 1; for(; r >= 0 && cards[suit][r] == 1; r--) { //try playing the straight flush found cards[suit][r] = 0; hand--; if(handClear(cards, hand)) return true; } r++; for(; r <= smallerRank; r++) { //backtrack if play did not work cards[suit][r] = 1; hand++; } } //look for 3/4 of a kind for cards[suit][rand] int n = cards[0][rank] + cards[1][rank] + cards[2][rank] + cards[3][rank]; if(n == 3 || n == 2) { int tmp1 = cards[(suit + 1) % 4][rank], tmp2 = cards[(suit + 2) % 4][rank], tmp3 = cards[(suit + 3) % 4][rank]; cards[(suit + 1) % 4][rank] = 0; //try playing the 3/4 of a kind cards[(suit + 2) % 4][rank] = 0; cards[(suit + 3) % 4][rank] = 0; hand -= n; if(handClear(cards, hand)) return true; cards[(suit + 1) % 4][rank] = tmp1; //backtrack if play did not work cards[(suit + 2) % 4][rank] = tmp2; cards[(suit + 3) % 4][rank] = tmp3; hand += n; } cards[suit][rank] = 1; hand++; } } } return false; }