Wednesday, August 12, 2020

[Interview Question ][Data Structure] Two Sum Problem -Array

Two sum problem is one of the most asked data structure questions for a java developer interview. There could be one or more ways to solve the problem but i am trying to give the optimized solution to this problem.



Lets first see the Problem Statement.

Problem Statement - Given an array, We need to find all the possible sets of 2 elements whose sum is equal to the target sum.


Solution: Given an array, lets say [10,-2,5,3,1,7,4] and given a target = 8 , We need to find all the possible 2 elements whose sum is equal to the 8.

the possible output will be 

[10,-2] ,[5,3],[1,7]


Pseudo code- 

  • Lets first sort the array.
  • After sorting, take 2 pointers, one is leftmost & second is rightmost.
  • we will start taking each element from left & right then check some of both the element.
  • If the sum is less then the target sum, then move the left pointer by one.
  • if the sum is greater than the target sum, then move the right pointer to left by one.
  • else if it is equal to target then put the elements one result array and move both left & right pointer by one.
Now let see the Java implementations.






public class TwoSumProblem {
	
	public static void main(String[] args) {
		int[] arr = {10,-2,5,3,1,7,4};
		
		twoSumArray(arr,8);
	}
	
	public static void twoSumArray(int[] arr, int i) {
		
//		sort the array using Arrays  sort
		
		Arrays.sort(arr);
		int size = arr.length;
		int left = 0;
		int right =size-1;
		List<Integer> list = new ArrayList<Integer>();
		
		while(left<right) {
			int diff = arr[left]+arr[right];
			if(diff<i) {
				left++;
			}else if(diff>i) {
				right--;
			}else {
				list.add(arr[left]);
				list.add(arr[right]);
				left++;
				right--;
			}
		}
		
		for(Integer it : list) {
			System.out.println(it);
		}
	}


If you run this program you will get the list of sub set whose sume is equal to 8.


Hope this will help you in your datastructre problem solving.

Thanks for reading.

Thursday, June 25, 2020

[Multi threading Interview Question ]Rate Limiter Implementation in java

There was one interesting problem I have encounter while preparing for a multithreading coding interview.


Question: We have an application for which we need to implement RateLimiter, 
Rate Limiter is an interface which will play a role to limit the number of Request client send to Server in a given time.

In the Current Question, it was asked to implement a rate limit who will do 2 things.

1) It will only allow one client to send 100 requests in 1 hrs. ( one client will be identified by the client Id).
2) It will allow a total of 10000 requests to be passed to the server in 1 hrs.

Rate Limiter Interface 
interface RateLimiter{

boolean accept(String clientId);
}

Java Implementation of Rate Limiter 

When we need to Implement such things where there is any restriction of accessing the resource for limited count We always start thinking using Semaphores  
Why Semaphores? 
Because it maintains the multi-access locking on its own with defined number of threads to access the critical section.

MyRateLimiter.java

class MyRateLimiter  {
 
 
    private Semaphore semaphore;
    private int maxPermits;
    private TimeUnit timePeriod;
    private ScheduledExecutorService scheduler;
    
    
 
    public static MyRateLimiter create(int permits, TimeUnit timePeriod) {
    MyRateLimiter limiter = new MyRateLimiter(permits, timePeriod);
        limiter.schedulePermit();
        return limiter;
    }
 
    private MyRateLimiter(int permits, TimeUnit timePeriod) {
        this.semaphore = new Semaphore(permits);
        this.maxPermits = permits;
        this.timePeriod = timePeriod;
    }
 
    public boolean tryAcquire() {
        return semaphore.tryAcquire();
    }
 
    public void stop() {
        scheduler.shutdownNow();
    }
 
    public void schedulePermit() {
        scheduler = Executors.newScheduledThreadPool(1);
        scheduler.scheduleAtFixedRate(() -> {
            semaphore.release(maxPermits - semaphore.availablePermits());
        }, 0, 1, timePeriod);
 
    }

 }

 RateLimiterImpl.java

	class RateLimiterImpl implements RateLimiter{

private static long MINUTE_TIME_LIMIT=1000*60L; // update as per question
private static long REQUEST_ALLOWED_PER_MINUTE=10000; // Update as per question
Queue<Long> q = new LinkedList<>();
private static int minuteLimit=100;

private Map<String, Optional<MyRateLimiter>> limiters = new ConcurrentHashMap<>();
     
@Override
public boolean accept(String clientId) {
if(!hit(System.currentTimeMillis())) {
return false;
}
Optional<MyRateLimiter> rateLimiter = getRateLimiter(clientId);
if(rateLimiter.isPresent()) {
boolean canAcquire= rateLimiter.get().tryAcquire();
if(canAcquire)
return q.add(System.currentTimeMillis());
}
return false;
}
private boolean hit(long timestamp) {
while(!q.isEmpty() && timestamp-q.peek() >= MINUTE_TIME_LIMIT) q.poll();
if(q.size() < REQUEST_ALLOWED_PER_MINUTE)
{
q.offer(timestamp); 
return true;
}
return false;
}
private Optional<MyRateLimiter> getRateLimiter(String clientId) {
        return limiters.computeIfAbsent(clientId, id -> {
            return Optional.of(createRateLimiter(id));
            
        });
    }
private MyRateLimiter createRateLimiter(String clientId) {
        return MyRateLimiter.create(minuteLimit, TimeUnit.MINUTES);
    }

}

Main Class Calling

public class RateLimiterDemo {


public static void main(String[] args) {

RateLimiter limiter = new RateLimiterImpl();
        System.out.println("test1 " + limiter.accept("test1"));
        System.out.println("test1 " +limiter.accept("test1"));
        System.out.println("test1 " +limiter.accept("test1"));
        System.out.println("test1 " +limiter.accept("test1"));
        System.out.println("test2 " +limiter.accept("test2"));
        System.out.println("test2 " +limiter.accept("test2"));
        System.out.println("test2 " +limiter.accept("test2"));
        System.out.println("test2 " +limiter.accept("test2"));
        System.out.println("test1 " +limiter.accept("test1"));


}

}

You can also check the Code from HERE 

Hope this will help you in understanding the Code

Tuesday, June 16, 2020

101 Most Useful Websites on Internet


The Most Useful Websites and Web Apps


  1. archive.is— take a snapshot of any web page and it will exist forever even if the original page is gone.
  2. autodraw.com — create freehand doodles and watch them magically transform into beautiful drawings powered by maching learning.
  3. fast.com  — check the current speed of your Internet connection.
  4. slides.com  — create pixel-perfect slide decks and broadcast your presentations to an audience of any size from anywhere.
  5. screenshot.guru — take high-resolution screenshots of web pages on mobile and desktops.
  6. dictation.io  – accurate and quick voice recognition in your browser itself.
  7. reverse.photos — upload an image and find similar pictures on the web.
  8. copychar.cc – copy special characters and emojis that aren’t on your keyboard.
  9. codeacademy.com  – the best place to learn coding online.
  10. noisli.com  — ambient noises to help you improve focus and boost productivity.
  11. iconfinder.com  – millions of icons for all kinds of projects. Also try icons8.com 39 and laticon.com 36.
  12. jotti.org  – scan any suspicious file or email attachment for viruses.
  13. wolframalpha.com  – gets answers directly without searching – see more wolfram tips.
  14. flightstats.com  – track flight status at airports worldwide.
  15. unsplash.com  – the best place to download images absolutely free.
  16. videos.pexels.com  — an online library of free HD videos you can use everywhere. Also see videvo.net 76.
  17. everytimezone.com  – a less confusing view of the world time zones.
  18. e.ggtimer.com  – a simple online timer for your daily needs.
  19. random.org  – pick random numbers, flip coins, and more.
  20. earn.com  — replace your email with a mailbox that pays when you reply to someone’s email.
  21. myfonts.com/WhatTheFont  – upload an image of any text and quickly determine the font family.
  22. fonts.google.com  – the best collection of open source fonts that you can use anywhere without restrictions.
  23. fontstruct.com  — draw and build your own fonts and use them in any application.
  24. calligraphr.com  — transform your handwriting into a real font.
  25. regex.info – find data hidden in your photographs – see more EXIF tools.
  26. youtube.com/webcam  — broadcast yourself live over the Internet without any complicated setup.
  27. remotedesktop.google.com  — access other computers or allow others to remote access your computer over the Internet.
  28. homestyler.com  – design from scratch or re-model your home in 3D.
  29. pdfescape.com  – lets you quickly edit PDF in the browser without Acrobat.
  30. draw.io  – create diagrams, wireframe and flowcharts in the browser.
  31. web.skype.com  — make voice and video calls in your browser with Skype.
  32. onlineocr.net  – recognize text from scanned PDFs – see other OCR tools.
  33. wetransfer.com  – for sharing really big files online.
  34. file.pizza — peer to peer file transfer over WebRTC without any middleman.
  35. snapdrop.com  — like Apple AirDrop but for the web. Share files directly between devices in the same network without having to upload them to any server first.
  36. hundredzeros.com  – the site lets you download free Kindle books.
  37. app.grammarly.com  — check your writing for spelling, style, andgrammatical errors.
  38. noteflight.com  – print music sheets, write your own music online ( review).
  39. translate.google.com  – translate web pages, PDFs and Office documents.
  40. kleki.com  – create paintings and sketches with a wide variety of brushes.
  41. similarsites.com  – discover new sites that are similar to what you like already.
  42. bubbl.us  – create mind-maps, brainstorm ideas in the browser.
  43. color.adobe.com  – get color ideas, also extract colors from photographs.
  44. canva.com  — make beautiful graphics, presentations, resumes and more with readymade template designs.
  45. lmgtfy.com  – when your friends are too lazy to use Google on their own.
  46. midomi.com  – when you need to find the name of a song.
  47. history.google.com  — see all your past Google searches, also among most important Google RLs
  48. faxzero.com  – send an online fax for free – see more fax services.
  49. tinychat.com  – setup your own private chat room in micro-seconds.
  50. privnote.com  – create text notes that will self-destruct after being read.
  51. domains.google.com  – quickly search domain names for your next big idea!
  52. downforeveryoneorjustme.com  – find if your favorite website is offline or not?
  53. gtmetrix.com  – the perfect tool for measuring your site performance online.
  54. builtwith.com  — find the web hosting company, email provider and everything else about a website.
  55. urbandictionary.com  – find definitions of slangs and informal words.
  56. seatguru.com  – consult this site before choosing a seat for your next flight.
  57. flightstats.com  – Track flight status at airports worldwide.
  58. mymaps.google.com  – create custom Google Maps with scribbles, pins and custom shapes.
  59. snopes.com  – find if that email offer you received is real or just another scam.
  60. typingweb.com  – master touch-typing with these practice sessions.
  61. todo.microsoft.com  — a beautiful todo app and task manager. Also see Trello.
  62. minutes.io  – quickly capture effective notes during meetings.
  63. talltweets.com  — Turn Google Slides in animated GIF presentations.
  64. ifttt.com  – create a connection between all your online accounts.
  65. namechk.com  — search for your desired username across hundreds of social networks and omain names.
  66. gist.github.com  — create anonymous and secret text notes and much more.
  67. flipanim.com — create flipbook animations, includes an onion skin tool to let you see the revious frame as you draw the next one.
  68. powtoon.com  — create engaging whiteboard videos and presentations with your own voiceovers. lso see videoscribe.co
  69. clyp.it — Record your own voice or upload an audio file without creating any account. Also see oundcloud.com
  70. carrd.co  — build one-page fully responsive websites that look good on every screen.
  71. spark.adobe.com  — make stunning video presentations with voice narration and wow everyone.
  72. anchor.fm — the easiest way to record a podcast that you can distribute on iTunes without have to pay for hosting.
  73. duolingo.com  — learn to speak Chinese, French, Spanish or any other language of your choice.
  74. webmakerapp.com  — an offline playground for building web projects in HTML, CSS and javascript.
  75. pixton.com  — create your own comic strips with your own characters and move them into any one.
  76. designer.io  — a full-featured vector drawing tool that works everywhere.
  77. sumopaint.com  – an excellent layer-based online image editor.
  78. vectr.com  — create vector graphics and export them as SVG or PNG files.
  79. twitterbots — create your own Twitter bots that can auto-reply, DM, follow people and more.
  80. headspace.com  — learn the art of meditation and reduct stress, focus more and even sleep better.
  81. class-central.com  — a directory of free online courses offered by universities worldwide.
  82. googleartproject.com  — discover museums, famous paintings and art treasure from all around the world.
  83. instructables.com  — step-by-step guides on how to build anything and everything.
  84. flowgram.com  — make data-driven graphics, charts and infographics. Also see adioma.com 18 and eas.ly.
  85. marvelapp.com  — create interactive wireframes and product mockups.
  86. slide.ly — make marketing videos and branded stories for Instagram, Facebook and YouTube trailers. Also, see animoto.com 13 and biteable.com 11.
  87. gohighbrow.com  — Take bite-sized courses on a variety of topics, chapters are delivered by email every morning.
  88. htmlmail.pro – send rich-text emails with gmail mail merge.
  89. wirecutter.com  — whether you need a vacuum cleaner or an SD card, this is the best product recommendation website on the Internet.
  90. camelcamelcamel.com  — Create Amazon price watches and get email alerts when the prices drop.
  91. mockaroo.com  — download mock data to fill the rows in your Excel spreadsheet.
  92. asciiflow.com  — a WYSIWYG editor to draw ASCII diagrams that you can embed in emails and tweets.
  93. buffer.com  — the easily way to post and schedule updates on Twitter, Instagram, LinkedIn, Google+ and Facebook.
  94. 10minutemail.com  — create disposable email addresses for putting inside sign-up forms.
  95. whereami — find the postal address of your current location on Google maps.
  96. sway.com  — create and share interactive reports, newsletters, presentations, and for storytelling.
  97. apify.com  — the perfect web scraping tool that lets you extract data from nearly any website.
  98. thunkable.com  — build your own apps for Android and iOS by dragging blocks instead of writing code. Also see: glitch.com 36
  99. zerodollarmovies.com  — a huge collection of free movies curated from YouTube.
  100. upwork.com  — find freelancers and subject experts to work on any kind of project.
  101. duckduckgo.com  – a clean alternative to google search that doesn’t track you on the Internet.

Know any useful website that is missing in the list? Please let me know via comment


Hope you hind these websites useful, 

Thanks for reading 
Noeik