?>


Coding Challenge: Find the longest sequence of only two unique numbers
Posted: Posted October 9th
Edited October 9th by Ghowilo
View Source Report Thread Views

Here's an easier one than the one I posted yesterday.

Given a sequence of numbers, find the longest sequence containing only two unique numbers.

Example: INPUT: [2, 5, 3, 5, 9, 3, 9, 3, 9, 8, 2] OUTPUT: 5

The longest sequence that contains only two unique numbers is [9, 3, 9, 3, 9]

Again, try to do this without peeping my solution first.



There are 3 Replies

I'm guessing you mean longest subsequence.

Posted October 10th by EN
View Source Quote Report
EN

Here's my (uncommented) Python solution. Probably can be improved (possibly by using sets to check if the subsequence should be extended or not) but pretty sure it's O(n).
https://pastebin.com/MDcaGgiA

Edited October 12th by EN
View Source Quote Report
EN

How it works is that it takes the first two elements of the sequence, which is guaranteed to be a valid subsequence, and calls that your maximal subsequence. Then moves does the sequence element by element to create the current subsequence. If the element it sees is the same, it gets added to the current subsequence. If not, the current sequence starts over with the new element as the last element in the current subsequence and the next most recent element that was different as the first element. If the current subsequence is ever longer than the maximal subsequence, call it the maximal subsequence. Basically, keep taking valid subsequences and ask yourself if it's longer than any valid ones you've seen so far.

Posted October 12th by EN
View Source Quote Report
EN
Reply to: Coding Challenge: Find the longest sequence of only two unique numbers
Enter your message here

Rules | Report Issue | Request Feature | Roadmap Facebook Page | Discord Group
GTX0 © 2009-2019 Xhin GameTalk © 1999-2008 lives on
You are not forgotten, Kevin, Liane, Norma, Jason, and Garrett