Jump to content



Photo

Programmers: Your favorite interview questions


107 replies to this topic

#46 _aLfa_

_aLfa_

    Neowinian

  • Joined: 01-September 05
  • Location: Aveiro, Portugal
  • OS: Windows 8/RT
  • Phone: Samsung Galaxy S2

Posted 10 October 2012 - 17:15

MrA really? lol

String Shortten(String text) {
  return text.Length <= 6 ? text : text.Substring(0, 3) + "...";
}



#47 MrA

MrA

    b47d2b5288e3c77

  • Joined: 09-November 03
  • Location: Oz.

Posted 10 October 2012 - 21:56

MrA really? lol

String Shortten(String text) {
  return text.Length <= 6 ? text : text.Substring(0, 3) + "...";
}


Hehe. I guess I wasn't clear. It's a trick question (and arguably, poorly defined), and according to my friend, no-one's been able to answer it. I certainly couldn't answer it, but at least I understand why I can't answer it.

#48 KayMan2K

KayMan2K

    Terra Atlantis!

  • Joined: 12-June 02

Posted 10 October 2012 - 22:26

Hehe. I guess I wasn't clear. It's a trick question (and arguably, poorly defined), and according to my friend, no-one's been able to answer it. I certainly couldn't answer it, but at least I understand why I can't answer it.


Huh? How is it a trick question? Seems extremely straight forward... what are we missing here?

#49 Pon

Pon

    Neowinian

  • Joined: 15-April 07

Posted 11 October 2012 - 01:24

The question was for a game programming position, where the ability to design algorithms that work with points and vectors in 2D and 3D space is very important. Actually I was tasked to design such an algorithm during my internship there.

Also the answer to that is not particularly difficult:

A circle is defined by a center point and a radius. To find the center point, find Xmax, Xmin, Ymax, Ymin in your cloud of points, and your center is the point in the middle of that (Xmin + ((Xmax - Xmin) / 2), Ymin + ((Ymax - Ymin) / 2)).

Now the radius is the smallest one that ensures the circle contains all the points: it therefore has to be as long as the distance to the furthest away point. The distance from the center to a point is simply the norm of the Point-Center vector. Go over your cloud of points, calculate the distance from the center for each, select the largest. Done.


Actually, the problem is considerably harder than that. How do you know that aabb center is always the center of the smallest circle? It's not clear that there's a relationship between the two. Here's an example:

Posted Image

The blue points are the point cloud, and the white subdivided box is their aabb (note the blue point in the upper-right corner). The red circle is the one described by your algorithm with red dot as center; the green circle with green dot as center is smaller (possibly the smallest) and still covers all points. Anyway, this problem is called the minimum bounding circle, and there are a lot of ways to approach it but it is basically an optimization problem.

#50 Andre S.

Andre S.

    Asik

  • Tech Issues Solved: 14
  • Joined: 26-October 05

Posted 11 October 2012 - 02:31

Anyway, this problem is called the minimum bounding circle, and there are a lot of ways to approach it but it is basically an optimization problem.

I hadn't thought of that, so thanks for the explanation. That said, now that I think about it, I don't think they mentionned it had to be smallest possible circle during the interview. That would've been kinda hard for an internship position. :p

#51 Aethec

Aethec

    Neowinian Senior

  • Joined: 02-May 10

Posted 12 October 2012 - 19:06

Hehe. I guess I wasn't clear. It's a trick question (and arguably, poorly defined), and according to my friend, no-one's been able to answer it. I certainly couldn't answer it, but at least I understand why I can't answer it.

The trick is that the naive algorithm only works with a monospace font. The extreme case, a string composed of 'i's, will hold much more letters than normal text in a certain amount of pixels. So you have to measure the text if you want to do it correctly.

#52 vetneufuse

neufuse

    Neowinian Senior

  • Tech Issues Solved: 1
  • Joined: 16-February 04

Posted 12 October 2012 - 20:04

The trick is that the naive algorithm only works with a monospace font. The extreme case, a string composed of 'i's, will hold much more letters than normal text in a certain amount of pixels. So you have to measure the text if you want to do it correctly.


but the way he wrote the question it said nothing about text width

2. In Java, write a function which takes a string and returns a string that is the input if the input is 6 characters or less, and the first 3 characters + "..." if it's greater than 6.

that is pretty straight forward, you are only careing about the number of characters... now if you said that as fit a string of text into a row that is 250 pixels wide with the font arial, and type settings of 12pt and bold, itallic, replace any overlap with an elipsis... that would make more sense... can't be a trick question if it only says take 6 char's replace anything over 6 with the first 3 plus an elipsis...

#53 MrA

MrA

    b47d2b5288e3c77

  • Joined: 09-November 03
  • Location: Oz.

Posted 13 October 2012 - 06:33

but the way he wrote the question it said nothing about text width

2. In Java, write a function which takes a string and returns a string that is the input if the input is 6 characters or less, and the first 3 characters + "..." if it's greater than 6.

that is pretty straight forward, you are only careing about the number of characters... now if you said that as fit a string of text into a row that is 250 pixels wide with the font arial, and type settings of 12pt and bold, itallic, replace any overlap with an elipsis... that would make more sense... can't be a trick question if it only says take 6 char's replace anything over 6 with the first 3 plus an elipsis...


Well, that's partially why I mentioned that the question is poorly defined. But the main issue is that Java strings are UTF-16, NOT UCS-2. So if you have a string where the first code point is a surrogate pair, then the naive algorithm will produce an invalid string. So what you want is code points. Of course, that's not the entire story. What do you do about control characters? You probably want to interpret those ones you can, like BOM. But what about accents and other "modifiers". Those aren't entire characters, so you probably want to treat "e" and circumflex as a single character. And of course, if the reason why you doing this is to display the string in a restricted space, then the whole "6 characters" is moot since you now need to take into account font, size, weight, and any number of other rendering factors. So overall, not an easy question.

#54 Aethec

Aethec

    Neowinian Senior

  • Joined: 02-May 10

Posted 13 October 2012 - 08:12

Well, that's partially why I mentioned that the question is poorly defined. But the main issue is that Java strings are UTF-16, NOT UCS-2. So if you have a string where the first code point is a surrogate pair, then the naive algorithm will produce an invalid string. So what you want is code points. Of course, that's not the entire story. What do you do about control characters? You probably want to interpret those ones you can, like BOM. But what about accents and other "modifiers". Those aren't entire characters, so you probably want to treat "e" and circumflex as a single character. And of course, if the reason why you doing this is to display the string in a restricted space, then the whole "6 characters" is moot since you now need to take into account font, size, weight, and any number of other rendering factors. So overall, not an easy question.

I don't know about all accents, but in UTF-16 the circumflex and other common accents are not separated from the character. (IIRC, windows-1257 does that, which is useful to remove accents from a string by converting it back into ASCII)

But your question was worded in a way that makes "s.length <= 6 ? s : s.substring(0,3)" an acceptable answer.

#55 tiagosilva29

tiagosilva29

    Looking for a job in Lisbon

  • Tech Issues Solved: 1
  • Joined: 08-May 04

Posted 13 October 2012 - 10:09

Well, that's partially why I mentioned that the question is poorly defined.

Then define properly the request. "Character" in Java means "Unicode scalar value" {\u0000 … \u10FFFF}.

And of course, if the reason why you doing (…)

It is irrelevant because it was not stated in the request.

#56 Rudy

Rudy

    Neowinian Senior

  • Joined: 30-September 01
  • Location: Ottawa, On

Posted 14 October 2012 - 03:03

I have a really hard time believing any "programmer" could be eliminated by the fizzbuzz question (I wish I had easy questions like that for my interviews :/)

Personally I think most "interviews" for developers are ridiculous and are usually aimed at making the person fail (only tool you have are pencil and paper and the questions are most of the time extremely obscure and could be answered with more time/better tools)

I know most people I work with that are "good" at interviews are usually just that, most of their code usually look like crap.

#57 Hardcore Til I Die

Hardcore Til I Die

    Neowinian Senior

  • Joined: 18-February 07
  • Location: England

Posted 14 October 2012 - 11:54

That's the whole pitfall of FizzBuzz (unless you do duplicate checks, which is usually not wanted)



Could you give the solution? Or is the solution language specific, like Python assigment:

A, B = B, A
But still, internally I'm sure a temporary variable(s!) is being used.


EDIT: Forgot to add my solution.
void FizzBuzz()
{
	for (int num = 1; num  < 101; num ++)
	{
		bool multiple = false;
		if (num % 3 == 0)
		{
			cout << "Fizz";
			multiple = true;
		}
		if (num % 5 == 0)
		{
			cout << "Buzz";
			multiple = true;
		}
		if (!multiple)
			cout << num;
		cout << endl;
	}
}

I'm still not sure if it's better to declare a variable outside of the loop, but I'm fairly sure it will be optimized by the compiler.
And my solution is fairly readable (I hope).


Why not use an else clause rather than a variable?

void FizzBuzz()
{
        for (int num = 1; num  < 101; num ++)
        {
                if (num % 3 == 0)
                {
                        cout << "Fizz";
                }
                else if (num % 5 == 0)
                {
                        cout << "Buzz";
                }
                else
                        cout << num;
                cout << endl;
        }
}


#58 Coolicer

Coolicer

    Comrad General

  • Joined: 22-December 10
  • Location: The Netherlands
  • OS: Windows 8 & Gentoo ~AMD64
  • Phone: Nokia Lumia 920 Black

Posted 14 October 2012 - 15:23

Why not use an else clause rather than a variable?


Because in the case of %3 && %5 you need to print 'FizzBuzz'. Now you don't and have failed the assignment (into it's pitfall).
That's why I have a boolean variable that keeps track of whether it printed "Fizz" OR "Buzz". I thought about doing
it differently, something with scopes but that wouldn't do much and my solution is fairly readable and simple.

#59 Rudy

Rudy

    Neowinian Senior

  • Joined: 30-September 01
  • Location: Ottawa, On

Posted 14 October 2012 - 22:02

Why not use an else clause rather than a variable?

void FizzBuzz()
{
        for (int num = 1; num  < 101; num ++)
        {
                if (num % 3 == 0)
                {
                        cout << "Fizz";
                }
                else if (num % 5 == 0)
                {
                        cout << "Buzz";
                }
                else
                        cout << num;
                cout << endl;
        }
}

You failed!

You're missing the FizzBuzz state (if dividable by both 3 and 5 aka divisible by 15)

#60 +snaphat (Myles Landwehr)

snaphat (Myles Landwehr)

    Electrical & Computer Engineer

  • Tech Issues Solved: 29
  • Joined: 23-August 05
  • OS: Win/Lin/Bsd/Osx
  • Phone: dumb phone

Posted 12 March 2014 - 18:12

I've been asked that question. As soon as you give the solution using modulus, they ask you to do it again without using modulus/multiplication/division.

I assumed by that you meant no arithmetic operations (including bitwise) whatsoever and was like hmm that's impossible. But, I see it was only the particular types.

 

EDIT: well other than just comparisons over and over...  :laugh: