## Linkedin Interview Question for Senior Software Development Engineers

Country: United States
Interview Type: Phone Interview

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

All the locker numbers which are perfect squares will remain open.

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

If anyone doesn't see why perfect squares are the only ones open. You should write out some examples. I didn't see it at first until I ran through some small scenarios n=10. You can see from this that the factorization of each number determines how many times a locker is flipped. For example for n=10, the 10th locked will be flipped 4 times for students 1, 2, 5, and 10. When you have a perfect square for example locker 9, the factors are 1, 3, 3, and 9 but 3 is duplicated and since student 3 wouldn't go through twice you get 1, 3, and 9 an odd number of factors which consequently is the only time you would end up with an open locker.

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

Programming Language: C#
Time Complexity: O(sqrt(n))

``````public static void Locker(int n)
{
for (var i = 1; i <= Math.Sqrt(n); i++) Console.WriteLine(i*i);
}``````

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

Programming Language: C#
Time Complexity: O(sqrt(n))

``````public static void Locker(int n)
{
for (var i = 1; i <= Math.Sqrt(n); i++) Console.WriteLine(i*i);
}``````

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

Programming Language: C#
Time Complexity: O(sqrt(n))

``````public static void Locker(int n)
{
for (var i = 1; i <= Math.Sqrt(n); i++) Console.WriteLine(i*i);
}``````

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

``````static public void lockers(int n) {
BitSet lockers = new BitSet(n);
for (int student = 1; student <= n; student++) {
int locker = student;
while (locker <= n) {
lockers.flip(locker - 1);
locker += student;
}
System.out.println("Student " + student + " Lockers " + lockers);
}
}``````

n = 36 => Student 36 Lockers {0, 3, 8, 15, 24, 35} => { 1^2 -1 , 2^2 -1, .... , 6^2 -1 }

therefore the method can be rewritten has :

``````static public void lockers(int n) {
for (int i=1;i<=Math.sqrt(n);i++) {
System.out.print(i*i-1+ " ");
}
}``````

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

With my rudimentary implementation I get the same values as Md Shahnath Ullah:

n = 100 => Lockers { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 }

``````import java.util.Map;
import java.util.HashMap;

public class Lockers {
static Map<Integer,Integer> lockers = new HashMap<Integer,Integer>();

public static void lockers(int n){
for(int i = 1; i <= n; i++){
toggleLocker(i);
}
}
public static void fillLockers(int n){
for( int i=1; i<=n; i++ ){
lockers.put(i, 1); // All closed (changed to open), it doesn't make sense since FIRST student will open all when passes
}
}
private static void toggleLocker(int student){
int currentLocker = student;
int counter = 1;
while( currentLocker <= lockers.size() ){
counter++;
currentLocker = student * counter;
if( currentLocker > lockers.size() ) break;
int toggle = lockers.get(currentLocker);
if( toggle==0 ){
lockers.put(currentLocker, 1);
} else {
lockers.put(currentLocker, 0);
}
}
}
private static void showLockers(){
for(int lockerId : lockers.keySet() ){
System.out.println("LockerID->" + lockerId + ",value->" + lockers.get(lockerId) );
}
}
public static void main(String[] args) {
fillLockers(36);
lockers(36);
showLockers();
}
}``````

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

interesting, i would like to do the math to see the reason behind the perfect sqrt. in the meantime, rudimentary procedural implementation:

``````<?php
function lockers(\$n){
\$locker=array();
for (\$i=1;\$i<=\$n;\$i++)
\$locker[\$i-1]=1;
for (\$student=1;\$student<=\$n;\$student++)
for (\$i=1;\$i<=(int)(\$n/\$student);\$i++)
\$locker[\$i*\$student-1]*=-1;
for (\$i=1;\$i<=\$n;\$i++)
if (\$locker[\$i-1]==-1)
echo "\$i ";
}
lockers(100);
?>``````

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

If the door has been toggled odd number of times, it'll be open.
Being toggled odd number of times, for Door N, means that N has odd number of factors (including factor 1).
The open door numbers happen to be perfect square, but this pattern is not quite easy to derive, without intensive whiteboarding.

``````#include <iostream>
#include <math.h>

using namespace std;

bool OddNumberOfFactors(int n)
{
int factors_count = 0;
for (int i = 1; i <= sqrt(n); ++i) {
if (n % i == 0) {
factors_count += (i * i == n) ? 1 : 2;
}
}
return (factors_count % 2) != 0;
}

int main()
{
for (int i = 0; i < 100; ++i) {
if (OddNumberOfFactors(i)) {
cout << i << ",";
}
}
cout << "\n";

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.