[Facebook] Products of all elements

Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i.

Input : [1, 2, 3, 4, 5]

Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]

      = [120, 60, 40, 30, 24]

You must do this in O(N) without using division.

[Thoughts]

An explaination of polygenelubricants method is: The trick is to construct the arrays (in the case for 4 elements)

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

Both of which can be done in O(n) by starting at the left and right edges respectively.
Then multiplying the two arrays element by element gives the required result
My code would look something like this:

int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i)
{
  products_below[i]=p;
  p*=a[i];
}

int products_above[N];
p=1;
for(int i=N-1;i>=0;--i)
{
  products_above[i]=p;
  p*=a[i];
}

int products[N]; // This is the result
for(int i=0;i<N;++i)
{
  products[i]=products_below[i]*products_above[i];
}

If you need to be O(1) in space too you can do this (which is less clear IMHO)

int a[N] // This is the input
int products[N];

// Get the products below the curent index
p=1;
for(int i=0;i<N;++i)
{
  products[i]=p;
  p*=a[i];
}

// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i)
{
  products[i]*=p;
  p*=a[i];
}

[FaceBook] Hanoi Moves, Solution

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.
A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
At anypoint of time, the decreasing radius property of all the pegs must be maintained.

Constraints:
1<= N<=8
3<= K<=5


Input Format:
N K
2nd line contains N integers.
Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
3rd line denotes the final configuration in a format similar to the initial configuration.

Output Format:
The first line contains M - The minimal number of moves required to complete the transformation.
The following M lines describe a move, by a peg number to pick from and a peg number to place on.
If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one.

Sample Input #00:

2 3
1 1
2 2
Sample Output #00:

3
1 3
1 2
3 2


Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1
Sample Output #01:
5
3 1
4 3
4 1
2 1
3 1
NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout
If you are using "Java", the classname is "Solution"


[Thoughts]
No good idea, only brute-force can hit my mind now. seems a simple question, but the implementation really costs me some time.

Update: some people talk about using tree to do the BFS (http://comments.gmane.org/gmane.comp.programming.algogeeks/30920) or A* search (http://en.wikipedia.org/wiki/A*_search_algorithm). But I would say this is a bit over engineering.


[Code]

1:  /*  
2:  Please write complete compilable code.  
3:  Read input from standard input (STDIN) and print output to standard output(STDOUT).  
4:  For more details, please check https://www.interviewstreet.com/recruit/challenges/faq/view#stdio  
5:  */  
6:  #include <climits>  
7:  #include <iostream>  
8:  using namespace std;   
9:  int initial[9];  
10:  int expected[9];  
11:  int CurDiscInPeg[9];  
12:  int n, k;  
13:  int moveSeq[9][2];  
14:  int minSteps = 7;  
15:  int minMoveSeq[9][2];  
16:  void refreshPeg()  
17:  {  
18:    for(int i =1; i<= k; i++)  
19:    {  
20:      CurDiscInPeg[i] = INT_MAX; //no disk on it.  
21:      for(int j =1; j<=n; j++)  
22:      {  
23:        if(initial[j] == i)  
24:        {  
25:          CurDiscInPeg[i] =j;  
26:          break;  
27:        }  
28:      }  
29:    }  
30:  }  
31:  bool verify(int depth)  
32:  {  
33:    int z = 1;  
34:    for(; z<=n; z++)  
35:    {  
36:      if(initial[z]!=expected[z])  
37:        return false;  
38:    }  
39:    minSteps = depth;  
40:    for(int z = 1; z<=minSteps; z++)  
41:    {  
42:      minMoveSeq[z][0] = moveSeq[z][0];  
43:      minMoveSeq[z][1] = moveSeq[z][1];  
44:    }       
45:    return true;        
46:  }  
47:  void Move(int depth)  
48:  {  
49:    if(depth > minSteps) return;  
50:    for(int i =1; i<=k; i++)  
51:    {  
52:      for(int j=1; j<=k; j++)  
53:      {  
54:        if(CurDiscInPeg[i] >= CurDiscInPeg[j])  
55:          continue;  
56:        int disc = CurDiscInPeg[i];  
57:        initial[disc] = j;  
58:        moveSeq[depth][0] = i;  
59:        moveSeq[depth][1] = j;  
60:        if(verify(depth)) return;  
61:        refreshPeg();  
62:        Move(depth+1);  
63:        initial[disc] = i;  
64:        refreshPeg();  
65:      }  
66:    }  
67:  }  
68:  int main()  
69:  {  
70:    cin>>n;  
71:    cin>>k;  
72:    for(int i =1; i<=n; i++)  
73:    {  
74:      cin>>initial[i];  
75:    }  
76:    for(int i =1; i<=n; i++)  
77:    {  
78:      cin>>expected[i];  
79:    }  
80:    refreshPeg();  
81:    Move(1);  
82:    cout<<minSteps<<endl;  
83:    for(int i =1; i<=minSteps; i++)  
84:    {      
85:      cout<<minMoveSeq[i][0]<<" "<<minMoveSeq[i][1]<<endl;  
86:    }  
87:  }  

[LeetCode] Decode Ways, Solution

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

» Solve this problem

[Thoughts]

Similar as "[LeetCode] Climbing Stairs, Solution". DP. Just add some logic to compare character.

Transformation function as:
Count[i] = Count[i-1]  if S[i-1] is a valid char
       or   = Count[i-1]+ Count[i-2]  if S[i-1] and S[i-2] together is still a valid char.

[Code]

1:    int numDecodings(string s) {  
2:      if(s.empty() || s[0] =='0') return 0;      
3:      if(s.size() ==1) return check(s[0]);  
4:      int fn=0, fn_1=0, fn_2=1;      
5:      fn_1 = (check(s[0]) * check(s[1]))+check(s[0], s[1]);       
6:      for(int i=2; i< s.size(); i++)  
7:      {    
8:        if(check(s[i])) fn+= fn_1;         
9:        if(check(s[i-1], s[i])) fn+=fn_2;  
10:        if(fn ==0)   
11:          return 0;  
12:        fn_2 = fn_1;  
13:        fn_1 = fn;  
14:        fn=0;     
15:      }  
16:      return fn_1;  
17:    }  
18:    int check(char one)   
19:    {  
20:      return (one != '0') ? 1 : 0;      
21:    }  
22:    int check(char one, char two)  
23:    {  
24:      return (one == '1' || (one == '2' && two <= '6'))  
25:      ? 1 : 0;      
26:    }   

[LeetCode] Count and Say, Solution

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

» Solve this problem

[Thoughts]
string-operation. The only trick thing is Line11. seq[seq.size()] always '\0'. It will help to save an "if" statement.


[Code]

1:    string countAndSay(int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      string seq = "1";  
5:      int it = 1;  
6:      while(it<n)  
7:      {  
8:        stringstream newSeq;  
9:        char last = seq[0];  
10:        int count =0;  
11:        for(int i =0; i<= seq.size();i++)  
12:        {  
13:          if(seq[i] ==last)  
14:          {  
15:            count ++;  
16:            continue;  
17:          }  
18:          else  
19:          {  
20:            newSeq<<count<<last;  
21:            last = seq[i];   
22:            count =1;  
23:          }  
24:        }  
25:        seq = newSeq.str();  
26:        it++;  
27:      }  
28:      return seq;  
29:    }  

[LeetCode] Convert Sorted List to Binary Search Tree, Solution

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

» Solve this problem

[Thoughts]
It is similar with "Convert Sorted Array to Binary Search Tree". But the difference here is we have no way to random access item in O(1).

If we build BST from array, we can build it from top to bottom, like
1. choose the middle one as root,
2. build left sub BST
3. build right sub BST
4. do this recursively.

But for linked list, we can't do that because Top-To-Bottom are heavily relied on the index operation.
There is a smart solution to provide an Bottom-TO-Top as an alternative way, http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

With this, we can insert nodes following the list’s order. So, we no longer need to find the middle element, as we are able to traverse the list while inserting nodes to the tree.

[Code]

1:    TreeNode *sortedListToBST(ListNode *head) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int len =0;  
5:      ListNode *p = head;  
6:      while(p)  
7:      {  
8:        len++;  
9:        p = p->next;  
10:      }  
11:      return BuildBST(head, 0, len-1);  
12:    }  
13:    TreeNode* BuildBST(ListNode*& list, int start, int end)  
14:    {  
15:      if (start > end) return NULL;  
16:      int mid = (start+end)/2;   //if use start + (end - start) >> 1, test case will break, strange!
17:      TreeNode *leftChild = BuildBST(list, start, mid-1);  
18:      TreeNode *parent = new TreeNode(list->val);  
19:      parent->left = leftChild;  
20:      list = list->next;  
21:      parent->right = BuildBST(list, mid+1, end);  
22:      return parent;  
23:    }  

[LeetCode] Container With Most Water, Solution

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

» Solve this problem

[Thoughts]
For any container, its volume depends on the shortest board.
Two-pointer scan. And always move with shorter board index.


[Code]

1:    int maxArea(vector<int> &height) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int start =0;  
5:      int end = height.size()-1;  
6:      int maxV = INT_MIN;  
7:      while(start<end)  
8:      {  
9:        int contain = min(height[end], height[start]) * (end-start);  
10:        maxV = max(maxV, contain);  
11:        if(height[start]<= height[end])  
12:        {  
13:          start++;  
14:        }  
15:        else  
16:        {  
17:          end--;  
18:        }  
19:      }  
20:      return maxV;  
21:    }  

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal, Solution

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

» Solve this problem

[Thoughts]

There is an example.

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11

The preorder and inorder traversals for the binary tree above is:

preorder = {7,10,4,3,1,2,8,11}
inorder = {4,10,3,1,7,11,8,2}

The first node in preorder alwasy the root of the tree. We can break the tree like:
1st round:
preorder:  {7}, {10,4,3,1}, {2,8,11}
inorder:     {4,10,3,1}, {7}, {11, 8,2}

        _______7______
       /              \
    {4,10,3,1}       {11,8,2}

Since we alreay find that {7} will be the root, and in "inorder" sert, all the data in the left of {7} will construct the left sub-tree. And the right part will construct a right sub-tree. We can the left and right part agin based on the preorder.

2nd round
left part                                                                            right part
preorder: {10}, {4}, {3,1}                                              {2}, {8,11}
inorder:  {4}, {10}, {3,1}                                                {11,8}, {2}

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4      {3,1}   {11,8}

see that, {10} will be the root of left-sub-tree and {2} will be the root of right-sub-tree.

Same way to split {3,1} and {11,8}, yo will get the complete tree now.

        _______7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11

So, simulate this process from bottom to top with recursion as following code.

[Code]

1:    TreeNode *buildTree(  
2:      vector<int> &preorder,   
3:      vector<int> &inorder) {  
4:      // Start typing your C/C++ solution below  
5:      // DO NOT write int main() function  
6:      return BuildTreePI(  
7:        preorder, inorder, 0, preorder.size()-1, 0, preorder.size());  
8:    }    
9:    TreeNode* BuildTreePI(  
10:      vector<int> &preorder,  
11:      vector<int> &inorder,  
12:      int p_s, int p_e,  
13:      int i_s, int i_e)  
14:    {  
15:      if(p_s > p_e)  
16:        return NULL;  
17:      int pivot = preorder[i_s];  
18:      int i =p_s;  
19:      for(;i< p_e; i++)  
20:      {  
21:        if(inorder[i] == pivot)  
22:          break;  
23:      }  
24:      TreeNode* node = new TreeNode(pivot);  
25:      node->left = BuildTreePI(preorder, inorder, p_s, i-1, i_s+1, i-p_s+i_s);  
26:      node->right = BuildTreePI(preorder, inorder, i+1, p_e, i-p_s+i_s+1, i_e);  
27:      return node;      
28:    }