Linkedin Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
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.
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+ " ");
}
}
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();
}
}
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);
?>
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;
}
All the locker numbers which are perfect squares will remain open.
- dontknow April 05, 2017