reverse linked list !recursion

My own solution. The set-up in the beginning is useful in coding demos.

#include <iostream>
using namespace std;
struct Node{
  int val; //payload
  Node * next;
  Node (int p, Node* n=NULL): val(p), next(n){}
};
Node _1(1); //tail
Node _2(2, &_1);
Node _3(3, &_2);
Node _4(4, &_3);
Node _5(5, &_4);

// Above is a useful, simple set-up of linked list for coding interview

Node * head = &_5;

int main(int argc, char *argv[]) {
   Node * a=head;
   Node * b=a->next;
   Node * c=b->next;
   // marker variables on 3 consecutive nodes

   a->next=NULL; // first fix the head node

   for (;;){
        b->next = a; //fix the "b" node
        a=b; b=c; c = c->next; //shift down the 3 markers
        // now between a and b there's no link; a is fixed; b is intact

        if (c == NULL){
                b->next = a;
                head = b;
                cout<<"Reverse Completed!"<<endl; break; } } for (Node * tmp=head;tmp;tmp = tmp->next){
      cout<< tmp->val <<endl;
   }
}

sorted circular array max() in O(log N)

/*http://practice.geeksforgeeks.org/problem-page.php?pid=819

A sorted array A[] with distinct elements is rotated at some unknown point, the task is to find the max element in it.

Expected Time Complexity : O(Log n)

–Analysis —
It takes a const time to determine if the list is ascending or descending.

(Take 1st 3 elements. If not sorted, then entire task is simple — answer is the max among the three because we hit the turning point)

Suppose we know it’s ascending, use binary search forward to locate the turn.
*/

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<double> v{57, 56, 55, 91, 82, 73, 64};
int N = v.size();

int main() {
	auto aa = v[0], bb = v[1], cc = v[2];
	if ((aa - bb)*(bb - cc) < 0) {
		cout << max(max(aa, bb), cc) << " found within fist 3 elements" << endl;;
		return 0;
	}

	if (aa<bb) { //ascending
		for (int probe = N / 2, left = 0, right = N - 1;; probe = (left + right) / 2) {
			if (left + 1 == right) {
				cout << max(v[left], v[right]) << endl;
				return 0;
			}
			if (v[left] < v[probe]) //normal
				left = probe;
			else 
				right = probe;
		}
	}
	else { //descending
		for (int probe = N / 2, left = 0, right = N - 1;; probe = (left + right) / 2) {
			if (left + 1 == right) {
				cout << max(v[left], v[right]) << endl;
				return 0;
			}
			if (v[left] < v[probe]) 
				left = probe;
			else //normal
				right = probe;
		}

	}
}

c++CollabEdit/Broadway IV: implement hash table#I used py

Q: implement a hash table class in any language. You could use existing implementations of linked list, array, hash function…

Q: talk about how you would implement rehash?
%%A: hash code won’t change for the key objects. But I would rerun the modulus against the new bucketCount. Based on the new index values, I would create the linked lists in each new bucket. Every pair needs to be relocated. Lastly I need to get rid of the old bucket array.

Q: how would you test your hash table?
%%A: try inserting (key1, val1), then (key1, val2), then look up key1
%%A: if I know any common weakness of the hash function, then test those.
%%A: trigger rehash

Q: what could go wrong in a multi-threaded context?
%%A: things like lost update or duplicate entries

Q: What concurrency solution would you choose for best performance?
%%A: could use lockfree algo at each point of writing to the bucket array or writing to a linked list.

algo: minimum-cost array shrinking #Citadel

Input is a vector of positive integers. You are to shrink it progressively. Each step you remove 2 selected elements, and replace with their sum. Therefore vector size drops by 1 at each step, until there’s one element left.

At each step there’s a cost, which is defined as that sum.

Eg: {4,2,1} becomes {4,3} after you combine 2/1. The cost at this step is the sum 2+1=3.

Q1: For a given vector, find a sequence of steps with the lowest total cost. Test your code in c++
Q2: how would you optimize your code, assuming high data volume.

#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional> // std::greater
using namespace std;

vector<int> vec = { 3,2,1 }; // a std::set will fail when duplicate values show up like {3,3}
priority_queue<int, vector<int>, std::greater<int> > pq(vec.begin(), vec.end());

void dumpVector(string msg) {
 cout << msg << ", size = " << vec.size() << endl;
 for (auto it = vec.begin(); it != vec.end(); ++it) cout << *it << ' ';
 cout << endl;
}

int operateVector(int sum = 0) {
 auto lowestItem = min_element(vec.begin(), vec.end());
 sum += *lowestItem;
 vec.erase(lowestItem); // now s1 is an invalidated iterator and unusable

 //remove() is bad as it removes all not one item having target value!
 //v.erase(std::remove(v.begin(), v.end(), *lowestItem), v.end()); 

 dumpVector("afer erase");
 return sum;
}

void dumpHeap(string msg) {
 auto clone = pq;
 cout << msg << ", size = " << clone.size() << endl;
 for (; !clone.empty();clone.pop()) {
 std::cout << clone.top() << ' ';
 }
 cout << endl;
}
int operateHeap(int sum = 0) {
 sum += pq.top();
 pq.pop();
 //dumpHeap("afer pop");
 return sum;
}

int f1(int sum = 0) {
 return operateHeap(sum);
}
int main87() {
 int totalCost = 0;
 for (; pq.size()>1;) {
 int sum = f1(f1()); //call f1() twice recursively.
 pq.push(sum);
 dumpHeap("afer push");
 totalCost += sum;
 }
 cout << "total cost = " << totalCost << endl;
 return 0;
}

construct graph from list of connections #BGC

Given an input file showing a list of {string, string} pairs, build a connection graph.

If you have a correct connection graph, then you can easily determine the connectedness (bool) of any 2 nodes. In a social-network, this bool flag indicates whether 2 individuals are completely unconnected or somehow connected.

—-analysis:
I see this as a social-network. Any pair represents an edge connecting 2 nodes.  At any time there are a number of disconnected islands. The next pair could 1) merge 2 islands or 2) add a node to an existing island or 3) create a new island 4) do nothing, if the 2 nodes are already in some existing island

  • Any known node appears exactly once in the entire graph, in exactly one of the islands.
  • All nodes are contained in a lookup table or hashmap  {node -> island}
  • Each island can be a implemented as a hashset of nodes.

So here’s a proposed algo to process a new pair {A, B}. Look for A and B in the  graph. 3 scenarios + a dummy scenario:

  • (Scenario 3) If both A an B are new comers, then they form a new island.
  • if both A and B are already in the graph,
    • (Scenario 4) if they are in the same island, then exit. Nothing to do
    • (Scenario 1) else we can merge the 2 islands
  • (Scenario 2) If A is in island 3 but B is new comer, then B joins island 3

The merge operation is expensive. The big lookup table needs update but here’s an alternative:

  • At merge time, the smaller island would have all the nodes moved to the bigger island. When the island is empty, it gets a pointer “this.redirect” to the bigger island.
  • lookup table needs no update, avoiding locking a global object.
  • At query time, we look up the table to get the original island, then we follow its pointer (defaults to null) until the island is non-empty.
  • endless loop? would only be a programming error.

seek successor of a given node in a BST, without uplinks

Input: root node and an arbitrary node A.

We can’t start from A because by moving left/right, we may not be able to locate the successor. So we start from root and will encounter A.

I think this is a simple, barebones in-order walk entering at root. We will encounter A, and the next node encountered would be A’s successor.

Note this barebones walk requires no uplink.

max profit #max subarray sum is similar


/* max profit or biggest drop. one pass
max subarray sum -- is a similar problem, if you visualize the items as price changes
*/
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

template<typename T> void dump(vector<T> const & v){
	copy(v.begin(), v.end(), ostream_iterator<T>(cout, " "));
	cout<<endl;
}
int main(){
    vector<int> v={9,1,3,7,8,1,6,5}; //prices
	dump(v);

	// HighestProfit, LowestPx
	int hp=0, lpx=v[0];
	for (unsigned int i=1; i<v.size();++i){
		int aa=v[i];
		if (aa<lpx){
			lpx=aa;
			continue;
		}
		int profit = aa-lpx;
		if (profit > static_cast<int>(hp)){
			cout<<profit<<" > "<<hp<<endl;
			hp=profit;
		}
	}
	cout<<"ret = "<<hp;
}

substring search – Boyer-Moore

Q: write a python function match(string haystack, string nonRegexNeedle), following the simplified Boyer-Moore algo:

Try matching at the left end. If mismatch, then identify the left-most offending char (J) in haystack. Now locate the right-most position of J in needle (if not found then simply shift all the way past the J.) and right-shift the needle to align the two J.

So when would we right-shift  by one? Not sure. Some author suggests “do that only if the heuristic would suggest a left-shift”.

Brute force — shift by one, then attempt to match the entire substring. My code below is more efficient. Mostly it shifts by one each time, but checks just one char.

def visualize(haystack, substring, offset):
  print '\t--' + '0123456789 123456789 12345-----'
  print '\t--' + haystack
  print '\t--' + ' '*offset + substring
  print '\t--' + '-------------------------------'

def match(haystack, substring):
  offset = 0 # offset from left end of haystack. This is where substring is right now
  while(True):
    #now locate first offender in haytack
    offenderOffset, offender = -9999, ''
    for i, char in enumerate(substring):
       offenderOffset = offset+i
       if substring[i] != haystack[offenderOffset]:
         offender = haystack[offenderOffset]
         print offender + ' &lt;-- spotted at offenderOffset = ', offenderOffset
         visualize(haystack, substring, offset)       
         break;
         
    if offender == '': return True
    
    # now back-scan substring to locate offender, and then shift to align
    while True:
      offset += 1
      if offset + len(substring) &gt; len(haystack):
           print 'Gave up complately:'
           visualize(haystack, substring, offset)       
           return False
      if offenderOffset - offset == -1: 
        print 'gave up on aligning: '
        visualize(haystack, substring, offset)
        break
      if substring[offenderOffset - offset] == offender:
        print 'aligned: '
        visualize(haystack, substring, offset)
        break # go back to start of outer while loop

print match('aborb bdb', 'abors') 

 

simple-regex %%code #Facebook

EPI Question 6.23 is very similar to my Facebook interview. I told FB interviewer that we don’t NEED such problem solving at work. He said this is one method (standard method?) they assess a candidate’s coding abilities.

I feel it (and google questions) is like IQ test or probability test or abstract reasoning test — irrelevant to work, but used to assess learning capacity. They don’t want a dumb person on their team.

The truth is, practice is key. There are patterns. A very very smart person will still fail if without enough practice. A mediocre guy can speed up significantly if practised enough. I said the same thing to My Hwa Chong math teacher Tony Tan. This factor is also the reason I became so strong in physics.

Q: A simple regex (SRE) can use alphanumerics, dot and star. It is enclosed between implicit ^ and $. Write a match() function taking a SRE and a word. No white space allowed.

def match(haystack, regex):
      print   'regex = ', regex, '   haystack = ', haystack
      if 0==len(regex): return 0==len(haystack)
      
      c,d = (regex[0],'') if len(regex)==1 else regex[0:2]

      assert c != '*', "regex first char is star -- illegal"
      
      if    c != '.' :
         if d != '*' : # alphanumeric without star
              if len(haystack) == 0: return False
              if c!= haystack[0]: return False
              return match(haystack[1:], regex[1:])
         assert d == '*' # Example: Q* eating up none to all leading Q's, if any
         if 0==len(haystack): return match(haystack, regex[2:])
         
         print '   v v v v v   starting * loop with haystack %s vs %s' %(haystack, regex)
         i = 0
         while haystack[i] == c:
           print 'trying in * loop with i = ', i
           if match(haystack[i:], regex[2:]): 
              if len(haystack): print '  ^^^^^ ending * loop ^^^ good haystack %s vs %s' %(haystack[i:], regex[2:])
              return True
           assert haystack[i] == c 
           i+=1  
         print '      ^^^^^ ending * loop ^^^  bad'
         return False
                
      assert c == '.'
      
      if d != '*' : # dot without star matches any single character
          return match(haystack[1:], regex[1:])

      assert c == '.' and d == '*' # dot * requires iteration over haystack
      print '   v v v v v   starting  .* loop with haystack %s vs %s' %(haystack, regex)
      for i in [0]+range(1,len(haystack)): # 0 to len-1 but never empty loop
          print 'in loop, trying i = ', i
          if match(haystack[i:], regex[2:]) :
              if len(haystack): print '  ^^^^^ ending .* loop ^^^ good haystack %s vs %s' %(haystack[i:], regex[2:])
              return True
      print '      ^^^^^ ending .* loop ^^^  bad'
      return False

assert match('xyab-abc', '.*ab.*c.*x*')
assert match('xyab-abc', '.*ab.*c.*.*')
assert match('xyab-abc', '.*ab.*c')
assert match('aaaaaaab-abc', 'a*aab.*c')
assert match('aab-abc', 'a*aab.*c')
assert match('aabc', 'a*aab.*..*x*')
assert not match('abc', 'a*aab.*c')
assert match('a-aab', 'a*.*a*aab')
assert not match('a-aab', 'a*a*aab')