Blogs

2xx Success

indicates the action requested by the client was received, understood, accepted, and processed successfully.

★ 200 OK

★ 201 Created

★ 202 Accepted

4xx Client Error

indicates client seems to have requested invalid information

★ 400 Bad Request

★ 401 Unauthorized

★ 402 Payment Required

★ 403 Forbidden

★ 404 Not Found

5xx Server Error

The server failed to fulfill an apparently valid request.

★ 500 Internal Server Error

★ 501 Not Implemented

★ 502 Bad Gateway

★ 503 Service Unavailable

★ 504 Gateway Timeout

... [Click on the blog title or image to read the entire blog.]

Tewodros | May. 29, 2024 | 265 Views |

using System;
using System.Collections.Generic;
using System.Linq;

public class Product
{
public int ProductId { get; set; }
public string Name { get; set; }
public decimal Price { get; set; }
public int CategoryId { get; set; }
}

public class Category
{
public int CategoryId { get; set; }
public string Name { get; set; }
}

public class Order
{
public int OrderId { get; set; }
public int ProductId { get; set; }
public int Quantity { get; set; }
}

public class Program
{
public static void Main()
{
List<Product> productList = new List<Product>
{
new Product { ProductId = 1, Name = "Product1", Price = 100, CategoryId = 1 },
new Product { ProductId = 2, Name = "Product2", Price = 200, CategoryId = 1 },
new Product { ProductId = 3, Name = "Product3", Price = 300, CategoryId = 2 }
};

List<Category> categoryList = new List<Category>
{
new Category { CategoryId = 1, Name = "Category1" },
new Category { CategoryId = 2, Name = "Category2" }
};
List<Order> OrderList = new List<Order>
{
new Order { OrderId = 1, ProductId = 1, Quantity = 5 },
new Order { OrderId = 2, ProductId = 1, Quantity = 3 },
new Order { OrderId = 3, ProductId = 2, Quantity = 2 },
new Order { OrderId = 4, ProductId = 3, Quantity = 4 },
new Order { OrderId = 5, ProductId = 3, Quantity = 1 }
};

var results = from product in productList
join category in categoryList on product.CategoryId equals category.CategoryId
select new
{
ProductId = product.ProductId,
ProductName = product.Name,
CategoryName = category.Name,

};

var result = from product in productList
join order in OrderList on product.ProductId equals order.ProductId
join category in categoryList on product.CategoryId equals category.CategoryId
select new
{
ProductId = product.ProductId,
ProductName = product.Name,
CategoryName = category.Name,
OrderQuantity = order.Quantity
};

foreach (var item in result)
{
Console.WriteLine($"Category: {item.CategoryName}, Product: {item.ProductName}, Order Quantity: {item.OrderQuantity}");
}

}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | May. 28, 2024 | 254 Views |

using System;
using System.Collections.Generic;
using System.Linq;

public class Product
{
public int ProductId { get; set; }
public string Name { get; set; }
public decimal Price { get; set; }
public int CategoryId { get; set; }
}

public class Category
{
public int CategoryId { get; set; }
public string Name { get; set; }

}

public class Program
{
public static void Main()
{
List<Product> productList = new List<Product>
{
new Product { ProductId = 1, Name = "Product1", Price = 100, CategoryId = 1 },
new Product { ProductId = 2, Name = "Product2", Price = 200, CategoryId = 1 },
new Product { ProductId = 3, Name = "Product3", Price = 300, CategoryId = 2 },
new Product { ProductId = 4, Name = "Product4", Price = 400, CategoryId = 2 },
new Product { ProductId = 5, Name = "Product5", Price = 500, CategoryId = 3 },
new Product { ProductId = 6, Name = "Product6", Price = 600, CategoryId = 3 }
};

List<Category> categoryList = new List<Category>
{
new Category { CategoryId = 1, Name = "Category1" },
new Category { CategoryId = 2, Name = "Category2" },
new Category { CategoryId = 3, Name = "Category3" }
};

// Group products by category and select relevant data
var groupedProducts = categoryList
.Select(c => new
{
Category = new Category
{
CategoryId = c.CategoryId,
Name = c.Name
},
Products = productList
.Where(p => p.CategoryId == c.CategoryId && p.Price > 100)
.OrderBy(p => p.Name)
.Select(p => new Product
{
ProductId = p.ProductId,
Name = p.Name,
Price = p.Price,
CategoryId = p.CategoryId,
})
.ToList()
})
.ToList();

// Display the results
foreach (var g in groupedProducts)
{
Console.WriteLine($"Category: {g.Category.Name}");
foreach (var p in g.Products)
{
Console.WriteLine($"\tProduct ID: {p.ProductId}, Name: {p.Name}, Price: {p.Price}");
}
}
}
}

If you want to use keywords like skip, take, distinct, Any

var catlist = categoryList
.Select(c => new
{
Category = new Category
{
CategoryId = c.CategoryId,
Name = c.Name
},
Products = productList
.Where(p => p.CategoryId == c.CategoryId)
.Distinct() // Ensure distinct products
.OrderByDescending(p => p.Price) // Order products by price in descending order
.Skip(1) // Skip the first product
.Take(2) // Take only 2 products
.Select(p => new Product
{
ProductId = p.ProductId,
Name = p.Name.ToLower(), // Convert product name to lowercase
Price = p.Price * 0.9m // Apply a discount of 10% to the product price
}).ToList()
})
.Where(cat => cat.Products.Any()) // Filter out categories with no products
.ToList();

In this modified code:

I've added .Distinct() to ensure that only distinct products are selected.
.OrderByDescending(p => p.Price) is used to order products by price in descending order.
.Skip(1) is used to skip the first product in each category.
.Take(2) is used to take only 2 products from each category.
.Where(cat => cat.Products.Any()) is used to filter out categories with no products.
I've also applied a 10% discount to the product price by multiplying it by 0.9.

... [Click on the blog title or image to read the entire blog.]

Tewodros | May. 28, 2024 | 271 Views |

The PARTITION BY clause in SQL is often used with window functions to perform calculations across sets of rows that are related to the current row.

RANK(): This column shows the rank of each sale within each salesperson partition, skipping ranks for ties.

DENSE_RANK(): This column shows the dense rank of each sale within each salesperson partition, without skipping ranks for ties.

SUM(): This column shows the total sales for each salesperson.

AVG(): This column shows the average sale amount for each salesperson.

To find the top sale for each salesperson based on the sale_amount, we can use the ROW_NUMBER() window function partitioned by salesperson_id:

SELECT
sale_id,
salesperson_id,
sale_amount,
sale_date,
ROW_NUMBER() OVER (PARTITION BY salesperson_id ORDER BY sale_amount DESC) as rank
FROM
sales;

Filtering to Get Top Sales

To get only the top sale for each salesperson, you can wrap the above query in a subquery and filter on the rank:

SELECT
sale_id,
salesperson_id,
sale_amount,
sale_date
FROM
(SELECT
sale_id,
salesperson_id,
sale_amount,
sale_date,
ROW_NUMBER() OVER (PARTITION BY salesperson_id ORDER BY sale_amount DESC) as rank
FROM
sales) ranked_sales
WHERE
rank = 1;

sale_id	salesperson_id	sale_amount	sale_date
1	101	500	2024-01-01
4	102	700	2024-01-01
6	103	400	2024-01-01

We can use Common Table Expression (CTE) to rewrite the last query as follows:

WITH RankedSales AS (
SELECT
sale_id,
salesperson_id,
sale_amount,
sale_date,
ROW_NUMBER() OVER (PARTITION BY salesperson_id ORDER BY sale_amount DESC) AS rank
FROM
sales
)
SELECT
sale_id,
salesperson_id,
sale_amount,
sale_date
FROM
RankedSales
WHERE
rank = 1;

... [Click on the blog title or image to read the entire blog.]

Tewodros | May. 20, 2024 | 431 Views |

Check if a given number is Palindrome. That is the number is the same when it reads forward and backward.

Example

5665

Solution

If we know how to reverse a number then it is easy to check it.

public class Solution {
public bool IsPalindrome(int x) {
if(x<0) return false;
if(x == reverse(x)) return true;

return false;
}

int reverse(int n)
{
int res = 0;
while(n != 0)
{
res = res * 10 + n%10;
n=n/10;
}
return res;
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Mar. 16, 2024 | 521 Views |

Given a string(word) with a combination of vowels and consonants , we want to reverse just the vowels only with out disturbing the place of the consonants

Example

happen Ans: heppan

public string ReverseVowels(string s) {
StringBuilder sb = new StringBuilder(s);

char [] v = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
int i=0, j=s.Length-1;
while(i<j)
{
if(v.Contains(sb[i]))
{
if(v.Contains(sb[j]))
{
char temp = sb[i];
sb[i] = sb[j];
sb[j] = temp;
i++;j--;
}
else
j--;
}
else
i++;
}
return sb.ToString();
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 28, 2024 | 338 Views |

Mark matrix corresponding row and column 0 if you find 0 at the given index (i,j)

Example

Input

[1 1 1]

[1 0 1]

[1 1 1]

Output

[1 0 1]

[0 0 0]

[1 0 1]

public class Solution {
public void SetZeroes(int[][] matrix) {
int m = matrix.Length;
int n = matrix[0].Length;

bool firstRowZero = false;
bool firstColZero = false;

// Check if the first row contains zero
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
}

// Check if the first column contains zero
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
}

// Use the first row and first column to mark rows and columns containing zeros
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}

// Set rows and columns to zero based on marks in the first row and first column
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}

// Set the first row to zero if needed
if (firstRowZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}

// Set the first column to zero if needed
if (firstColZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 27, 2024 | 359 Views |

Given a list of integers array we want to rotate the numbers to the right K times

Example

[1,2,3,4,5] k = 3

Ans:

[3,4,5,1,2]

Solution

This problem can be solved as follows.

Reverse the entire array.
Reverse the first k elements of the array.
Reverse the remaining elements of the array.

public class Solution {
public void Rotate(int[] nums, int k) {
if (nums == null || nums.Length <= 1 || k % nums.Length == 0) return;

k %= nums.Length;

Reverse(nums, 0, nums.Length - 1);
Reverse(nums, 0, k - 1);
Reverse(nums, k, nums.Length - 1);
}

private void Reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 27, 2024 | 453 Views |

Given any positive integer, we want to know how many trailing 0s does it have.

Example

1000 Ans. 3

4500 Ans 2

Solution

In order to find this we just need to see how many times the number can be divided by 5

public class Solution {
public int TrailingZeroes(int n) {
int count = 0;
while (n > 0) {
n /= 5;
count += n;
}
return count;
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 27, 2024 | 378 Views |

Given any positive integer, we want to know how many trailing 0s does it have.

Example

1000 Ans. 3

4500 Ans 2

Solution

In order to find this we just need to see how many times the number can be divided by 5

public class Solution {
public int TrailingZeroes(int n) {
int count = 0;
while (n > 0) {
n /= 5;
count += n;
}
return count;
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 27, 2024 | 324 Views |

Create a new stack like data structure with Push, Pop and Get Min that runs in O(1).

Solution

The key to solving this problem is what kind of data structure we shall use in the stack class to compute the min in linear time.

For this the best approach is to use another stack called MinStack which will keep track of all the minimum elements of the array in their size order.

Basically we keep checking if the min stack has the least element at the top and if we we encounter a new min we just keep pushing to the top of the list on the minstack

public class MinStack {
private Stack<int> stack;
private Stack<int> minStack;

public MinStack() {
stack = new Stack<int>();
minStack = new Stack<int>();
}

public void Push(int val) {
stack.Push(val);
if (minStack.Count == 0 || val <= minStack.Peek()) {
minStack.Push(val);
}
}

public void Pop() {
if (stack.Count == 0) return;

int popped = stack.Pop();
if (popped == minStack.Peek()) {
minStack.Pop();
}
}

public int Top() {
if (stack.Count == 0) throw new InvalidOperationException("Stack is empty");
return stack.Peek();
}

public int GetMin() {
if (minStack.Count == 0) throw new InvalidOperationException("Stack is empty");
return minStack.Peek();
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 27, 2024 | 347 Views |

Given a list of integers, we want to find a subarray with maximum product.

Example:

[1,-2,4,2,-2] Ans: 32

[5,3,1,-2, 0, -4,10,-10]. Ans: 400

Solution:

Here we need to track of minimum product and max product and we ask our selves if it is better of to take:

just the number at the given index or
the product of the number at the given index with the min prod or
the product of the number at the given index with the max prod

Don’t forget to save the prev min value in a temp variable to avoid overwritten by the new min

public int MaxProduct(int[] nums) {
if(nums.Length == 1 )
return nums[0];
int min = nums[0], max= nums[0];
int maxProd = max;
for(int i=1 ;i < nums.Length; i++)
{
int temp = min;
min = Math.Min(Math.Min(temp * nums[i], max * nums[i]), nums[i]);
max = Math.Max(Math.Max(temp * nums[i], max * nums[i]), nums[i]);
maxProd = Math.Max(max, maxProd);
}
return maxProd;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 27, 2024 | 381 Views |

Given a sorted list of numbers in a linked list we want to remove all occurrence of duplicates and return a list with out them. Note that we need to delete the number that is repeated altogether without leaving one.

Example:

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

Ans:

[1,2,5]

Solution:

We can have two pointers , curr and prev.

The curr pointer will move to the end of the repeating sub array while the prev pointer is staying at the beginning of the repeating sub array.

Then we break the link to set the next of the prev pointer to the next of curr pointer and by doing so we delete all the occurrences of a the repeating numbers.

We shall repeat the above step as long as the curr pointer doesn’t reach the end.

public ListNode DeleteDuplicates(ListNode head)
{
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode current = head;

while (current != null) {
while (current.next != null && current.val == current.next.val) {
current = current.next;
}

if (prev.next == current) {
prev = prev.next;
} else {
prev.next = current.next; //this deletes of repeated numbers
}

current = current.next;
}

return dummy.next;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 26, 2024 | 340 Views |

Given a list of integers that represents the daily temperatures, we want to calculate the number of days one has to wait to see a higher temp calculated for each day.

Example

nums = [9,6,10,4,11]

Ans = [2,1,2,1,0]

Example

nums = [73,72,71,70,90]

Ans = [4,3,2,1,0]

Example

nums = [73,72,71,70]

Ans = [0,0,0,0]

Solution

The right data structure for this is stack.

We need to push the daily temps in the stack as long as we don't see a higher temperature. But when we do, we keep removing them one by one from the stack and calculate the distance. For this purpose we need to store the index of the temp array not the actual values.

In the case where we won't see any temp increase, we don't need to do any thing since we have already initialized all the elements of the result array as 0.

public int[] DailyTemperatures(int[] temperatures) {
int n = temperatures.Length;
int[] result = new int[n];
Stack<int> stack = new Stack<int>();

for (int i = 0; i < n; i++) {
while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()]) {
int prevIndex = stack.Pop();
result[prevIndex] = i - prevIndex;
}
stack.Push(i);
}
return result;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 16, 2023 | 716 Views |

Given a list of numbers and a target, return the minimal length of a subarray whose sum is greater than or equal to target. Otherwise return 0.

Example:

nums = {3, 5, 6, 2 , 5, 7}

target = 12

Ans: 2

Explanation: the subarray 5,7 sum = 12.

We can use sliding window approach. We will have two pointers I (left) and J(right). We increment j while calculating the sum of subarray between I and j is less than target. We then check if sum ≥ target, if so we calculate the distance between I and j and save it in a min variable.

public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int sum =0;
int i=0, j=i+1;
int min = Int32.MaxValue;
sum = nums[0];
while(i <nums.Length && j <= nums.Length)
{
if(i > 0)
sum = sum - nums[i-1];
while(sum<target && j < nums.Length)
{
sum +=nums[j];
j++;
}
if(sum >= target)
min = Math.Min((j-i), min);

i++;
}
return (min == Int32.MaxValue)?0:min;
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 15, 2023 | 405 Views |

Binary search tree level by level average

We need to use a for loop with BFS to solve this problem.

class Program
{
public class Solution
{
static void Main()
{

MyBST bst = new MyBST();
bst.InsertNode(11);
bst.InsertNode(9);
bst.InsertNode(12);
bst.InsertNode(8);
bst.InsertNode(10);
bst.printTree(bst.head);
Console.WriteLine("____");
IList<double> ans = bst.AverageOfLevels(bst.head);
foreach (double num in ans)
Console.WriteLine(num);
}

public class MyBST
{
public TreeNode head { get; set; }
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
{
this.val = val;
this.left = left;
this.right = right;
}
}

public void InsertNode(int x)
{
insert(x, head);
}
public void insert(int x, TreeNode root)
{
if (root == null)
{
TreeNode n = new TreeNode(x, null, null);
root = n;
head = n;
}

else
{
if (x < root.val)
{
if (root.left == null)
{
TreeNode n = new TreeNode(x, null, null);
root.left = n;
}
else
insert(x, root.left);
}

else if (x > root.val)
{
if (root.right == null)
{
TreeNode n = new TreeNode(x, null, null);
root.right = n;
}
else
insert(x, root.right);
}
}
}

public IList<double> AverageOfLevels(TreeNode root)
{
Queue<TreeNode> q = new Queue<TreeNode>();
IList<double> list = new List<double>();

if (root != null)
{
q.Enqueue(root);
while (q.Count != 0)
{
int c = q.Count;
double sum = 0;

for (int i = 0; i < c; i++)
{
TreeNode curRoot = q.Dequeue();
if (curRoot != null)
{
sum += curRoot.val;
}

if (curRoot.left != null)
q.Enqueue(curRoot.left);
if (curRoot.right != null)
q.Enqueue(curRoot.right);
}

list.Add(sum / c);
}
}
return list;
}

public void printTree(TreeNode root)
{

Queue<TreeNode> queue = new Queue<TreeNode>();

queue.Enqueue(root);

while (!(queue.Count == 0))
{

TreeNode node = queue.Peek();

if (node != null)
{

Console.WriteLine(node.val + " ");

queue.Dequeue();

if (node.left != null)

queue.Enqueue(node.left);

if (node.right != null)

queue.Enqueue(node.right);

}

}
}
}

}

}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 3, 2023 | 520 Views |

Given a sorted integers and a target value, return the index if the target is found. If not, return the index where it should be inserted.

Example

Input:

nums = [1,3,5,5,6], target = 2

Output:

1

Input: nums = [1,2,3,5,6], target = 7 Output: 5

Solution

we can use binary search to find if the number exist in the given list. If so, return the index.

If not, we will do a modification of binary search in which we keep finding the index where the target should be and we return the index

public class Solution {

public int SearchInsert(int[] nums, int target)
{
int res = Array.BinarySearch(nums, target);
if (res < 0)
return BS(0, nums.Length, nums, target);
else
return res;
}

public int BS(int low, int high , int[] nums, int target)
{
if (low >= high)
return low;
int mid = (low + high) / 2;
if (nums[mid] > target)
return BS(low, mid, nums, target);

else
return BS(mid+1,high, nums, target);
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 2, 2023 | 437 Views |

Given a list of numbers as an array treat it as a whole number and add one to it and return the result as an array

Example

Input [9,9,9 ]

Output [1,0,0,0]

Example

Input [8,9,9]

output [9,0,0]

public int[] PlusOne(int[] nums)
{

   int[] result = new int[nums.Length+1];

   bool carry = false;
   bool first = true;
   for (int i = nums.Length-1; i>=0; i--)
   {
if (first && nums[i] == 9)
   {
   result[i+1] = 0;
   carry = true;
   }
else
   {
   if (carry || first)
   {
   result[i+1] = nums[i] + 1;
   first = false;
   carry = false;
   }
   else
   result[i+1] = nums[i];
   }
   }
   if (carry)
   result[0] = 1;

   if (result[0] == 0)
   {
   int[] res = new int[nums.Length];
   for (int i = 0; i < result.Length-1; i++)
   {
res[i] = result[i + 1];

   }
   return res;
   }

   return result;

}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 2, 2023 | 442 Views |

Given an a list of array nums and a target number k, return true if there are two i and j in the array indices such that nums[i] == nums[j] and abs(i - j) <= k.

Example

nums = 1,4,3,1,9

k = 2

Answer: False

Example

nums = 10,4,3,1,9,1

k = 2

Answer: True

Solution:

Dictionaries can be used to solve this problem.

we need to check the dictionary if you already saved it, and if you already save this number, will calculate the distance between this number and the previously saved number, and if that gap is less than or equal to the target value we return true. otherwise, will replace the key with this new number and we keep searching for the new gap.

public bool ContainsNearbyDuplicate(int[] nums, int k) {
Dictionary<int, int> dict = new();

for (int i = 0; i < nums.Length; i++)
{
if (!dict.ContainsKey(nums[i]))
dict.Add(nums[i], i);
else
{
int start = dict[nums[i]];
int end = i;
int diff = Math.Abs(start - end);
if (diff <= k)
return true;
else
{
dict.Remove(nums[i]);
dict.Add(nums[i], i);
}
}
}
return false;

}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 2, 2023 | 454 Views |

Find the indices of two numbers from a given list of numbers that adds up to a given target number

Example

nums = 1,3,5,4

Target= 6

ans = 0,2

Example

nums = 3 , 4, 2

Target = 6

ans = 1, 2

Solution:

This problem can be solved using hashtable as follows:

We first throw target - nums(i) in to the hash table.

Then we will check if the hash table contains a(i) which is an indication that the pair exists that will make the target sum.

We also need to put an additional check that the current index is different from what we have stored in the hash table for current number:
i!= (int)ht[nums[i]]

public class Solution {
public int[] TwoSum(int[] nums, int target) {
int [] result = new int[2];

Hashtable ht = new Hashtable();
for(int i=0; i<nums.Length; i++)
{
if(!ht.Contains(nums[i]))
{
ht[target-nums[i]] = i;
}
}

for(int i=0; i<nums.Length; i++)
{
if(ht.Contains(nums[i]) && i!= (int)ht[nums[i]] )
{
result[0]= i;
result[1] = (int)ht[nums[i]];
break;
}
}

return result;
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 1, 2023 | 424 Views |

remove duplicate adjacent characters

Example

absaasbb

output:

a

Solution:

We can use two pointers approach in this case. We need to create a result array and copy non repeating character to this array. When we check if adjacent chars are duplicate we need to do it one char from the input string and the other char from the result array.

static string RemoveAdjacentDuplicates(string input)
{
if (string.IsNullOrEmpty(input))
return input;

char[] result = new char[input.Length];
int index = 0;

for (int i = 0; i < input.Length; i++)
{
if (index > 0 && result[index - 1] == input[i])
{
// Remove the duplicate character
index--;
}
else
{
// Add the character to the result
result[index] = input[i];
index++;
}
}

return new string(result, 0, index);
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 31, 2023 | 437 Views |

Given a string with a list of parentheses composed of { [ ( } ] ) we want to return true if it is balanced. The last bracket that is opened must be the first one to be closed.

Example of valid parentheses

{[()]}

{}[]()

Solution:

Since the last bracket that is opened must also be the first one to be closed, it makes sense to use stack data structure.

public class Solution {
public bool IsValid(string s) {
Stack<char> stack = new Stack<char>();
if(s[0] == ')' || s[0] == '}' || s[0] == ']') return false;

for(int i=0; i<s.Length; i++)
{
if(s[i] == '(' || s[i] == '{' || s[i] == '[')
stack.Push(s[i]);

else if(s[i] == ')' && stack.Count !=0)
{
char ch = stack.Peek();
if(ch == '(')
stack.Pop();

else return false;
}
else if(s[i] == ']' && stack.Count !=0)
{
char ch = stack.Peek();
if(ch == '[')
stack.Pop();

else return false;
}
else if(s[i] == '}' && stack.Count !=0)
{
char ch = stack.Peek();
if(ch == '{')
stack.Pop();
else return false;
}
else
return false;
}

if(stack.Count == 0)
return true;
else
return false;
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 27, 2023 | 511 Views |

Remove some duplicates in-place from a sorted list of numbers in such a way that each unique element appears at most twice. The relative order of the elements should be kept the same.

Input: nums = [0,1,1,1,1,2,3,3]

Output: 6, nums = [0,1,1,2,3,3,_,_]

Solution:

To solve this problem, we can maintain two pointers: one to iterate through the array (i) and another (j) to mark the position where we should insert the next valid number. Initially, j will point to the third position (index 2), since we know the first two elements are already valid.

While iterating with i, we will compare the current element with the element at position j-2 (two positions behind j). If they're different, it means we can safely insert the current element at position j, then we can increment both pointers. If they're the same, it means we've already inserted this number twice, and we simply move on.

public int RemoveDuplicates(int[] nums) {
if (nums.Length <= 2)
return nums.Length;

int j = 2;
for (int i = 2; i < nums.Length; i++) {
if (nums[i] != nums[j - 2]) {
nums[j] = nums[i];
j++;
}
}
return j;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 13, 2023 | 510 Views |

Given an integer array nums sorted in ascending order, remove the duplicates in place with out creating another array. The order of the elements should be kept the same. Then return the number of unique elements in nums.

Example:

nums = [1,4,4,4,5,5,6,6,7,7,8,8,8,8]

Ans

nums = [1,4,5,6,7,8,…]

count = 6

public int RemoveDuplicates(int[] nums) {
int count = 1;
int j = 0;
for(int i=0; i<nums.Length; i++)
{
if(nums[i] != nums[j])
{
nums[++j] = nums[i];
count++;
}
}
return count;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 13, 2023 | 424 Views |

Given an a list of array numbers and an integer value val, remove all occurrences of val in nums without creating a new array. You have to do it in place. Then return the number of elements in nums which are not equal to val.

Example:

nums = {3,6,3,6,7,3,5,1,9}

val = 3

Ans: {6,6,7,5,1,9}

count = 6

Solution:

public class Solution {
public int RemoveElement(int[] nums, int val) {
int count = 0;
int j = 0;
for(int i=0; i<nums.Length; i++)
{
if(nums[i] != val)
{
nums[j] = nums[i];
count++;
j++;
}
}
return count;
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 13, 2023 | 407 Views |

public static IList<int> Find(int [] nums, int k)
{
IList<int> ans = new List<int>();
var set = new SortedSet<int>();

for(int i=0; i<nums.Length; i++)
{
if(set.Count < k)
set.Add(nums[i]);
else if(nums[i] > set.Min)
{
set.Remove(set.Min);
set.Add(nums[i]);
}
}

foreach(int num in set)
{
ans.Add(num);
}

return ans;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 11, 2023 | 425 Views |

Given different denominations of coins and a total amount, find the minimum number of coins that make up that amount. If that amount cannot be made up by any combination of the coins, return -1.

Example:

int[] coins = {1, 2, 5};

int amount = 11;

Outputs:

3 (because 11 = 5 + 5 + 1)

Solution:

This problem is similar to combination sum

public int CoinChange(int[] coins, int amount) {
int result = CoinChangeRecursive(coins, amount);
return result == int.MaxValue ? -1 : result;
}

private int CoinChangeRecursive(int[] coins, int amount) {
// Base cases
if (amount == 0) return 0;
if (amount < 0) return int.MaxValue;

int minCoins = int.MaxValue;
foreach (var coin in coins) {
int result = CoinChangeRecursive(coins, amount - coin);
if (result != int.MaxValue) {
minCoins = Math.Min(minCoins, result + 1);
}
}

return minCoins;
}

This problem is similar to combination sum

Example 1:

Input:

candidates = [2,3,6,7], target = 7

Output:

[[2,2,3],[7]]

public class Solution {
public IList<IList<int>> CombinationSum(int[] candidates, int target) {
   List<IList<int>> ans = new List<IList<int>>();
   BackTrack(candidates,0, target,new List<int>(), ans);
   return ans;
}

   public void BackTrack(int[] cand, int start,int target,List<int> list, List<IList<int>> result)
{
if (target < 0)
return;
if (target == 0)
result.Add(new List<int>(list));

for (int i = start; i < cand.Length; i++)
{
list.Add(cand[i]);
BackTrack(cand, i, target - cand[i], list, result);
list.RemoveAt(list.Count-1);
}
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 10, 2023 | 439 Views |

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Inputs:

values[]: Array representing the values of the items.
weights[]: Array representing the weights of the items.
W: Total capacity of the knapsack.
n: Number of items.

Output:

Maximum value that can be achieved with items whose combined weight is less than or equal to W.

Example

int[] values = {60, 100, 120};

int[] weights = {10, 20, 30};

int W = 50;

int n=3;

int result = Knapsack(weights, values, W);

Outputs: 220

One practical application of this problem is the problem of loading items in a container of limited carrying capacity in such a way that it maximizes the value by carrying the minimum weight. Items with great value but minimum weight will be selected.

Solution: We can use dynamic programming to solve this problem. Let's define a 2D array dp[i][w] where i is the item index and w is the weight. dp[i][w] will represent the maximum value we can achieve using the first i items and a knapsack of weight w.

Here's the C# code to solve the Knapsack problem:

public int KnapsackRecursive(int[] values, int[] weights, int n, int W) {
// Base condition
if (n == 0 || W == 0) return 0;

// If the weight of the nth item is more than the capacity W,
// then this item cannot be included in the optimal solution
if (weights[n - 1] > W) {
return KnapsackRecursive(values, weights, n - 1, W);
}

// Return the maximum of two cases:
// (1) nth item included
// (2) nth item not included
return Math.Max(
values[n - 1] + KnapsackRecursive(values, weights, n - 1, W - weights[n - 1]),
KnapsackRecursive(values, weights, n - 1, W)
);
}

This solution is not efficient for larger values

we need to store previously computed values in a dictionary or array. This technique is called memoization.

public int Knapsack(int[] values, int[] weights, int W) {
int totalItems = weights.Length;
int?[,] memo = new int?[totalItems, W + 1];
return KnapsackRecursive(values, weights, W, totalItems - 1, memo);
}

private int KnapsackRecursive(int[] values, int[] weights, int W, int n, int?[,] memo) {
// Base cases
if (n < 0 || W <= 0) {
return 0;
}

// If result is already computed, return it
if (memo[n, W].HasValue) {
return memo[n, W].Value;
}

// Exclude the current item
int exclude = KnapsackRecursive(values, weights, W, n - 1, memo);

// Include the current item (if possible)
int include = (weights[n] <= W)
? values[n] + KnapsackRecursive(values, weights, W - weights[n], n - 1, memo)
: 0;

// Store the result in memo table and return the maximum of include and exclude
memo[n, W] = Math.Max(include, exclude);
return memo[n, W].Value;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 10, 2023 | 411 Views |

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Given a positive integer convert it in to its Roman number’s representation.

Example 1:

Input:

num = 3

Output:

"III"

Explanation:

3 is represented as 3 ones.

Example 2:

Input:

num = 58

Output:

"LVIII"

Explanation:

L = 50, V = 5, III = 3.

Example 3:

Input:

num = 1994

Output:

"MCMXCIV"

Explanation:

M = 1000, CM = 900, XC = 90 and IV = 4.

Solution

public string IntToRoman(int num) {
string[] thousands = {"", "M", "MM", "MMM"};
string[] hundreds = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
string[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
string[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};

return thousands[num / 1000] +
hundreds[(num % 1000) / 100] +
tens[(num % 100) / 10] +
ones[num % 10];
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 10, 2023 | 411 Views |

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example

Input:

nums = [4,5,6,7,0,1,2], target = 0

Output:

4

Solution

we need to find the pivot element. This is where the pattern of ascending order is broken.

public class Solution {
public int Search(int[] A, int target) {

if(A.Length == 2)
{
   if(A[0] == target) return 0;
   if(A[1] == target) return 1;
   }
int pivot = -1;
//return BinarySearch(A, 0, A.Length-1, target);
for(int i=0; i<A.Length-1; i++)
{
if (A[i] > A[i + 1])
{
pivot = i + 1 ; break;
}
}
if(pivot == -1)
return BinarySearch(A, 0, A.Length - 1, target);
else
{
   if (target == A[pivot])
return pivot;

return BinarySearch(A, 0, pivot, target) == -1 ? BinarySearch(A, pivot, A.Length - 1, target): BinarySearch(A, 0, pivot, target);

}
}

public static int BinarySearch(int [] A, int left, int right, int target)
{
int mid = (left + right) / 2;

if (left > right)
   return -1;
if (A[mid] == target)
return mid;
else if(A[left] <= A[mid]) //left is sorted properly
{
if (A[left] <= target && target <= A[mid])
return BinarySearch(A, left, mid, target);
else
return BinarySearch(A, mid + 1, right, target);
}

else if (A[mid] < A[left])
//right is sorted properly. eg 9,10,11,2,4,7,8 a(mid) = 2 is < aleft = 9 means left is wired and right is sorted
{
if (target > A[mid] && target < A[right])
return BinarySearch(A, mid, right, target);
else
return BinarySearch(A, left,mid-1, target);
}
else return -1;
   }
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 10, 2023 | 379 Views |

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

Solution:

We count the size of the linked list.

To find them nth node from the end we just need to subtract n from count. That is the trick!

public class Solution {
public ListNode RemoveNthFromEnd(ListNode head, int n) {
ListNode i = head;
int count = 0;
while(i!=null)
{
i=i.next;
count++;
}

int m = count-n;
ListNode it = head;
int j=0;
while(j<m-1)
{
it=it.next;
j++;
}

if(count==n)
{
return head.next;
}

if(it.next!=null )
it.next = it.next.next;

if(count==1 && n==1) return null;
return head;
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 10, 2023 | 432 Views |

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Solution

To solve this problem, we can use a two-pointer approach. The idea is to initialize two pointers, a and b, where a starts from 0 and b starts from the square root of c.

Upper Bound: For any non-negative integer c, the largest possible value for a or b such that a2+b2=c is square root of c. This is because if both a and b were greater than square root of c then their sum of squares would exceed c.

Then:

Calculate the sum of squares: sum = a^2 + b^2.
If sum is equal to c, return true.
If sum is less than c, increment a.
If sum is greater than c, decrement b.
Repeat steps 1-4 until a is greater than b.

public bool JudgeSquareSum(int c) {
long a = 0;
long b = (long)Math.Sqrt(c);

while (a <= b) {
long sum = a * a + b * b;
if (sum == c) {
return true;
} else if (sum < c) {
a++;
} else
b--;
}
}

return false;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 9, 2023 | 419 Views |

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates can only be used once in the combination.

public class Solution {
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
   List<IList<int>> ans = new List<IList<int>>();
   Array.Sort(candidates);
   BackTrack(candidates,0, target,new List<int>(), ans);
   return ans;
}

   public void BackTrack(int[] cand, int start,int target,List<int> list, List<IList<int>> result)
{
if (target < 0)
return;
if (target == 0)
result.Add(new List<int>(list));

for (int i = start; i < cand.Length; i++)
{
if (i > start && cand[i] == cand[i - 1])
   continue; // skip duplicates
list.Add(cand[i]);
BackTrack(cand, i+1, target - cand[i], list, result);
list.RemoveAt(list.Count-1);
}
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 9, 2023 | 414 Views |

Given an array of distinct integers candidates and a target integer target, return a list of all combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times.

Example 1:

Input:

candidates = [2,3,6,7], target = 7

Output:

[[2,2,3],[7]]

Solution:

public class Solution {
public IList<IList<int>> CombinationSum(int[] candidates, int target) {
   List<IList<int>> ans = new List<IList<int>>();
   BackTrack(candidates,0, target,new List<int>(), ans);
   return ans;
}

   public void BackTrack(int[] cand, int start,int target,List<int> list, List<IList<int>> result)
{
if (target < 0)
return;
if (target == 0)
result.Add(new List<int>(list));

for (int i = start; i < cand.Length; i++)
{
list.Add(cand[i]);
BackTrack(cand, i, target - cand[i], list, result);
list.RemoveAt(list.Count-1);
}
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 9, 2023 | 442 Views |

- The `MergeSort` function first checks if the array is of length 1 or less. If so, it returns because the array is already sorted.

- It then divides the array into two halves: `left` and `right`.

- It recursively sorts both halves using `MergeSort`.

- After sorting both halves, it merges them together in sorted order using the `Merge` function.

The `Merge` function takes in the main array and its two halves. It then merges the two halves back into the main array in sorted order.

public static void MergeSort(int[] arr) {
if (arr.Length <= 1) {
return;
}

int mid = arr.Length / 2;
int[] left = new int[mid];
int[] right = new int[arr.Length - mid];

for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < arr.Length; i++) {
right[i - mid] = arr[i];
}

MergeSort(left);
MergeSort(right);
Merge(arr, left, right);
}

private static void Merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;

while (i < left.Length && j < right.Length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}

while (i < left.Length) {
arr[k++] = left[i++];
}

while (j < right.Length) {
arr[k++] = right[j++];
}
}

```

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 9, 2023 | 612 Views |

Implement pow(x, n), which calculates x raised to the power n

solution :

To implement the power function, we can use the "fast exponentiation" or "exponentiation by squaring" method. This method allows us to compute the power in logarithmic time complexity.

The basic idea is:

x^n = (x^{n/2}) (x^{n/2}) if n is even

public double Pow(double x, int n) {
if (n == 0) return 1.0;
if (n < 0) {
x = 1 / x;
n = -n;
}
return FastPow(x, n);
}

private double FastPow(double x, int n) {
if (n == 0) return 1.0;

double half = FastPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}

This solution efficiently calculates in O(log n) time complexity.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 9, 2023 | 452 Views |

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Solution:

To solve this problem, we can use a combination of sorting and the two-pointer technique. Here's a step-by-step approach:

1. Sort the array: This will allow us to easily skip over duplicate numbers and use the two-pointer technique.

2. Iterate over the array: For each number `nums[i]`, we'll try to find pairs `nums[j]` and `nums[k]` such that their sum is `-nums[i]`.

3. Two-pointer technique: For each `nums[i]`, initialize two pointers: `j` starting at `i+1` and `k` starting at the end of the array. Then:

- If `nums[i] + nums[j] + nums[k]` is less than 0, move `j` to the right.

- If the sum is greater than 0, move `k` to the left.

- If the sum is 0, add the triplet to the result and move both pointers, skipping any duplicates.

Here's the C# code to implement this approach:

public IList<IList<int>> ThreeSum(int[] nums) {
Array.Sort(nums);
List<IList<int>> result = new List<IList<int>>();

for (int i = 0; i < nums.Length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates

int j = i + 1;
int k = nums.Length - 1;

while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
result.Add(new List<int> { nums[i], nums[j], nums[k] });
j++;
k--;

// Skip duplicates for j and k
while (j < k && nums[j] == nums[j - 1]) j++;
while (j < k && nums[k] == nums[k + 1]) k--;
} else if (sum < 0) {
j++;
} else {
k--;
}
}
}
return result;
}

This solution efficiently finds all unique triplets in the array that sum up to zero.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 9, 2023 | 562 Views |

Explain the different types of Dependency Injection:

There are three types of Dependency Injection

Transient
Scoped
Singleton

1. Transient

When ever you want to create a new instance of service object every time the object is injected in to different components of the app.

Example:

If an service is injected/used in Class A and B, then a new instance of the service is created by the DI

Usage:

Mainly used for stateless operations like formatting…

2. Scoped

When ever you want to create a new instance of service object every time a new HTTP request is made. However, the same object is reused in the different places the object is injected. No new object needs to be created.

Note: If you open a new tab and hit the same endpoint API, then it is considered a separate HTTP request which will result in creating a new service object.

Usage:

If you want to maintain the state of an object across different components of the app. For example, you have created the order and want to maintain the state of the order across several pages/parties of the page.

May be a shopping cart object can be injected as a scoped to keep the state of the object with you across different controllers or classes.

Another scenarios may be managing session object. Session store the state of an object and it should be available when you navigate through the app from one control to the other.

Another scenario is reusing same DB connections within same HTTP request.

Another scenario is for logging. You may want to use the same object for logging error which may have relevant info about the error in previous controllers and you want to append the error across several components of the app.

It should not be used as singleton due to concurrency issues. This leads us to our last type of DI:

3. Singleton

In singleton DI, once the service is created in the first HTTP request, the same object is reused in the subsequent HTTP requests of same app.

Usage:

Use singleton for very expensive operation like cacheing

Cache requires to store the state of a very big object possibly what you read from DB that will expire in 30 minute or so which might be expensive to recreate every time you get a new HTTP request

———

Here are some more advanced .NET Core MVC Web API interview questions to help you prepare for your interview:

1. Explain the differences between ASP.NET Core MVC and ASP.NET Web API.

- ASP.NET Core MVC is primarily used for building web applications with user interfaces, whereas ASP.NET Core Web API is used for creating RESTful APIs to serve data to clients, often as JSON or XML.

2. What is attribute routing in ASP.NET Core MVC? How does it differ from convention-based routing?

- Attribute routing allows you to define routing rules directly on controller actions or at the controller level using attributes like `[Route]`. Convention-based routing relies on naming conventions to map URLs to controller actions. Attribute routing provides more flexibility and control over route definitions.

3. Explain how model binding works in ASP.NET Core MVC.

- Model binding is the process of mapping incoming HTTP request data to action method parameters or model classes. ASP.NET Core MVC uses model binding to automatically convert request data (e.g., form values, route values, query strings) into method parameters or objects.

4. What are content negotiation and media types in ASP.NET Core Web API?

- Content negotiation is the process of selecting the appropriate response format (media type) based on the client's preferences and the server's capabilities. Media types (e.g., JSON, XML) specify the format of data exchanged between the client and the API.

5. What is dependency injection, and why is it important in ASP.NET Core?

- Dependency injection is a design pattern and a built-in feature in ASP.NET Core that allows you to inject dependencies (e.g., services, components) into your application's components, promoting modularity, testability, and maintainability.

6. Explain the use of action filters in ASP.NET Core MVC. Provide examples of scenarios where you would use them.

- Action filters are attributes that can be applied to controller actions to perform custom logic before or after the action is executed. They are used for tasks such as authentication, logging, and caching. Examples include `[Authorize]`, `[ValidateAntiForgeryToken]`, and custom filters.

7. What is JWT (JSON Web Token), and how is it used for authentication in ASP.NET Core Web API?

- JWT is a compact, self-contained token format used for securely transmitting information between parties. In ASP.NET Core Web API, JWTs are commonly used for implementing token-based authentication, where the server issues tokens to authenticated users, and clients include the token in subsequent requests.

8. What is CORS (Cross-Origin Resource Sharing), and why is it important in Web API development?

- CORS is a security feature that controls which domains can access resources (e.g., APIs) from another domain. In ASP.NET Core Web API, CORS policies are used to specify which origins are allowed to make requests to the API, helping to prevent unauthorized access.

9. Explain how to implement versioning in ASP.NET Core Web API. Why might versioning be necessary for an API?

- API versioning allows you to provide multiple versions of your API to accommodate changes and backward compatibility. ASP.NET Core Web API supports versioning through URL path, query string, or header versioning. It is essential for maintaining existing clients while introducing new features or changes.

Why is API Versioning Necessary? API versioning is essential in API development for several reasons:

Backward Compatibility: As your API evolves, you may need to make changes to existing endpoints or introduce new features. API versioning allows you to do this while ensuring that existing clients continue to work with the older version of the API. This prevents breaking changes.

Client Needs: Different clients may require different versions of your API. Some clients may not be ready to migrate to a newer version immediately, while others may need the latest features. Versioning enables you to cater to the diverse needs of your client base.

Granular Control: Versioning provides granular control over which features and changes are available to clients. It allows you to deprecate and remove older versions when they are no longer needed or supported.

How to Implement API Versioning in ASP.NET Core Web API: ASP.NET Core provides multiple approaches to implement API versioning:

URL Path Versioning: In this approach, the version is specified directly in the URL path. For example:

To implement URL path versioning, you can use the Microsoft.AspNetCore.Mvc.Versioning package.

https://api.example.com/v1/products
https://api.example.com/v2/products

Query String Versioning: In this approach, the version is specified using a query string parameter. For example:

This approach is more flexible and does not affect the URL structure significantly.

https://api.example.com/products?api-version=1.0
https://api.example.com/products?api-version=2.0

Header Versioning: In this approach, the version is specified in a custom HTTP header. This can be useful when you want to keep URLs clean and standardize versioning across different endpoints.

GET /products HTTP/1.1
Host: api.example.com
Api-Version: 1.0

Implementation Steps:

Install the appropriate versioning package, such as Microsoft.AspNetCore.Mvc.Versioning, via NuGet.

Configure versioning in the Startup.cs file's ConfigureServices method:

services.AddApiVersioning(options =>
{
options.ReportApiVersions = true;
options.AssumeDefaultVersionWhenUnspecified = true;
options.DefaultApiVersion = new ApiVersion(1, 0);
});

This code sets up default versioning behavior and specifies version 1.0 as the default.

Apply versioning attributes to your controllers or actions to indicate which version(s) they support:

[ApiVersion("1.0")]
[Route("api/v{version:apiVersion}/[controller]")]
public class ProductsController : ControllerBase
{
// Controller actions for version 1.0
}

Test your API by specifying the desired version in the URL, query string, or headers, depending on your chosen versioning approach.

API versioning is a powerful tool for managing the evolution of your API while ensuring that existing clients remain functional. It provides flexibility and control over how clients interact with different versions of your API, making it a crucial aspect of API design and maintenance.

10. What is Swagger/OpenAPI, and how can it be used to document ASP.NET Core Web APIs?

- Swagger/OpenAPI is a specification for documenting APIs. In ASP.NET Core Web API, the Swashbuckle library is often used to generate Swagger documentation automatically. It provides a user-friendly interface for developers to understand and test the API's endpoints.

These advanced ASP.NET Core MVC Web API interview questions cover topics like routing, model binding, authentication, dependency injection, and API documentation. Be prepared to provide practical examples and discuss real-world scenarios during your interview.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 28, 2023 | 519 Views |

1. What is SQL, and what is its primary use?

- SQL (Structured Query Language) is a domain-specific language used for managing and querying relational databases. Its primary use is to interact with databases to create, retrieve, update, and delete data.

2. Explain the difference between SQL and NoSQL databases.

- SQL databases are relational databases that use tables with structured schemas to store data. NoSQL databases, on the other hand, are non-relational and store data in various formats, including key-value, document, column-family, and graph.

3. What is a primary key, and why is it important in a relational database?

- A primary key is a unique identifier for each record in a table. It ensures data integrity by preventing duplicate rows and allows for efficient data retrieval. A primary key can consist of one or more columns.

4. What is an index in SQL, and why would you create one?

- An index is a database structure that improves the speed of data retrieval operations on a table. It works like an index in a book, helping the database quickly locate rows based on the values in one or more columns. Indexes are created to optimize query performance.

5. Explain the difference between the INNER JOIN and LEFT JOIN operations in SQL.

- INNER JOIN returns only the rows that have matching values in both tables being joined. LEFT JOIN returns all rows from the left table and the matched rows from the right table. If there is no match, NULL values are returned for columns from the right table.

6. What is the SQL injection attack, and how can it be prevented?

- SQL injection is a type of security vulnerability where an attacker can manipulate SQL queries by injecting malicious SQL code. To prevent SQL injection, use parameterized queries or prepared statements, validate user input, and limit database user privileges.

7. What is normalization in database design, and why is it important?

- Normalization is the process of organizing data in a database to reduce redundancy and improve data integrity. It helps in minimizing data anomalies, such as update anomalies, and ensures that data is stored efficiently without unnecessary duplication.

8. What is a subquery in SQL, and how is it different from a JOIN operation?

- A subquery is a query nested inside another query. It can be used to retrieve data that will be used by the main query. The difference from a JOIN operation is that a JOIN combines data from multiple tables into a single result set, whereas a subquery returns data to be used within the main query.

9. Explain the ACID properties in the context of database transactions.

- ACID stands for Atomicity, Consistency, Isolation, and Durability. These properties ensure that database transactions are reliable:

- Atomicity: A transaction is treated as a single, indivisible unit. It either succeeds completely or fails, leaving the database in a consistent state.

- Consistency: A transaction brings the database from one consistent state to another.

- Isolation: Transactions are executed as if they are the only transactions in the system, preventing interference.

- Durability: Once a transaction is committed, its effects are permanent even in the event of system failures.

10. What is the difference between a clustered and a non-clustered index in SQL?

- A clustered index determines the physical order of data rows in a table. There can be only one clustered index per table, and it directly affects the table's storage order. Non-clustered indexes, on the other hand, provide a separate data structure that points to the actual data rows. Multiple non-clustered indexes can be created for a table.

Certainly, let's continue with more advanced SQL interview questions:

11. What is a foreign key, and how is it used to maintain referential integrity in a database?

- A foreign key is a column or set of columns in a table that establishes a link between data in two related tables. It enforces referential integrity by ensuring that values in the foreign key column(s) of one table match values in the primary key column(s) of another table.

12. Explain the difference between a view and a table in SQL. When would you use one over the other?

- A table is a physical storage structure that contains data, while a view is a virtual table generated from one or more tables or other views. Views are often used to simplify complex queries, restrict access to certain data, or provide an abstraction layer over the underlying tables.

13. What is the purpose of the GROUP BY clause in SQL, and how does it differ from the HAVING clause?

- The GROUP BY clause is used to group rows from a table based on one or more columns, typically to perform aggregate functions (e.g., SUM, COUNT) on groups of data. The HAVING clause is used to filter the results of the GROUP BY operation, specifying conditions that aggregated values must meet.

14. Explain the difference between a SQL stored procedure and a function. When would you use one over the other?

- A stored procedure is a precompiled set of one or more SQL statements that can be executed as a single unit. A function returns a single value or a table variable based on input parameters. Functions can be used in SQL queries, while stored procedures are typically used for performing actions or executing complex logic. Functions are also deterministic, while stored procedures may not be.

15. What is a self-join in SQL, and when would you use it? Provide an example.

- A self-join is a type of join where a table is joined with itself. It is used when you need to relate rows within the same table based on common attributes. An example is when dealing with hierarchical data, such as an organizational chart:

SELECT e1.EmployeeName, e2.ManagerName
FROM Employees e1
INNER JOIN Employees e2 ON e1.ManagerID = e2.EmployeeID;

16. What is SQL normalization, and what are the normal forms (1NF, 2NF, 3NF)?

- SQL normalization is the process of organizing data in a database to reduce redundancy and improve data integrity. The normal forms are stages of normalization:

- 1NF (First Normal Form): Eliminate repeating groups and ensure each column holds atomic values.

- 2NF (Second Normal Form): Meet 1NF criteria and ensure that non-key attributes depend on the entire primary key.

- 3NF (Third Normal Form): Meet 2NF criteria and remove transitive dependencies (attributes that depend on non-key attributes).

17. What is an SQL injection attack, and how can you prevent it in your SQL queries?

- An SQL injection attack occurs when an attacker injects malicious SQL code into an application's input fields, potentially gaining unauthorized access to the database. To prevent SQL injection, use parameterized queries or prepared statements, validate user input, and employ input sanitization techniques.

18. Explain the concept of an SQL trigger and provide examples of scenarios where triggers can be useful.

- An SQL trigger is a predefined action that automatically executes when a specified event (e.g., INSERT, UPDATE, DELETE) occurs on a table. Triggers are useful for enforcing business rules, auditing changes, maintaining referential integrity, and logging events.

19. What is the purpose of the SQL CASE statement? Provide an example of its usage.

- The SQL CASE statement is used for conditional logic within SQL queries. It allows you to return different values or perform different actions based on specified conditions. Here's an example:

SELECT
ProductName,
CASE
WHEN UnitPrice > 10 THEN 'Expensive'
ELSE 'Affordable'
END AS PriceCategory
FROM Products;

20. Explain the concept of SQL transactions and the importance of the COMMIT and ROLLBACK statements.

- A SQL transaction is a sequence of one or more SQL statements treated as a single unit of work. COMMIT is used to save the changes made during a transaction to the database, while ROLLBACK is used to undo the changes and restore the database to its previous state in case of an error or failure.

21. Explain the difference between an SQL JOIN and a UNION. When would you use one over the other?

- An SQL JOIN combines rows from two or more tables based on a related column, resulting in a combined result set. A UNION combines rows from two or more SELECT statements into a single result set, removing duplicate rows by default. You use JOINs to retrieve related data from different tables, while UNIONs are used to combine data from separate queries.

22. What are SQL indexes, and why are they important for database performance?

- SQL indexes are data structures that improve the speed of data retrieval operations on a table by providing a quick way to look up rows based on the values in specific columns. Indexes are crucial for optimizing query performance, especially for large datasets, but they come at the cost of additional storage and maintenance overhead.

23. Explain the concept of SQL views. What are the advantages of using views in a database?

- An SQL view is a virtual table generated from one or more tables or other views. Views provide several advantages:

- They simplify complex queries by encapsulating the logic.

- They restrict access to specific columns or rows of a table.

- They offer an abstraction layer over the underlying tables.

- They can improve security by limiting direct access to tables.

24. What is the difference between the SQL WHERE clause and the HAVING clause in a query?

- The WHERE clause is used to filter rows before grouping (if applicable), and it operates on individual rows in a table. The HAVING clause, on the other hand, filters rows after grouping (typically with GROUP BY) and operates on groups of rows. HAVING is used to filter aggregated results.

25. What is the purpose of SQL aggregate functions (e.g., SUM, AVG, COUNT)? Provide examples of their usage.

- SQL aggregate functions perform calculations on a set of values and return a single result. Examples include:

- SUM: Calculates the sum of values in a column.

- AVG: Calculates the average of values in a column.

- COUNT: Counts the number of rows in a table or matching a condition.

- MAX: Returns the maximum value in a column.

- MIN: Returns the minimum value in a column.

26. What is a SQL subquery? Provide an example of how you would use a subquery in a query.

- A subquery is a query nested inside another query. It can be used to retrieve data to be used within the main query. Here's an example using a subquery to find employees with salaries above the average salary:

`
SELECT EmployeeName
FROM Employees
WHERE Salary > (SELECT AVG(Salary) FROM Employees) `

27. Explain the concept of SQL indexing strategies, such as B-tree and hash indexing. When would you use one over the other?

- B-tree indexing is commonly used for columns with ordered or range-based searches. Hash indexing is suitable for columns with exact-match searches. Choosing the appropriate indexing strategy depends on the types of queries performed and the data distribution.

28. What are SQL stored procedures, and what are their benefits in database development?

- SQL stored procedures are precompiled sets of one or more SQL statements that can be executed as a single unit. Benefits of using stored procedures include improved code reusability, better security (parameterization), reduced network traffic, and centralized logic on the database server.

29. Explain the SQL DML (Data Manipulation Language) and DDL (Data Definition Language) commands.

- DML commands (e.g., SELECT, INSERT, UPDATE, DELETE) are used to manipulate data in a database. DDL commands (e.g., CREATE, ALTER, DROP) are used to define, modify, or delete database structures (tables, indexes, views).

30. What is database normalization, and why is it important in database design?

- Database normalization is the process of organizing data in a database to reduce redundancy and improve data integrity. It helps in minimizing data anomalies, such as update anomalies, and ensures that data is stored efficiently without unnecessary duplication. The normalization process results in a set of related tables with minimal data redundancy.

31. Explain the concept of SQL injection and provide examples of how to prevent it in SQL queries.

- SQL injection is a security vulnerability where an attacker can manipulate SQL queries by injecting malicious SQL code. To prevent SQL injection, you should use parameterized queries or prepared statements. Parameterized queries ensure that user input is treated as data and not executable code.

32. What is the purpose of SQL indexes, and how do you decide which columns to index in a table?

- SQL indexes improve query performance by allowing the database to quickly locate rows based on the values in specific columns. When deciding which columns to index, consider columns used in WHERE clauses, JOIN conditions, and columns with high selectivity (distinct values). Indexes should be chosen carefully to balance query performance with storage overhead.

33. Explain the difference between UNION and UNION ALL in SQL, and when would you use one over the other?

- UNION combines the result sets of two or more SELECT statements into a single result set, removing duplicate rows. UNION ALL includes all rows from all SELECT statements, including duplicates. You would use UNION when you want to merge distinct values, and UNION ALL when you want to include all values without removing duplicates.

34. What is a SQL subquery, and how does it differ from a JOIN operation?

- A SQL subquery is a query nested inside another query and can return a single value, a list of values, or a result set. A JOIN operation combines rows from multiple tables based on related columns.

35. Explain the concept of SQL transactions, and how do you ensure the ACID properties (Atomicity, Consistency, Isolation, Durability) are maintained?

- SQL transactions are sequences of one or more SQL statements treated as a single unit of work. ACID properties are ensured by using appropriate isolation levels (e.g., READ COMMITTED, SERIALIZABLE), committing transactions to make changes permanent (or rolling back to undo changes), and designing transactions to maintain data consistency.

36. What is a SQL self-join, and when would you use it? Provide an example.

- A SQL self-join is a type of join where a table is joined with itself. It's used when you need to relate rows within the same table based on common attributes. A common example is a hierarchical structure, like an organizational chart:

SELECT e1.EmployeeName, e2.ManagerName
FROM Employees e1
INNER JOIN Employees e2 ON e1.ManagerID = e2.EmployeeID;

37. Explain the difference between SQL INNER JOIN, LEFT JOIN, RIGHT JOIN, and FULL OUTER JOIN. Provide examples of when to use each type of join.

- INNER JOIN returns only the rows with matching values in both tables. LEFT JOIN returns all rows from the left table and matching rows from the right table (or NULL values if there's no match). RIGHT JOIN is similar but returns all rows from the right table. FULL OUTER JOIN returns all rows from both tables.

38. What is the purpose of SQL cursors, and when would you use them in database operations?

- SQL cursors are database objects used to iterate over rows of a result set one at a time. They are used in situations where you need to process rows individually, typically in stored procedures or when procedural logic is required to manipulate data row by row.

39. Explain the concept of SQL indexing strategies, such as B-tree and hash indexing. When would you use one over the other?

- B-tree indexing is commonly used for columns with ordered or range-based searches. Hash indexing is suitable for columns with exact-match searches. The choice between them depends on the types of queries performed, data distribution, and specific database system capabilities.

40. What is the SQL CASE statement, and how is it used? Provide an example.

- The SQL CASE statement allows you to perform conditional logic within SQL queries. It returns different values or performs different actions based on specified conditions. Here's an example that assigns a grade based on a student's score:

SELECT StudentName,
CASE
WHEN Score >= 90 THEN 'A'
WHEN Score >= 80 THEN 'B'
WHEN Score >= 70 THEN 'C'
ELSE 'F'
END AS Grade
FROM Students;

41. Explain the difference between DELETE," "TRUNCATE," and "DROP"

DELETE

In SQL, "DELETE," "TRUNCATE," and "DROP" are three different operations used for data manipulation and table management. Let's explore each of them:

- The DELETE statement is used to remove one or more rows from a table based on a specified condition.

- DELETE is a DML (Data Manipulation Language) operation.

- It is used when you want to remove specific rows while preserving the table structure.

- DELETE can be rolled back, meaning that you can undo the delete operation if it is part of an active transaction.

- It can be used with a WHERE clause to specify the condition for row deletion.

Example:

DELETE FROM Customers WHERE CustomerID = 101;

TRUNCATE:

- The TRUNCATE statement is used to remove all rows from a table quickly.

- TRUNCATE is typically faster than DELETE because it doesn't generate individual row delete statements and doesn't log individual row deletions.

- TRUNCATE is also a DDL (Data Definition Language) operation.

- It resets the identity seed of a table (if applicable) and deallocates storage space.

- TRUNCATE cannot be used with a WHERE clause because it removes all rows from the table.

- TRUNCATE cannot be rolled back.

Example:

TRUNCATE TABLE Orders;

DROP:

- The DROP statement is used to delete an entire database object, such as a table, view, index, or even the entire database itself.

- DROP is also a DDL operation.

- It permanently removes the object and all its associated data.

- Be extremely cautious when using DROP, as it cannot be undone.

- When using DROP TABLE, all indexes, triggers, and constraints associated with the table are also dropped.

- When using DROP DATABASE, the entire database and all its objects are deleted.

Example (Dropping a table):

DROP TABLE Customers;

Example (Dropping a database):

DROP DATABASE MyDatabase;

It's important to use these SQL statements carefully, especially DROP, as they can have a significant impact on your database and data. Always ensure you have backups and appropriate permissions before executing these commands in a production environment.

These are common SQL interview questions that cover various aspects of SQL database management, querying, and design. Depending on the job role and company, you may encounter more specialized questions related to specific database systems (e.g., SQL Server, MySQL, Oracle) or complex SQL scenarios. Be prepared to discuss your SQL experience and provide examples of real-world projects where you've applied SQL skills.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 28, 2023 | 530 Views |

1. What is C#?

- C# (pronounced as "C-sharp") is a modern, object-oriented programming language developed by Microsoft. It is designed for building Windows applications, web applications, and other software components within the .NET framework.

2. What is the difference between C# and .NET?

- C# is a programming language, while .NET is a framework. C# is one of the languages that you can use within the .NET framework. .NET provides libraries, tools, and runtime support for building and running applications.

3. Explain the importance of the Main method in a C# program.

- The `Main` method is the entry point of a C# program. It is where the program starts execution. Without a `Main` method, the program won't run.

4. What is a class in C#?

- A class in C# is a blueprint for creating objects. It defines the structure and behavior of objects. It can contain fields, properties, methods, and events.

5. What are value types and reference types in C#?

- Value types store their data directly, whereas reference types store a reference (or pointer) to the data. Examples of value types include int, float, and char, while examples of reference types include classes, interfaces, and delegates.

6. What is the difference between a struct and a class in C#?

- Structs are value types, and classes are reference types. Structs are typically used for lightweight objects that have value semantics, while classes are used for more complex objects with reference semantics.

7. Explain the difference between inheritance and interface in C#.

- Inheritance is a mechanism where a class can inherit properties and behaviors from another class. An interface, on the other hand, defines a contract that a class must implement. C# supports single inheritance but allows a class to implement multiple interfaces.

8. What is an abstract class, and when would you use it?

- An abstract class is a class that cannot be instantiated on its own and is meant to be subclassed. It often contains abstract methods (methods without implementation) that must be implemented by derived classes. Abstract classes provide a common base for related classes.

9. What is the purpose of the 'using' statement in C#?

- The `using` statement is used to manage resources like files, streams, or database connections. It ensures that these resources are properly disposed of when they are no longer needed, even if an exception is thrown.

10. Explain what delegates are in C# and give an example of their usage.

- Delegates are reference types that can hold references to methods with a particular signature. They are often used for implementing events and callback mechanisms. Here's a simple example:

delegate void MyDelegate(string message);

void DisplayMessage(string message)
{
Console.WriteLine(message);
}

// Usage:
MyDelegate myDelegate = DisplayMessage;
myDelegate("Hello, World!");

11. What is LINQ, and how does it work in C#?

- LINQ (Language Integrated Query) is a set of features in C# that allows you to query and manipulate data from various sources like collections, arrays, databases, and XML using a SQL-like syntax. LINQ provides a way to write expressive and readable code for data manipulation.

12. Explain the concept of exception handling in C#.

- Exception handling in C# is a mechanism to deal with runtime errors gracefully. It involves using try-catch blocks to handle exceptions that may occur during program execution. Exceptions can be caught and processed to prevent program crashes and provide error information.

13. What is asynchronous programming in C#? How is it achieved?

- Asynchronous programming in C# allows you to write non-blocking code that can perform tasks concurrently. It is achieved using the `async` and `await` keywords. The `async` keyword is used to mark a method as asynchronous, and `await` is used to asynchronously wait for a task to complete without blocking the main thread.

14. What is a lambda expression, and when would you use it?

- A lambda expression is an anonymous function that can be used to create delegates or expression tree types. Lambdas are often used to write concise and inline code for functions or actions that can be passed as arguments to methods.

15. Explain the concept of garbage collection in C#.

- Garbage collection is the process by which the .NET runtime automatically manages memory by reclaiming memory that is no longer in use. It helps prevent memory leaks and allows developers to focus on writing code without explicitly deallocating memory.

16. What are extension methods in C#?

- Extension methods allow you to add new methods to existing types without modifying their source code. They are defined as static methods in static classes and are commonly used to extend built-in classes or third-party libraries.

17. What is the purpose of the 'using' directive in C#?

- The `using` directive is used to import namespaces in C#. It allows you to access types and members of a namespace without fully qualifying their names. It simplifies code readability and reduces the likelihood of naming conflicts.

18. Explain the difference between a shallow copy and a deep copy. How would you perform these copies in C#?

- A shallow copy of an object copies the object itself and references to the objects it contains, but not the objects within. A deep copy, on the other hand, creates a new object and recursively copies all objects it contains. In C#, you can implement a shallow copy using the `MemberwiseClone` method and a deep copy using custom code.

19. What are attributes in C#? How are they used?

- Attributes are metadata that can be added to code elements like classes, methods, or properties to provide additional information. They are often used for documentation, code analysis, and runtime behavior control. You can create custom attributes by defining classes that inherit from the `System.Attribute` class.

20. Explain the concept of dependency injection in C#.

- Dependency injection is a design pattern used to achieve loose coupling in software components. It involves injecting dependencies (e.g., objects or services) into a class rather than having the class create them. Dependency injection frameworks like Unity, Ninject, or the built-in DI container in ASP.NET Core help manage dependencies.

21. What is the difference between a value type and a reference type in terms of memory management and performance?

- Value types are stored on the stack and have better performance due to their direct storage, while reference types are stored on the heap and involve overhead for memory management. Understanding when to use each type is crucial for efficient memory utilization.

22. Explain the concept of inversion of control (IoC) and how it relates to C# development.

- IoC is a design principle where the control over object creation and lifecycle management is transferred from the application to a container or framework. In C#, this is often implemented using dependency injection containers to manage object dependencies and their lifetimes.

23. What is Entity Framework, and how does it simplify database operations in C#?

- Entity Framework (EF) is an object-relational mapping (ORM) framework in C# that simplifies database interactions by allowing developers to work with database entities as .NET objects. EF automates tasks like CRUD operations, tracking changes, and generating SQL queries.

24. Explain the concept of asynchronous streams in C#.

- Asynchronous streams are a feature introduced in C# 8.0 that allow you to efficiently process sequences of data asynchronously. They are useful when working with data sources that produce items over time, such as reading data from a network stream or database.

25. What is the purpose of the 'async' and 'await' keywords in asynchronous programming, and what are the potential pitfalls to avoid?

- The 'async' keyword marks a method as asynchronous, and 'await' is used within an asynchronous method to pause its execution until an asynchronous operation is complete. Pitfalls to avoid include not using 'await' with async methods and not handling exceptions properly.

26. What is a delegate in C#, and how does it differ from an event?

- A delegate is a type that represents a reference to a method with a specific signature. An event is a higher-level construct built on delegates and is used to notify other parts of the program when something of interest happens, providing better encapsulation and safety.

27. Explain the difference between 'var' and explicitly specifying data types when declaring variables.

- 'var' is used for implicit typing, where the data type of a variable is determined by the compiler based on the assigned value. Explicitly specifying data types (e.g., 'int', 'string') is known as explicit typing. 'var' can make code more concise and flexible but should be used judiciously for clarity.

28. What is the IDisposable interface, and why is it important in C#?

- IDisposable is an interface used to release unmanaged resources explicitly. It's crucial in scenarios where you need to clean up resources like file handles or database connections. The 'using' statement is commonly used with IDisposable objects to ensure proper resource disposal.

29. Explain the concept of threading in C#, and how can you create and manage threads?

- Threading allows you to run multiple threads of execution concurrently. You can create and manage threads using the `Thread` class or use higher-level constructs like the Task Parallel Library (TPL) for simplified asynchronous programming.

30. What is the purpose of the Common Language Runtime (CLR) in the .NET framework, and how does it manage memory and resources?

- The CLR is responsible for managing memory, executing code, and handling exceptions in .NET applications. It uses a garbage collector to automatically reclaim memory, ensuring efficient memory management and resource cleanup.

31. What is the purpose of attributes like `[DllImport]` and `[MarshalAs]` in C#?

- `[DllImport]` is used to call functions from native (unmanaged) libraries in C#. `[MarshalAs]` is used to specify how data should be marshaled between managed and unmanaged code. These attributes are often used in platform invoke scenarios when working with external APIs.

32. Explain how C# handles multiple inheritance and what is the role of interfaces in this context.

- C# does not support multiple inheritance for classes (i.e., a class cannot inherit from more than one class). However, it supports multiple interface inheritance, where a class can implement multiple interfaces. Interfaces provide a way to achieve polymorphism and code reuse without the complexities of multiple inheritance.

33. What are extension methods, and when would you use them in C#? Provide an example.

- Extension methods allow you to add new methods to existing types without modifying their source code. They are commonly used to extend classes that you can't modify, such as system or third-party classes. Here's an example:

public static class StringExtensions
{
public static bool IsPalindrome(this string str)
{
// Check if the string is a palindrome.
// Implementation logic here.
}
}

// Usage:
string word = "racecar";
bool isPalindrome = word.IsPalindrome();

```

34. What is the purpose of the `using` statement in the context of IDisposable objects, and how does it ensure proper resource disposal?

- The `using` statement is used to acquire and dispose of resources that implement the `IDisposable` interface. It ensures that the `Dispose` method of the object is called when the scope of the `using` block is exited, guaranteeing proper resource cleanup, even in the presence of exceptions.

35. Explain the concept of code access security (CAS) in C#. Is it still relevant in recent versions of .NET?

- Code Access Security (CAS) was a security feature in earlier versions of .NET that controlled the permissions and access rights of code running in a managed environment. However, CAS has been largely deprecated in recent .NET versions, and security is now primarily based on role-based and claims-based security models.

36. What is reflection in C#, and how is it used? Provide a practical example.

- Reflection allows you to inspect and interact with the metadata of types, assemblies, and objects at runtime. It's often used for tasks like dynamic loading of assemblies and classes, creating objects, and invoking methods. Here's a simple example:

// Load an assembly dynamically.
Assembly assembly = Assembly.LoadFrom("MyAssembly.dll");

// Get a type by name and create an instance.
Type type = assembly.GetType("MyNamespace.MyClass");
object instance = Activator.CreateInstance(type);

// Invoke a method dynamically.
MethodInfo method = type.GetMethod("MyMethod");
method.Invoke(instance, null);

```

37. What are nullable value types in C#? When and why would you use them?

- Nullable value types, represented by the `Nullable<T>` struct or using the shorthand `T?` syntax, allow value types (e.g., `int`, `float`) to have a value of `null`. They are often used when you need to represent the absence of a value in situations like database columns that can be null.

38. Explain the concepts of covariance and contravariance in C# with respect to generics.

- Covariance allows you to use a more derived type (e.g., a derived class) when a less derived type (e.g., a base class) is expected. Contravariance allows the opposite, using a less derived type when a more derived type is expected. These concepts are primarily applicable to generic interfaces and delegates.

39. What is the purpose of the `yield` keyword in C#? Provide an example of its usage.

- The `yield` keyword is used to create iterator methods. It allows you to return a sequence of values lazily, making it useful for working with large data sets without loading them all into memory. Here's an example of a simple iterator method:

public IEnumerable<int> GetNumbers()
{
for (int i = 1; i <= 5; i++)
{
yield return i;
}
}

```

40. Explain the concept of asynchronous programming patterns in C#, including APM (Asynchronous Programming Model) and TAP (Task-based Asynchronous Pattern).

- APM is an older asynchronous pattern in C# that uses methods with names ending in `Begin` and `End` (e.g., `BeginRead`, `EndWrite`). TAP, introduced in .NET 4.5, uses the `Task` class and the `async` and `await` keywords for asynchronous programming. TAP is more modern and provides better readability and composability.

41. What is the purpose of the `volatile` keyword in C#? When and why would you use it?

- The `volatile` keyword is used to indicate that a field may be modified by multiple threads and should not be cached by the compiler or optimized. It ensures that reads and writes to the field are always performed directly from memory, making it suitable for certain multithreading scenarios.

42. Explain the difference between value types and reference types in terms of memory allocation and garbage collection.

- Value types are typically allocated on the stack, have a fixed size, and are short-lived. Reference types are allocated on the heap, have a variable size, and are managed by the garbage collector. Understanding these differences is crucial for optimizing memory usage and avoiding memory leaks.

43. What is the purpose of the `StringBuilder` class, and how does it improve string manipulation in C#?

- `StringBuilder` is a mutable string class in C# that is designed for efficient string concatenation and manipulation. Unlike regular strings, which are immutable (cannot be changed after creation), `StringBuilder` allows you to modify the contents of a string without creating new string objects, improving performance.

44. Explain the concept of a finalizer (destructor) in C# and its role in resource cleanup.

- A finalizer, implemented using a destructor, is a method in a C# class that is called by the garbage collector before an object is reclaimed. It can be used to release unmanaged resources (e.g., file handles, database connections) and perform cleanup operations. However, it's generally recommended to use the `IDisposable` pattern with `Dispose` instead of finalizers.

45. What is a closure in C#? Provide an example and explain how it works.

- A closure is a function that "closes over" variables from its outer scope, allowing it to access those variables even after the outer scope has exited. Closures are commonly used in lambda expressions and anonymous methods. Here's an example:

public Func<int, int> CreateMultiplier(int factor)
{
return x => x * factor;
}

// Usage:
var multiplyByTwo = CreateMultiplier(2);
int result = multiplyByTwo(5); // Result is 10

46. What is the purpose of the `async` modifier on event handlers in C#?

- The `async` modifier on event handlers allows you to write asynchronous code within event handlers. It is often used to prevent blocking the UI thread in GUI applications when performing time-consuming operations, such as I/O or network requests.

47. Explain the concept of data serialization and deserialization in C#. How can you implement it using built-in classes like `XmlSerializer` or `JsonSerializer`?

- Data serialization is the process of converting data objects into a format that can be easily stored, transmitted, or reconstructed. Deserialization is the reverse process of converting serialized data back into data objects. In C#, you can use classes like `XmlSerializer` or `JsonSerializer` to serialize and deserialize data to XML or JSON formats.

48. What is the purpose of the `async` modifier on methods in C#?

- The `async` modifier on methods indicates that the method contains asynchronous code and can use the `await` keyword. It allows the method to pause and yield control back to the caller while awaiting asynchronous operations to complete, preventing blocking and keeping the application responsive.

49. What is the IDisposable pattern, and how is it typically implemented in C#?

- The IDisposable pattern is used for managing resources that need explicit cleanup. It involves implementing the `IDisposable` interface, providing a `Dispose` method to release resources, and optionally implementing a finalizer (destructor) for additional cleanup. It's commonly used with the `using` statement.

50. Explain the concept of application domains (AppDomains) in C#.

- Application domains are a feature of the .NET framework that provides isolation and separation of code execution within a single process. They are used to create a sandboxed environment for executing code with different levels of trust and isolation. AppDomains are primarily used for security and reliability in certain scenarios.

51. Explain SOLID principles in software design

The SOLID principles are a set of five fundamental design principles in object-oriented programming and software development. These principles were introduced to create more maintainable, flexible, and understandable software systems. Each letter in "SOLID" represents one of these principles:

Single Responsibility Principle (SRP):

This principle states that a class should have only one reason to change, meaning it should have only one responsibility. In other words, a class should have a single job or purpose. If a class has multiple responsibilities, it becomes harder to maintain, test, and understand.

Open/Closed Principle (OCP):

The Open/Closed Principle suggests that software entities (classes, modules, functions) should be open for extension but closed for modification. This means that you should be able to extend the behavior of a system without changing its existing code. You achieve this through techniques like inheritance, interfaces, and abstract classes.

Liskov Substitution Principle (LSP):

This principle states that objects of a derived class should be able to replace objects of the base class without affecting the correctness of the program. In simpler terms, if a class is a subclass of another class, it should be able to be used interchangeably with its parent class without causing issues.

Interface Segregation Principle (ISP):

ISP suggests that clients should not be forced to depend on interfaces they do not use. In other words, it's better to have multiple, smaller interfaces that are specific to the needs of clients, rather than a single large interface that contains everything.

Dependency Inversion Principle (DIP):

DIP emphasizes that high-level modules (e.g., application logic) should not depend on low-level modules (e.g., database access) but both should depend on abstractions (e.g., interfaces or abstract classes). Additionally, it states that abstractions should not depend on details; details should depend on abstractions.

By adhering to these SOLID principles, software developers can create more modular, maintainable, and robust code that is easier to extend, test, and understand. These principles are fundamental to object-oriented design and can help prevent common design flaws and challenges in software development.

These advanced C# interview questions cover various topics related to C# programming, including advanced language features, security, reflection, and asynchronous programming patterns. Remember to practice coding examples and be ready to discuss real-world scenarios where you've applied these concepts in your previous projects.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 28, 2023 | 489 Views |

Given a list of strings that may or many not have a common prefix, we wan to find the longest common prefix.

Example:

Input = { “Hospital”, “Host”, “Hostage”}

Ans: Hos

Solution:

We can use the “StartsWith” string function to make our lives easier.

Basically we will make initial assumption and make the first string as a common prefix.

We then iterate through each string (1,2…) starting from index 1 and check if it starts with our string at 0 index (common prefix)

If it doesn't start with it, then we will remove one char from the end of the common prefix and keep checking until it does.

public string LongestCommonPrefix(string[] strs) {
string common = strs[0];
for(int i=1; i < strs.Length; i++) {
while(!strs[i].StartsWith(common)) {
common = common.Substring(0, common.Length-1);
}
}
return common;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Mar. 2, 2022 | 1,044 Views |

Check if the string repeats itself any number of times and return true if it does. Otherwise return false

Examples:

abaaba True

ababa False

ababab True

aaaaa True

Solution:

public static bool RepeatedSubstringPattern(string s)
{
int n = s.Length;
StringBuilder sb = new StringBuilder();
for (int i = n / 2; i >= 1; i--)
{
if (n % i == 0)
{
for (int j = 0; j < n / i; j++)
{
sb.Append(s.Substring(0, i));
}
if (sb.ToString().Equals(s)) return true;
sb.Clear();
}
}

return false;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 23, 2022 | 1,022 Views |

Given two strings S1 as a pattern and S2 as a list of words that should follow the pattern in S1, return if S2 follows the pattern in S1.

Example 1

S1 = “caat”

s2 = “cat mouse dog bat”

Ans = False

Example 2

S1 = “daat”

s2 = “cat mouse mouse cat”

Ans = True

Example 3

S1 = “aba”

s2 = “mouse mouse mouse ”

Ans = False

Solution

This question resembles the problem of ISOMORPHIC strings. The only difference is that on Example 3 even if the pattern tells us ‘a’ is mouse and ‘b’ is mouse too, we should return false as this breaks the pattern. That is why we use nested ifs in this problem to handle if the value is already present in the dictionary.

Dictionary<char, string> dict = new Dictionary<char, string>();
List<string> list = new List<string>();
bool ans = true;

string [] words = s.Split(" ");
list = words.ToList();

if(words.Length != pattern.Length) return false;

for(int i=0;i<pattern.Length; i++)
{
if(!dict.ContainsKey(pattern[i]))
{
if(!dict.ContainsValue(words[i]))
dict[pattern[i]] = words[i];
else
{
ans= false;
break;
}
}
else
{
if(!dict[pattern[i]].Equals(words[i]))
{
ans= false;
break;
}

}
}

return ans;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 23, 2022 | 881 Views |

Given two list of integers L1 and L2, we want to sort the numbers in L1 in the order as they appear in L2. In addition to that we also want to sort the remaining items on L1 in ascending order.

Example

Input: L1= [3,1,3,4,6,7,9,19], L2= [1,4,3,9,6]

Output: [1,4,3,3,9,6,7,19]

public int[] RelativeSortArray(int[] arr1, int[] arr2) {
Array.Sort(arr1);
int [] result = new int[arr1.Length];
int k = 0, l = 0;
for(int i=0; i < arr2.Length; i++) {
for(int j=0; j < arr1.Length; j++) {
if(arr1[j] == arr2[i]) {
result [k] = arr1[j];
k++;
}
}
}

Hashtable ht = new Hashtable();
foreach(int x in arr2) {
if(!ht.ContainsKey(x)) {
ht[x] = x;
}
}

int t=0;
foreach(int x in arr1) {
if(!ht.ContainsKey(x)) {
result[k] = x;
k++;
}
}
return result;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 22, 2022 | 882 Views |

Given a positive integer n, we want to generate all n possible combinations of open and closed brackets while we should always match all open brackets with a closed bracket.

Example:

If n = 1: then display ()

If n=2: then display () (), (())

If n=3: then display ((())) , (()()), (())(), ()(()), ()()()

Solution:

This is a typical candidate for dynamic programming using recursion.

Basically we will have mainly two variables that we keep track in each recursion in terms of how many open or closed bracket we append so far.

Beginning will keep track the opening brackets for each valid parenthesis we are going to generate (eg ((())) )

Ending will keep track from closing brackets for each valid parenthesis we are going to generate (eg ((())) )

In each recursion, we will append “(” and decrease the beginning pointer and append “)” and decrease the ending parenthesis to eventually check if we ran out of both of them and when we do we copy the generated string to our list.

class GenerateBracketN {
public static void Main() {
List<string> list = new List<string>();
int n = 10;
Generate(list, n,n, new char[2*n], 0);
int a = 0;
}
static void Generate(List<string> list, int begining, int ending, char[] str, int index) {
if (begining < 0 || ending < begining) return; //exit cond
if (ending == 0 && begining == 0) //base
list.Add(new string(str));
else {
str[index] = '(';
Generate(list, begining - 1, ending, str, index + 1);
str[index] = ')';
Generate(list, begining, ending - 1, str, index + 1);
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 22, 2022 | 865 Views |

Given a string containing substrings that should be replaced from a list of key value pairs, we want to return a deciphered string after replacing the keys with the values.

Example:

S = (Name) loves to (action)

[[name][Jane], [action][drive]]

Ans: Bob loves to drive

We should be able to replace unmatched keys in the string with question mark(?).

Example:

S = (nam) loves to (action)

[[name][Jane], [action][drive]]

Ans: ? loves to drive

Solution:

It should be straightforward instantly that this problem deserves dictionaries.

public string Evaluate(string s, IList<IList<string>> dic) {
Dictionary<string, string> dict = new Dictionary<string, string>();
string result = string.Empty;
foreach (List<string> list in dic) {
dict[list[0]] = list[1];
}

foreach (string k in dict.Keys) {
int index = s.IndexOf("(" + k + ")");
if (index !=-1)
s = s.Replace("(" + k + ")", dict[k]);
}

//In the end we should replace unmatched keys with ?
while(s.IndexOf("(") !=-1){
int i = s.IndexOf("(");
int j = s.IndexOf(")");

if (i != -1 && j != -1) {
string sub = s.Substring(i, j-i+1);
s = s.Replace(sub, "?");
}
}
return s;
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 22, 2022 | 1,018 Views |

Given a N X N matrix (2-D array) of integers, we want to rotate it 90 degrees to the left only one time as shown in the above image.

Solution:

We first transpose (switch first row second column with second row first column…) the array as shown in the image above (see the first two matrices) .

Then we revert the numbers in each row to get the final outcome.

public void Rotate(int[][] matrix) {
for(int i=0;i<matrix.Length; i++) {
for(int j=i;j<matrix[0].Length; j++) {
swap(ref matrix[i][j], ref matrix[j][i]);
}
}
for(int i=0;i<matrix.Length; i++) {
int m = matrix[0].Length;
for(int j=0;j<matrix[0].Length/2; j++) {
swap(ref matrix[i][j], ref matrix[i][m-j-1]);
}
}
}

void swap(ref int i, ref int j) {
int temp = i;
i = j;
j = temp;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 22, 2022 | 890 Views |

Create a Queue from two Stacks

Solution:

Here we will be using stack1 to store the items as we Insert items in to it and the second stack will be used to rearrange the items as it should be when we use the Queue (FIFO).

We do this by looping through each item in stack1 and pop it and push it to stack2. But we do this only if there are no more items in stack2. In other words we don't shuffle every time we dequeue, instead we pop the top item from stack2 when asked which has the old elements at the top. But if there are no more items left in our stack2, then we will shuffle items from stack1 to stack2 again.

Therefore, at any given point, stack1 will be used as a temp storage while stack2 has all the items as they should be.

class QueueFromTwoStack {
Stack stack1 = new Stack();
Stack stack2 = new Stack();
public void Enqueue(int num) {
stack1.Push(num);
}
public int Dequeue() {
if(stack2.Count == 0)
while(stack1.Count !=0) {
stack2.Push(stack1.Pop());
}
return (stack2.Count == 0)? -1: (int)stack2.Pop();
}

}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 22, 2022 | 919 Views |

Given two integers in a linked list format, we want to add them and return the result in a linked list format.

Example:

4 8 7 2

3 9 3

Ans:

7 7 1 3

Explanation:

It is a normal addition of number but from left to right.

Solution:

We will iterate each corresponding digits in both linked lists and we add them together.

The key point in solving this problem is knowing that we should use a while loop as we don't know when the loop ends to use a for loop.

The condition of the while loop should as long as there is item in Linked List 1 OR Linked List 2 OR our carryover is greater than 0. As long as these three conditions met we will create a new node and keep adding it to our result linked list.

static Node addIntegers(Node head1, Node head2) {
int carry = 0, h1=0,h2=0, sum;
Node head = null;
Node tail = null;
while(head1 != null || head2 != null || carry >0) {
if(head1!=null)
h1 = head1.val;
else
h1 = 0;
if(head2!=null)
h2 = head2.val;
else
h2 =0;
sum = (carry + h1 + h2) % 10;
carry = (carry + h1 + h2) / 10;
Node n = new Node(sum);
if(head == null) {
head = n;
tail = n;
}
else {
tail.next = n;
}
tail = n;
if(head1!=null)
head1 = head1.next;
if(head2!=null)
head2 = head2.next;
}
return head;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 22, 2022 | 1,021 Views |

Given a list of number, Find Starting and Ending Index of a Key in a Sorted List where there may be duplicate items in it.

Example

int [] nums = {2,5,6,8,8,8,8,9,9,9,10,13,13,13,40};

k=9

Ans: 7,9

Explanation: We can find 9 in the list at index 7,8 and 9 but we only need the starting and ending index.

Solution:

Any time we are asked to find an element inside a sorted array, we should think of a binary search (O(logn)) as it faster than linear search(O(N)).

Therefore, we will do a simple binary search on the given key and we then iterate backwards till we find the smallest index we can find this number and iterate forward to find the largest index we can find this number.

public static int FindLow(int [] nums, int k) {
int index = BSearch(0, nums.Length-1, nums,k);
int i = index;
while(nums[i] == k) {
i--;
}
return i+1;
}

public static int FindHigh(int [] nums, int k) {
int index = BSearch(0, nums.Length-1, nums,k);
int i = index;
if(i==nums.Length-1)
return i;

while(nums[i] == k) {
i++;
}
return i-1;
}

public static int BSearch(int low, int high, int [] nums, int k) {
if(low > high) return -1; //base case
int mid = (low + high)/2;
if(nums[mid] < k)
return BSearch(mid+1, high, nums, k);
else if(nums[mid] > k)
return BSearch(low, mid, nums, k);
else
return mid;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 22, 2022 | 938 Views |

Create a data structure in which insert and delete operations run time costs = O(1).

You should not insert duplicate items. You should just return false if asked to insert a dup item.

You should be able to delete an item from the list given the number to be deleted.

We can use dictionaries and list data structures together to come up with a new type of data structure where the cost of insertion and deletion is just O(1).

public class RandomizedSet {
Dictionary <int,int> ht = new Dictionary<int,int>();
List<int> nums = new List<int>();
public RandomizedSet() {
}

public bool Insert(int val) {
if(ht.ContainsKey(val))
return false;
else {
nums.Add(val);
ht[val] = nums.IndexOf(val);
return true;
}
}

public bool Remove(int val) {
if(!ht.ContainsKey(val))
return false;
else {
nums.Remove(val);
ht.Remove(val);
return true;
}
}

public int GetRandom() {
Random r = new Random();
return nums[r.Next(0,nums.Count-1)];
}

public void Display() {
foreach(int i in nums)
Console.WriteLine(i);
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 21, 2022 | 1,010 Views |

Given a list of positive integers, your task is to remove all the even elements from the array and return only odd integers.

Example:

{2,3,4,5,7,8}

Ans:

{3,5,7}

Solution:

We simply count the number of even integers and we set the size of our result array.

We then iterate over the elements of the array and selectively put only the odd integers in to the result array

public static int[] RemoveEven(int[] nums) {
int count = 0;
for(int i=0; i<nums.Length; i++) {
if(nums[i] % 2 != 0) {
count++;
}
}

int [] result = new int [count];
int j=0;
for(int i=0; i<nums.Length; i++) {
if(nums[i] % 2 != 0) {
result[j] = nums[i];
j++;
}
}
return result;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 20, 2022 | 1,223 Views |

Given N count of stairs we want to know how many ways are there to climb all the stairs if we are allowed to climb only one or two stairs at a time.

Solution:

This problem lends itself to dynamic programing using recursion

In order to climb stairs we can take one step which leaves us with N-1 steps and we may take two steps which leaves us with N-2 steps which gives us the following

public int ClimbStairs(int[] memo, int n) {
if (n == 0)// If no stairs
return 0;
if (n == 1)//If one stair to climb then we just take one step
return 1;
if(n==2) //If two stairs to climb then either we can take two single steps or one two step jump. So there are two ways.
return 2;
if (memo[n] == 0) {
int result1 = ClimbStairs(memo, n - 1);
int result2 = ClimbStairs(memo, n - 2);
memo[n] = result1 + result2 ;
}
return memo[n];
}

If the rule was we could take three steps in addition to the one and two steps then we would add one more result

int result3 = ClimbStairs(memo, n - 3);

Note:

This question is almost similar to fibonacci series.

In febonacci we calculate the first two number to get the next number

Same is here, we need the result of all the possible ways to come to one step below and all ways to come to two steps below and we add them together.

In this problem we used dynamic programing memoization technique (top-down) approach. Memoization helps us to store already computed values so that we don't have to compute again and hence more efficient.

We can also use Bottom-up approach of dynamic programing to solve this problem using iteration instead of recursion.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 19, 2022 | 918 Views |

Find all set of elements to express n as a sum of a given list.

Example:

If A = {2,3,6,7}, n = 7

Ans: {2,2,3} and {7}

Solutions:

This problem is can be solved by solving the sub problems (dynamic programing) using recursion.

Basically, we have the option to include or not to include {2,3,6,7} in each result.

Therefore, for example when we don't need 2 in the result, we have to remove it also from the given sum (eg 7-2 => sum = 5)

Therefore the solution is adding each sub solution by including and excluding {2,3,6,7} from the list.

public IList<IList<int>> CombinationSum(int[] candidates, int target) {
List<IList<int>> ans = new List<IList<int>>();
BackTrack(candidates,0, target,new List<int>(), ans);
return ans;
}

public void BackTrack(int[] cand, int start,int target,List<int> list, List<IList<int>> result) {
if (target < 0)
return;
if (target == 0)
result.Add(new List<int>(list));

for (int i = start; i < cand.Length; i++) {
list.Add(cand[i]);
BackTrack(cand, i, target - cand[i], list, result);
list.RemoveAt(list.Count-1);
}
}
}

In case of duplicate elements are not allowed in the result set, in other words we should us each element of the array only once when we add up to make the sum, we just need to add two things to the above code:

Sort the candidates array since we want to compare adjacent numbers in candidate and see if they are the same, if so we ignore it
Just add a simple check to compare adjacent numbers

if (i > start && cand[i] == cand[i - 1]) continue; // skip duplicates

Here is the entire code:

public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
List<IList<int>> ans = new List<IList<int>>();
Array.Sort(candidates);
BackTrack(candidates,0, target,new List<int>(), ans);
return ans;
}

public void BackTrack(int[] cand, int start,int target,List<int> list, List<IList<int>> result) {
if (target < 0)
return;
if (target == 0)
result.Add(new List<int>(list));

for (int i = start; i < cand.Length; i++) {
if (i > start && cand[i] == cand[i - 1]) continue; // skip duplicates
list.Add(cand[i]);
BackTrack(cand, i+1, target - cand[i], list, result);
list.RemoveAt(list.Count-1);
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 19, 2022 | 867 Views |

Find all possible ways to express a given number, n as a sum of 1,2,3 assuming that we can reuse 1 or 2 or 3 many times and we may or may need 1 or 2 or 3 in each result.

Example

n=3

Ans: 4 since there are 4 ways to express 4 as a sum of 1,2,3

{1,1,1}, {1,2}, {2,1} , {3}

Solutions:

This problem is can be solved by solving the sub problems (dynamic programing) using recursion.

Basically, we have the option to include or not to include {1,2,3} in each result

Therefore, when we don't need 1 in the result, we have to remove it also from the given sum (eg 3-1 when n=3 => sum becomes 2)

Therefore the solution is adding each sub solution by including and excluding {1,2,3} from the list.

We use memorization to store values that we have already computed in memory so that we don't have to calculate them again.

public int Helper(int[] memo, int n) {
if (n == 0)
return 1;
if (n == 1)
return 1;
if (n == 2)
return 1;
if (n == 3)
return 2;

if (memo[n] == 0) {
int result1 = Helper(memo, n - 1);
int result2 = Helper(memo, n - 2);
int result3 = Helper(memo, n - 3);
memo[n] = result1 + result2 + result3;
}
return memo[n];
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 19, 2022 | 912 Views |

Given an integer number n, we want to reverse its digits. We are not allowed to use extra memory like arrays to do this. We have to do it only using antiemetics.

Example:

n = 123

Ans: 321

Solution:

We want to make sure we handle negative integers first. To do that we just multiply the number by -1 to make it positive.

The trick here is to understand the formula here

reverse = (reverse * 10) + (n%10); where reverse = 0 initially and it got the new value every time we divide n by 10

public int Reverse(int x) {
long reverse = 0;
long n = (x<0)? -1*x: x;
while(n > 0) {
rev = (reverse * 10) + (n%10);
n/=10;
}
if(reverse > Int32.MaxValue)
return 0;
return (x<0)? (int)(-1*rev): (int)reverse ;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 19, 2022 | 847 Views |

Given a binary tree we want to check if the tree is binary search tree or not

Example:

[5,2,9,null,null,3,10] is not a valid BST since 3 is less than the root value 5.

whereas

[5,2,9,null,null,8,10] is a valid BST.

Solutions:

To solve this problem we want to use dynamic programing using recursion.

What we are going to do is we validate the left and right side of the tree at each node level and see if it passes.

At each node, we will set a minimum and maximum value that we need to validate. Each node has to be greater than the minimum value we set and less than the maximum value and the min and max value changes for every node as we go down the tree using DFS (depth first search).

Initially we can assume the min is smallest double (Double.MinValue) and max is the biggest double number (Double.MaxValue).

When we recursively check if the node we are at is at the correct position, we do two things:

If we are drilling down to the left side of the tree, then we pass the parent node as a max value and we don't care about the min value as long as it is greater than Double.MinValue.
If we are drilling down to the right side of the tree, then we pass the parent node as a min value and we don't care about the max value as long as it is less than Double.MaxValue.

We check the above two things then we are good to go. Here is the code:

public bool IsValidBST(TreeNode root) {
if(root == null) return false;
if(root.left==null && root.right == null) return true;
return ValidateBSTHelper(root,Double.MinValue,Double.MaxValue);
}

public bool ValidateBSTHelper(TreeNode n, double min, double max) {
if(n==null) return true;
if(n.val <= min ) return false;
if(n.val >= max) return false;
return ValidateBSTHelper(n.left, min, n.val) && ValidateBSTHelper(n.right, n.val, max);
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Feb. 19, 2022 | 859 Views |

Given a list of number we want to find Count of Sub Array with Target Sum K.

Example:

A = [1,2,1,4,1,3,7,1,6] K= 7

Answer = 3

Since we can find 3 sub arrays [2,1,4] , [7] , [1,6] whose sum of these sub arrays are equal to the given target sum, 7.

Example:

A = [5,6,4,2,1,9]

K = 10

Ans: 2 since we can find two sub array [6,4] and [1,9] that can add up to 10

Solution:

The key to solving this problem lies in a very important mathematical understanding of what it means the sum of sub array. Mind you the sub array we need to find has to be next to each other elements of the array.

When we closely examine the above diagram, we will soon understand that

Sum(i)-k == Sum(j) if a(j+1) + a(J+2) + a(j+3) … a(i) == k

If we can visualize this then the rest is a simple mater left for dictionaries.

Basically what we need to do after here is we run through a for loop for each item in the given array and we we calculate a running total at each index and we throw them in a dictionary.

We also check if our dictionary contains sum(i) - k and if it does that means we found our first consecutive sum equals to target sum and we keep going until we find all sub array with given sum.

if (nums == null || nums.Length == 0) return 0;
int sum = 0;
int count = 0;
Dictionary<int, int> map = new Dictionary<int, int>();
map.Add(0, 1);
for (int i = 0; i < nums.Length; i++) {
sum += nums[i];
if (map.ContainsKey(sum - k)) {
count += map[sum - k];
}
int val = (map.ContainsKey(sum) ? map[sum] : 0) + 1;
map[sum] = val;
}
return count;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Dec. 8, 2021 | 868 Views |

Given an array of positive integers representing a height of a container we want to find the largest area of with most water.

Example:

A= {5,3,6,4,2} Ans = 12

Solution

As it is indicated in the above picture, the largest area that can be constructed with the given heights is 12 (see yellow highlighted rectangle)

We can use a brute force approach first.

We will need a nested loop wit i and j. We will go one by one and compute the area of each rectangle that can be constructed with i and j.

Area = min height of i and j times the horizontal distance covered by i and j

We take the minimum because we cannot draw a rectangle if we take the longest height.

public int MaxAreaBruteForce(int[] height)
{
int maxarea = 0;
int min = 0;

//brute force
for (int i = 0; i < height.Length; i++)
{
for (int j = i + 1; j < height.Length; j++)
{
min = Math.Min(height[i], height[j]);
maxarea = Math.Max(maxarea, min * (j - i));
}
}
return maxarea;
}

The optimal approach will be based on two pointers.

Instead of checking areas n*n times where n is the length of the given array, we can optimize that by passing through the array only one times using two pointers.

We will have i going forward starting from index 1 and j coming backwards staring from n and we basically do what we did in the body of the inner loop in the brute force solution. The only thing we check is we need to increment i or decrement j based on who will give us the biggest area.

public static int MaxAreaOofNWorks(int[] height)
{
int maxarea = 0;
int min = 0;

int i = 0;
int j = height.Length - 1;
while (i < j)
{
min = Math.Min(height[i], height[j]);
maxarea = Math.Max(maxarea, min * (j - i));
if (height[i] < height[j])
i++;
else
j--;
}
return maxarea;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Dec. 6, 2021 | 1,021 Views |

Find all duplicate values in Array containing random number which are repeating or distinct.

Example: 3, 4, 8, 6, 7, 9, 4,3, 77 Ans = {4, 3}

Example: 3, 8, 6, 7, 9, 4, 77 Ans = {}

Solution:

We loop through the array one element at a time and we throw it in to a hashtable if we didn't do this before. But if we already add it to the hashtable , then we found the answer and we add it to our result array or list.

public IList<int> solution(int[] A) {
IList<int> ans = new List<int>();
Hashtable ht = new Hashtable();

for(int i=0; i< A.Length; i++) {
if (!ht.ContainsKey(A[i]))
ht[A[i]] = A[i];
else {
ans.Add(A[i]);
}
}
return ans;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Dec. 5, 2021 | 867 Views |

Given a singly linked list we want to reverse it.

Example:

1,2,3,4,5

Ans. 5,4,3,2,1

Solution

We can solve this problem with three pointers approach

We need Original Head, NewHead and NewNode pointers.

Steps

We will create a Newhead pointing to null
We will iterate through the linked list one node at a time and do the following steps
1. We create a new node with value from Original Head. So in the first iteration we will have one Node with value 1
2. We will assign the next of the NewNode to New head. So in the first iteration we will have one node 1 pointing to Null as new head is null and hence we make it the end node
3. update newHead where Newnode is so that in the next iteration newnode next will be assigned newHead at step 2

static SinglyLinkedListNode ReverseLinkedList(SinglyLinkedListNode origHead)
{
SinglyLinkedListNode newHead = null;
while (origHead != null) {
SinglyLinkedListNode newNode = new SinglyLinkedListNode(origHead.data);
newNode.next = newHead;
newHead = newNode;
origHead = origHead.next;
}
return newHead;
}

The space complexity of this algorithm is O(n). We can do better with just reversing the pointers as follows

public ListNode ReverseListUsingTemp(ListNode head)
{
ListNode prev = null;
ListNode next = null;
ListNode curr = head;

while (curr != null) {
next = curr.next; // Save the next node
curr.next = prev; // Reverse the current node's pointer
prev = curr; // Move the previous pointer one step forward
curr = next; // Move the current pointer one step forward
}
return prev; // New head of the reversed linked list
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Dec. 2, 2021 | 912 Views |

Given a pair of numbers (intervals) we want to merge overlapping intervals.

Example:

Given (1, 3), (2, 5), (5, 8), (7,9), (10,11) we can merge overlapping intervals and return (1,5), (5,9), (10,11)

Solution:

To solve this problem we can check the ending number of an interval with the starting number of another interval and if it is greater then we need to merge them in to one interval by taking the start number from the first interval and end number from second interval.

example (1,3) , (2,5) we see that 3 > 2 so we can merge it in to (1,5)

Next we need to chose the right data structure to store a given interval.

Well we can create our own data structure called Range by implementing a class.

class Range
{
public int start { get; set; }
public int end { get; set; }

public Range(int start, int end)
{
this.start = start;
this.end = end;
}
}

Then we can chose another data structure to store the collection of intervals.

We can use Linked Lists, Stacks…

For this example lets us use Stack<> as they are relatively simple to understand.

We need to create a stack of ranges, Stack<Range>.

So what we are going to do is we pick up one range from the given list of ranges and we see if it is in the stack if not we add it to the stack.

Then we peak at the top element of the stack and see if the ending number of this interval is greater than the starting number of the current interval we are in the given list. If so we merge them in to one interval by taking the start number from the range we peaked and end number from current interval in the list. We pop the top element in the stack and push this newly created range to the stack.

public List<Range> solution(List<Range> ranges) {
Stack<Range> stack = new Stack<Range>();
foreach(Range range in ranges) {
if (stack.Count == 0) {
stack.Push(range);
}
else {
Range r = stack.Peek();
if (r.end > range.start) {
r.end = Math.Max(r.end,range.end);
stack.Pop();
stack.Push(r);
}
else
stack.Push(range);
}
}
return stack.ToList<Range>();
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Dec. 2, 2021 | 875 Views |

Given a list of numbers we like to find the first Non Repeating number.

Example:

{ 1,1,2,3,3,4,5,8,9,2,4,7,5 } Ans = 8

Solution:

We can use a dictionary data structure to collect similar items in a single bucket and we update the count of repeated items as a value to the dictionary

So the dictionary we are going to build would look like (a(i), frequency(a(i))

[1,2]

[2,2]

[3,2]

[4,2]

[5,2]

[8,1]

[9,1]

So the first non repeated number would be 8 as every other number before it has a frequency of 2 (repeated two times).

public int FirstNonRepeating(int [] nums) {
Dictionary<int,int> dict = new Dictionary<int,int>();
int nonrepeat = 0;
for(int i=0; i < nums.Length; i++) {
if (!dict.ContainsKey(nums[i]))
dict.Add(nums[i], 1);
else
dict[nums[i]]++;
}

foreach(int item in dict.Keys) {
if (dict[item] == 1)
return item;
}
return nonrepeat;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Dec. 1, 2021 | 944 Views |

Given two list of integers and a target number k, we want to find pairs (one number from each array) that add up to target number k.

Example:

Let A = { 1,1, 2, 3,5,6 } and B= { 2, 3, 4, 5,8 }; and Target=10

We need to return the pairs [2,8] , [5,5], [6,4] as these pairs are selectively picked from each array since each pair add up to target sum 10.

Solution:

We can solve this problem by first iterating on the first array and calculate k-a(i) and save it in a dictionary where k-a(i) is the key and a(i) is the value.

Then we can iterate through the second array and see if each element is in the dictionary and if it does we found our first pair and we save it in a hashset.

public HashSet<KeyValuePair<int, int>> FindPairsAddupToTarget(int [] A, int [] B, int k) {
Dictionary<int, int> dict = new Dictionary<int, int>();
HashSet<KeyValuePair<int, int>> pairs = new HashSet<KeyValuePair<int, int>>();
for(int i=0; i < A.Length; i++) {
int diff = k - A[i];
if(!dict.ContainsKey(diff))
dict.Add(diff,A[i]);
}

foreach(int item in B) {
if (dict.ContainsKey(item))
pairs.Add(new KeyValuePair<int, int>(item, dict[item]));
}
return pairs;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Dec. 1, 2021 | 864 Views |

Given a sorted array that has been already rotated, we need to find the minimum element.

Example:

{4,6,7,2,3,4} Ans: 2

Solution:

To solve this, we need to find the element in the array where we see the rotation started/ended. We can call this element the pivot element where the subarrays before and after it are sorted.

In the above example, we can see that 2 is the pivot since we have two sub arrays that are sorted before and after it. A1 = {4,6,7} A2= {2,3,4}

We can easily solve this problem by finding the pivot element, in this case 2.

We can find it by checking if there is increase by 1 to the array's next element.

In the case where there is no rotation and hence no pivot, we simply return the first element.

public int FindMin(int[] nums) {
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] > nums[i + 1])
return nums[i + 1];
}
return nums[0];
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 30, 2021 | 851 Views |

Given a list of numbers as an array we would like to find the index of the peak element which is greater than the numbers before and after it.

Example

Let A= {1, 2, 1, 3, 5, 5, 4} Ans: 1 since the number at index 1 which is 2 is greater than the the numbers before and after it.

Let A= {1, 0, 1, 3, 5, 6, 4} Ans: 5 since the number at index 5 which is 6 is greater than the the numbers before and after it.

Solution:

We can iterate through the array using a for loop and see if the number is greater than the numbers before and after it. A pick can also exist in the end of the array and in that case we can simply check using the A.Max() math function to do that.

for (int i = 0; i < A.Length - 2; i++) {
if (A[i] < A[i + 1] && A[i + 1] > A[i + 2])
return i+1;
}

if (A.Max() == A[A.Length - 1]) {
return A.Length - 1;
}

return 0;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 24, 2021 | 869 Views |

Given a binary tree we want to traverse the tree in different ways.

Breadth First Search
Depth First Search

Breadth First Search

This is also called level by level traversal of a binary tree starting from the root.

Given the node class as shown below

public class Node {
public int element;
public Node left;
public Node right;

public Node(int element, Node left, Node right) {
this.element = element;
this.left = left;
this.right = right;
}
}

We can use a queue to do the Breadth Frist traversal. Basically we start from the root node and add that to the queue.

We then iterates as long as the queue is not empty and we print the node and remove it from the queue.

public void BFS(Node root) {
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(root);
while (!(queue.Count == 0)) {
Node node = queue.Peek();
if (node != null) {
Console.WriteLine(node.element + " ");
queue.Dequeue();
if (node.left != null)
queue.Enqueue(node.left);
if (node.right != null)
queue.Enqueue(node.right);
}
}
}

Depth First Search

We have three types of DFS.

In order traversal
Post order traversal
pre order traversal

In order traversal

Print left child first, then the parent and then the right child

private void printTreeIn(Node t) {
if (t != null) {
printTreeIn(t.left);
Console.WriteLine(t.element);
printTreeIn(t.right);
}
}

Post order traversal

print left, right and lastly parent in that order

private void printTreePost(Node t) {
if (t != null) {
printTreePost(t.left);
printTreePost(t.right);
Console.WriteLine(t.element);
}
}

Pre order traversal

print parent, left and lastly right in that order

private void printTreePre(Node t) {
if (t != null) {
Console.WriteLine(t.element);
printTreePre(t.left);
printTreePre(t.right);
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Nov. 23, 2021 | 1,007 Views |

Given a linked list definition as follows, we want to insert a new node at a given position.

public class Node {
public Object value;
public Node next;
public Node previous;
public Node(Node next, Node previous, Object value) {
this.next = next;
this.previous = previous;
this.value = value;
}

Solution:

We start from the root node and keep traversing through the elements of the linked list until the position index we are given to insert.

We then create the new node based on the data passed to us, the next node will be current node next node and the previous node will be current. Mind you, current is at the node we try to insert a new node after. So the above referencing makes sense.

Then lastly we need to fix the the next references of the previous node to be new node and the current node next node previous to be new node.

Moreover, to handle invalid data we can do the following. If position we are asked to insert is negative, assume we can insert at first place. If position is greater than size of the linked list, then we can assume we can insert it at the last position.

public class MyLinkedList {
private Node header;
private int size;

public MyLinkedList() {
header = new Node(null, null, null);
size = 0;
}
public void insert(Object data, int pos) {
if (pos < 0)
pos = 0;
if (pos > size)
pos = size;
Node current = header;
for (int i = 0; i < pos; i++)
current = current.next;
Node n = new Node(current.next, current, data);
//same as inserting at first
if (current.next != null)
// needed if list is empty at first
current.next.previous = n;
current.next = n;
size++;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 16, 2021 | 937 Views |

Binary Search Tree is a data structure in which the given tree is structured in such a way that the left child node is always less than the parent node and the parent node is always less than the right child node.

In this tutorial we will see how to find an element with any given target value.

First we create a node with data and left and right pointers which will help us store information about any given node's two children node.

public class Node {
public int element; // The data in the node
public Node left; // Left child
public Node right; // Right child

public Node(int element, Node left, Node right) {
this.element = element;
this.left = left;
this.right = right;
}
}

This problem is a perfect example for recursive programming.

In order to find the any element in a BST, we have to understand that smaller values always resides on the most left side of the tree and greater values on the right side of the tree.

To find the given target value, we can start from the root, if we the root node is equal to target then we can return true.

Otherwise check if target is smaller than the root, if so then we can keep looking on the left side of the tree.

Else if target is greater than the root, then we can keep looking on the right side of the tree.

public bool find(int x) {
return find(x, root);
}

private bool find(int x, Node n) {
if (n == null) return false;
if (n != null && n.element==x)//if it found on the root
return true;
return ((x - n.element) < 0) ? find(x, n.left) : find(x, n.right);//binary search
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 16, 2021 | 1,525 Views |

Binary Search Tree is a data structure in which the given tree is structured in such a way that the left child node is always less than the parent node and the parent node is always less than the right child node. You can visualize a tree like an actual inverted tree as shown in the above picture where the root is on the top and branches are below it.

In this tutorial we will see how to find an element with the maximum value and also how to delete it from a BST.

First we create a node with data and left and right pointers which will help us store information about any given node's two children node.

public class Node {
public int element; // The data in the node
public Node left; // Left child
public Node right; // Right child

public Node(int element, Node left, Node right) {
this.element = element;
this.left = left;
this.right = right;
}
}

In order to find the maximum element in a BST, we have to understand that the maximum always resides on the most right side of the tree. That means we keep traversing to the right side of the tree until it is null.

To remove the maximum , we need to keep track of two references (one is the right hand side node on each level of the tree and one is the parent of this node).

As soon as we reach the last node of the right most side of the tree, then we will check if that node has any left children.

If so we should let the parent of the this right most node to adapt them as its own children.

If no children, then we can simply assign the parent of this right most node right child as null.

public class MyBST
{
/** The tree root. */
private Node root;

public int findMax() {
return findMax(root).element;
}
private Node findMax(Node start) {
Node max = start;
if (max.right != null)
return findMax(max.right);
else
return max;
}
public object removeMax() {
if (root == null)
return null;
return removeMax(root, root);
}
private int removeMax(Node n, Node curparent) {
if (n.left != null) {
return removeMax(n.left, n);
}
else {
if (n.right != null)
curparent.right = n.left;
else
curparent.right = null;
return n.element;
}
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 16, 2021 | 1,901 Views |

Binary Search Tree is a data structure in which the given tree is structured in such a way that the left child node is always less than the parent node and the parent node is always less than the right child node.

In this tutorial we will see how to find the minimum element and also how to delete the node with the minimum value from a BST.

First we create a node with data and left and right pointers which will help us store information about any given node's two children node.

public class Node {
public int element; // The data in the node
public Node left; // Left child
public Node right; // Right child

public Node(int element, Node left, Node right) {
this.element = element;
this.left = left;
this.right = right;
}
}

In order to find the minimum element in a BST, we have to understand that the minimum always resides on the most left side of the tree. That means we keep traversing to the left side of the tree until it is null.

To remove the minimum, we need to keep track of two references (one is the left hand side node on each level of the tree and one is the parent of this node).

As soon as we reach the last node of the left most side of the tree, then we will check if that node has any right children.

If so we should let the parent of the left most node to adapt them as its own children.

If no children, then we can simply assign the parent left child as null.

public class MyBST
{
/** The tree root. */
private Node root;
public int findMin() {
return findMin(root).element;
}
private Node findMin(Node start){
Node min = start;
if (min.left != null)
return findMin(min.left);
else
return min;
}
public object removeMin() {
if (root == null)
return null;
return removeMin(root, root);
}
private int removeMin(Node n, Node curparent) {
if (n.left != null) {
return removeMin(n.left, n);
}
else {
if (n.right != null)
curparent.left = n.right;
else
curparent.left = null;

return n.element;
}
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 16, 2021 | 1,760 Views |

Binary Search Tree is a data structure in which the given tree is structured in such a way that the left child node is always less than the parent node and the parent node is always less than the right child node.

In this tutorial we will see how to store and retrieve data in BST.

First we create a node with data and left and right pointers which will help us store information about any given node's two children node.

public class Node {
public int element; // The data in the node
public Node left; // Left child
public Node right; // Right child

public Node(int element, Node left, Node right) {
this.element = element;
this.left = left;
this.right = right;
}
}

After this we will implement how to insert node in to a BST

public class MyBST {
/** The tree root. */
private Node root;

//--insert an element in the correct position---
public void insert(int x) {
if (root == null) {
root = new Node(x, null, null);
}
else {
Node n = root;
bool inserted = false;
while (!inserted) {
if (x < n.element ) {
//space found on the left
if (n.left == null) {
n.left = new Node(x, null, null);
inserted = true;
}
else {
n = n.left;
}
}
else if (x > n.element) {
//space found on the right
if (n.right == null) {
n.right = new Node(x, null, null);
inserted = true;
}
else {
n = n.right;
}
}
}
}
}
}

Let's understand what is going on here.

Initially the BST is empty so we just create a new node and make left and right as null
If there is an item already in the BST, then we will ask ourselves if the new number we want to insert is less than the root, if yes we will drill down to left by moving our reference to the left (n = n.Left). If in case we see that n.Left is null, then space is available for the new node and we can insert right there. (n.left = new Node()).
Otherwise, we keep asking the same question we ask in the beginning and keep navigating down the tree based on whether data is less than or greater than the current node we are in .

We can also insert a node using the recursive method.

public void InsertByRecursion(int x, Node root) {
if (root == null) {
Node n = new Node(x, null, null);
root = n;
}
else {
if (x < root.element) {
if (root.left == null) {
Node n = new Node(x,null, null);
root.left = n;
}
else
InsertByRecursion(x, root.left);
}
else if (x > root.element) {
if (root.right == null) {
Node n = new Node(x,null,null);
root.right = n;
}
else
InsertByRecursion(x, root.right);
}
}
}

Now let see how to print the values in the nodes of the tree in sorted order(In order traversing) . That is left child first then parent and then right child.

public void printTree() {
if (root == null)
Console.WriteLine("Empty tree");
else
printTree(root);
}

private void printTree(Node t) {
if (t != null) {
printTree(t.left);
Console.WriteLine(t.element);
printTree(t.right);
}
}

As you can imagine, we use recursion here to print the left node first and then the parent and finally the right node.

Let's test it.

public static void Main(string[] args) {
MyBST bst = new MyBST();
bst.insert(9);
bst.insert(2);
bst.insert(3);
bst.insert(4);
bst.insert(5);
bst.printTree();
}
output: 2 3 4 5 9

This is how it should look like in a diagram.

9

2

3

4

5

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 16, 2021 | 1,115 Views |

Given a list of integers representing the values of stocks on a daily basis, we would like to calculate Max Stock Profit where multiple buy and sell allowed. In other words you can sell a stock after you purchased it at any given day and able to purchase again and sell it repeatedly. In the end, you profit should be the sum of the individual profits you have accumulated over and over again.

Example:

{7, 1, 5, 3, 6, 4 } Max Profit = 7

Since you can buy on day 2 at price 1 and sell on day 3 at price 5 with a profit of 5-1 = 4 ;

In addition, you may buy on day 4 at price 3 and sell on day 5 at price 6 with a profit of 6 - 3 = 3

Therefore, Max Profit = 4+3 = 7

Example:

{ 8, 3, 2, 6, 7, 2, 7, 8 }; Max Profit = 11

Since you can buy at 2 and sell at 6 ; buy at 2 and sell at 8 ==> Max Profit = 5+6 =11

Solution:

The trick here is you can sell and buy the same stock at the same price on the same day.

This problem can be solved easily if we can understand that this is really all about calculating the cumulative sum of the difference between a(i) and a(i-1) if a(i) > a(i-1).

For example for the first array, we can see that the only time we increment cumulative sum is at 5-1 + 6-3 = 4 + 3 = 7

For the second array, we do it at 6-2 + 7-6 + 7-2 + 8-7 = 4 + 1 + 5 + 1 = 11

public static int solution(int[] prices) {
int ans = 0;
for (int i = 1; i < prices.Length; i++) {
if (prices[i] > prices[i - 1])
ans += prices[i] - prices[i - 1];
}
return ans;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 16, 2021 | 919 Views |

Recursive Programming is similar to iterative programing (for loop..) since we are executing a specific code block several times until an exit condition is met. Recursion is an alternative solution to iterative and it calls itself repeatedly until the condition we set inside the code block is met.

Syntax

function(parameters) {
//exit condition
function(slightly different parameters)
}

Example:

Let us recursively calculate the sum of all numbers in a given array.

int Sum(int[] a, int i) {
if (i == a.Length)
return 0;
return a[i] + Sum(a, i + 1);
}

Testing:

int answer= Sum(new int[] { 1, 1, 2, 2, 3,1 }, 0); //output 10

Explanation:

We have set up our recursive Sum function by passing the array of integers and 0 which is the start index of an array.
Basically we can think of recursion as a way of chopping the whole task in to a smaller unit of work as follows.
Sum(ai ) = a[0] + (a[1] + a[2] + a[3] … a[n]) In other words, Sum(ai) = a[0] + Sum(a[1]…a[n])
But we can also use the same strategy to calculate Sum(a[1]…a[n]). Sum(a[1]…a[n]) = a[1] + Sum(a[2]…a[n])
We can repeat the same process until we met an exit condition .
Exit condition is to pass the current index we are on to the sum function and check if we reach the end of the array, in which case we return 0.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 15, 2021 | 807 Views |

Linked Lists are a data structure that are based on sequential order of items like an array but they are more robust and efficient in terms of insertion, deletion of items at any given place inside of the linked list.

In order to insert an item in to an array at the beginning of the array, we have to shift all the items from index 0 … N, where N is the size of the array which has a time complexity of O(N). These matter significantly when N gets very large. But in linked list it is a matter of rearranging some pointers/references of nodes which has a time complexity of O(1). It cannot get better than that.

Therefore linked lists are perfect candidate for data that needs to be stored in the order they are received.

For example, if you want to store bank transactions in the order you received them and retrieve them back when needed, we can leverage the power of linked list.

Linked list node has basically two things. One the data it stores and two a reference of the node that is next/previous to it.

The data can be of any data type like int , datetime, double, stack etc. We can store on or more variables in here to represent our data.

The reference is an object of the same type the linked list class is defined. For example, if the linked list data structure we want to represent is called Transaction, then we as part of our reference to the next node, we can use Transaction as a data type for this pointer.

Linked list has a head and tail. Head is the first node whereas tail is the last node.

Linked list can be unidirectional (singly linked list) or bi-directional (doubly linked list).

Singly linked list

Singly linked list contains node(s) that store a reference of a node to only what is next to it.

class Solution {
static void Main(string[] args) {
SinglyLinkedList slist = new SinglyLinkedList();
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);

slist.Insert(node1);
slist.Insert(node2);
slist.Insert(node3);
slist.Display();
}

public class SinglyLinkedList {
public Node head;
public SinglyLinkedList() {
}

public void Insert(Node n) {
if(head == null)
head = n;
else {
Node iter = head;
while(iter.next!=null) {
iter = iter.next;
}
iter.next = n;
}
}

public void Display() {
Node iter = head;
while(iter!=null) {
Console.WriteLine(iter.val);
iter = iter.next;
}
}
}
public class Node {
public Node next;
public int val;
public Node() {

}
public Node(int val)
{
this.val = val;
}
}
}

Doubly linked list

Doubly linked list contains node(s) that store a two references of a node to what is next to it and what comes before it.

Let define our first linked list.

public class Transaction{
public DateTime? Date { get; set; }
public double Amount { get; set; }
public Transaction Next { get; set; }
public Transaction Previous { get; set; }

public Transaction(DateTime? date, double amount){
this.Date = date;
this.Amount = amount;
}
public override string ToString() {
return "Transaction Date: " + Date + "\n\t" + "Transaction Amount: " + "$" + Amount;
}
public void Print() {
Console.WriteLine(ToString());
}
}

Here we define a doubly linked list that has two types of data we want to store transaction date and amount, and also we keep a reference of the next and previous nodes to this node. This is just a blue print of what we are going to do in the next phase where we actually use it.

Now let's see how we can actually use this linked list.

Transaction History table we can create a transaction linked list using the default constructor.

In the default constructor we will create two empty head and tail nodes but we link them together by making tail's next node to be head node and head's previous node to be tail node.

Head → ←Tail

Every time we add a new transaction we will create a new node with data (transaction date and amount). Then we will take care of the order in which the node is inserted. We have to make sure new nodes are inserted at the end of the linked list (before the empty tail). It is like first come first served. When we display them we go in the order from head to tail.

Assume you have a chain of nodes like this.

Head →

← First →

←Tail

Now let's say we want to add a new node just after the First Node

Head →

← First →

← New →

←Tail

We need to do the following:

Set new node's next reference to the tail. New →
Set new node's previous reference to the tail's previous ← New
Overwrite the next reference of the First node with the new Node. But this change based on how many node we have. If we have First and Second Nodes this will change to set it to Second node next should be new node, if there is third node, then third node next should be new node… So the trick here is to set tail's previous next node to be the new node as tail's previous would simply means First or Second or Third node depending the size of your linked list. Head→ or First → or Second → etc.
Overwrite the previous reference of the Tail node with the new node. ←Tail

public class TransactionHistory {
private Transaction Head { get; set; }
private Transaction Tail { get; set; }
TransactionHistory(){
Head = new Transaction(null, 0.0);
Tail = new Transaction(null, 0.0);
Head.Next = Tail;
Tail.Previous = Head;
}
public void AddTransaction(double amount) {
Transaction NewTrans = new Transaction(DateTime.Now, amount);
NewTrans.Next = Tail;
NewTrans.Previous = Tail.Previous;
Tail.Previous.Next = NewTrans;
Tail.Previous = NewTrans;
}
public void Print() {
Transaction current = Head.Next;
while (current != Tail) {
current.Print();
current = current.Next;
}
}
public double Balance() {
Transaction current = Head.Next;
double balance = 0;
while (current != Tail) {
balance += current.Amount;
current = current.Next;
}
return balance;
}
}

public static void Main(string[] args) {
TransactionHistory transHistory = new TransactionHistory();
transHistory.AddTransaction(100);
Thread.Sleep(1000);
transHistory.AddTransaction(-200);
Thread.Sleep(1000);
transHistory.AddTransaction(300);
Thread.Sleep(1000);
transHistory.AddTransaction(400);
Thread.Sleep(1000);
transHistory.Print();
Console.WriteLine(transHistory.Balance());
}

Output:

Transaction Date: 10/15/2011 6:53:37 PM
Transaction Amount: $100
Transaction Date: 10/15/2011 6:53:38 PM
Transaction Amount: $-200
Transaction Date: 10/15/2011 6:53:39 PM
Transaction Amount: $300
Transaction Date: 10/15/2011 6:53:40 PM
Transaction Amount: $400
600

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 15, 2021 | 901 Views |

Iterative Programming is executing a specific code block several time until an exit condition is met.

There are four ways to do Iterative Programming in C#

for Loops
foreach loop
while loop
do while loop

For Loop

Syntax

for(variable initialization; condition ; variable increment) {
//code block goes here
}

Example:

for( int i=0;i<10;i++) {
Console.Write(i);
}

Output: 12345678910

Explanation:

We want to execute the body of the loop as long as an integer i < 10 starting from i=0 and incrementing it by 1 in each iteration.

Example:

for (char c = 'a'; c < ='z'; c++) {
Console.Write(c);
}

Output: abcdefghijklmnopqrstuvwxyz

Explanation:

We want to execute the body of the loop as long as a character c < ‘z’ starting from a and incrementing it by one letter in each iteration.

Loops are very effective in working hand to hand with arrays specially when we want to navigate through array items.

Example: The follwoing program displays only even number from the given array list of integers.

int [] nums = {1,2,3,4,5,6,7,8,9,10};
for( int i=0;i<10;i++) {
if(nums[i] %2 == 0)
Console.Write(nums[i]);
}

Output: 1235678910

Foreach loop

Foreach loop is similar to for loop but it is a has a relatively shorter syntax. Basically it iterates over a collection of list items and do something with the items while a for loop uses index based access system which works based with index based collections like arrays.

Example:

int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
foreach (int digit in nums) {
if (digit % 2 == 0)
Console.Write(digit);
}

Example:

List<int> digits = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9,10 };
foreach(int digit in digits ) {
if(digit %2 == 0)
Console.Write(digit);
}

Output: 2 4 6 8 10

While loop

while loop is a litter different than for loop, we do the initialization part outside of the while loop and the increment part in side the code block

Syntax:

variable initialization
while(condition ) {
//code block goes here
variable increment
}

Example:

int i=0;
while( i<10) {
Console.Write(i);
i++;
}

char c = 'a';
for ( c < ='z';) {
Console.Write(c);
c++;
}

While loop are used when you don't know how many times you want to loop through the code block and you just want to execute it until some condition is met which is triggered by what is going on in side the code block.

do while loop

do while loop is a kind of the same as while loop, we do the initialization part outside of the while loop and the increment part in side the code block but it is is different due to small syntax difference.

Syntax:

variable initialization
do{
//code block goes here
variable increment
} while(condition) ;

Example:

int i=0;
do {
Console.Write(i);
i++;
} while( i<10) ;

Output 0123456789

As you can see, the code block always is executed at least once regardless of the condition set in the while statement.

Nested Loops

Nested loops are loops that are inside other loop. We call the outside loop outer loop and the inside one inner loop.

We can use any of the above loop type (for, while, do.. while) to create a nested loop.

The time complexity of nested loops(how many times the body of the inner loop shall be executed) can be calculated using N time M, where N is the size of the outer loop and M is the size of the inner loop.

Nester loop are perfect fit for navigating a multi-dimensional arrays.

Let's see an example:

We want to represent the following table in a two dimensional array and retrieve it back.

1	10	5	9
5	2	3	4
6	8	5	5

int[,] array = new int[3, 4];
array[0, 0] = 1;
array[0, 1] = 10;
array[0, 2] = 5;
array[0, 3] = 9;
array[1, 0] = 5;
array[1, 1] = 2;
array[1, 2] = 3;
array[1, 3] = 4;
array[2, 0] = 6;
array[2, 1] = 8;
array[2, 2] = 5;
array[2, 3] = 5;

for (int i=0; i<array.GetLength(0); i++) {
for(int j=0; j< array.GetLength(1); j++) {
Console.Write(array[i, j] + " " );
}
Console.WriteLine();
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 14, 2021 | 774 Views |

Before we dive in to conditions, we need to understand some key concepts

Expressions

Arithmetic expressions are code that we need to compute and evaluate to reach to an answer

For example (3 * 5) + 9 is an an expression that will evaluate to 24.

Boolean expression always evaluate to true or false

Example: (5 * 9) < 40 is false where as 5 > 2 is true

Operators

Increment and decrement operators ( i++, i--) increase or decrease the value a variable by a certain value

Example:

int i = 0;

i+=5; this means i = i + 5; which increases i by 5 and therefore i = 5

Addition, subtraction, division and multiplication operators are also working in the same way.

Comparative Operators

Less than (<)
Less than or equal to (< =)
Equal (==)
Not Equal( ! =)
greater (>)
greater or equal to (> =)

Logical (or, and, not) operator

Logical (or, and, not) operators takes to Boolean expressions and return Boolean value (true, false)

In C#, or is written as || , and is written as && and not is written as !

Examples:

int i = 2;

int j = 4;

(i <5 ) || ( j > 2) this will evaluate to true or true => true

(i <5 ) && ( j > 2) this will evaluate to true and true => true

!(i <5 ) || ( j > 2) this will evaluate to false or true => true

Assignment operator ( = )

when we assign a value to a variable we are using the equal sign to do that and that is what we call the assignment operator

int i = 9;

Operation precedence

When evaluate operators we need to take into consideration operator precedence and associativity to determine the order in which the operations in an expression are performed.

We evaluate the expression inside the bracket followed by division and multiplication and then addition and subtraction

Therefore, ((2*3) + (10/5 -2))/2 evaluates to 3

Conditional Statements

Are used for code flow control while evaluating the different conditions set

There are four type of conational statement

If
if.. else
if…else if… else
switch

If Statement

If the condition is evaluated to true, performs a function or displays information

Example

int a = 9;
int b = 4;
If(a>b)
Console.WriteLine(a + “>” + b); // output 9 > 4

If Else Statement

If the condition is evaluated to true, performs a function or displays information otherwise perform the else block

Example

int a = 1;
int b = 4;
If(a>b)
Console.WriteLine(a + “>” + b);
else
Console.WriteLine(a + “<” + b); // output 1 < 4

Assume we want to check if a given number is odd or even.

We can use the usual if else statement

int a = 1;
bool IsEven;
If(a%2==0)
IsEven = true;
else
IsEven = false;

We can rewrite the above if else statements in a very short hand form as follows

bool IsEven= (a%2==0)? true:false;

This means evaluate the bracket Boolean expression and ask if it is true or false and it it is true assign the true to IsEven variable otherwise assign false to the IsEven variable.

If …Else If… Else Statement

If the condition is evaluated to true, performs a function or displays information otherwise check the second if and it is true , performs a function or displays information, otherwise display what is in the else block.

Example

int a = 4;
int b = 4;
if(a > b)
Console.WriteLine(a + ">" +b);
else if(a < b)
Console.WriteLine(a +"<" +b);
else
Console.WriteLine(a + "=" + b); //output 4 = 4

Note: We can have as many else ifs as we want but only one else condition

if(condition1) {…}
else if(condition2) {…}
else if(condition3) {…}
else if(condition4) {…}
else {…}

We can also have nested if...else statements inside other if else statements which can get really messy if we don't know what we are doing.

if(condition1) {
if(condition1) {…}
else if(condition2) {…}
else {…}
}
else if(condition2) {…}
else if(condition3) {…}
else if(condition4) {…}
else {…}

Switch Statement

Switch Statement is like many else ifs but it has a different syntax and better performance than else..ifs.

We need to separate each case block with a break keyword and provide a default plan at the end in case none of the conditions met.

string day = "Monday";
switch (day) {
case "Monday":
Console.WriteLine("Happy Monday!");
break;
case "Tuesday":
Console.WriteLine("Happy Tuesday!");
break;
case "Wednesday":
Console.WriteLine("Happy Wednesday!");
break;
case "Thursday":
Console.WriteLine("Happy Thursday!");
break;
case "Friday":
Console.WriteLine("Happy Friday!");
break;
default:
Console.WriteLine("Happy Weekend!");
break;
}

Output: Happy Monday!

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 14, 2021 | 811 Views |

Basic Programing Tutorial using C# Language

In this tutorial we will discuss basic programing concepts. We will mainly go through the basic datatypes and how we represent, define and store data in memory.

Literals

Literals are any values we may want to store in memory. Example. 12, 55, “New York”, true or false, ‘A’, 4.99 etc.

Datatypes

Datatypes are used to define the type of data we want to store in a variable. These the commonly used datatypes.

short: stores small integer numbers like 5255
long: stores big integer number like 4541245
int: stores medium integer number like 1254, -562, 42555
char: stores as single character like ‘A’ or ‘T’. Should be enclosed with single quote
bool: stores a Boolean value (true or false)
double: stores small to very big floating numbers/decimals. Eg. 25462455.25
float: stores medium sized floating values like 5.25, 8245.65
decimal: stores financial data
string: stores one or more characters like “John” or “New York”. Should be enclosed with double quotes

Variables

Variables are storage places in memory for a specific data we want to save to memory and retrieve it later. Variables are declared with the given datatype

When we declare a variable we need access modifiers, datatype and identifier.

Identifier

Identifier means a valid name for your variable like store, account, student, i, n etc. Variable name can be combination of any alphanumeric character except some keywords that has special meaning by the C# language (like for, if, switch, struct, foreach)

Keywords

have special meaning to the C# language and are reserved to do special task like conditional branching, looping, or datatypes.

Example: all the datatypes are keywords

for, if, switch, struct, foreach, class, interface, abstract, extends are all keywords and cannot be used as our identifiers when we create our variables or class or interface..

Example of variable definitions.

int i = 0;

Here int is the datatype, i is the identifier/variable name and 0 is the literal/value that is stored in memory under the name of i.

More Examples:

int num1 = 10;
short num2 = 500;
long num3 = 6;
float num4 = 30.05f;
double num5 = 3.35;
decimal num6 = 3.5M;
bool flag = true;
char c = 'a';
string s = "Hello World!";

We can change the value of a variable by assigning a new value to it.

num1 = 20;
num5 = 30.35;
flag = false;
c = 'b';
s = “Hello”;

Single dimensional array

Arrays are used to store one or more items of the same data type in memory.

For example we want to store all prime number below 20.

int [] array = {1,3,5,7,11,13,17,19};

We may want to store names of best selling cars

string [] cars = {"Toyota", “Chevy”, “Ford”};

We may want to store all the English alphabets

char [] alphabets = {'a', ‘b’, ‘c’, ‘d’, 'e' ,'f'}; //you get the idea

If we don't know how many items we are going to store in the array, then we can take a guess of the maximum number of items (like 26 for English alphabets) or give some arbitrary big number. Any memory slot that we didn't use will be wasted so we need to be careful.

int[] A= new int[3];

Here we create an array of integers who can store up to 3 numbers. Array indexing always start from 0 up to n-1, where n is the size of the array which is 3 in the above example.

We can access arrays using angled brackets to put or retrieve values in to memory.

A[0] = 1;
A[1] = 2;
A[2] = 3;

A[0] retrieves 1 from memory for us.

A[1] retrieves 2 from memory for us.

If we know the items we want to store in the array then we can declare the array as follows.

int[] A= new int {1,2,3};
string [] cars = {"Toyota", “Chevy”, “Ford”};
char [] alphabets = {'a', ‘b’, ‘c’, ‘d’, 'e' ,'f'};
bool [] response = {true, false};

Two dimensional array

Two dimensional array store rows and columns of information of the same data type. The can also perceived as an array of arrays or matrix.

For example, the following table represents a two dimensional array with 3 rows and 4 columns.

1	10	5	9
5	2	3	4
6	8	5	5

int[,] array = new int[3, 4];
array[0, 0] = 1;
array[0, 1] = 10;
array[0, 2] = 5;
array[0, 3] = 9;

array[1, 0] = 5;
array[1, 1] = 2;
array[1, 2] = 3;
array[1, 3] = 4;

array[2, 0] = 6;
array[2, 1] = 8;
array[2, 2] = 5;
array[2, 3] = 5;

Constants

are variables but their values never change. In C# we can use the keyword const to declare a constant variable. A constant field also need a value we we declare it and we can't change the value after we assigned the value to it.

const double PI = 3.14;

const double PI ; //error since we didn't assign a value to it.

const double PI = 3.14;

PI = 3.1415; //error since you cannot change the value of a constant after it is initialized.

Enum

Enum are like arrays and are used to store a set of items which are under the same category like colors, responses, items but are stored and retrieved differently. Here is how we define our color enumeration.

enum Colors { white, red, green };

We can reassign/change the values of an array like A[0] = 10; but we cannot change enum values. So they are like constant arrays.

In order to access our enum we can use our . navigator like this

Console.WriteLine(Colors.white); //white

Struct

Struct are similar to a class but they don't support OOP concepts like inheritance, polymorphism, abstraction…

Class

A class is a a blue print of a real world entity like a student, class, account. It has attributes and set of behaviors/operations that we can do on those attributes.

A class is created using the class keyword followed by the name of the class and preceded by the access modifier. Public means this class can used from outside of this class. More on access modifiers in another lesson.

We have different types of classes

Concrete Class
Abstract Class
Interface Class

Concrete Class

is a stand alone class which has concrete properties and methods. It can act as a parent class or a child class. We can instantiate a concreate class on it own.

Abstract Class

an abstract class cannot stand on it own and hence we cannot instantiate (or create an instance abject from it).

An abstract class has its own concreate methods and properties but it must have at least one abstract method in which the child classes are forced to implement the details of it.

Interface Type

An interface type is like an abstract class with just the template of a class and doesn’t implement the members that it defines. The derived/sub/child class of an interface can implement the members of the interface.

Interfaces can contain methods signature and properties with no concrete implementation of methods. The interface method signature acts as a blue print for sub classes to implement.

Access modifiers

Access modifier dictates the scope of a variable. The scope means the part of our program where a variable is visible. You can only access the variable in the scope in which it is defined. This is sometimes within a method or a loop or a conditional statement block or a class. More on variable below. There are 5 access modifiers.

private : means the variable is only accessible inside the class
internal: accessible inside a given namespace/package.
protected: accessible inside the class and also to any sub class
protected internal : accessible inside the class, to any sub class and also inside the same namespace
public: Is accessible anywhere outside the class

Value and Reference types

Basically types can be classified as value type and reference types.

The difference is value types occupy a copy of the data and is immutable means in order to change the value you have to abandon the variable completely and start with a new variable. Value type its create a unique copy of data. Each variable has its own spot in memory.

However, reference types share a single copy of their data and if we make a change using one variable, then the value of the other variable will also change if they are pointing in to the same area in memory.

All the datatype listed below are value types except string.

A String is a reference type even though it has most of the characteristics of a value type such as being immutable. Immutable means you cannot change the value of the variable.

Every time you assign a new value to a string it will create a new memory space for you.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 13, 2021 | 956 Views |

Given an area, A for a rectangle, find the minimum perimeter for the rectangle.

Example

If Area = 60, we can think of 5 rectangles with area 60.

1 * 60 = 60. Perimeter = 2* ( 1 + 60) = 122

2 * 30 = 60. Perimeter = 2* ( 2 + 30 ) = 64

3 * 20 = 60. Perimeter = 2* ( 3+ 20 ) = 46

4 * 15 = 60. Perimeter = 2* ( 4 + 15 ) = 38

6 * 10 = 60. Perimeter = 2* ( 6 + 10 ) = 32

So the minimum perimeter is 32.

Solution:

Steps:

we can start with the obvious and keep finding the smallest perimeter. 1 * Area = Area. So, P = 2* ( 1 + A)
We can start from i=2 and keep checking if A% i == 0, then take A/i, in our case these are the 30,20,15, and 10, which we get when we divide Area by i, where i > 1 and i * i < A
The last step is to compare if the new perimeter we find is less than what we already have in step 1 and if it is save the new perimeter

int min = 2*A + 2; int i = 2; int x = 1;
while(i * i <= A) {
if(A % i == 0) {
x = A / i;
if( ((2*i) + (2*x)) < min) {
min = (2 * i) + (2 * x);
}
}
i++;
}
return min;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 13, 2021 | 1,017 Views |

Given an array of integers and a target value K, find the count of pairs of array elements that have a difference equal to the target value, K.

Example:

Given A = { 1, 2, 3, 5, 7 } and Target = 2

Answer: 2 since there are two pairs in this list whose difference equals to 2

Solution:

This problem is very similar to ADD TO TARGET ALGORITHM, just a subtle but very important difference.

The optimal solution that will run O(N) time would be to use the dictionary data structure.

First, we will run through the array elements and throw a(i) - target in to the dictionary because we want to find any element in the array if it is a(i) - target, where a(i) is any element of the array. This makes sense if we solve for b in the equation:

a(i) - b = target. [find any two pairs a(i) , b so that a(i) - b = target]. Therefore, b = a(i) - target

Then we are going to iterate through the array elements second time and find if any one of them are present in the dictionary and if it does then that is what we want.

public int solution(int[] A, int K) {
int count = 0;
HashSet<string> myhash = new HashSet<string>();
for (int i = 0; i < A.Length; i++) {
if(A[i]>K) {
myhash.Add((A[i]-K).ToString());
}

for (int i = 0; i < A.Length; i++) {
if (myhash.Contains(A[i].ToString())) {
count++;
}
}
return count;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 13, 2021 | 862 Views |

Inheritance

One of the basic concepts of OOP is inheritance. Inheritance is a way of sharing a bunch of features that are defined at a super class level from a sub class level. Inheritance defines a child-parent relationship among classes. Child classes can inherit one or more properties and methods from parent class. This means any property or method that is defined in parent class can be reused in child class with out the need for redefining the same thing in the sub class.

Abstract Class

Abstract is like a base/super/parent class with concrete properties and methods but we also have abstract methods in which we delegate the responsibilities of the class to child/sub classes as we don't have the details of the sub class information and it may vary depending on the sub class.

For example we may have two concreate classes (Circle and Sphere) inheriting from Shapes parent abstract class.

The shape can provide the common pieces for the different shapes that can inherit from this class.

But the shape class has no idea how to compute the Area of shapes that inherit from it and therefore only provide the template for it and leave the implementation details to sub classes. We use the abstract keyword to indicate we are just putting the method signature and only subclasses can provide the implementation.

public abstract class Shape {
public const double PI = Math.PI;
protected double x, y;
public Shape() {
}
public Shape(double x, double y) {
this.x = x;
this.y = y;
}
public abstract double Area();
}

Now the definition of the Circle class is only to define the implementation of the Area class. Every thing else is automatically inherited from parent class Shape. We use the colon : after the name of the class to indicate Circle is a subclass of Shape and we use :base keyword to call parent constructor to initialize the properties of the sub class. We also use the keyword overrride to indicate that we are overriding the abstract method in the subclass.

public class Circle : Shape {
public Circle(double r) : base(r, 0) {
}
public override double Area() {
return PI * x * x;
}
}

Now, let's do the same for Sphere

class Sphere : Shape {
public Sphere(double r) : base(r, 0) {
}
public override double Area() {
return 4 * PI * x * x;
}
}

As you can see, the only difference between the subclasses Circle and Sphere is how they implement the Area() method as we use different formulas to calculate the area of a Circle from that of a Sphere.

Polymorphism

Polymorphism is dynamically binding methods of a class as if they are present in the super class by calling the appropriate methods of the subclass at run time.

To understand this let us see how this is done using the following example.

static void Main() {
double r = 3.0, h = 5.0;
Shape c = new Circle(r);
Shape s = new Sphere(r);

Console.WriteLine("Area of Circle = " + c.Area());
Console.WriteLine("Area of Sphere = " + s.Area());
}

Output:

Area of Circle = 28.27
Area of Sphere = 113.10

Shape c = new Circle(r);
c.Area()

How in the whole world does Shape knows how to calculate the area of a circle c. After all we don't see the formula in the Shape class, it is empty.

Well, that is the magic of Polymorphism.

Shape c = new Circle(r);

Polymorphism resolves which area we are calculating based on the object type we attached to the shape as shown in bold.

If c is of type Circle, then I we are calculating the area of the Circle.

Note. We can always assign a subclass to a super class but not vice versa.

Therefore,

Shape c = new Circle(r); and Circle c = new Circle(r); is a correct way of instantiating a class.

However, we cannot assign a super class object to a subclass.

Circle c = new Shape(r, h); //Compile Error.

We should never instantiate an abstract class since it doesn't stand by itself due to its abstract methods.

Shape s2 = new Shape(r, h);//Compile Error.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 13, 2021 | 867 Views |

We recommend the introductory articles on OOP before reading this article.

BASIC PROGRAMING TUTORIAL
C# OBJECT ORIENTED PROGRAMING (OOP) : CREATING A PERSON CLASS AND ITS MEMBERS
INHERITANCE AND POLYMORPHISM

In this OOP exercise we will create two classes Project and Task. A project can be any real world project like Construction, Business, Software, Humanitarian etc. A project has a list of tasks that needs to be done to complete the project. A project has a start date and end date as well as the name of the project.

A given task has duration of the task, and which project it belongs to as well as the name of the given task.

As you guessed, there is a One-Many relationship between a task and a project. For this we have to use a collection data structure (List ) to create the relationship.

private IList<Task> Tasks = new List<Task>();

IList collection class has built methods to add or remove items to the list.

Tasks.Add(task);

Let's see everything put together now.

public class Project {
public string ProjectName { get; set; }
public DateTime StratDate { get; set; }
public DateTime EndDate { get; set; }

private IList<Task> Tasks = new List<Task>();
public Project(string ProjectName, DateTime stratDate, DateTime endDate) {
this.ProjectName = ProjectName;
this.StratDate = stratDate;
this.EndDate = endDate;
}
public void AddTask(Task task) {
Tasks.Add(task);
}
public void RemoveTask(Task task) {
Tasks.Remove(task);
}
public double CalculateTotalCost() {
double TotalCost = 0;
foreach (Task t in Tasks) {
TotalCost += t.CalculateCost();
}
return TotalCost;
}
}

Task can be defined as an abstract class as we can have other concreate class depending on which task we want to implement. So the abstract class delegate the job of calculating the cost to the sub classed which inherit from this class.

public abstract class Task {
public string Name { get; set; }
public int Duration { get; set; }

private Project Project;

public Task(string name, int duration, Project project) {
this.Name = name;
this.Duration = duration;
this.Project = project;
project.AddTask(this);
}
public abstract double CalculateCost();
}

For example, Building the foundation is one task where as Painting Job is another task. Each task has a way of calculating its total cost which a different way from other subclasses of Task. For example for BuildingTask class it may be a matter of adding Labor and material cost but for others sub classes there may be other parameters we need to consider.

public class BuildingTask : Task {
public double LaborCost { get; set; }
public double MaterialCost { get; set; }
public BuildingTask(string TaskName, int duration, Project project, double LaborCost, double MaterialCost) :
base(TaskName, duration, project) {
this.MaterialCost = MaterialCost;
this.LaborCost = LaborCost;
}
public override double CalculateCost() {
return LaborCost + MaterialCost;
}
}
}

public class Tesing {
static void Main(string[] args) {
Project ConstructionProj = new Project("ABC Building", new DateTime(1/1/2000), new DateTime(10/10/2030));
Task TFoundation = new BuildingTask("ABC Building Foundation ", 10, ConstructionProj, 2000, 5000);
Console.WriteLine( TFoundation.Name + " will take " + TFoundation.Duration + " Month and costs " +
TFoundation.CalculateCost());
Task TPaint = new BuildingTask("ABC Painting", 20, ConstructionProj, 5000, 5000);
Console.WriteLine(TPaint.Name + " will take " + TPaint.Duration + " Month " + TPaint.CalculateCost());
Console.WriteLine("Total Construction and Paint cost is for ABC Building:" + ConstructionProj.CalculateTotalCost());
Console.ReadLine();
}

Here is the output we get from the above code.

ABC Building Foundation will take 10 Month and costs 7000
ABC Painting will take 20 Month 10000
Total Construction and Paint cost is for ABC Building:17000

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 12, 2021 | 1,078 Views |

In this OOP exercise we will try to create a person class definition and create properties/Data Fields with Modifier Methods and constructors.

Class

A class is a representation of real world object like a Person, Vehicle, Student, Employee..

A class is created using the class keyword followed by the name of the class and preceded by the access modifier. Public means this class can used from outside of this class. More on access modifiers in another lesson.

public class Person {

}

A class has mainly three components

Data Fields
Methods
Constructors

Data Fields

Stores the state of the attributes of the object that is created when the class is instantiated.

For example, if the object we want to create is a person, then some of the attributes will be First Name, Last Name, Age, etc. These are what we call the Fields of the class..

public string GivenName ;

Static Fields vs Instance Fields

There are certain type of fields that don't change from object to object no mater how many times we instantiate the object.

These are constant fields are static by nature and they don't change at all. Const is the keyword we use to create constant fields and they are static by default.

Example:

private const int VOTE_AGE = 18;

But instance fields are the regular fields in which their values change from every time we create a new instance of the object.

Example

public string FamilyName { get; set; }

Methods

Method on the other hand are used to do some kind of action on the state of the class. In other words they change the state of the class. For Example if a person's name is John, we can change this name to Paul using the methods of the class.

An accessor method is used to do this. They have direct access to the properties/fields of the class and they are mostly used from outside of the class.

public string GivenName { get; set; }

Other than accessor methods, we can use other types of methods including doing some kind of computation like calculating the age of the person based on property age.

Constructors

Constructors are used to instantiate the class. They are used to initialize the class with some basic staff. Without constructors we cannot create an object of the class.

Instantiation means creating an instance of the class. We will see how to do this at the end.

parameterized constructor

We can pass all the parameters that we want to initialize the class with in the constructor when we instantiate the class.

public Person(string ID) {
IDNumber = ID;
}

If we don't want to initialize the class with default values, we can just use the default constructor as shown below.

public Person()
{
}

Let's see everything put together now.

public class Person {
  //PROPERTIES/Data Fields
public string GivenName { get; set; }
public string FamilyName { get; set; }
public string IDNumber { get; set; }
public int BirthYear { get; set; }
private const int VOTE_AGE = 18;
private const int SENIOR_AGE = 65;

  //Constructors
public Person() {
}
public Person(string ID) {
IDNumber = ID;
}
public Person(string first, string family, string ID, int birth) {
GivenName = first;
FamilyName = family;
IDNumber = ID;
BirthYear = birth;
}

   //Methods
public int Age(int year) {
return year - BirthYear;
}
public bool CanVote(int year) {
int theAge = Age(year);
return theAge >= VOTE_AGE;
}
public bool IsSenior(int year) {
return Age(year) >= SENIOR_AGE;
}
public string Tostring() {
return "Given name: " + GivenName + "\n"
+ "Family name: " + FamilyName + "\n"
+ "ID number: " + IDNumber + "\n"
+ "Year of birth: " + BirthYear + "\n";
}
public bool Equals(Person per)
{
if (per == null)
return false;
else
return IDNumber.Equals(per.IDNumber);
}
}

Now that we have implemented the class definition with all the necessary components of the class, how do we actually use this class. Unless we instantiate it and create objects then it is useless to do all of this.

Class Instantiation

The simples way to create an object of type Person is as follows:

Person person = new Person();

Here person is an object of type Person.

We used an empty constructor and therefore person has no actual values at this point.

We have two options to initialize an object (or pass values). One using the accessor methods and second one is using the parameterized constructor.

Using accessor methods

person.GivenName = “Sam”
person.ID = "1234";

Using parameterized constructor

Person p2 = new Person("Jane", "Jones", "5678", 1990);

Once we set the values of the person's given name or Id, we can get it back using the same accessor method as follows:

p1.GivenName

We can also use the calculating methods like Age to get the age of the person. Mind you, we don't store age as a property in the object but we can calculate the age from the birthdate property and return that when asked.

For example the following code will return the calculated age of a person after calculating the difference of the passed in (current) year value from the birth date.

p1.Age(2014)

We can also use another calculating method CanVote() to check if the person can vote (if he/she is above 18 years old)

static void Main(string[] args) {
Person p1 = new Person("Sam", "Jones", "1234", 1950);
Person p2 = new Person("Jane", "Jones", "5678", 2010);
Console.Write("Age of " + p1.GivenName + " is " + p1.Age(2014));
if (p1.IsSenior(2004))
Console.WriteLine(p1.GivenName + " can ride the bus for free");
else
Console.WriteLine(p1.GivenName + " must pay to ride the bus");

Console.Write("Age of " + p2.GivenName + " is " + p2.Age(2004));
if (p2.CanVote(2004))
Console.WriteLine(p2.GivenName + " can vote");
else
Console.WriteLine(p2.GivenName + " can't vote");
}

Here is the output we get from the above code.

Age of Sam is 71. Sam can ride the bus for free

Age of Jane is 11. Jane can't vote

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 12, 2021 | 1,188 Views |

Find customers who never order any product so far.

Solution:

select custname from Customer
where custid not in (
select custid from Orders
)

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 12, 2021 | 1,012 Views |

Given a list of employees and their corresponding managers, we would like to find those customers who earn less than their managers.

CustomerID	Name	Salary	Manager
1	Dave	1000	2
2	Peter	2000
3	Salem	3000	2
4	Doe	5000	2

In this example, we can see that Peter is the manager of three customers (Dave, Salem and Doe). But only Salem and Doe earn more than him.

Solution.

In this kind of situation, we can see that the manger is also an employee and it is stored in the same employee table. Therefore, we can have a self join here and check if a certain employee e make more money than his manager m.

select e.Name Employee
from Employee e , Employee m
where e.Manager = m.Id and
e.salary > m.Salary and
e.Manager is not null

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 12, 2021 | 986 Views |

Check for Duplicate Values in Array containing random number which are repeating or distinct. Our job is to tell if the array contains repeating elements.

Example: 3, 4, 8, 6, 7, 9, 4, 77 Ans = True. 4 appears twice

Example: 3, 8, 6, 7, 9, 4, 77 Ans = False. No dups

Solution:

We loop through the array one element at a time and we throw it in to a hashset if we didn't do this before. But if we already visit this number before, then we can check it in the set and quickly tell the list has distinct elements or not.

public bool ContainsDuplicate(int[] nums) {
HashSet<int> hs = new HashSet<int>();
for(int i=0;i < nums.Length; i++) {
if(!hs.Contains(nums[i]))
hs.Add(nums[i]);
else
return true;
}
return false;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 12, 2021 | 875 Views |

Given two sorted arrays of integers, we want to find the Median of the elements of the two sorted array.

Example: A = { 2, 4, 10, 11, 12, 14 } and B = { 1, 5 }

Output: 7.5. Since (5 + 10 )/2 = 7.5

Solution:

The trick here is how to merge them together.

Steps

We create a new empty array, C, with the size of A+B
we iterate through A and B simultaneously with two variables i and j and check if A[i] < B[j] and save which ever is smaller in to C.
At this point we run out the number in the shorter array, if any. So we need to copy the rest of the elements from the longest array to the result array C.

Once the two sorted arrays are merged in to one single sorted array C, then calculating the median is as easy as picking the middle element if the number of items in C is odd or calculate the average of the middle two elements.

public double FindMedianSortedArrays(int[] a, int[] b) {
int[] c = MergeArrays(a, b);
double median = 0;
int n = c.Length;
if (n % 2 == 0) {
median = (c[(n / 2) - 1] + c[(n / 2)]) / 2.0;
}
else {
median = c[(n / 2)];
}
return median;
}

public static int[] MergeArrays(int [] a, int [] b) {
int[] c = new int[a.Length + b.Length];
int i = 0,j = 0, k=0;
while ( i<a.Length && j < b.Length) {
if(a[i] < b[j]) {
c[k] = a[i];
i++;k++;
}
else {
c[k] = b[j];
j++;k++;
}
}
while (i < a.Length) {
c[k] = a[i];
i++;k++;
}
while(j < b.Length) {
c[k] = b[j];
j++;k++;
}
return c;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 12, 2021 | 1,020 Views |

Given two sorted arrays of integers, we want to merge them together in to one sorted array.

Example:

Let A= { 3, 4, 6, 10, 11, 15 } and B = {1, 2, 5, 7, 12}

Output: C= { 1, 2, 3, 4, 5, 6, 7, 10, 11,12, 15 }

Solution

Steps

We create a new empty array, C, with the size of A+B
we iterate through A and B simultaneously with two variables i and j and check if A[i] < B[j] and save which ever is smaller in to C.
At this point we run out of numbers in the shorter array, if any. So we need to copy the rest of the elements from the longer array to the result array C.

public static int[] MergeArrays(int [] a, int [] b) {
int[] c = new int[a.Length + b.Length];
int i = 0,j = 0, k=0;
while ( i<a.Length && j < b.Length) {
if(a[i] < b[j]) {
c[k] = a[i];
i++;k++;
}
else {
c[k] = b[j];
j++;k++;
}
}
while (i < a.Length) {
c[k] = a[i];
i++;k++;
}
while(j < b.Length) {
c[k] = b[j];
j++;k++;
}
return c;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 12, 2021 | 925 Views |

Give a list of distinct nodes in a singly linked list, we want to check if a there is a cycle in it.

Example:

Input: 1→3→5→6→7

Output: No cycle detected

Input: 1→3→5→6→7→9→2→5. Here assume that the last node(5) is same as the middle node(5) and everything repeats after that as depicted in the picture above.

Output: Cycle detected

Solution:

To solve this problem we need to visualize it as a real world example. If indeed a cycle exists then we can visualize this like fast runners overlap other relatively slow runners in a track field running computation. Therefore, we can use two runners (pointers) for our linked list and we deliberately make one slow by moving the cursor one node at a time but the other one fast by moving it two nodes at a time. As a result these two runner eventually overlap each other and hence bingo we know that there is a cycle in the linked list.

bool hasCycle(SinglyLinkedListNode head) {
SinglyLinkedListNode slow = head;
SinglyLinkedListNode fast = head;

while(fast!=null && fast.next !=null) {
slow = slow.next;
fast = fast.next.next;
if(slow==fast)
return true;//cycle exists
}
return false;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 12, 2021 | 889 Views |

Give a list of nodes with duplicate values in a sorted singly linked list, we want to remove the duplicates and return distinct ones.

Example:

Input: 1→3→5→5→6→6→7

Output: 1→3→5→6→7

Solution:

Here we will have to pointers. One will keep the current node and one (lets call it runner) will go through the whole list and check for duplicates. Whenever the two pointers point to the same value nodes (duplicates), we will remove the later node by adjusting the next value of the node to it is next of next node and hence deleting the node.

SinglyLinkedListNode RemoveDuplicates(SinglyLinkedListNode head) {
SinglyLinkedListNode current = head;
while(current !=null) {
SinglyLinkedListNode runner = current;
while (runner.next!=null) {
if(runner.next.data == current.data)
runner.next = runner.next.next;
else
runner = runner.next;
}
current = current.next;
}
return head;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 12, 2021 | 914 Views |

Given a string with several opening and closing brackets, we want to check if the brackets are balanced when every opening bracket is closed.

Examples:

( ( ) ( ( ) ) ) is balanced whereas ( ) ) is not.

( ) ( ) ( ) ( ) is balanced whereas ( ( ) ( ) ) ) is not

) ) ( ( is not balanced.

Solutions:

This is a perfect fit for our stack data structure.

Every time we see the opening bracket, we can push it to the stack. Also if we see a closing bracket before we see an opening bracket, we return false / not balanced.
Every time we see a closing bracket, we pop the opening bracket we already pushed if the stack is not empty
Finally, if we still have left overs in the stack after we are done through the string it means there is a closing bracket missing.

Stack<string> stack = new Stack<string>();
for (int i = 0; i < A.Length; i++) {
if (A[i] == '(')
stack.Push(A[i].ToString());
else {
if (stack.Count != 0)
stack.Pop();
else
return false;
}
}
if (stack.Count == 0)
return true;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 4, 2021 | 984 Views | 1 Comments

Given to string s1 and s2, we want to check if they are isomorphic strings. Two string are Isomorphic when there exists a one to one mapping between each character of both string.

Example.

Consider s1 = abefbctba and s2 = ghtdhdshg

Ans. True.

S1	S2
a	g
b	h
e	t
f	d
b	h
c	d
t	s
b	h
a	g

Example.

Consider s1 = abefbctba and s2 = ghtdhdsfg

Ans. False as the last b in s1 is not approprtely mapped to h in s2. S2 has f instead.

Solution:

This problem can easily be solved using a dictionary data structure as it is efficient in dealing with key value pairs like we saw in the above table.

All we have to do is store the characters of s1 in the dictionary using the above mapping (s1 as key, s2 as value) if it is not added yet.

If it is already there that means we can get the value using the key (s1) and compare it with what is in there in s2 and it doesn't match, bingo!!! It means they are not Isomorphic strings.

Dictionary<char, char> dict = new Dictionary<char, char>();
int i = 0;
foreach(char c in s1)
{
if(!dict .ContainsKey(c))
dict .Add(c, s2[i]);
else if (dict [c]!=s2[i])
return false;
i++;
}
return true;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 4, 2021 | 878 Views |

Find the number that is repeating from distinct random numbers.

Example: 3, 4, 8, 6, 7, 9, 4, 77 Ans = 4

Solution:

This problem can easily be solved by using hashtable

We put the elements of the array in hashtable and check if we already put the number if so we will return the number

Hashtable ht = new Hashtable();
for (int i = 0; i < a.Length; i++) {
if (!ht.ContainsKey(a[i]))
ht.Add(a[i],0);
else
return a[i];
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 3, 2021 | 852 Views |

Given a list of unsorted numbers 1…n , we need to find the missing element assuming that if we sort the array, we will get consecutive number except one missing number. Note that the list always have 1 as a member.

Example: 1,3,5,4,6,8,9,2 Ans = 7 Since if we sort the array we get 1,2,3,4,5,6,8,9 and we can see 7 is missing

Solution:

We can sort the list in O(NlogN) time and iterate through the array and check if A[i] ≠ A[i+1]. If so we find the missing one. But we can do better than O(NlogN) here by using a simple formula.

To solve this problem in linear time we have to use a math formula to get the sum of consecutive numbers.

1+2+3+4….N = n (n+1) / 2 where n is the size of the array.

Example: 1+2+3+4+5 = 5(6)/2 = 15

Therefore to find the missing number first we will find the sum with the above formula and the sum of the given array and we will subtract each other to find the answer.

Note: When we calculate N, we need to consider the missing element so we add one to it (N+1)

int N = A.Length + 1;
int calctotal = N * (N + 1) / 2;
int actualtotal = 0;
foreach (int i in A) {
actualtotal += i;
}
return calctotal - actualtotal;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 3, 2021 | 937 Views |

Given a list of integers, we would like to find the majority element. The majority element is the number that is repeated more than half of the size of the given array.

Examples:

Let A = { 3,5,3,5,3,7,3,9,3 } Ans: 3 since 3 occurred more than half of this array.

Solution:

Method 1

We can easily solve this with the power of hashtable. First we store the count of each integer as a value for a hashtable with key of the integer.

Then we come back and iterate through the keys of the hashtable and we check if any of them are greater than half of the count of the array

if (nums.Length == 0)
return -1;
Hashtable ht = new Hashtable();
for (int i = 0; i < nums.Length; i++) {
if (!ht.ContainsKey(nums[i])) {
ht.Add(nums[i], 1);
}
else {
ht[nums[i]] = (int)ht[nums[i]] + 1;
}
}
foreach (int i in ht.Keys) {
if ((int)ht[i] > nums.Length / 2)
return i;
}
return 0;

Method 2

We can also calculate the majority element in each iteration as follows:

If our count of current candidate number goes to zero , we will update our majority element to the current item in the list.
Else check if current item is same as our candidate and if so, we will increment count by 1
otherwise decrement count by one
Finally the real count of our candidate by running a new loop and see if that is more than half of the items.

Note: The key thing in this algorithm is that for a number to be a majority number it shall be present in the array at least every other number including boundary values. Therefore as long as there is chance I can see the candidate after another number, I won't change my majority candidate number. Otherwise I have to update my majority number and keep checking the same way.

int count =0 ;
int majority = 0;

for (int i = 0; i < a.Length; i++) {
if (count == 0) {
majority = a[i];
count = 1;
}
else if (a[i] == majority)
count++;
else
count--;
}

count = 0;
for (int i = 0; i < a.Length; i++) {
if (a[i] == majority)
count++;
}

if (count > a.Length / 2)
return majority;
else
return 0;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 3, 2021 | 828 Views |

Given two string s1 and s2, we want to check if one can be reproduced by permutating the chars of the others.

Example:

Given s1 = "race" and s2 = "care" Ans = true

Given s1 = "heart" and s2 = "earth" Ans = true

Given s1 = "test" and s2 = "set" Ans = false

Solution:

First we can check the length of each string and if they are not the same we can return false.

Then we can throw both chars of each string into a dictionary the chars as a key and the count of each occurrence of chars as a value.

Then we can iterate through one of the dictionary and check if the values (count of chars) matches for each key (char in the string)

public static bool CheckPermutation (string s1, string s2) {
if (s1.Length != s2.Length) return false;
Dictionary<char, int> dict = new Dictionary<char, int>();
Dictionary<char, int> dict2 = new Dictionary<char, int>();

foreach (char c in s1) {
if (!dict.ContainsKey(c))
dict.Add(c, 0);
else
dict[c]++;
}
foreach (char c in s2) {
if (!dict2.ContainsKey(c))
dict2.Add(c, 0);
else
dict2[c]++;
}
foreach (KeyValuePair<char, int> kv in dict) {
if (!dict2.ContainsKey(kv.Key))
return false;
else
if (kv.Value != dict2[kv.Key])
return false;
}
return true;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 2, 2021 | 866 Views |

Given a list of numbers that represent the values of stocks that you can buy or sell at a given day, we would like to find maximum profit that we get by buying a stock at the minimum price and selling it at the maximum price. You must buy first before you sell a stock and you can buy and sell only one time.

Example:

A = { 8, 3, 2, 6, 7, 2, 7, 8 }; Ans = 6. You can buy at a minimum price of 2 and sell it at a maximum price of 8

Solution:

Here, we will go through the numbers in the list and try to see where we can buy at a minimum price. We can assume the first element is the minimum but update it if we find less number than this.

Also we will start with maxprofit =0 and we will see if we can get a better profit by checking each element minus minimum is greater than our maxproft, if it does we will update our max profit.

The trick here is we should always do finding the minimum part first before we attempt to do max profit calculation since it depends on it.

if (prices.Length <= 0)
return 0;
int minBuyPrice = prices[0];
int maxProfit = 0;

for (int i = 1; i < prices.Length; i++) {
if (prices[i] <= minBuyPrice) {
minBuyPrice = prices[i];
}
else {
if (prices[i] - minBuyPrice > maxProfit)
maxProfit = prices[i] - minBuyPrice;
}
}
return maxProfit;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 1, 2021 | 961 Views |

Given an array of characters we want to reverse it in place [no extra array is allowed].

Example:

A = { 'a','b','c','d','e'};

Ans: {'e', ‘d’, ‘c’, ‘b’, ‘a’}

Solution

Here run a loop and swap the elements one from the beginning and one from the end till we reach to the center of the array. after that we don't need to do anymore since it has already swapped.

int n = A.Length;
for(int i=0; i<n/2; i++) {
char temp = A[i];
A[i] = A[n - i-1];
A[n - i - 1] = temp;
}
return A;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 1, 2021 | 852 Views |

Given a list of numbers we want to transform the array by rotating the numbers to left K times.

Example:

A = {1,2,3,4,5} K=1

Ans: {2,3,4,5,1}

Example:

A = {1,2,3,4,5} K=2

Ans: {3,4,5,1,2}

Example:

A = {1,2,3,4,5} K=3

Ans: {4,5,1,2,3}

Explanation:

Rotating the array means moving the elements one position to the left in a circular manner which means the first element becomes the last and everything else shifts to the left

We want to do that for K number of times.

Solution:

Rotating the array K times means we copy all the elements from K to N ,and then elements 0 to K respectively to our result table where N is the size of the array. If K = N then all the elements will come back to their original place as though no rotation happened or K = 0.

But this is true if K < N. For larger K values we want to harness the power of modulo operator which is the remainder of the division operation of two number.

In the above example, N = 5

K % 5 = 0 if K = 0

K % 5 = 1 if K = 1

K % 5 = 2 if K = 2

K % 5 = 3 if K = 3

K % 5 = 4 if K = 4

K % 5 = 0 if K = 5

K % 5 = 1 if K = 6

K % 5 = 2 if K = 7

…

K % 5 = 0 if K = 10

…

K % 5 = 0 if K = 15

Do you see that pattern here, K% 5 is always between 0 and K-1 which is exactly how many times we have to rotate the array.

static int[] rotLeft(int[] a, int k) {
int[] result = new int[a.Length];
int n = a.Length;
k= k % n;
int count = 0;
for (int i = k; i < n; i++) {
result[count++] = a[i];
}
for (int i = 0; i < k; i++) {
result[count++] = a[i];
}
return result;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 1, 2021 | 949 Views |

Given two arrays of integers, we want to find all pairs of two integers one from each array in such a way that if we swap these two integers the sum of the elements of each array will be equal. We are trying to balance the disproportional arrays to have the same sum at the end.

Example:

int[] a = { 1,5,2,3,4,7 };

int[] b = { 2,1,5,10};

answer: {3,1}, {4,2}, {7,5} It means if you switch 3 and 1 from both arrays the sum of the elements of the array will be equal (20).

Also {4,2} can be the answer. It means if you switch 4 and 2 from both arrays the sum of the elements of the array will be equal (20).

Also {7,5} can be the answer. It means if you switch 7 and 5 from both arrays the sum of the elements of the array will be equal (20).

Solution

Strategy here is do the math.

Lets say s1 is the sum of all elements in array 1 (int [] A)

Lets say s2 is the sum of all elements in array 2 (int [] B)

Therefore we are trying to make s1 = s2 only on one condition and that is we swap two numbers (say a coming out of A and put it in to B and b coming out of B and put it in to A)

s1+ b - a = s2 + a - b
s1-s2 = 2a - 2b
s1 - s2 = 2(a-b)
(s1-s2)/2 = a-b
a = (s1-s2)/2 + b
Let target = (s1-s2)/2
Then a = target + b
b = a - target.

Now, throw all items of B in hashset (not hashtable because we don't want to store and retrieve by key. We just want to check the existence of a value in a set) then loop A and look for if any element in A, ai equals ai - target.

public static List<IList<int>> FindTwoElements(int[] A, int[] B) {
IList<IList<int>> res = new List<List<int>>();
int sum1 = 0, sum2 = 0;
foreach (int a in A)
sum1 += a;
foreach (int b in B)
sum2 += b;
HashSet<int> ht = new HashSet<int>();
int target = Math.Abs(sum1 - sum2) / 2;
foreach (int b in B)
ht.Add(b);

foreach (int a in A) {
if (ht.Contains(a - target)) {
List<int> pair = new List<int>();
pair.Add(a);
pair.Add(a-target);
res.Add(pair);
}
}
return res;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 1, 2021 | 907 Views |

Given unsorted list we would like to find one or more pairs of three numbers that will add up to a given target value K. For the sake of simplicity you can assume K=0.

Example: int[] nums = { -1, 1, -1, 5, -3, -5, 6, 2, -4, 7 };

Ans: There are 5 pairs that add up to 0. {-5,-1,6} {-4,-3,-7} {-4,-1,5} {-3,1,2} {-1,-1,2}

Solution:

Step 1: We sort the list in ascending order in nlog(n) time. This is the time complexity of this algorithm

Step 2: We will have three indexes (i, j and k) where i and j traverse the array forward but k backwards.

In each iteration we will check three things:

If nums(i) + nums(j) + nums(k) < 0, then j++ because in a sorted array if the sum of the three numbers is less than target, it means we need to try greater values which are found going forward since array is sorted in ascending order.
If nums(i) + nums(j) + nums(k) > 0, then k-- because in a sorted array if the sum of the three numbers is greater than target, it means we need to try smaller values which are found going backwards since array is sorted in ascending order.
If nums(i) + nums(j) + nums(k) = 0, then it means we found our pair and we need to save that in a list of lists.

Note: We can use HashSet of KeyValuePair to check for duplicate pairs. We want to make sure each pair we put in the answer list is unique.

public static List<List<int>> ThreeSumer(int[] nums) {
if (nums == null || nums.Length == 0) return new List<List<int>>();
Array.Sort(nums);
List<List<int>> res = new List<List<int>>();
HashSet<KeyValuePair<int, int>> set = new HashSet<KeyValuePair<int, int>>();
for (int i = 0; i < nums.Length - 2; i++) {
int j = i + 1, k = nums.Length - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] > 0) k--;
else if (nums[i] + nums[j] + nums[k] < 0) j++;
else {
if (!set.Contains(new KeyValuePair<int, int>(nums[i], nums[j]))) {
List<int> pair = new List<int>();
pair.Add(nums[i]);
pair.Add(nums[j]);
pair.Add(nums[k]);
res.Add(pair);
set.Add(new KeyValuePair<int, int>(nums[i], nums[j]));
}
j++;
k--;
}
}
}
return res;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Oct. 1, 2021 | 928 Views |

Given a list of integers and a target number K, we would like to find the largest adjacent sum of size K.

Examples:

{1,12,-5,-6,50,3}; K= 4

Ans = 51. since Maximum sum is (12-5-6+50)

{ 1,-1,2,4,1,-8,10,9}; K=2

Ans = 19 since {10,9} are the only two adjacent number which gives us the maximum sum

{ 1,-1,2,4,10,-8,10,9}; K=3

Ans = 16 since {2,4,10} are the only three adjacent number which gives us the maximum sum

Solution:

we first add the first k numbers and then we will try to compare the sum with sum + nums[i] - nums[i - k] where i = k, k+1, k+2… nums.Length

Basically this means we temporarily assume the sum of the first k number is the best sum but we need to reevaluate our assumption as we navigate through the array one element at a time by forgetting our trailing number (forget the past) and adding the next number in the loop (grasp the future)

double sum = 0;
for (int i = 0; i < k; i++)
sum += nums[i];
double res = sum;
for (int i = k; i < nums.Length; i++)
{
sum += nums[i] - nums[i - k];
res = Math.Max(res, sum);
}
return res;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 28, 2021 | 1,293 Views |

Given the above table definitions, write a SQL query to find employees who earn the top three salaries in each of the department.

Here we need to use Dense_Rank() function that will basically rank the employees based on salary after partitioning with department ID.

Dense_Rank() over(partition by E.DepartmentId order by E.salary desc) as Rank

Then we can use subquery to get only top three earners.

Select Department,Employee,salary
from (
select D.Name as Department, E.name as Employee, E.salary,
Dense_Rank() over(partition by E.DepartmentId order by E.salary desc) as Rank
from employee E join Department D
on E.DepartmentId =D.Id
) as topearners where Rank <=3

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 28, 2021 | 1,230 Views | 4 Comments

Given a list of integers with positive and negative numbers, we want to find sum of maximum sub array with greatest sum. This means the numbers we added together has to be next to each other.

Example 1:

Given a = { 1,-1,2,4,1,-8,10,9} Ans: 19 since the sub array {10,9} gives the largest sum

Example 2:

{ 3, -8, 9, 7, -6 , 0, 1} Ans 9 + 7 = 16

Example 3:

{ 2, -8, 3, -2, 4, -10 }) Ans: 5

Example 4:

{ 2, -8, 3, 4, 7, -20, 4, -10,1 } Ans: 14

Example 5

{ -2, 1, -3, 4, -1, 2, 1, -5, 4 } Ans: 6

Solution

There are two optimal solutions for this question.

Method 1:

We need two variables to track the temp max and the actual max or sum we need to find.

The temp max (lets call it sum) always tries to compare what is in it (sum) with what is in front of it plus sum.

This means we will try to calculate the sum of the adjacent array elements and try to take the max of its current array element or sum plus the current array element.

In other words , sum= Math.Max(a(i), sum+ a(i))

This will be a good solution if there are no negative numbers. As soon as we encounter them our sum goes down significantly. Therefore, we need to store the sum value to another actual maxsum variable before we reset it (reduce the value) when we see the negative number.

int sum= A[0];
int maxsum= A[0];

for (int i = 1; i < A.Length; i++) {
sum= Math.Max(A[i], A[i] + sum);
maxsum= Math.Max(sum, maxsum);
}

return maxsum;

Here we ask the question do we get the greater sum by considering the cumulative sum or it is better off Just taking the number at this index. (Like a business owner reevaluating the contribution of all the sum of the workers and deciding if it will be a good idea taking in that as part of the total effort. If it is not worth equal or greater than the boss effort by himself then don’t even bother including them in the process.)

Let us trace the last example:

Iteration 1: sum: 1, MaxSoFar: 1

Iteration 2: sum: -2, MaxSoFar: 1

Iteration 3: sum: 4, MaxSoFar: 4

Iteration 4: sum: 3, MaxSoFar: 4

Iteration 5: sum: 5, MaxSoFar: 5

Iteration 6: sum: 6, MaxSoFar: 6

Iteration 7: sum: 1, MaxSoFar: 6

Iteration 8: sum: 5, MaxSoFar: 6

The sum of the contiguous subarray with the largest sum is: 6

The running time of this algorithm is liner time O(N).

Method 2:

The second approach is to keep adding each elements for the array until the sum goes below 0 and it does we reset the sum to 0 and if not we keep updating our maxsum when we get a new bigger sum. We reset sum to zero if it goes below 0 because if all the numbers before a certain number add up to 0 or less then we can ignore the whole sub array and assume we start a new array with the remaining items. We also tend to think the same way when we think about how to solve this kind of problem.

int Maxsum = 0;
int sum = 0;
for (int i = 0; i < A.Length; i++) {
sum += A[i];
if (sum < 0)
sum = 0;
else if(sum > Maxsum) {
Maxsum = sum;
}
}
return Maxsum;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 28, 2021 | 873 Views |

Move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example: Given A = {1,0,0,2,5,6,6,0,3,0}

Answer = {1,2,5,6,6,6,3,0,0,0,0}

Solution:

Here we would iterate through the list and we shift numbers to the left in the list. The shift happens only if the number is non-zero number.

Here we will have one runner j that gets incremented only if we don't see zero. At the end this runner(index) will be behind by the count j is behind .

Once we reached the end, we exit and started a new loop that we will put as many zeros we counted at the end starting from j.

int j = 0;
for (int i = 0; i < A.Length; i++) {
if (A[i] ! = 0) {
A[j] = A[i];
j++;
}
}
for (int i = j; i < A.Length; i++) {
A[i] = 0;
}
return A;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 27, 2021 | 986 Views |

Move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example: Given A = {1,0,0,2,5,6,6,0,3,0}

Answer = {1,2,5,6,6,6,3,0,0,0,0}

Solution:

Here we would iterate through the list and we shift numbers to the left while counting how many zeros we have in the list. The shift happens only if the number is non-zero number.

Here we will have one runner j that gets incremented only if we don't see zero. At the end this runner(index) will be behind by the number of zeros.

Once we reached the end, we exit and started a new loop that will we will put as many zero we counted at the end using the count of zeros we did in the first loop and the runner j.

int countZeros = 0;
int j = 0;
for (int i = 0; i < A.Length; i++) {
if (A[i] == 0) {
countZeros++;
}
else {
A[j] = A[i];
j++;
}
}
for (int i = j; i < A.Length; i++) {
A[i] = 0;
}
return A;

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 27, 2021 | 963 Views |

In this exercise we are going to write a SQL to find employees who have the highest salary in their departments

select * from Employee where salary in
(
select max(e.Salary)
from Employee e
group by DepartmentId
)

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 27, 2021 | 1,221 Views |

In this exercise we are going to write a SQL to find employees who have the highest salary in their departments

select * from Employee where salary in (
select max(e.Salary)
from Employee e
group by DepartmentId
)

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 27, 2021 | 1,045 Views |

Given the above tables definition, we would like to find top selling products in each store

Solution:

Here we have to join three tables to get the result

Since the relationship between a product and and store is one-to-many relationship meaning one store has several products but a specific product is stored in a specific store for this organization.

And when we want data from both tables, we have to connect the two tables together as follows

select * from product p inner join store s on p.storeid = s.storeid

To get actual products that are sold in each store, we need to join with the orders table

Here let us find which items are sold from which stores with how much price and quantity:

select p.prodid, s.StoreId, p.price , o.quantity , p.price * o.quantity totalprice
from orders o
inner join product p on p.prodid = o.prodid
inner join Store s on s.storeid = p.storeid

ProdId	StoreID	Price	Quantity	Total Price
1	1	100	1	100
1	1	100	2	200
2	2	200	5	1000
3	1	300	3	900
5	1	900	6	5400

As you can see here, there is repetition of products as multiple customer can purchase the same product from a given store

No we can leverage the power of “group by” to see what are the top selling products in each store.

select s.storeid, max(p.price * o.quantity) TotalPrice
from orders o
inner join product p on p.prodid = o.prodid
inner join Store s on s.storeid = p.storeid
group by s.storeid

StoreId	TotalPrice
1	5400
2	1000

Now the final step is to use subqueries to get the details of the above rows. We want to know the best selling product in each store

select s.storeid, p.prodid,p.price , o.quantity quantity, p.price * o.quantity totalprice
from orders o
inner join product p on p.prodid = o.prodid
inner join Store s on s.storeid = p.storeid
where ( p.price * o.quantity) in (
select max(p.price * o.quantity) TotalPrice
from orders o
inner join product p on p.prodid = o.prodid
inner join Store s on s.storeid = p.storeid
group by s.storeid
)

ProdId	StoreID	Price	Quantity	Total Price
2	2	200	5	1000
5	1	900	6	5400

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 27, 2021 | 5,344 Views |

Given the above tables definition, we would like to find top selling products in each store

Solution:

Here we have to join three tables to get the result

Since the relationship between a product and and store is one-to-many relationship meaning one store has several products but a specific product is stored in a specific store for this organization.

And when we want data from both tables, we have to connect the two tables together as follows

select * from product p inner join store s on p.storeid = s.storeid

To get actual products that are sold in each store, we need to join with the orders table

Here let us find which items are sold from which stores with how much price and quantity:

select p.prodid, s.StoreId, p.price , o.quantity , p.price * o.quantity totalprice
from orders o
inner join product p on p.prodid = o.prodid
inner join Store s on s.storeid = p.storeid

ProdId	StoreID	Price	Quantity	Total Price
1	1	100	1	100
1	1	100	2	200
2	2	200	5	1000
3	1	300	3	900
5	1	900	6	5400

As you can see here, there is repetition of products as multiple customer can purchase the same product from a given store

No we can leverage the power of “group by” to see what are the top selling products in each store.

select s.storeid, max(p.price * o.quantity) TotalPrice
from orders o
inner join product p on p.prodid = o.prodid
inner join Store s on s.storeid = p.storeid
group by s.storeid

StoreId	TotalPrice
1	5400
2	1000

Now the final step is to use subqueries to get the details of the above rows. We want to know the best selling product in each store

select s.storeid, p.prodid,p.price , o.quantity quantity, p.price * o.quantity totalprice
from orders o
inner join product p on p.prodid = o.prodid
inner join Store s on s.storeid = p.storeid
where ( p.price * o.quantity) in (
select max(p.price * o.quantity) TotalPrice
from orders o
inner join product p on p.prodid = o.prodid
inner join Store s on s.storeid = p.storeid
group by s.storeid
)

ProdId	StoreID	Price	Quantity	Total Price
2	2	200	5	1000
5	1	900	6	5400

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 27, 2021 | 1,452 Views |

Given the above tables definition, we would like to find customers who ordered more than two product type.

Solution:

Here we have to join three tables to get the result

Since the relationship between a customer and product is many-to-many relationship, we have orders table as a third table to handle this complex relationship

And when we want data from both tables, we have to connect the three tables together as follows

SELECT c.custname, p.prodname
FROM customer c
INNER JOIN orders o ON c.custid = o.custid
INNER JOIN product p on p.prodid = o.prodid

Custname	ProdName
John	Laptop
Doe	Tablet
Smith	Coat
John	Chair
Doe	Ball
Smith	Jacket
John	T-Shirt

This will give us all the customer who ordered items and what orders they ordered.

But if we we see the result, we will see that there are multiple rows for the same customer if he ordered several products.

In this case, we can use SQL group by with aggregate functions, to count the number of items he purchased.

SELECT c.custid, c.custname, COUNT(o.prodid) as products_count
FROM customer c
INNER JOIN orders o ON c.custid = o.custid
INNER JOIN product p on p.prodid = o.prodid
GROUP BY c.custid, c.custname

custid	custname	product count
1	John	3
2	Smith	2
3	Doe	2

Finally, we can filter the result returned by the group by by using having clause to count if the customer purchased more than n number of items. In this case n=2

custid	custname	product count
1	John	3

SELECT c.custid, c.custname, COUNT(o.prodid) as products_count
FROM customer c
INNER JOIN orders o ON c.custid = o.custid
INNER JOIN product p on p.prodid = o.prodid
GROUP BY c.custid, c.custname
HAVING COUNT(o.prodid) > 2

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 27, 2021 | 920 Views | 1 Comments

Given the above tables definition, we would like to find customers who ordered more than two product type.

Solution:

Here we have to join three tables to get the result

Since the relationship between a customer and product is many-to-many relationship, we have orders table as a third table to handle this complex relationship

And when we want data from both tables, we have to connect the three tables together as follows

SELECT c.custname, p.prodname
FROM customer c
INNER JOIN orders o ON c.custid = o.custid
INNER JOIN product p on p.prodid = o.prodid

Custname	ProdName
John	Laptop
Doe	Tablet
Smith	Coat
John	Chair
Doe	Ball
Smith	Jacket
John	T-Shirt

This will give us all the customer who ordered items and what orders they ordered.

But if we we see the result, we will see that there are multiple rows for the same customer if he ordered several products.

In this case, we can use SQL group by with aggregate functions, to count the number of items he purchased.

SELECT c.custid, c.custname, COUNT(o.prodid) as products_count
FROM customer c
INNER JOIN orders o ON c.custid = o.custid
INNER JOIN product p on p.prodid = o.prodid
GROUP BY c.custid, c.custname

custid	custname	product count
1	John	3
2	Smith	2
3	Doe	2

Finally, we can filter the result returned by the group by by using having clause to count if the customer purchased more than n number of items. In this case n=2

custid	custname	product count
1	John	3

SELECT c.custid, c.custname, COUNT(o.prodid) as products_count
FROM customer c
INNER JOIN orders o ON c.custid = o.custid
INNER JOIN product p on p.prodid = o.prodid
GROUP BY c.custid, c.custname
HAVING COUNT(o.prodid) > 2

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 27, 2021 | 1,782 Views |

Given a list of positive integers, find count of longest consecutive numbers.

Example:

Let A = {4, 5, 6, 8, 44, 69, 68, 66, 67, 7}

Ans = 5

Explanation: {4,5,6,7,8} is the longest consecutive numbers and count = 5. We do have another consecutive numbers here {66,67,68,69} but the count is 4 which is less.

Another example:

{1,2,4,3,99,100,5} output 5. since {1,2,3,4,5} is the longest consecutive numbers and count = 5.

Solution:

Step 1:

We need to iterate through the array and throw that to hashtable having the elements of the array as a key

Step 2:

We need to track if we visited each item in the list by creating an empty array same size as the given array and initialize it to false by default.

Step 3:

We need to iterate the list again only if it is not visited and check if A[i]-1 is in the hashtable. If it is present then we need to iterate till the hastable doesn't contain A[i] + 1 using a while loop.

While doing so we need to set the INDEX of Visited array we created at step 2 to be true for the array element we are visiting in the while loop. We also need to count how many elements we found to satisfy this condition.

There is a huge performance advantage by marking the numbers we visited to be true otherwise we may end up in O(N Squared) time complexity if we keep checking what we already visited in the previous checking.

The reason we need to skip what we have already visited is because once we checked a number is part of a series of consecutive number and count the length of this temp series, we are sure that it wont appear in another series we will start to count as far as this serious is concerned.

example:

1,2,4,3, 8,10,9,11,12

There are two series in this example. The first one {1,2,3,4} and second is {8,9,10,11,12}

Here once we visited all the elements of the first array, we don't have to go through over them when we do the same process for the second series. That is the benefit of tracking the Visited status.

Step 4:

We need to have max count variables which is the largest of count and max count.

public static int LongestConsecutive(int[] A) {
if (A.Length == 0)
return 0;
int n = A.Length;
int count = 0;
int maxcount = 0;
Hashtable hs = new Hashtable();
bool[] visited = new bool[A.Length];
for (int i = 0; i < n; i++) {
if (!hs.ContainsKey(A[i]))
hs.Add(A[i], i);
visited[i] = false;
}
for (int i = 0; i < n; i++) {
count = 0;
if (!visited[i]) {
int num = A[i];
if (!hs.Contains(num - 1)) {
while (hs.Contains(num + 1)) {
num++; count++;
visited[(int)hs[num]] = true;
}
maxcount = Math.Max(count, maxcount);
}
}
}
return maxcount + 1;
}

For type safety and performance we can use dictionaries instead of hashatable and avoid the boxing and unboxing.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 24, 2021 | 924 Views |

A hiker can go down a valley (D units) take rest and come out or go even deeper for another D units as much as he wants and come up. He can also goes up to a mountain (U units) and keeps climbing another units after a small break and goes down.

We want to know how many times a hiker goes down to a valley after he successfully emerging out of it.

Example:

UUDDUDDU -→ Ans = 1 time

DUDUDUDU-→ Ans = 4 times

UDDDUUUDU-→ Ans = 2 times

Solution:

This is a perfect example for stack data structure

We want to check each action he takes (either U or D) and then we will save it in the stack. But ever time there is item in the stack and it is the opposite of what we get when we iterate from the string, we pop it out other wise we keep stacking it.

We keep the count of how many D we see while the stack is empty.

public int solution(string str) {
char[] A = str.ToCharArray();
int result = 0;

Stack<string> stack = new Stack<string>();

for (int i = 0; i < A.Length; i++) {
if(stack.Count == 0) {
if (A[i].ToString().Equals("D"))
result++;
}

if (A[i].ToString().Equals("D")) {
if (stack.Count != 0) {
if (stack.Peek().Equals("U"))
stack.Pop();
else
stack.Push("D");
}
else
stack.Push("D");
}

//Do the exact opposite for U
else if (A[i].ToString().Equals("U")) {
if (stack.Count != 0 ) {
if(stack.Peek().Equals("D"))
stack.Pop();
else
stack.Push("U");
}
else
stack.Push("U");
}
}
return result;
}
}
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 23, 2021 | 918 Views |

Find missing positive number

Given a list of integers we like to find the smallest missing integer number.

Examples:

{1,2,5,8,9,4} Ans = 3

{ 3, 4, -1, 1 } Ans = 2

{8,10,7,9,4} Ans = 1

Solution:

We want to throw all numbers to the hashset

We then iterate from num = 1 and keep checking if the hashset contains num and if it is true, we will keep increment num by 1 until we no longer find the number in the hashset. When we do, then num will be the answer.

We need to also handle extreme cases like if all elements are negative number, then we just return 1.

public static int FirstMissingPositive(int[] A) {
if (A.Length == 0)
return 0;
if (A.Max() <= 0)
return 1;
int n = A.Length;
HashSet<int> hs = new HashSet<int>();
for (int i = 0; i < n; i++) {
if (!hs.Contains(A[i]))
hs.Add(A[i]);
}
int num = 1;
while (hs.Contains(num)) {
num++;
}
return num;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 23, 2021 | 940 Views |

Given a string with repeated and no repeated characters, we want to find the longest substring without repeating.

Example 1:

abcabcd

Ans = 4 since abcd is the longest substring with no repeated character in the substring. All chars are unique.

Example 2:

lemenmetahm

Ans: 5 since metah is the longest substring with no repeated character in the substring.

Example 3: abcdeabceghedt

Ans: 6 since abcegh is the longest substring with no repeated character in the substring.

Explanation:

Here we want to use a Hashset data structure to solve this problem in linear time.

We need two variable to track the position of the chars in the string. One will be the starting point and the other one will be the end point of the non repeating substring.

Let us say i tracks the starting where as j tracks the ending

We also want to save each char to hashset as we traverse the string using j.

we also want to calculate the length of non-repeating char as we traverse and update it if we find a new substring longer than the previous value.

public int LengthOfLongestSubstring(String s) {
int n = s.Length;
HashSet<char> set = new HashSet<char>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.Contains(s[j])) {
set.Add(s[j]);
j++;
ans = Math.Max(ans, j - i);
}
else {
set.Remove(s[i]);
i++;
}
}
return ans;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 23, 2021 | 847 Views |

Given an array of integers and an integer target, return indices of the two numbers such that they add up to target.

Example:

Given int[] a = { 1, 2, 5, 7 } and Target = 8

Answer = {0,3}

Explanation:

In the given array we know that the first element a[0] and the last element a[3] add up to target = 8.

Solution:

The optimal solution that will run O(N) time would be to use the dictionary data structure.

First, we will run through the array elements and throw target - a(i) in to the dictionary because we want to find any element in the array if it is target - a(i), where a(i) is any element of the array. This makes sense if we solve for b in the equation:

a(i) + b = target. [find any two pairs a(i) , b so that a(i) + b = target]. Then b = target - a(i)

Then we are going to iterate through the array elements second time and find if any one of them are present in the dictionary and if it does then that is what we want.

public int[] solution(int[] A, int target){
int [] a = new int[2];
Dictionary<int, int> dict = new Dictionary<int, int>();
int j = 0 ;
for(int i=0; i < A.Length; i++){
if(!dict.ContainsKey(i))
dict.Add(i, target - A[i]);
}
for (int i = 0; i < A.Length; i++){
if (dict.ContainsValue(A[i])){
a[j] = i; j++;
}
if (j == 2) break;
}
return a;
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 23, 2021 | 945 Views |

Given two arrays of integers, we want to find two integers one from each array in such a way that if we swap these two integers the sum of the elements of each array will be equal. We are trying to balance the disproportional arrays to have the same total at the end.

Example:

int[] a = { 4, 1, 2, 1, 1, 2 };

int[] b = { 3, 6, 3, 3 };

answer: {1,3}. It means if you switch 1 and 3 from both arrays the sum of the elements of the array will be equal (13).

Example:

int[] a = { 1,5,2,3,4,7 };

int[] b = { 2,1,5,10};

answer: {3,1}. It means if you switch 3 and 1 from both arrays the sum of the elements of the array will be equal (20).

Also {4,2} can be the answer. It means if you switch 4 and 2 from both arrays the sum of the elements of the array will be equal (20).

Solution

Strategy here is do the math.

Lets say s1 is the sum of all elements in array 1 (int [] A)

Lets say s2 is the sum of all elements in array 2 (int [] B)

Therefore we are trying to make s1 = s2 only on one condition and that is we swap two numbers (say a coming out of A and put it in to B and b coming out of B and put it in to A)

s1+ b - a = s2 + a - b
s1-s2 = 2a - 2b
s1 - s2 = 2(a-b)
(s1-s2)/2 = a-b
a = (s1-s2)/2 + b
Let target = (s1-s2)/2
Then a = target + b
b = a - target.

Now, throw all items of B in hashset (not hashtable because we don't want to store and retrieve by key. We just want to check the existence of a value in a set) then loop A and look for if any element in A, ai equals ai - target.

public static int[] FindTwoElements(int[] A, int[] B) {
int sum1 = 0, sum2 = 0;
foreach(int a in A)
sum1 += a;
foreach(int b in B)
sum2 +=b;
HashSet<int> ht = new HashSet<int>();
int target = Math.Abs(sum1 - sum2) / 2;
foreach(int b in B)
ht.Add(b);
foreach(int a in A) {
if(ht.Contains(a - target )) {
return new int[] { a, a - target };
}
}
return new int[] { };
}

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 22, 2021 | 1,066 Views |

SQL Group by keyword

used to categorize and group items under separate bucket and then you can use aggregate function to calculate the total items in each group

Given a list of countries and their corresponding population, calculate the total number of people in each continent

select Continent, sum(population) AS TotalPopulation
from Countries
group by Continent

Given a list of items and their corresponding prices, calculate the total sales prices under each category

select category , sum(price) as totalprice
from Sales
group by category

Given a list of employees and their corresponding departments, calculate the total salary of employees in each department

select department, sum(salary) as NoofEmployees
from Employees
group by department

Given a list of employees and their corresponding departments, calculate the number of employees in each department

select department, count(*) as NoofEmployees
from Employees
group by department

Having and Order by

Having is condition set to filter the rows that are generated from group by. It should always come after group by

Find all departments and their counts of employees from employees table where there are more than 1000 employees under it

select department, count(*) as NoofEmployees
from Employees
group by department
having count(*) > 1000
order by Department

The where clause comes before the group by

Find all departments and their counts of employees from employees table where there are more than 1000 employees under it and department name like sales

select department, count(*) as NoofEmployees
from Employees
group by department
where department like ‘Sales%’
having count(*) > 1000
order by Department

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 21, 2021 | 865 Views |

These are libraries that we can use to do some calculations.

example: sum, avg, min, max

Example:

Select the total deposits

select sum(depositAmount) as TotalDeposit
from Account

Select the minimum deposit

select min(depositAmount) as MinDeposit
from Account

select maximum deposit

select max(depositAmount) as MaxDeposit
from Account

select average deposit

select avg(depositAmount) as AverageDeposit
from Account

There are also other functions that are used to transform a single data item like making it upppercase

UCASE()
LCASE()
MID()
LEN() – to count number of characters of a string

example:

select upppercase(firstname)
from Employee

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 21, 2021 | 840 Views |

Distinct Keyword:

It gives unique records from database

It remove repeated rows

example:

Find unique merchant names form Account table

select distinct MerchantName
from Account

Order by Keyword:

It is used to sort rows based on column names

Sort account table by deposit amount in ascending order

select * from Account
order by DepositAmount asc

***asc means ascending

By default it will be ascending

Sort account table by deposit amount in descending order

select * from Account
order by DepositAmount desc

*** desc means descending

Top keyword

Will give the only the top rows you need

Question:

select top three maximum deposits

select top(3) *
from Account
order by DepositAmount desc

Question:

select top three minimum deposits

select top(3) *
from Account
order by DepositAmount asc

Question:

Select all rows from account table where deposit amount is between (500 and 5000)

Between keyword allows you to select data from a range of values.

example

select * from account
where depositamount between 500 and 5000

We can rewrite this with out between keyword like this:

select * from account
where depositamount >= 500 and depositamount <= 5000

Question: select records from account where WithdrawAmount is between 10 and 90:

select * from Account where WithdrawAmount between 10 and 90

Question: select records from account where TransactionDate is between '1/1/2001' and '1/1/2020'

select * from Account where TransactionDate between '1/1/2001' and '1/1/2020'

Count keyword

will give us the number records in our database

select count(*)
from Account

Alias: use the “as” keyword to give column names where there is no name

select count(*) as NoofRecords
from Account

Calculated Column

If you want get a new column that is not present in the table, you can create it using Alias and some math operations

select DepositAmount, WithdrawAmount, (DepositAmount - WithdrawAmount) as Balance
from Account

The Like keyword

It will search for items with similar values. You have to use wild characters (eg %)

Question: Find all customer(s) whose name starts with J

select customername
from Account
where customername like 'J%'

Find all customer name who has ‘m’ in the middle or end

select customername
from Account
where customername like '%m%'

Find all merchants whose name contains ‘mart’

select merchantname
from Account
where merchantname like '%mart%'

The “In” operator

We use it in the where condition and it helps us to match items from a list

It is the same as using multiple “or” conditions

Example:

select DepositAmount, WithdrawAmount, MerchantName, MerchantAddress
from Account
where MerchantName = 'Giant' or MerchantName = 'Lows'

Rewrite this using the IN operator

select DepositAmount, WithdrawAmount, MerchantName, MerchantAddress

from Account

where MerchantName in ( 'Giant' , 'Lows')

It will qualify to pick the item if merchant name belongs to this list ( 'Giant' , 'Lows')

Not in Operator

It will select only if the item is not contained in the list

select DepositAmount, WithdrawAmount, MerchantName, MerchantAddress
from Account
where MerchantName not in ( 'Giant' , 'Lows')

This means I want a list of accounts where merchant name is not in this list ( 'Giant' , 'Lows')

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 21, 2021 | 1,092 Views |

Select Query:

GET All Columns and all Rows From a table

select * from Account

* means all columns

select * means select all columns

from specifies which table

for example: from Account => this will tell the database to get date from account table

Get Specific Columns

If you want to select only DepositAmount, WithdrawAmount, MerchantName, MerchantAddress columns from account table

select DepositAmount, WithdrawAmount, MerchantName, MerchantAddress
from Account

Filter Rows using Where

where: will allow to filter on rows

To select all columns from account table where the deposit amount is greater than 300 dollars:

select *
from Account
where DepositAmount > 300

Filter Rows and Columns

Question: select only four columns (DepositAmount, WithdrawAmount, MerchantName, MerchantAddress) from account table where the deposit amount is greater than 300 dollars:

select DepositAmount, WithdrawAmount, MerchantName, MerchantAddress
from Account
where DepositAmount > 300

Compound expression (and, or)

To select only four columns (DepositAmount, WithdrawAmount, MerchantName, MerchantAddress) from account table where the deposit amount is greater than 300 dollars or MerchantName is 'Giant' or MerchantName is 'Lowes'

select DepositAmount, WithdrawAmount, MerchantName, MerchantAddress
from Account
where DepositAmount > 300 or MerchantName = 'Giant' or MerchantName = 'Lows'

And: to get a true result you need to have all test/expression should return true

Example: Condition: true, false, true, false ===> Result: False

Example: Condition: true, true, true, true ===> Result: true

Example: Condition: true, true, true, false ===> Result: False

OR: to get a true result you need to have at least one of the condition to be true

Example: Condition: true, false, true, false ===> Result: true

Example: Condition: true, true, true, true ===> Result: true

Example: Condition: false, false, false, false ===> Result: False

To select records from account table where deposit amount is greater than 300 and merchant name is either giant or lowes

select DepositAmount, WithdrawAmount, MerchantName, MerchantAddress
from Account
where DepositAmount > 300 and (MerchantName = 'Giant' or MerchantName = 'Lows')

To select records from account table where deposit amount is greater than 300 and merchant name is giant; or merchant name is lowes

select DepositAmount, WithdrawAmount, MerchantName, MerchantAddress
from Account
where (DepositAmount > 300 and MerchantName = 'Giant') or MerchantName = 'Lows'

***Do the bracket first when you evaluate true or false

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 21, 2021 | 910 Views |

SQL Queries are categorized as follows :

Data Definition Language (DDL):

DDL is used to define the data structure and create of the components of our database like tables.

Example: create database, create table, create store procedure, create function.

create table: we create the columns of the table with data type

CREATE TABLE Account (
     ID int IDENTITY(1,1) NOT NULL,
     DepositAmount float NOT NULL,
     WithdrawAmount float NULL,
     TransactionDate datetime NULL,
     MerchantName nvarchar(50) NOT NULL,
     MerchantAddress nvarchar(50) NULL,
     MerchantPhone nvarchar(50) NULL,
     CustomerName nvarchar(50) NULL,
     CustomerAddress nvarchar(50) NULL,
     CustomerPhone nvarchar(50) NULL,
     LastUpdateDate datetime] NULL,
LastUpdateBy nvarchar(50) NULL
)

Data Manipulation language (DML)

DML is used to modify the data that is stored inside the tables

example: insert, update, delete.

Insert into table: we want to insert data to the created table

example:

INSERT INTO [dbo].[Account] (
[DepositAmount]
,[WithdrawAmount]
,[TransactionDate]
,[MerchantName]
,[MerchantAddress]
,[MerchantPhone]
,[CustomerName]
,[CustomerAddress]
,[CustomerPhone]
,[LastUpdateDate]
,[LastUpdateBy])

VALUES (
600,
25,
1/1/2021,
'Sears',
'100 Georgia Ave',
'202-655-4566',
'John Doe',
'2 test drive',
'202-655-5555',
1/12/2021,
'admin'
)

Update table: you want to modify the data that you already inserted

Example:
UPDATE [dbo].[Account]
SET [DepositAmount] = 600
,[WithdrawAmount] = 100
,[TransactionDate] = 1/2/2021
,[MerchantName] = 'Best buy'
,[MerchantAddress] = '1 test st'
,[MerchantPhone] = '252-545-6454'
,[CustomerName] = 'Fred'
,[CustomerAddress] = '2 test drive'
,[CustomerPhone] = '252-656-2666'
,[LastUpdateDate] = 2/2/2021
,[LastUpdateBy] = 'Jimmy'
WHERE id = 1

delete table

that is to completely remove the table rows from data base. We can also specify the row we want to delete as follows:

delete Account
where id = 2

If we don't specify the where condition, then all the rows will be completely wipe out.

truncate table

This is the time when you want to delete all the rows of the table completely resetting it as if the table is recreated. One way to check this is once you run this command, if you have an auto incremented column like ID, this command will reset it back to 1.

truncate table Account

drop table

This command will delete this table from database

drop table Account

Data Control Language (DCL)

used to provide access/permission to database

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 21, 2021 | 923 Views |

Create new database

Syntax:

create database {db name}

Example:

create database BankApp

Create new table

create table {table name}(
{column name} {data type} {optional/required},
{column name} {data type} {optional/required},
{column name} {data type} {optional/required},
{column name} {data type} {optional/required}
)

Note: {optional/required} specify using null which means optional, but not null means required

Example:

create table customer (
id int not null,
firstname varchar(50) null
)

CREATE TABLE Account (
     ID int IDENTITY(1,1) NOT NULL,
     DepositAmount float NOT NULL,
     WithdrawAmount float NULL,
     TransactionDate datetime NULL,
     MerchantName nvarchar(50) NOT NULL,
     MerchantAddress nvarchar(50) NULL,
     MerchantPhone nvarchar(50) NULL,
     CustomerName nvarchar(50) NULL,
     CustomerAddress nvarchar(50) NULL,
     CustomerPhone nvarchar(50) NULL,
     LastUpdateDate datetime] NULL,
LastUpdateBy nvarchar(50) NULL
)

Identity : will make sure you will have nonrepeating numbers for the Id

Default Value: will set the default value of the column

example: We want LastUpdateDate to be the date the data was last touched. In this case we can set the default value in SQL server designer to be getdate(). getdate() is a sql function to get the current date.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 21, 2021 | 1,006 Views |

One To One

One record from the first table can be associated with only one record from the second table.

Example: Employee table and Address table

Ultimately, we merge the table together.

One To Many

one record from the first table can be associated with one or more records from the second table.

Example: Employee and department tables have one to many relationships.

To create one to many relationships: the rule is to take the id of the one side as a foreign key to the many side.

In other words, take the id of the department and insert in to the employee side.

More Example:

Merchant vs customers

patient and doctors (one patient can see only one doctor but a doctor can have one or more patients)

student and advisors

Many to Many

One or more records from the first table can be associated with one or more records from the second table.

Examples:

student vs instructor
student vs course
patients and doctors (one patient can see one or more doctors)
customer and products, they purchase.
Merchant vs products

(One customer can purchase several products and, one product can be purchase by many customers)

(One merchant can sell several products and, one product can be sold by several merchants)

To create many to many relationship: the rule is to take the primary keys of both tables in to a separate table. We have to create a new (third) table to do this.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 21, 2021 | 864 Views |

Database

storage place for related date
contains tables that actually stores the data.
tables contain fields or attributes or columns.

Tables

stores information about specific real-world object
examples: student, course, instructor, employee, department
contains fields or attributes or columns.

Columns

they are the final storage place for data.
examples: first name, last name, salary
tells you what kind of data you are storing.
should specify the datatype of each column.

Rows

actual entries/sample data
example: Abebe, 2000

Datatype

is the type of data that you are storing in to the column
example: int, bigint, float, varchar(25), varchar (max), bit
bit: Boolean( only true or false)
int (numbers starting from 0, 1, ----)
varchar: any text for ex. John, Doe
decimal: decimal number like 2.5, 2000.50
char: to store only one character for ex. ‘M’ for Male
datetime: to store date and time together. example: 2/28/2021 5:04 PM
smalldatetime : is the same as datetime except with out the hour part. ex. 2/28/2021

Primary Key

It is unique identifier of the records of a given table

Ex: Id ,SSN ,Driver License

But first name, last name or address, DOB cannot a primary key
All attributes of a record are dependent on the primary key

Foreign Key

A primary key from other table inserted in to another table to establish a relationship with the other table.

... [Click on the blog title or image to read the entire blog.]

Tewodros | Sep. 21, 2021 | 871 Views |