Questions for 18-Aug and 25-Aug session. This week and next we will review strings, permutations and combinations. Want to join us? Head over to SDE Skills Meetup (http://www.meetup.com/SDE-Skills-Seattle/events/232467359/) to RVSP 

The Basics:

  • Given a String of N chars
    • Permutations: Generate all arrangements of R letters
    • Combinations: Generates all selections of R letters
  • Given a Symbol set of N chars
    • Perm with Replacement: Generate all arrangements of R length with replacement

Easy questions

  • isRearrangement: Given two strings, validate if they are rearrangements of each other.
  • InferSymbolSet: Given an array of strings, find the symbol set that can be used to generate these strings.
  • InferMasterString: Given an array of strings, create the shortest “master string” such that all the strings in the array are arrangements of.

25-Aug-2016 Session

Medium

  • De Bruijn Sequence: Generate and print the “De Bruijn sequence” of B(Base, Length). Output for B(2,3) is 00010111 or 11101000

Hard

  • Longest Alternating Subsequence: Given an array of ints, Find the longest alternating subsequence. Alternating inc, dec, inc or dec, inc dec.
  • Find Close Species: You are given the genetic sequence of all the species of a planet (in the form of nucleobases AGCT). Two species are considered “close” if the order in which these nucleobases occur in their generic sequence matches more than 50% of the smaller sequence.
    Example:
    S1=AAAAAAAAAA
    S2=CCCCCCCCCC
    S3=ACACACACAC
    S1 is “not close” to S2, nothing in common
    S1 is “close” to S3, as 5 A’s appear in order (not necessarily together) in S3.
    S2 is “close” to S3, as 5 C’s appear in order in S3

Tricky

  • Given a string, find the longest palindrome you can make if you are permitted to rearrange the letters in the String. How will you make this happen with minimum number of swap operations?

Video 2016-Aug-18

Video 2016-Aug-25

Comments

comments