jimmythefung
BAN USERThe question as stated has no unique solution, in the sense of not relying on extra variable. Clearly the answer, q, will be different depending on how much is p2 moving faster than p1.
Here's the mathematical formula:
Let's say p2 is moving faster than p1 by a factor of k.
By the time p1 enters the loop (equivalently, traveled a distance n), p2 would have traveled a distance of kn.
From here we can say the gap between p2 & p1 is G = (kn-n)%P.
Then every subsequent step, s, the gap is increased by an amount (ks-s) = (k-1)s.
The gap keeps increasing until p2 is exactly P ahead of p1. At this point, we have
(k-1)s+G % P =0.
And at this point, the location of p1 meeting p2, which we called "q" can be observed to be:
q = s % P
So we have 3 equations
1. G = (kn-n)%P
2. (k-1)s+G % P = 0
3. q = s % P
1. implies that there is a constant "x" such that Px+G = (kn-n)
2. implies that there is a constant "y" such that Py = (k-1)s+G
3. implies that there is a constant "z" such that Pz + q = s
By manipulating the algebra of the 3 implications, you can obtain the following important result:
q = P [(x+y)/(k-1) - z] - n
Testing - Assume p2 is twice as faster as p1, and we choose set the constants x=y=z=1 (this means the p2 catches p1 without running more than 1 loop).
The result simplifies to:
q = P - n
If the non-cycle part has length 3 and the cycle part has length 4, then
q = 4 - 3 = 1.
Which you can verify by drawing a picture.
#include <string>
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<string, int> buildFreq(const string &s){
unordered_map<string, int> freq;
for(char ch:s){
string c(1,ch);
if (freq.count(c)==0){
freq[c] = 1;
}else{
freq[c] += 1;
}
}
return freq;
}
string longestPal(const string &s){
unordered_map<string, int> freq = buildFreq(s);
string L, M, R, c;
M="";
int count;
for(auto it=freq.begin(); it!=freq.end(); it++){
c = it->first;
count = it->second;
if(count>2){
while(count>1){
L=L+c; // forward string
R=c+R; // reverse of L
count=count-2;
}
}
// either count is 1 to begin with or the left over is now 1
if (count==1){
M=c;
}
}
return L+M+R;
}
void longPalTest(){
string s = "gggaaa";
cout << "Input s: " << s << endl;
cout << "Longest Palindrome: " << longestPal(s) << endl;
}
int main(){
longPalTest();
return 0;
}
#include <stdlib.h> /* srand, rand */
#include <time.h> /* time */
int rand50(){
srand(time(NULL));
int randInt= rand(); // randInt is between 0 and RAND_MAX
(x%2)==0? return 1 : return 0;
}
int rand75(){
int x = rand50(); // x is now one of {0, 1}
x = x << 1; // x is now one of {00, 10}
x = x ^ rand50(); // x is now one of {00, 01, 10, 11} in binaries
(x>0)? return 1 : return 0;
}
#include <iostream>
#include <vector>
using namespace std;
bool checkD(int row, int col, vector<vector<int>> M){
int m=M[0].size(); // number of rows <= m-1
int n=M.size(); // number of columns <= n-1
int curr, next;
while(true){
curr = M[col][row];
// advance to next cell along diagonal
col++;
row++;
// check next diagonal cell is identical
if( col<n && row<m ){
next = M[col][row];
if( curr!=next ){
return false;
}
}else{
break;
}
}
return true;
}
bool isToepliz(vector<vector<int>> M){
int m=M[0].size(); // number of rows <= m-1
int n=M.size(); // number of columns <= n-1
// horizontal-percolation at row=0
for(int col=0; col<n; col++){
if(!checkD(0, col, M)){ return false; }
}
// vertical-percolation at col=0
for(int row=0; row<m; row++){
if(!checkD(row, 0, M)){ return false; }
}
// passed both test
return true;
}
void printM(vector<vector<int>> M){
int m = M[0].size();
int n = M.size();
for(int row=0; row<m; row++){
for(int col=0; col<n; col++){
cout << M[col][row] << " ";
}
cout << endl;
}
}
void isToeplizTest(){
cout << "Input matrix, M:" << endl;
vector<vector<int>> M = {
{6,4,1,0},
{7,6,4,1},
{8,7,6,4},
{9,8,7,6},
{2,9,8,7}
};
printM(M);
cout << "Is M toepliz? " <<(isToepliz(M)? "true":"false") << endl;
}
int main(){
isToeplizTest();
return 0;
}
Implemented in C++.
Python version, as well as my solution comment:
https://github.com/jimmythefung/archive/tree/master/EPI_Problems/overlapPairs
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
string AtoS(vector<string> A){
string s;
for(string c:A){
s=s+c;
}
return s;
}
deque<deque<string>> overlap(vector<string> A, unordered_map<string, deque<deque<string>>> &cache){
deque<string> q;
deque<deque<string>> Qin, Qout;
vector<string> v(A.begin()+1, A.end());
if(A.size()==1){
q.push_back(A[0]);
Qout.push_back(q);
return Qout;
}
else if (cache.count(AtoS(A))!=0){
return cache[AtoS(A)];
}
Qin = overlap(v, cache);
q.push_front(AtoS(A));
Qout.push_front(q);
for(auto it=Qin.begin(); it!=Qin.end(); it++){
q = *it;
q.push_front(A[0]);
Qout.push_front(q);
}
cache[AtoS(A)] = Qout;
return Qout;
}
deque<deque<string>> helper(vector<string> A){
string firstLetters;
deque<deque<string>> Qin, Qout;
unordered_map<string, deque<deque<string>>> cache;
int i=0;
while(i<A.size()-1){ // split A into L, R: A=[abcd] vL=[a] vR=[bcd], each loop move 1 letter to vL from vR
vector<string> vL(A.begin(), A.begin()+1+i);
vector<string> vR(A.begin()+1+i, A.end());
firstLetters = AtoS(vL);
Qin = overlap(vR, cache); //firstLetters=(a), Qin=[ (bcd), (b,cd), (b,c,d) ] and so on
for(auto q=Qin.begin(); q!=Qin.end(); q++){
(*q).push_front(firstLetters); //(a)(bcd), (a)(b,cd), (a)(b,c,d)
Qout.push_back(*q);
}
i++;
}
return Qout;
}
int main(){
vector<string> A = {"1", "2", "3", "4"};
deque<deque<string>> Q = helper(A);
for(auto q=Q.begin(); q!=Q.end(); q++){
for(auto e:(*q)){
cout << "(" << e << ")";
}
cout << endl;
}
return 0;
}
Python, O(n), employs 3 pointers to implement LL.reverse()
a is the "previous"
b is the "current"
c is the "next"
class node:
data = None
nxt = None
class LL:
head = None
def __init__(self):
self.head = node()
self.head.nxt = node()
def insert(self, data):
n = node()
n.data = data
tmp = self.head
while tmp.nxt.data != None:
tmp = tmp.nxt
tmp.nxt = n
# end with sentinel node; last node has data = None
tmp = tmp.nxt
sentinal = node()
tmp.nxt = sentinal
def printer(self):
tmp = self.head
while tmp.nxt.data != None:
tmp = tmp.nxt
print tmp.data
def reverse(self): # needs 3 helping pointers to reverse
a = self.head
b = a.nxt
c = a.nxt.nxt
while True:
b.nxt = a
a = b
b = c
if c.data == None: # we're at last element;
c.nxt = a # point back to second last
break
c = c.nxt
self.head.nxt = None # turns head into sentinal node
self.head = c # assign head to point at last element of LL
if __name__ == '__main__':
l = LL()
l.insert(5)
l.insert(1)
l.insert(3)
l.insert(9)
l.insert(7)
l.printer()
l.reverse()
l.printer()
Python, O(n), employs 2 running index: rear, front
def pushZero(A):
rear = 0
front = 0
zeroes = 0
# initization; find the first zero
while front < len(A):
if A[front] == 0:
zeroes += 1
# rear jumps to front where the zero is located
rear = front
front += 1
break
front += 1
# No zero found
if front == (len(A)-1):
return zeroes
# front and rear are at the first found 0
else:
while front < len(A): # front runs til the end of array
if A[front] != 0: #front keeps running and swaping with rear
# swap front to the zero location where rear is at
A[rear] = A[front]
A[front] = 0
# advances
rear += 1
front += 1
else: #A[front] == 0; front just keep running
zeroes += 1
front += 1
return zeroes
if __name__ == '__main__':
A = [1, 0, 2, 0, 0, 3, 4]
z = pushZero(A)
print z, A
Python, O(2^(n-1)) as it is. Non-recursive, iterative, No dynamic programming.
The O(2^(n-1)) comes from generating all permutations of binary states from getBinaryStates().
Approach: combinatorics and permutations reasoning.
Edit: O(n) can be achieved by simply combining removeOverlap() into getBinaryState(). (i.e. so that if the left most bit of the previous groups of states start with 1, such as {(1), (10, 11), (100, 101,...111), (1000, 1001, 1010, ... 1111)}, then just makes sure that we skip over prepending the new left most bit with 1, since '11' is not allowed.)
def findAllCodes(s):
length = len(s)
nPairs = length - 1
possibleStates = getBinaryStates(nPairs)
discreteStates = removeOverlap(possibleStates)
validStates = getValidStates(s, discreteStates)
print 'Number of strings generated:', len(validStates)
for state in validStates:
codeArr = convertToCode(state, s)
print "".join(convertToAlpha(codeArr)), '->', codeArr
def convertToAlpha(codeArr):
d = dict()
i = 1
while i < 27:
d[i] = chr(ord('a')+i-1)
i += 1
output = []
for code in codeArr:
output += d[int(code)]
return output
def convertToCode(state, s):
output = []
# loop over binary places
j = 0
i = 0
while j < len(state):
# turn all binary 0 to code (simply take the single digit number)
while state[j] != '1':
output += [ s[i] ]
j += 1
i += 1
if j > len(state)-1:
break
# arrived at first binary 1, take the next 2 digits, combine as single number
else: # state[j] == '1'
output += [ s[i] + s[i+1] ]
i += 2 # shift 2 indice because we've used s[i] + s[i+1]
j += 2
# turn the remaining binary 0 to code
while i <= len(s)-1:
output += [ s[i] ]
i += 1
return output
def getBinaryStates(n):
possibleStates = []
for i in range(2**n):
binary = bin(i)[2:]
if len(binary) != n:
binary = '0'*(n - len(binary))+binary
possibleStates += [binary]
return possibleStates
def removeOverlap(possibleStates):
discreteStates = []
for state in possibleStates:
# Remove pairs whose index overlaps
if "11" not in state:
discreteStates += [state]
return discreteStates
def getValidStates(s, discreteStates):
validStates = []
for state in discreteStates:
keep_flag = 1
for index in range(len(state)):
chrNum = int(s[index]+s[index+1])
# Remove pairs whose letter corresponds values bigger than z=26
if (state[index]=='1') and chrNum > 26:
keep_flag = 0
if keep_flag == 1:
validStates += [state]
return validStates
if __name__ == '__main__':
s = "1123"
s2 = '1422616325'
findAllCodes(s)
findAllCodes(s2)
The requirements for
- jimmythefung July 23, 20161. O(n)
2. In place sort
3. preserve order (stable)
are a stingy combination.
All common sorting algorithms takes O(nlogn):
-Quicksort can sort in-place, but its partitioning function is not stable (does preserve element order), and it's not O(n)
-Mergesort can sort in-place, and preserve order (stable), but is not O(n)
-Bubble sort sort in-place, but O(n^2)
Radix sort is possibly the only sub-O(nlogn) algorithm. It runs O(wn) where w is the length of word (in this problem where elements are either 1 or 0, w=1). It also preserves order, but does not sort in place (it creates bucket).
None of the solution offered so far satisfy the 3 requirements simultaneously. I think interviewer is looking for RadixSort, which gives O(n) and stable order preservation. But I doubt he meant in-place (otherwise, creating buckets during RadixSort cost extra space)