|
The commodities lifted energy equities, with coal stocks like Peabody (BTU), CONSOL (CEIX) and Alliance (ARLP) leading the sector higher. Oil-focused E&Ps like Devon (DVN), Continental (CLR) and Ovintiv (OVV) rallied 3%+ on the day. While natural gas names like EQT (EQT) and Southwestern (SWN) traded up 1-2%.
April 12, 2022
Here is the link.
C# | Last position | Bit manipulation | Study code
April 12, 2022
Introduction
There is only one C# solution in discuss, and I chose to study it and wrote my own C# code.
Bit manipulation
From each integer n from 0 to 9, 2^n can be ranged from 1 to 512. So it is working solution to define masks array using those 10 numbers.
Case study: 76263
Given an integer 76263, longest substring 626 can be swapped into a palindrome.
Substring starting from index = 0, "7" can be mapped to prefixes[0] = 2^7 = 128. How to find a longest substring starting from index = 1 which can be swapped to a palindrome substring.
One of search is to find lastPosition defined as int[1024], here key is 128, lastPosition[128], if it is not defined or found, the default value of integer array is 0. Since maximum substring default value is 1, it is not a problem using default value 0 of lastPosition.
Another of search is to go through all possible masks - 1st to 9th bit, masks array index position from 0 to 9, XOR two values, one is prefixes[0] = 2&6 = 128, and look for last position of the mask value. If it is not found, then lastPosition array's lookup is 0, and then
lastPosition[prefixes[i] ^ mask] - i + 1
The above expression returns negative value, which does not matter since it will not be bigger than default value 1 of variable answer - maximum length of substring.
So "7", with all possible one extra digit, look for lastPosition with same odd and even count of string "70","71","72","73","74","75","76","77","78","79".
First tip | Use array for 10 bits = 1111111111 in binary form = 2^9 + 2^8 + ...+ 2^0 < 2^10 = 1024 | Compare to use HashMap
It is hard level algorithm. Most of important is to design a working solution. Using array compared to HashMap on this algorithm definitely makes it easy to write a working solution.
Last position vs first position | Luck or smartness | I do not know
I chose to first position, but I came cross a bug and I could not fix it. My design and the algorithm failed one test case: 9498331. Here is my C# practice with failed test case.
I learned to write using last position by studying discuss section C# code. I do not know how to advance myself in such short time to prepare for May Meta onsite.
The following code passes online judge.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _1542_study_code
{
class Program
{
static void Main(string[] args)
{
var max = LongestAwesome("9498331");
Debug.Assert(max == 3);
var max2 = LongestAwesome("30003");
Debug.Assert(max2 == 5);
// 76263 - 30003
var max3 = LongestAwesome("76263");
Debug.Assert(max3 == 3);
}
/// <summary>
/// study code:
/// https://leetcode.com/problems/find-longest-awesome-substring/discuss/952409/C-Bit-Manipulation
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static int LongestAwesome(string s)
{
var masks = new int[] { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 };
var length = s.Length;
// calculate prefixes
var prefixes = new int[length + 1];
for (var i = 1; i <= length; i++)
{
// XOR - 1 or 0, even or odd count
prefixes[i] = prefixes[i - 1] ^ masks[s[i - 1] - '0'];
}
// calculate last indexes of prefixes
// 1024 - what for? 2^10 = 1024, 0 - 9, 2^0 = 1, ..., 2^9 = 512
var lastPosition = new int[1024];
for (var i = 0; i < s.Length; i++)
{
lastPosition[prefixes[i + 1]] = i;
}
var answer = 1;
// check max length between last index (+ any variations(10)) and current index
// I failed in my practice since I chose to work on previous position - this makes buggy code
for (var i = 0; i < length; i++)
{
answer = Math.Max(answer, lastPosition[prefixes[i]] - i + 1);
foreach (var mask in masks)
{
answer = Math.Max(answer, lastPosition[prefixes[i] ^ mask] - i + 1);
}
}
return answer;
}
}
}April 12, 2022
Here is the link.
C# | First position | Bit manipulation | Failed: "9498331" | Lessons learned
April 12, 2022
Introduction
It is a hard level algorithm. I chose to work on it, since I just did solve a similar bit manipulation algorithm 1371. Find the Longest Substring Containing Vowels in Even Counts based on discuss post by votrubac. I chose to work on first position of bit manipulation, and I came cross this failed test case "9498331". I could not solve the issue, and I just could not believe that how others solve the problem but no warning on this first position idea and its bugg issue.
Brute force solution | O(N^2)
It takes O(N^2) to find all substrings, and then it can be calculated to maximum substring to be swapped to a palindrome.
Optimal solution | Hashmap to record count of digits
It is easy to come out the design to use 10 bits to represent 0 to 9 10 digits, even or odd count using 0 or 1 to represent.
Case study | "9498331" | Should return 3, not 4
The following code failed test case: 78 / 153 test cases passed.
Input:
"9498331"
Output: 4
Should be: 3
Lesson learned:
Analysis:
949833
94 - remove 9, so, 4 maps to a number 1<< 4 = 2^4 = 16.
949833 - remove 8, 94933 maps to a number 1 << 4 = 2^4 = 16
first position with 16's index = 1, and the current positon with 16's index = 5, so the answer is 4, but "9833" can not be a palindrome by the option to remove one char.
There are more than two issues in my design using those 10 bits mask to map 0 to 9 10 digits. It took me hours to figure out what is wrong, and how to address the issues.
Faulty design | Save substring with all possible one extra digit into HashMap
I just gave it a quick try without strictly proof that it should work. I even save extra key into HashMap to pad at the end one more digit - any digit from 0 to 9.
I chose to use first position, and then handle extra digit case. It is not easy to figure out so many things in such a short time. Just be patient. Learn from those failed submissions and those failed test cases, and I think that the failures should be best teacher for me. To prepare for Mata onsite in May 2022, I should try 10 hard level algorithms, and learn from all those mistakes in practice. Here is my discuss post related to Meta onsite 30 day preparation.
I should work on last position instead.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _1542_find_longest_awesome_substring
{
class Program
{
static void Main(string[] args)
{
//var maximumLength = LongestAwesome("3242415");
//Debug.Assert(maximumLength == 5);
var max = LongestAwesome("9498331");
Debug.Assert(max == 3);
}
/// <summary>
/// April 8, 2022
/// Brute force solution O(N^2)
/// find all substrings and then check if it is an awesome substring
/// Optimal solution should be O(N), go through the array once, and then
/// record all digits count in terms of even or odd, using one integer 10 bits
/// to contain all 10 bits - left to right, 0 - 9
///
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static int LongestAwesome(string s)
{
if (s == null || s.Length == 0)
{
return 0;
}
var map = new Dictionary<int, int>();
map.Add(0, -1); //
var length = s.Length;
var bitsForDigits = 0;
var maxLength = 0;
// 0 ^ 0 = 0
// 0 ^ 1 = 1
// 1 ^ 1 = 1 // xor - determine odd or even in each bit
for (int i = 0; i < length; i++)
{
var digit = s[i] - '0';
bitsForDigits ^= 1 << digit;
if (!map.ContainsKey(bitsForDigits))
{
map.Add(bitsForDigits, i);
}
else
{
maxLength = Math.Max(maxLength, i - map[bitsForDigits]);
}
// search odd matching
// brute force all digits with 1 - at most 10 cases
for (int shift = 0; shift <= 9; shift++)
{
// mask one bit
if ((bitsForDigits & (1 << shift)) == 0)
{
continue;
}
var key = bitsForDigits ^ (1 << shift); // remove one digit
if (!map.ContainsKey(key))
{
map.Add(key, i);
}
else
{
// 949833, remove 4, 99833, but 8's count is odd
//if (key == 0) // make sure that all digits have even count
{
maxLength = Math.Max(maxLength, i - map[key]);
}
}
}
}
return maxLength;
}
}
}April 12, 2022
I try to manage myself better in terms of equity research, organize discussion of equities, and also track my progress and balance the art of risk and return.
April 11, 2022
I understand that it is important for me to learn from T purchase. I do not know too much about AT & T, since I am so frugal and do not use monthly service plan of mobile phone. I live to minimum level and try to survive in Canada, in other area I do not know how T business brings into life and business change on most people. I decided to make changes.
April 9, 2022
It is important to learn how to be a value investor. I think that I could not learn oil stock and values of stocks, and learn lesson. I like to share with friends, and encourage myself to learn better as an investor
CVE.TO and CNQ.TO stock
April 9, 2022
It is my quick review of my Ameritrade.com IRA account. I had very big loss and my balance dropped from $29,274 to $24,500 in less than one month. I was too busy but actually too lazy, I thought that it will rebound as usual. It is hard to get back from lowest point $24,500. Now my balance is around $27,275.00 dollars.
I like to write down something to learn from my own experience.
April 7, 2022
It takes time for me to learn as a value investor or long term investor. I think that life is more important to live in peace and happy thing in daily life, but as an investor on stock market, it takes a lot of learning and pain to go through up and downs, and then I still do not make profit, and easy to see those profits to go away.
April 7, 2022
Here is the link.
I like to spend hours to learn more detail about crude oil price, and gas price.
1:12:28/ 6:07:29
Buy back and increase dividend for shareholders - increase production / invest
77 billion profit - dividend, buyback - increase production, not shareholder wealth, six companies here.
60,000 people laidoff - 2022 - gauge American people today
So if I buy $T shares after 04/05/22 I won't get any shares of WBD? serious question, thanks in advance!
