Depends on what the input is like. A linear search would be ideal on an unsorted collection. If it is sorted, then a binary search will yield an O(log n) search time. This is assuming searching for any arbitrary number. Granted, if the list was sorted and the task was to find the largest, well then that search would be O(1) now wouldn't it?

This post was edited by Minkomonster on Mar 5 2014 09:16pm

One company asked me, given an array of integers, what the best way to find the integer that appears an odd number of times (assuming the rest of the integers appear an even number of times)
i only had 15 mins to solve this, i just put the array in a frequency map, then iterated through the map and returned the one that was odd

Other question was: given an integer n and a singly linked list, return the data of the element that is n spots away from the end of the list
i made a new linked list that pointed backwards each step of the way so that at the end, i could just traverse the new list n times

Needless to say I didn't get the job -.-

This post was edited by oOn on Mar 5 2014 09:31pm

i hate those brain farts. the next time you hear it without any pressure you immediately scream out the answer



The first time i heard that, i came up with using a stack of size n. some months later i read it in PIE and smacked my head since i was so close

This post was edited by carteblanche on Mar 5 2014 09:44pm

Couldn't you have 2 pointers ( A and B ) to the head node of the list. Advance pointer A N times, and then advance each pointer until pointer A hits the end of the list. Since pointer A and pointer B were N nodes apart, pointer B now points at the Nth node from the end?

This post was edited by Minkomonster on Mar 5 2014 09:52pm

yeah. it's one of the classic examples in PIE (programming interviews exposed). should have read that a lot earlier than i did tbh.

This post was edited by carteblanche on Mar 5 2014 09:56pm

I was curious what PIE stood for lol. I was scratching my head getting hungry.

3.1415926535 ofc. trig teacher gave us extra credit for every digit of pi we knew. i only had a minute to look it up. no time for google so i grabbed my TI-83. it only had 3.141592654, but i missed the last digit because it rounded. i'll always remember that now.

Programming Pearls was another good book. (no, it's not about perl)

@Eep: read both of those books.

This post was edited by carteblanche on Mar 5 2014 10:01pm

What was the point value per digit? I knew some kid in highschool that knew some ridiculous number of digits. He would have aced that course with just the extra credit.

The hardest programming interview I had recently (this one really made me hate life):


Say there's a game where you can either score 0 or 1 or 2 points each round

Probability of scoring 0: 0.45
Probability of scoring 1: 0.3
Probability of scoring 2: 0.25

Given n rounds, Find the probability of the final score ending in 0, 1, 2, ...., 9 (for each integer 0 - 9 )

This post was edited by oOn on Mar 5 2014 10:06pm

only 1 point each, on a test.

if i was a teacher, i'd weigh them so the farther you go the more valuable they became. the obvious ones (3.14) would be worth 1 point each. then for every 2 digits, the points increase by one. so the next two digits were worth 2 points, the next two digits were worth 3 points, the next two digits were worth 4 points, etc.

if i was a literature teacher, i'd assign everyone 10 page research papers due every month. and i'd grade them by just counting the pages. no point reading them since nobody got time for that

This post was edited by carteblanche on Mar 5 2014 10:09pm