animageofmine
BAN USER- 3of 3 votes
AnswersN queen problem.
- animageofmine in United States
In NXN chess board, you have to arrange N queens such that they do not interfere each other. Following is how you define interference of queens.
1. Two queens cannot be on the same diagonal
2. Two queens cannot be in same horizontal or vertical line
3. Queen can jump like a knight. So, two queens cannot be at a position where they can jump two and half steps like a knight and reach the other queen.
You should return the possible ways to arrange N queens on a chess board.
This was a tech screen, but since I was local, they called me in their office rather than phone interview.
Hint: Don't try too hard, the best solution is n!| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 0of 0 votes
AnswersGiven an array of meetings, find out the minimum number of conference rooms required.
- animageofmine in United States
class Meeting
{
long startTime;
long endTime;
};
Got 20 minutes to think through and write the code. Too short in my opinion, but well, it seemed like the interviewer didn't understand C++ either :-).| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm
My first guess would be token bucket algorithm, which would allow you to throttle requests.
- animageofmine June 09, 2015search for 1008019 at stackoverflow. Make sure you click all the links in the article, it is quite a bit of information, but worth reading. I sent you c++ article because I think Bloomberg prefers c++ over other languages
- animageofmine June 08, 2015I will keep it brief and provide my opinion.
1. If you are a recent graduate, you can avoid citing your GPA on your resume. Make sure you don't lie on your resume at all. You should know everything you have on it.
2. Write an excellent cover letter, a convincing one as to why you should be considered for the position.
3. You can upload your 8 iOS applications to github. I don't think recruiters look at code in github. The mere fact that you develop something else will give you some credit. Also sign up for stack overflow and try to contribute to the community. Sometimes recruiter do peek at stackoverflow profile. I have had a few calls from recruiters via stackoverflow career section.
4. Apply directly to company website. If you have contacts, ask them to refer you to the companies.
5. Last but not the least, prepare thoroughly. This is where most of us feel later on: "I wish I would have spent a few more days on this part".
I know its kind of sad that everytime you switch, you have to keep proving that you know data structures and algorithms, but that's how it is and probably not going to change anytime soon.
I have the same problem and have been trying to tackle it with a few different trials. Here is what has worked well for me so far.
1. It is proven scientifically that there is no difference between being actually performing an action or simulating the same in your mind. For example, the same set of nerves fired for an athlete when he was asked to imagine if he was on the track field vs when he was actually on track field. I tried the same. I bought a white board at my place, imagined that someone was in front of me and then just picked up a random question from leetcode. It actually made me nervous for a first few questions. After a couple of days, I could clearly feel the difference. I was much more comfortable on white board. And surprisingly, it helped me in one of my in person interview (only taken one in person interview so far). I was able to think clearly.
2. The same thing goes for a phone interview. Try out solving some questions on leetcode, hackerrank with a timer (be honest with yourself). You might get nervous in the beginning, but you will get into that comfort zone soon.
3. I have never tried this, but ask your friend / relative in the same field to take your interview and see how well you do. I have heard from a couple of friends that it works.
Also, don't revise anything on the day of interview. It helped me a lot to stay relaxed.
Just follow up again with the recruiting coordinator. It happened with me once that the coordinator left the company after she sent me an email. But she was good enough to add someone else in CC. Good luck!
- animageofmine April 09, 2015There are a lot of resources available. I am going to list a few of my favorites to learn data structures and algorithms.
1. Introduction to Algorithms by Cormen. It is really the best book written to boost your knowledge of data structures. You really don't have to go through every single data structure, otherwise it might take a lot of time. Just make sure you cover the important ones like hash map, heaps, graphs algorithms, MST, Link Lists, Binary Tree and sorting algorithms. It would be also good to go through some advanced data structures like Fibonnaci heap, Balanced Trees, B+ trees and be familiar with their complexities.
some of other data structures that are not really covered comprehensively in Cormen that I think are very useful: Trie and Bloom Filter. You should be able to find them on web quite easily.
2. Coursera: I personally like the course from Stanford University. It is titled Algorithms: Design and Analysis, Part 1 and Part 2. I think it will boost your confidence.
Make sure that you implement these data structures on your own computer in a language you are most familiar with. Hope this helps and good luck with your prep.
This is definitely a hard problem to solve. If you have never heard of this problem, you will most likely get stuck while designing the problem because you won't accept the fact that the actual solution is n! (unless you knew it beforehand).
There is a solution available on the web, but I can't post the link since it is not allowed. Check on sanfoundry dot com. It is in c++. Only thing it does not have is knight. You just have to develop a function to check for knight position and add it to the program. Ideally, this problem should not be even asked in interview in my opinion because it would take at least an hour to solve it if you haven't heard of it before.
This one is a brute force algorithm.
Also, why are you returning back after this check:
{
if ((meeting.startTime < scheduledMeeting.endTime) && (meeting.endTime > scheduledMeeting.startTime))
return false;
}
You are not iterating through each scheduled meeting. I think my solution so far O(nlogn) time seems to be better (see above)
Let's take an example to understand the question. I am not using long for start and end times, just using int for simplicity.
M1: 9-10
M2: 10-11
M3: 10:30-11
M4: 12-1
If you observe, total amount of conference rooms required are just 2 for all the meetings. That's because you can use the same room for M1 and M2, but since M3's start time is less than M2's (or other active meetings) end time, you will have to grep a new conf room. And as for M4, the meeting starts after all the 3 meetings are over. Hope that clarifies the question.
My solution was to sort the meetings by start times. As you iterate through the meetings, add the end times to the min-heap by key = end time. Then for each iteration, check if startTime of current meeting < extract-min(heap). If so, you will increment the counter for counting conference rooms.
Complexity will be O(nlogn). That's because the loop runs for n times and heap operation is O(logn). And sorting the input vector of conference rooms by start times takes O(nlogn). So, overall complexity is O(nlogn). I think this is optimal. It is a problem discussed in algorithms book of Eva Tardos (found it after interview)
I think the interviewer was expecting a lot of questions to clarify. Sometimes, they keep the questions vague intentionally. I am only going to consider the information provided here by OP and post my thoughts.
- animageofmine June 18, 2015Requirements:
-> Send 100 Million emails (don't know the time frame, but assuming 1 day for now)
-> 5 machines to send emails. Client machine who sends the email is not included here
-> All machines are of same processing power
Let's go top down:
-> 100 Million emails can be divided into 5 machines, not necessary uniform, but approximately it would translate to 20 M per machine
-> 20 M / 24 hours means 231 emails per sec
-> This means that there are 231 QPS required approximately for a single machine on an average
Email Service:
-> A service that would accept messages via open socket connection
-> Validates the message before sending it asynchronously
-> Sends response back to caller/client with success failure. In case of failure, it sends appropriate Error messages
-> Has retry mechanism for certain types of errors (e.g. network error)
-> Uses message queuing system like Rabbit MQ to send messages (RabbitMQ can convert SMTP messages to AMQP) to send emails
-> You don't need this really since you are using Rabbit MQ, but can implement throttling using token bucket algorithm
Email Client Lib:
1. Validates the email content before sending it to Email Service (e.g. maximum size of attachment, parameters of the email, etc.)
2. Compresses the message before sending to reduce network traffic
3. Retry logic in certain failure scenarios (e.g. in case email sever is busy, it can back off before retrying)
Client API can include following steps:
1. Setting SMTP Client : SetUpEmail(host, port, enableSSL, deliveryMethod, credentials)
2. Setting up Email: CreateEmail(sourceEmail, destEmail, subject, body, attachment)
Email Service APIs can be created in a similar way. I guess the idea here is to design than code.
As of security, SMTP requires credentials. We are also compressing the packet while sending it on network and using SSL to send email. Should be pretty safe. You can add encryption from client to server in addition to compression, if your email includes unicode characters.
We can discuss about the challenges of this design:
1. Availability: One of the machines might go down affecting the performance
2. Scalability: You can add more machines to make it scalable, but then you would have to update your design accordingly.