## Google Interview Question for Software Engineers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

``````//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;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution to 1st Question in Round2 blog.csdn.net/taoqick/article/details/21814849

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

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

// 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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)

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

// 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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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:
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``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.