Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
4
of 6 vote

Let's first ask a question: how the path is constructed?
The user chooses one of 'n' available points, then goes to another point of 'n-1' points left, then goes to another point of 'n-2' points, and so on.

How many different paths of length 'n' are there?
Assumming 9 points on the screen.
For length 9, there are 9*8*7*6*5*4*3*2*1 paths.
For length 8, there are 9*8*7*6*5*4*3*2 paths.
For length 7, there are 9*8*7*6*5*4*3 paths.
For length 6, there are 9*8*7*6*5*4 paths.
For length 5, there are 9*8*7*6*5 paths.
For length 4, there are 9*8*7*6 paths.

Python code of the solution:

``````def paths_of_length(number_of_staring_points, length_of_path):
"""
Returns number of different paths of length length_of_path when there are
number_of_staring_points available

>>> paths_of_length(9,1)
9
>>> paths_of_length(9,2)
72
>>> paths_of_length(1,1)
1
"""
different_paths = 1
for choosing_from in range(number_of_staring_points,
number_of_staring_points - length_of_path,
-1):
different_paths = different_paths * choosing_from

return different_paths

def android_paths():
"""
Returns number of different android lockscreen paths
"""
different_paths = 0
minimum_length = 4
maximum_length = 9
number_of_staring_points = 9
for length in range(minimum_length,maximum_length + 1):
different_paths += paths_of_length(number_of_staring_points,length)

return different_paths

if __name__ == '__main__':
import doctest
doctest.testmod()

print(android_paths())``````

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

There are a couple of edge cases missed. If you intersect an unused dot, it is included. For example, when you go from point 1->9, 5 is hit in the middle, so 1->9 is not valid. However, the pattern 5->1->9 is valid.

1 2 3
4 5 6
7 8 9

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

Also, I think you can repeat a particular number as long as it's >= 1 steps away from itself. For example:
1->2->5->1
That's a question I would ask the interviewer.

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

Your solution includes invalid as well as repeated paths and it does not follows the constraints of android lock.

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

Hello,
A little diversion from my suggestions above. The rules for Android locked patterns are :
Each pattern must connect at least four dots.
The dots in the pattern must all be distinct.
If the line segment connecting any two consecutive dots in the pattern, middle dot (between them) should be already in pattern.
Also it is allowed to have "knight" moves - for example two points on 0,0 and 2,1.
So what should be done : 1 Generate all variations of 4...9 of 9 points and cut all solutions that are not valid. We coudn't come to there following pattern rules.
Here below is Java code. Hope will help.

``````public class AndroidLockPattern {

private boolean used[] = new boolean[9];

private boolean isValid(int index, int last) {
if (used[index])
return false;
if(last == -1)
return true;
// knight moves
if((index + last)%2 == 1)
return true;
// indexes are from both side of the diagonals for example 0,0, and 8,8
int mid = (index +last)/2;
if ( mid == 4)
return used[4];
// adajcent cells on diagonal  - for example 0,0 and 0,1
if ((index%3 != last%3) && (index/3 != last/3)) {
return true;
}
// all other adjacent cells (two cells in one row or two cells in one column)
return used[mid];

}

public void numberOfPatterns() {
int res =0;
for (int len = 4; len <= 9; len++) {
res += calcPatterns(-1,len);
for (int i = 0; i < 9; i++) {
used[i] = false;
}
}
System.out.println(res);
}

private int calcPatterns(int last,int len) {
if (len == 0) {
return 1;
}
else {
int sum = 0;
for (int i = 0; i < 9; i++) {
if (isValid(i, last))
{
used[i] = true;
sum += calcPatterns(i, len - 1);
used[i] = false;
}
}
return sum;
}
}
}``````

Comment hidden because of low score. Click to expand.
3
of 5 vote

Could be the problem represented as a graph problem where we need to find number of all simple paths with length >=4 and <=9?

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

quite so, you are right.

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

Why does it need to be >=4?
Is that an andriod specification?

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

suppose, that is not important, but the idea itself is quite good.

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

Assuming we have 10 keys and paths have to be 4 <= length <=9 with no repeats, we can sum up the permutations of 10 permute r between [4,9], which is defined as (10!)/(10-r)!

``````import math
def getLockScreenCombos():
sum = 0
for i in range(4,10):
sum += math.factorial(10) / math.factorial(10-i)
return sum``````

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

You are right but there are only 9 points in the Android lock screen (so it should be factorial(9)).

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

create recursive procedure which traverses through 2D matrix, while counting all the valid paths (valid means that there are no intersections inside one path and a path is of at least needed length).
Call this procedure in loop for every element of given 2D matrix.

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

I read that lock pattern is at least 4 keys up to 9 where no key repeats (no cycles). But I am not sure if this is specified by Android.

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

Use permutations! n permute r = (n!)/(n-r)!

Assuming path length is between 4 and 9 include, with no repeats:

``````import math
def getLockScreenCombos():
sum = 0
for i in range(4,10):
sum += math.factorial(10) / math.factorial(10-i)
return sum``````

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

Assume that 1st point as 1 and corresponding points as 2 3 .... Horizontally then for a 4 point key if you use 1st 3rd 7th and 9th key it is not possible as there are other keys in between and if you form others using permutations there would be many exceptions like this(which has a key in between them if you want to take those two keys as 1st and 2nd key in your pattern)

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

Assume that 1st point as 1 and corresponding points as 2 3 .... Horizontally then for a 4 point key if you use 1st 3rd 7th and 9th key it is not possible as there are other keys in between and if you form others using permutations there would be many exceptions like this(which has a key in between them if you want to take those two keys as 1st and 2nd key in your pattern)

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

Assume that 1st point as 1 and corresponding points as 2 3 .... Horizontally then for a 4 point key if you use 1st 3rd 7th and 9th key it is not possible as there are other keys in between and if you form others using permutations there would be many exceptions like this(which has a key in between them if you want to take those two keys as 1st and 2nd key in your pattern)

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

Assume that 1st point as 1 and corresponding points as 2 3 .... Horizontally then for a 4 point key if you use 1st 3rd 7th and 9th key it is not possible as there are other keys in between and if you form others using permutations there would be many exceptions like this(which has a key in between them if you want to take those two keys as 1st and 2nd key in your pattern)

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

This can be represented as a graph problem. May be we can run DFS or BFS on the graphs 123
456
789
and find all the paths of length ;n', where n is the length of path which can be obtained as input from the user.

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

one possible solution can be the following:

1. create an adjacency matrix with all the points handling the edge cases like 1 won't connect to 3.

2. then matrix^3 will tell number of paths a to b of length 4 and so on...
count all the paths and you have the answer.

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

``````public class Solution1 {
public static void main(String[] args) {
int total = 0;
for (int i = 4; i <= 9; i++) {
total = total + countPatterns(i);
}
System.out.println(total);
}

private static int countPatterns(int i) {
return (int) Math.pow(9, i);
}
}``````

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

``````public class Solution1 {
public static void main(String[] args) {
int total = 0;
for (int i = 4; i <= 9; i++) {
total = total + countPatterns(i);
}
System.out.println(total);
}

private static int countPatterns(int i) {
return (int) Math.pow(9, i);
}
}``````

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

I'm not quite sure what exactly the rules are, but I'm interpreting it as as a path min=4 and max=9 length, you can do 'knight moves' (aka L) and all adjacent, but never touching back on something you already did. If so then this algorithm isn't quite right as is, but you could keep a similar recursive solution.

``````def nextPossibleMoves(spot):
# grid is
# 1 2 3
# 4 5 6
# 7 8 9
allMoves = {
1: [1, 2, 4, 5, 6, 8],
2: [1, 2, 3, 4, 5, 6, 7, 9],
3: [2, 3, 4, 5, 6, 8],
4: [1, 2, 3, 4, 5, 7, 8, 9],
5: [1, 2, 3, 4, 5, 6, 7, 8, 9],
6: [1, 2, 3, 5, 6, 7, 8, 9],
7: [2, 4, 5, 6, 7, 8],
8: [1, 3, 4, 5, 6, 7, 8, 9],
9: [2, 4, 5, 6, 8, 9] }
return set(allMoves[spot])

pathMin = 4
pathMax = 9
def countPaths(fromSpot, pathLength=1, visited=set()):
if pathLength == pathMax:
return 1 # we're at the end, count ourselves

# get plausible
nextSpots = nextPossibleMoves(fromSpot)
# remove visited
nextSpots.difference_update(visited)
# check if no possible left
if len(nextSpots) == 0:
if pathLength < pathMin:
# backtrack
return -1
else:
# count ourselves
return 1
# get recursively path length possibilities from here out
nextLengths = [countPaths(spot, pathLength + 1, visited | set([fromSpot]))
for spot in nextSpots]
# remove backtracks
nextLengths = filter(lambda x: x != -1, nextLengths)
if len(nextLengths) == 0 and pathLength < pathMin:
# we have no possible moves, and we don't qualify either
# turns out not needed for this particular problem but
# i wouldn't have guessed that
return -1 # backtrack
# add ourselves as valid plus the sum of the options
return 1 + sum(nextLengths)

def calcTotalPossibilities():
fromEachSpot = [countPaths(spot) for spot in range(1, 10)]
return sum(fromEachSpot)``````

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

In this Graph problem we have to find the Combinations of all possible numbers which will create a pattern.
n=9, minlength = 4
So the total Combinations are
9C4 + 9C5 +9C6 +9C7 + 9C8 + 9C9

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

Using backtracking.

``````public class CountPatternsInAndroidLockScreen {

private static int count = 0;

private static int[][] graph = new int[][] { { 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 1, 0, 1, 1, 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 1, 1, 1, 0, 1, 0, 1, 1, 1 }, { 1, 1, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 0, 1, 1, 1 }, { 0, 1, 0, 1, 1, 1, 0, 1, 0 }, { 1, 0, 1, 1, 1, 1, 1, 0, 1 },
{ 0, 1, 0, 1, 1, 1, 0, 1, 0 } };

/*
* Must take care of the corner cases. 1->9 is not a valid case because 5
* lies in the way, however 1->5->9 is.
*/
public static void count(int level, int index, boolean[] visited, int minLevel) {
if (allVisited(visited))
return;
if (level >= minLevel)
count++;
for (int i = 0; i < 9; i++) {
if (!visited[i] && graph[index][i] == 1) {
visited[i] = true;
count(level + 1, i, visited, minLevel);
visited[i] = false;
}
}
}

private static boolean allVisited(boolean[] visited) {
for (boolean b : visited)
if (!b)
return false;
return true;
}

public static void main(String[] args) {
for (int i = 0; i < 9; i++) {
count(0, i, new boolean[9], 3);
}
System.out.println(count);
}

}``````

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

389112

Consider the Android grid as a matrix -
0 1 2
3 4 5
6 7 8

any valid move is one which has length greater than 4 and does not have any illegal jumps (like going from 1 to 3 without visiting 2).
The solution basically checks all possible patterns for illegal jumps and eliminates the illegal patters.

Java Code for Solution -

``````package PracticeStuff;

import java.util.HashMap;

public class AndroidLockScreen {
static boolean [] visited={false,false,false,false,false,false,false,false,false};
static HashMap<String, String> illegal=new HashMap<String,String>();
static int count;

public static void main(String [] args){
illegal.put("02", "1");
illegal.put("06", "3");
illegal.put("08", "4");
illegal.put("17", "4");
illegal.put("26", "4");
illegal.put("28", "5");
illegal.put("35", "4");
illegal.put("68", "7");
illegal.put("20", "1");
illegal.put("60", "3");
illegal.put("80", "4");
illegal.put("71", "4");
illegal.put("62", "4");
illegal.put("82", "5");
illegal.put("53", "4");
illegal.put("86", "7");

for(int i=0;i<9;i++)
getMoves(i);
System.out.println(count);
}
static void getMoves(int i){

int length=0;
visited[i]=true;
for(int j=0;j<9;j++){
if ((visited[j]!=true)&&(validmove(i,j))){
getMoves(j);
}
}
for(int k =0;k<9;k++){
if (visited[k]==true)
length++;
}
if (length>=4)
count++;
visited[i]=false;
}
static boolean validmove(int i, int j){
String y = i + "" +j;
//System.out.println(y);
String x =illegal.get(y);
if (x==null)
return true;
return visited[Integer.parseInt(x)];

}
}``````

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

Consider the Android grid as a matrix -
0 1 2
3 4 5
6 7 8

any valid move is one which has length greater than 4 and does not have any illegal jumps (like going from 1 to 3 without visiting 2).
The solution basically checks all possible patterns for illegal jumps and eliminates the illegal patters.

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

Brute-force Python solution:

``````from copy import deepcopy

def count_possibilities():
cnt = 0
keys = [[ False, False, False ],
[ False, False, False ],
[ False, False, False ]]
for num_of_patterns in range(4,10):
for i in range(3):
for j in range(3):
keys_cp = deepcopy(keys)
keys_cp[i][j] = True
cnt += _count_possibilities(keys_cp, 0, i, j, num_of_patterns)
return cnt

def _count_possibilities(keys, cnt, i, j, num_of_patterns):
if check_complete(keys, num_of_patterns):
return 1
for x in range(3):
for y in range(3):
if is_valid(keys, i, j, x, y) and not keys[x][y]:
keys_cp = deepcopy(keys)
keys_cp[x][y] = True
cnt += _count_possibilities(keys_cp, 0, x, y, num_of_patterns)
return cnt

def is_valid(keys, i, j, x, y):
if (i == x+1 or i == x-1) and (j == y+1 or j == y-1 or j == y):
return True
if (i == x+1 or i == x-1 or i == x) and (j == y+1 or j == y-1):
return True
if (i == x+2 or i == x-2) and (j == y+1 or j == y-1):
return True
if (i == x+1 or i == x-1) and (j == y+2 or j == y-2):
return True
if is_middle_valid(keys, i, j, x, y):
return True
return False

def is_middle_valid(keys, i, j, x, y):
if abs(i-x) == 2 and abs(j-y) == 2:
return keys[1][1]
elif abs(i-x) == 2 and j == y:
return keys[1][j]
elif abs(j-y) == 2 and i == x:
return keys[i][1]
else:
return False

def check_complete(keys, num_of_patterns):
cnt = 0
for i in range(3):
for j in range(3):
if keys[i][j]:
cnt += 1
return cnt == num_of_patterns

if __name__ == "__main__":
print(count_possibilities()) # => 389112``````

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

You can look at this as a recurrence problem you can solve with a primitive form of dynamic programming
There are 3 types of positions
The center: you can get to it from an of the other positions
Let center(n) be the number of ways to end up in the center point after n moves
An edge: you cannot get to the edge on the other side
Let edge(n) be the number of ways to end up on one particular edge after n moves
A corner: you can get to it from any edge and the center but not the other edges.
Let corner(n) be the number of ways to end up on one particular corner after n moves
The total number of patterns consists of how many ways it could take to end up on a particular location.
This will be
patterns(n) = center(n) + 4 * edge(n) + 4 * corner(n);
To get to the center after n moves we can come from some other location by n-1 moves so we get
center(n) = 4 * edge(n-1) + 4 * corner(n-1);
likewise we can compute the number of ways to get to the other points.
corner(n) = 4 * edge(n-1) + center(n-1)
edge(n) = 2 * edge(n-1) + center(n-1) + 4 * corner(n-1)
there is only one way to get to a key when you start so :
center(0) = 1, corner(0) = 1, edge(0) =1
all you now need is a loop that computes new values of 3 values but each time through you need to compute from the previous values:

center_old = 1; corner_old = 1; edge_old = 1;
for(I = 0:n)

center_new = 4 * edge_old + 4 * corner_old;
corner_new = 4 * edge_old + center_old;
edge_new = 2 * edge_old + center_old + 4 * corner_old;

corner_old = corner_new;
center_old = center_new;
edge_old = edge_new;

end loop

return center_old + 4 * edge_old + 4 * corner_old;

if you are clever you might be able to reduce it to a single recurrence and then possibly get a direct solution but that is beyond my current ability.
Note my code is pretty slack about n so there might be a +/- error in it

I ran it on a spread sheet and got this:

corner edge center total
1 1 1 9
5 7 8 56
36 42 48 360
216 276 312 2280
1416 1728 1968 14544
8880 11088 12576 92448
56928 70272 79872 588672
360960 448128 508800 3745152
2301312 2848896 3236352 23837184
14631936 18139392 20600832 151686144
93158400 115407360 131085312 965348352
592714752 734533632 834263040 6143256576

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

You can look at this as a recurrence problem you can solve with a primitive form of dynamic programming
There are 3 types of positions
The center: you can get to it from an of the other positions
Let center(n) be the number of ways to end up in the center point after n moves
An edge: you cannot get to the edge on the other side
Let edge(n) be the number of ways to end up on one particular edge after n moves
A corner: you can get to it from any edge and the center but not the other edges.
Let corner(n) be the number of ways to end up on one particular corner after n moves
The total number of patterns consists of how many ways it could take to end up on a particular location.
This will be
patterns(n) = center(n) + 4 * edge(n) + 4 * corner(n);
To get to the center after n moves we can come from some other location by n-1 moves so we get
center(n) = 4 * edge(n-1) + 4 * corner(n-1);
likewise we can compute the number of ways to get to the other points.
corner(n) = 4 * edge(n-1) + center(n-1)
edge(n) = 2 * edge(n-1) + center(n-1) + 4 * corner(n-1)
there is only one way to get to a key when you start so :
center(0) = 1, corner(0) = 1, edge(0) =1
all you now need is a loop that computes new values of 3 values but each time through you need to compute from the previous values:

center_old = 1; corner_old = 1; edge_old = 1;
for(I = 0:n)

center_new = 4 * edge_old + 4 * corner_old;
corner_new = 4 * edge_old + center_old;
edge_new = 2 * edge_old + center_old + 4 * corner_old;

corner_old = corner_new;
center_old = center_new;
edge_old = edge_new;

end loop

return center_old + 4 * edge_old + 4 * corner_old;

if you are clever you might be able to reduce it to a single recurrence and then possibly get a direct solution but that is beyond my current ability.
Note my code is pretty slack about n so there might be a +/- error in it

I ran it on a spread sheet and got this:

corner edge center total
1 1 1 9
5 7 8 56
36 42 48 360
216 276 312 2280
1416 1728 1968 14544
8880 11088 12576 92448
56928 70272 79872 588672
360960 448128 508800 3745152
2301312 2848896 3236352 23837184
14631936 18139392 20600832 151686144
93158400 1.15E+08 1.31E+08 965348352
5.93E+08 7.35E+08 8.34E+08 6143256576

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

``````int main(){
long total = 9 * 8 * 7 * 6;
long sum = total;
for (int i = 5; i > 0; i--){
total *=  i;
sum += total;
}
printf("%ld",sum);
return 0;
}``````

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.