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.

- dontknow April 05, 2017 | Flag Reply
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.

- cwa July 21, 2017 | Flag Reply
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);
}

- Md Shahnath Ullah April 05, 2017 | Flag Reply
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);
}

- Md Shahnath Ullah April 05, 2017 | Flag Reply
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);
}

- Shahnath April 05, 2017 | Flag Reply
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+ " ");
        }
    }

- terminator June 03, 2017 | Flag Reply
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();
	}
}

- Julio Molinero June 06, 2017 | Flag Reply
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);
?>

- jdprsaga July 18, 2017 | Flag Reply
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;
}

- Alex August 07, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More