Last time you used a Binary Search?

krazyklown

I was just wondering when was the last time anyone here used a binary search implementation?
The reason I am asking is I did an interview for a position yesterday which included a technical test. It was multiple choice and one of the questions was something along the lines what is the disadvantage of a binary search.

My initial reaction was because I haven't heard or seen that since year 1 or 2 in college, that it is a ridiculous question to be asking (i have four years industry experience). Out of pure curiosity I am checking to see if any developers have used it in a professional capacity?

L.Jenkins

I've been kicking around the IT Industry as a Developer since 2009 and I've yet to make use of or have the need to use a Search Algorithm.

Aswerty

Can't say I'd hear of it before though my background is engineering as opposed to CS. I've about the same amount of industry experience as yourself.

A lot of the time technical tests are about checking your CS fundamentals as opposed to more practical examples. Just take it as a learning experience and be aware that the technical tests can go that way. A lot of people will brush up on fundamental algorithms and data structures before jumping back into the job market.

Personally I'm not a fan of these questions but that is because I don't have the academic background and haven't done the learning on my own time.

ohnonotgmail

I have been writing software for 20 years. Never used one.

krazyklown

Thanks guys - I did feel kind of shortchanged at the time - i recently delivered a Windows 8 LOB app with an associated REST API and website portal - the question seems trivial compared to that type of experience and I just wanted to check that maybe my narrow experience in development was not representative of the norm. In fairness, I am a little conflicted in that I did do CS and did learn about it so maybe I should be lamenting my own memory loss!! funnily enough I realized the answer at half four this morning!

Talisman

krazyklown wrote: »

I was just wondering when was the last time anyone here used a binary search implementation?

Around 1998.

The most obvious answer to the question you were asked is that data has to be in an ordered structure before you can perform a search.

Any such off the wall questions are just checking your knowledge of some fundamentals. All the major languages have a binary search implementation in their standard libraries so you should almost never have to implement it yourself.

Idleater

I haven't implemented it in recent years, but just the other day I narrowed down which version of a rpm (many produced daily) actually broke .

Sometimes the technical tests can be used to determine how you approach a technical problem rather than actually requiring your solution for use.

CreepingDeath

ohnonotgmail wrote: »

I have been writing software for 20 years. Never used one.

Same here.
A binary search requires the data to be sorted first.

In general if I needed a fast lookup in memory I'd use a Hashtable instead.

moycullen14

It is a strange one. I find tech interviews very stressful because there is an implicit assumption that you are lying on your CV. 'Oh, so you've been using C++ for years? Let's see if I can catch you out......'

Fo example if you've been in IT for 20 years, worked at all sorts of reputable companies and worked on lots of varied projects, you would think that you could assume that you have mastered the basics of the craft - or at least are able to retrieve/marshal the information. But no, companies think it's fine to ask you about quicksort, binary trees and all manner of crap that you probably haven't looked at in years.

Unless you have a good reason, implementing basic algorithms should be grounds for dismissal. It would be like a builder making his own blocks. Why on earth would you do it?

I guess interviewers ask these questions because they have been burnt by employing useless people. Thing is that useless people are useless, they are not ignorant. What you need to determine in an interview is if someone can be trusted to get a job done with the minimum of fuss and not wreck the place whilst doing it. IMHO, knowledge of algorithms is low on the list of requirements.

A more worrying thing is that it seems qualifications in IT count for almost nothing.

CreepingDeath

moycullen14 wrote: »

Unless you have a good reason, implementing basic algorithms should be grounds for dismissal.

True, but the OP was only given a multiple choice question on the disadvantage of a binary search. They weren't asked to implement one.

moycullen14 wrote: »

IMHO, knowledge of algorithms is low on the list of requirements.

Knowledge of how they are coded I assume you mean ?

Knowledge of which data structure and algorithm to use for a particular problem, based on speed, memory, scalability, concurrency etc... is vital for well written code.

Although a few months back I took an online coding test and there were a lot of array/string processing questions that weren't a million miles away from a binary search.

satchmo

I use plenty of searching & sorting algorithms regularly. Not necessarily binary search because there are algorithms out there with better worst-case performance, but I need to understand it to know that.

Even for multiple choice tests, it all depends on why an interview question is asked, and who you're asking.

If I was interviewing someone for a job as a 3D or engine programmer here, they damn well better be able to tell me what a binary search is, what its limits are, what alternatives there are, and when they would use one over the other. Just like they should be able to do the same for sorting algorithms. Just because there are libraries that already have the algorithm implemented doesn't mean that you don't need to understand how it works - you still need to know when to use one over the other. And besides, somebody has to actually implement those libraries, they don't just appear by magic. But that's only applicable to some job descriptions.

However I can still see it being a fair question in an interview for a web developer, if asked properly. If I was the interviewer, I would say it's fine if you don't remember the details, then explain the concept again and ask you to talk through what you see as being its limitations. If you already know what it is - bonus points - but that's probably not what the interviewer is interested in. It's the same for many interview questions when you obviously have the experience and knowledge for the job - the interviewer's more interested in how you think, and if you're generally smart and a good fit for the team.

Of course there are also many, many bad interviewers out there, who range from "I'm going to ask all of these questions, and mark you based on how many you get right" to the ultra-****ty "I'm going to prove how much smarter than you I am". There's not much you can do about that, except not work there as it's a big sign that you wouldn't be happy there anyway.

Tar.Aldarion

Never used one nor have I sorted a thing. And if I ever needed to I would google it.

ArseBurger

moycullen14 wrote: »

Fo example if you've been in IT for 20 years, worked at all sorts of reputable companies and worked on lots of varied projects, you would think that you could assume that you have mastered the basics of the craft

That would be nice. In practice, it doesn't happen. People get to narrow focused within areas. So you have to test fundamentals.

For example. The simple question "How does DNS work?" may seem easy. It isn't. Most people can't answer this question sufficiently. This is a fundamental technology for anyone working in Internet technologies.

The binary search implementation question is valid.

fergalr

moycullen14 wrote: »

Fo example if you've been in IT for 20 years, worked at all sorts of reputable companies and worked on lots of varied projects, you would think that you could assume that you have mastered the basics of the craft - or at least are able to retrieve/marshal the information. But no, companies think it's fine to ask you about quicksort, binary trees and all manner of crap that you probably haven't looked at in years.

You have been in IT for 20 years - but you have never met someone who fit the profile of "been in IT for 20 years, worked at all sorts of reputable companies and worked on lots of varied projects" but was actually really bad?

moycullen14 wrote: »

Thing is that useless people are useless, they are not ignorant. What you need to determine in an interview is if someone can be trusted to get a job done with the minimum of fuss and not wreck the place whilst doing it. IMHO, knowledge of algorithms is low on the list of requirements.

People use it as a proxy. If you can answer fundamental CS questions, you can probably reason about [complex CS thing] better than someone who flunks the fundamentals.

moycullen14 wrote: »

A more worrying thing is that it seems qualifications in IT count for almost nothing.

If you can test people directly, then why would you emphasize qualifications?
Surely you've seen really incompetent people with good qualifications.

moycullen14

ArseBurger wrote: »

That would be nice. In practice, it doesn't happen. People get to narrow focused within areas. So you have to test fundamentals.

For example. The simple question "How does DNS work?" may seem easy. It isn't. Most people can't answer this question sufficiently. This is a fundamental technology for anyone working in Internet technologies.

The binary search implementation question is valid.

My original response was badly thought out. I didn't mean that you shouldn't know these things, I meant that there are more important things - perhaps the softer things - that are more important.

If the qualifications are not worth a damn, then the problem is the qualifications.

Having said all that, DNS? I mean, really. What do most people need to know about DNS beyond the fact that it's the internet's phone book? Yes, it's important but knowledge of it? Not so much.

You see that's the problem. Everyone has different views about what is fundamentally important. And for each one of those 'fundamentals', someone will say 'Shure, I can just google dat, if I need it' - and, most of the time, that would be fine.

We're not alone in this. The case of the radiologists in Roscommon who couldn't read a scan highlights the danger of relying on qualifications.

moycullen14

fergalr wrote: »

You have been in IT for 20 years - but you have never met someone who fit the profile of "been in IT for 20 years, worked at all sorts of reputable companies and worked on lots of varied projects" but was actually really bad?

Of course I have. Pretty much every 'Project Manager' I ever come across fits the bill. :eek:

People use it as a proxy. If you can answer fundamental CS questions, you can probably reason about [complex CS thing] better than someone who flunks the fundamentals.



If you can test people directly, then why would you emphasize qualifications?
Surely you've seen really incompetent people with good qualifications.

Yes I have and they probably would have sailed through interviews on balanced trees and quicksort implementations. Their uselessness was not a function of knowledge, it is all to do with personal traits and characteristics.

gleesonger

Not in IT by career, but I'd use a binary search often enough. Generally working with small, static data where performance is important.
I'm surprised that most folks here haven't/rarely use it.

gleesonger

Actually if I take a loose interpretation of your definition of binary search I would say most people here use it without even knowing, few examples;
I think the hash lookup backing some dictionaries are using a binary search.
If you debug your application and know the rough region/parameter range where your bug appears you'll take a binary search debugging approach without knowing about it
You lookup a sorted collection looking for the closest value

Colonel Panic

I sort and search and use algorithms all the time. Performance is more than. Just throwing more processing power at a thing.

ectoraige

Earlier I had to replace a broken touchscreen computer in work, but the screw securing it to its mounting needed an allen key. My set of bits was ordered from smallest to largest so I picked one that looked about right and tried it. It was too large so I picked a smaller one from the set, and it worked.

Other than that, can't recall implementing a binary search in the past fifteen years since college.

FSL

I used it extensively on 8 bit micro-processors in the seventies.

Giblet

git bisect

krazyklown

Thanks for all the replies - interested to see that some people have used it so the question on the test was valid.
Some good points being made.
In any case I got offered the role but have turned it down in favour of another offer. The recruitment process could not have been more different - the one i accepted was basically an hour and a half interview with two members of the team i am joining. The other process was two online tests (logical reasoning and a maths test) after which i was invited to an interview. The interview was with a three person panel and then the technical test. In fairness the role was more or less a pure programming one, whereas most of my experience has been more of a project end-to-end one (requirements analysis, solution design and then implementation). This has probably skewed my impression of what l should know.

ArseBurger

moycullen14 wrote: »

Having said all that, DNS? I mean, really. What do most people need to know about DNS beyond the fact that it's the internet's phone book? Yes, it's important but knowledge of it? Not so much.

Absolutely disagree.

ectoraige

If your role involves managing web-hosting or the like, and you're expected to trouble-shoot, then understanding DNS is quite important. If you're just programming, then no, not so much.

The point of questions like this is kind of being missed, they aren't an exam paper, they are supposed to be a launchpad to explore how the candidate thinks and the level of competence they can display. If you are asked about DNS, but don't really know much, then a good answer would be "well, I understand it's like a phone book for the Internet, but I've never really had the need to delve into the fundamentals so far - what I've spent most of my time working on is... ". Ideally though these kind of questions should be based on what is being claimed on their CV, or for graduates, what they've studied. I've spent 15 years doing web development, system administration and tech support, all in unixy environments, so if somebody asks about Visio, well, they aren't going to learn much about me or my skills.

The problem is if the interviewer themselves aren't competent enough to determine what you might know from your CV then they might fall back to "stock" questions. When this happens though, you should divert them into something you can talk about - they aren't paying attention to the details, and wouldn't understand them anyway, so they are looking for a display of confidence in your own abilities. Having a list of buzzwords on your CV is a good tip, it helps the HR drones ask you a relevant question. My CV had a section "Skills/Knowledge" that had headings such as Networking, Programming Languates, Operating Systems which just listed things like "FreeBSD, Linux, DNS, Ethernet, Wifi, TCL, Perl" - any buzzwords that can guide the interviewer to a useful question.

If you've claimed to have done lots of customer technical support around Internet services such as email or hosting, then I may well ask a question on DNS. What I'd be more interested though is how the person models the concepts in their head, and how they layer their knowledge. The best interviews are the ones where you sit down with somebody and work with them to solve a problem, writing a bit of code, and seeing how they approach things. When a company does things like this, it's a sign they have good people working for them, and that they will understand what you are worth to them. I'd never hire somebody on the basis of an interview alone anymore, I've learned my lesson.

ArseBurger

If you're a coder or anyone who has to do any name lookups then you need to understand DNS. It's a foundational protocol.

ectoraige

ArseBurger wrote: »

If you're a coder or anyone who has to do any name lookups then you need to understand DNS. It's a foundational protocol.

What level of understanding?

Does anybody who has to send any emails need to understand SMTP? It's a foundational protocol, after all.

Somebody who works in game development doesn't need to know the details of DNS - use a library to resolve up a host, it either works, or it fails, handle the conditions. Do they really need to understand why you can't use a CNAME for an MX record? TCP? That's pretty foundational, but I don't think anybody who uses a networked computer needs to understand it though.

moycullen14

ArseBurger wrote: »

Absolutely disagree.

Why?

and don't say because it's important. We get that, no DNS => no internet.

Why is it important that someone has a detailed knowledge of DNS when it is not required in their day-to-day work?

I can think of dozens of things that are more important in the environments that I work in: maven, eclipse, spring, blah blah, blah

CreepingDeath

ectoraige wrote: »

Somebody who works in game development doesn't need to know the details of DNS

True, but it's a good example of retrieving distributed hierarchal data across a cluster of machines.
As a design pattern, it might be applied to sharing world game space across servers or multiplayer communication/messaging.

ectoraige

CreepingDeath wrote: »

True, but it's a good example of retrieving distributed hierarchal data across a cluster of machines.
As a design pattern, it might be applied to sharing world game space across servers or multiplayer communication/messaging.

It sure is, but it's still not something of which I would expect all coders to have a detailed knowledge. It is something that, when explained to them, I would expect a decent coder to grasp and understand, but if somebody says they've spent their career so far modelling physics engines I'm not going to probe their knowledge of DNS.

moycullen14

I suppose this thread highlights the problem with interviews. We can't even agree on whether one topic - DNS - is important or not.

Can you imagine medical interviews along the same lines?

TB? We haven't seen it in years! It's the ERD of diseases. Now ebola - there's a 'github' of an illness. Very hipster. Tell me what you know about scrofula?

yes there

moycullen14 wrote: »

I suppose this thread highlights the problem with interviews. We can't even agree on whether one topic - DNS - is important or not.

Can you imagine medical interviews along the same lines?

TB? We haven't seen it in years! It's the ERD of diseases. Now ebola - there's a 'github' of an illness. Very hipster. Tell me what you know about scrofula?

Please dont ever put hipster and program related tools in the same sentence again.

moycullen14

yes there wrote: »

Please dont ever put hipster and program related tools in the same sentence again.

ozmo

krazyklown wrote: »

I was just wondering when was the last time anyone here used a binary search implementation?
..My initial reaction was ... that it is a ridiculous question to be asking

I think its a perfectly valid thing to ask - too often I have seen crazy iterative searches through data in code - when a Hashtable/Dictionary<>/SQLIndex would have done the job in a fraction of the time.

Yes, you don't obviously write these implementations yourself - but knowing these are binary searches or similar and that coding your app to be able to use them will make all the difference with large data sets or getting a quick response on a webpage

ArseBurger

ectoraige wrote: »

What level of understanding?

Does anybody who has to send any emails need to understand SMTP? It's a foundational protocol, after all.

Somebody who works in game development doesn't need to know the details of DNS - use a library to resolve up a host, it either works, or it fails, handle the conditions. Do they really need to understand why you can't use a CNAME for an MX record? TCP? That's pretty foundational, but I don't think anybody who uses a networked computer needs to understand it though.

Actually, I would expect anybody working in the IT industry to understand all of the above. Even if they don't use it on a day to day basis.

ArseBurger

moycullen14 wrote: »

Why?

and don't say because it's important. We get that, no DNS => no internet.

Why is it important that someone has a detailed knowledge of DNS when it is not required in their day-to-day work?

I can think of dozens of things that are more important in the environments that I work in: maven, eclipse, spring, blah blah, blah

You think you don't need to understand DNS to understand how Maven, Eclipse, and Spring work? Hm.

Giblet

ArseBurger wrote: »

You think you don't need to understand DNS to understand how Maven, Eclipse, and Spring work? Hm.

Yet people use them every day without knowing! You don't need to know much of anything to code beyond the basics of the language itself. It might not make you very good or successful (not that it's stopped anyone before) but seeing as a lot of programmers don't know the language they are using very well, I don't expect to find that they also know the basics of DNS, SMTP or even what an A Record is.

Tar.Aldarion

It in no way stops people being good or successful. Somebody that never works with SMTP (or insert anything here) doesn't know how SMTP works, big deal

ArseBurger wrote: »

Actually, I would expect anybody working in the IT industry to understand all of the above. Even if they don't use it on a day to day basis.

I don't think reality will meet those expectations for the majority of people.

ozmo wrote: »

I think its a perfectly valid thing to ask - too often I have seen crazy iterative searches through data in code - when a Hashtable/Dictionary<>/SQLIndex would have done the job in a fraction of the time.

Yes, you don't obviously write these implementations yourself - but knowing these are binary searches or similar and that coding your app to be able to use them will make all the difference with large data sets or getting a quick response on a webpage

A lot of the time I use these things because I have looked it up and found out it is better to use over something else, I have no idea what is going on under the hood and for most instances I don't need to know (whereas sometimes you do and would look it up)

Idleater

Giblet wrote: »

I don't expect to find that they also know the basics of DNS, SMTP or even what an A Record is.

But it makes a nice open interview question to see the candidate's thought process. Thinking how to go about understanding a problem starts with breaking down and formulating your current understanding.

It'll help when the boss comes in with the project Yoko Ono moment "we're taking the project in a new direction"

moycullen14

ArseBurger wrote: »

You think you don't need to understand DNS to understand how Maven, Eclipse, and Spring work? Hm.

No what I said at all. My point - and I'll make it again - is that DETAILED knowledge of DNS is unimportant for most programming tasks. Rather than just contradicting me, how about you give some examples of common scenarios where DETAILED knowledge of DNS is important in day-to-day work?


If I was being interviewed and someone was focusssing on DNS, I would assume that knowledge of it was important for the job.

I can think of dozens of things in Spring, Hibernate, Maven, Eclipse et al that are FAR more important than DNS.

Berserker

Interview questions like this make me wonder. A company has a few hours to decided whether an interviewee is suitable for the job and they throw out questions like this. Personally, from a .Net perspective, I would just write a quick program with a List<T> and call the BinarySearch() on that. Five lines of code should do it. Why re-invent the wheel?